C, PHP, VB, .NET

Мултимножествата са множества, за които повторенията от елементи се отчитат и са от значение. Например мултимножеството {1, 1, 1, 2} е различно от мултимножеството {1, 1, 2}, защото имат различни елементи в него. Подредбата обаче няма значение. За такива множества често ни интересува т.нар. кардиналност (мощност): броят на различните елементи. Или казано по-просто – ако вземем едно цялото количество от всички обекти в едно мултимножество, колко от тях са различни?

Нека демонстрираме с пример. Ще създадем един масив в Java с 10_000_000 елемента, който ще запълним с произволни числа (които ще са нашите обекти). Естествено и очаквано е някои от числата, които добавим, да се повтарят.

int setSize = 10_000_000;
int possibleElements = Integer.MAX_VALUE;
Integer[] myMultiset = new Integer[setSize];
Random r = new Random();
for(int i=0; i<setSize; i++){
   myMultiset[i] = r.nextInt(possibleElements);
}

Колко са уникалните числа в масива? Eдин подход към решаването на тази задача е да се създаде паралелна структура от данни списък. След това един по един се взимат елементите от множеството и се добавят в списъка, но само и единствено ако в списъка все още няма същия повтарящ се елемент. По този начин повторенията ще бъдат премахнати и в списъка ще останат само уникалните елементи. Проблемът на това решение е, че отнема изключително много процесорно време при големи мултимножества (заради проверките на всеки елемент – ще видите, че дори този пример е прекалено бавен и вероятно няма да пожелаете да го изчакате):

List<Integer> uniquesList = new LinkedList<>();
for(Integer i: myMultiset){
   if(!uniquesList.contains(i)){
      uniquesList.add(i);
   }
}
System.out.println("Unique elements: "+uniquesList.size());

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

Set<Integer> uniquesSet = new HashSet<>();
for(Integer i: myMultiset){
   uniquesSet.add(i);
}
System.out.println("Unique elements: "+uniquesSet.size());

За разлика от двата описани метода, алгоритъмът на Флажоле-Мартин е вероятностен. Той не дава точен отговор (не може да кажем със сигурност каква е точната кардиналността на мултимножеството), а дава само приблизителен. За сметка на това не отнема нито много процесорно време, нито заема допълнителна памет. Неговото действие е следното:

1. Избира се хеш функция h(x), която на всеки подаден обект x ще съпоставя бинарно число с дължина L, която е с максимално добра ентропия (генерираната поредица от нули и единици изглежда максимално непредвидима);
2. Дефинира се функция p(b), която връща броят на нулите в края на подадено бинарно число b;
3. Създава се бинарен масив BM с L на брой елемента, който първоначално е нулиран (всички елементи са 0);
4. За всеки елемент x от даденото мултимножество се изчислява i=p(h(x)), след което в масива се задава BM[i]=1;
5. След като калкулацията е извършена за всички елементи се намира най-малкото число n, такова че BM[n]==0;
6. Числото 2ⁿ/0.77351 се приема за броят на различните елементи в мултимножеството.

Оригиналната статия, където алгоритъмът е описан подробно, е следната:

Flajolet, P., & Martin, G. N. (1985). Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2), 182-209.

Оказва се, че при много големи множества, точността на отговора на този алгоритъм е задоволителна, но все пак може да варира значително. Един исторически често използван вариант за подобрение е да се приложи през няколко различни хеш функции, след което резултатът да се усредни. Друг вариант е да се направи същото и да се вземе медианата. Използвал се е и смесен вариант между двете.

Най-популярната реализация с подобрение, която се използва в днешно време, е т.нар. HyperLogLog алгоритъм. При него мултимножеството се разделя на подмножества, изчислява се кардиналността на всяко едно по алгоритъма на Флажоле-Мартин, след което се изчислява тяхното среднохармонично число (по този начин се дава по-голяма тежест на по-малките числа). Алгоритъмът e показал, че дава много точни приближения при много големи мултимножества. Описан е подробно в следната статия:

Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007, June). Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science (pp. 137-156). Discrete Mathematics and Theoretical Computer Science.

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

Къде може да се прилага този алгоритъм в практиката? Навсякъде, където е нужно приложение на функцията COUNT(DISTINCT *) – по аналогия от SQL, – но обемът на данните е изключително голям, а абсолютната точност не е от изключително значение. Най-често приложение получава при нерелационни бази от данни.