Учени са създали нов ефективен начин за преброяване на уникални елементи

Представете си, че сте изпратени в тропическа гора, за да проведете преброяване на дивата природа. Всеки път, когато видите животно, правите снимка. Фотоапаратът ви проследява общия брой снимки, но ви интересува само броят на уникалните животни, които още не са били в кадър. Кой е най-добрият начин да получите този брой? Очевидното решение изисква запомняне на всяко животно и сравняване на всяко ново животно с тези, които вече са в списъка. При хиляди записи обаче този подход става труден.

Ситуацията се усложнява още повече, ако например Facebook иска да преброи броя на уникалните потребители, които посещават сайта всеки ден, дори ако те го посещават от няколко устройства и по различно време. Тук вече става дума за списък, който може да достигне милиарди записи.

Наскоро изследователи описаха нов метод за приблизително определяне на броя на уникалните записи в дълъг списък, който изисква запомняне само на малък брой записи.

Алгоритъмът е подходящ за всеки списък, в който елементите пристигат един по един, независимо дали са думи в речта, стоки на конвейер или автомобили на магистрала.

Алгоритъмът CVM е наречен на името на създателите си – Сурав Чакраборти от Индийския статистически институт, Винодчандран Вариям от Университета на Небраска-Линколн и Кулдип Мила от Университета на Торонто. Той представлява значителна стъпка към решаването на проблема с уникалните елементи, с който учените се борят повече от 40 години. Този проблем се състои в намирането на начин за ефективно проследяване на потока от елементи и оценка на броя на уникалните.

„Новият алгоритъм е изненадващо прост и лесен за изпълнение. Няма да се учудя, ако това се превърне в стандартен подход за решаване на проблема с уникалните множества от елементи в практиката.“

казва Андрю Макгрегър от Масачузетския университет в Амхърст

За да илюстрирате проблема и решението на CVM алгоритъма, представете си, че слушате аудиокнигата на Хамлет. В пиесата има 30 557 думи. Колко от тях са уникални? За да разберете, можете да слушате пиесата, като записвате всяка дума по азбучен ред в тетрадка и пропускате вече записаните. Този подход изисква капацитет на паметта, приблизително равен на броя на уникалните думи.

В типични ситуации на стрийминг може да има милиони елементи. Може да не искате да съхранявате всичко. Именно тук на помощ идва алгоритъмът CVM. Основният трик е да се използва случайността.

Да се върнем към „Хамлет“, но сега работната ви памет – вашата дъска за писане съдържа само 100 думи. Когато започнете да слушате, записвате първите 100 думи, които чувате, като пропускате повтарящите се. Когато паметта ви се напълни, правите пауза и хвърляте монета за всяка дума. Ези – думата остава, тура – думата се изтрива. След това ви остават около 50 уникални думи.

Следва първият кръг. Продължавате да слушате „Хамлет“, като добавяте нови думи, когато се появят. Ако думата вече е в списъка, хвърляте монетата отново. ези – думата се премахва, тура – остава. Продължавате, докато на таблото има 100 думи, след което премахвате половината от тях на случаен принцип.

Следващата стъпка е втори кръг. Продължавате както в първия кръг, но сега е по-трудно да запазите думата. При повторение на думата хвърляте монетата два пъти и я запазвате само ако и двата пъти ези се падне. Рундът завършва с подобно изтриване на половината думи.

В третия кръг са ви необходими три поредни ези, за да спасите думата, в четвъртия кръг са ви необходими четири и т.н.

В края на последния рунд, в края на Хамлет, всяка случайно избрана дума има една и съща вероятност да попадне в списъка: 1/2^k. Ако например в края след 6 кръга имате 61 думи, можете да разделите 61 на вероятността 1/2^6, за да изчислите броя на уникалните думи – получавате 3 904.

Чакраборти, Вариам и Мил доказаха математически, че точността на тази техника се увеличава с размера на паметта. В „Хамлет“ има точно 3967 уникални думи. При експерименти с памет от 100 думи средният резултат след 5 опита е 3 955 думи. При памет от 1000 думи средният резултат се подобрява до 3964.

„Разбира се, ако паметта е толкова голяма, че побира всички думи, ще получим 100-процентова точност.“

казва Вариам

„Това е чудесен пример за това как дори за много елементарни и добре изучени проблеми понякога могат да се намерят много прости, но не очевидни решения.“

каза Уилям Кузмаул от Харвардския университет