To jeden z projektów badawczych, przez które obecnie przechodzę. Wymagania są prawie takie same, jak Twoje, a my opracowaliśmy ładne algorytmy do rozwiązania problemu.
Wejście
Dane wejściowe to niekończący się strumień angielskich słów lub zwrotów (nazywamy je tokens).
Wyjście
- Wyprowadź N najlepszych tokenów, które widzieliśmy do tej pory (spośród wszystkich tokenów, które widzieliśmy!)
- Wyświetl N górnych żetonów w oknie historycznym, powiedzmy, ostatni dzień lub ostatni tydzień.
Zastosowanie tego badania polega na znalezieniu gorącego tematu lub trendów na Twitterze lub Facebooku. Mamy robota indeksującego stronę internetową, który generuje strumień słów, które zostaną wprowadzone do systemu. System następnie wypisze słowa lub frazy o najwyższej częstotliwości, ogólnie lub historycznie. Wyobraź sobie, że w ciągu ostatnich kilku tygodni na Twitterze wielokrotnie pojawiało się hasło „Mistrzostwa Świata”. Tak samo jak „Paul the Octopus”. :)
Ciąg na liczby całkowite
System posiada całkowity identyfikator dla każdego słowa. Chociaż w Internecie jest prawie nieskończenie wiele możliwych słów, to po zgromadzeniu dużego zestawu słów możliwość znalezienia nowych słów staje się coraz mniejsza. Znaleźliśmy już 4 miliony różnych słów i do każdego przypisaliśmy unikalny identyfikator. Cały zestaw danych można załadować do pamięci jako tablicę mieszającą, zajmującą około 300 MB pamięci. (Zaimplementowaliśmy własną tablicę mieszającą. Implementacja języka Java wymaga ogromnej ilości pamięci)
Następnie każdą frazę można zidentyfikować jako tablicę liczb całkowitych.
Jest to ważne, ponieważ sortowanie i porównywanie liczb całkowitych jest znacznie szybsze niż na łańcuchach.
Archiwizuj dane
System przechowuje dane archiwalne dla każdego tokena. Zasadniczo to pary (Token, Frequency). Jednak tabela przechowująca dane byłaby tak ogromna, że musielibyśmy fizycznie podzielić tabelę. Raz schemat partycji jest oparty na ngramach tokenu. Jeśli token jest pojedynczym słowem, jest to 1 gram. Jeśli token jest frazą składającą się z dwóch słów, jest to 2 gramy. I to trwa. Przy przybliżeniu przy 4 gramach mamy 1 miliard rekordów, a rozmiar tabeli wynosi około 60 GB.
Przetwarzanie strumieni przychodzących
System będzie wchłaniał nadchodzące zdania, dopóki pamięć nie zostanie w pełni wykorzystana (tak, potrzebujemy MemoryManagera). Po pobraniu N zdań i zapisaniu ich w pamięci, system zatrzymuje się i zaczyna tokenizować każde zdanie na słowa i frazy. Każdy token (słowo lub fraza) jest liczony.
W przypadku bardzo częstych żetonów są one zawsze przechowywane w pamięci. W przypadku rzadszych tokenów są one sortowane na podstawie identyfikatorów (pamiętaj, że tłumaczymy String na tablicę liczb całkowitych) i serializowane do pliku na dysku.
(Jednak dla twojego problemu, ponieważ liczysz tylko słowa, możesz umieścić całą mapę częstotliwości słów tylko w pamięci. Starannie zaprojektowana struktura danych zajmie tylko 300 MB pamięci na 4 miliony różnych słów. Wskazówka: użyj znaku ASCII, aby reprezentują ciągi znaków) i jest to bardzo akceptowalne.
W międzyczasie, po znalezieniu dowolnego pliku dyskowego wygenerowanego przez system, aktywowany zostanie inny proces, a następnie rozpocznie się scalanie. Ponieważ plik na dysku jest posortowany, scalanie wymagałoby podobnego procesu, jak sortowanie przez scalanie. Tutaj również należy zadbać o niektóre projekty, ponieważ chcemy uniknąć zbyt wielu przypadkowych wyszukiwań dysku. Chodzi o to, aby uniknąć odczytu (procesu scalania) / zapisu (wyjście systemowe) w tym samym czasie i pozwolić procesowi scalania na odczyt z jednego dysku podczas zapisywania na innym dysku. Jest to podobne do wdrażania blokady.
Koniec dnia
Pod koniec dnia system będzie miał wiele częstych tokenów z częstotliwością przechowywanych w pamięci oraz wiele innych rzadziej używanych tokenów przechowywanych w kilku plikach dyskowych (a każdy plik jest posortowany).
System opróżnia mapę w pamięci do pliku dyskowego (sortuje ją). Teraz problemem staje się scalanie zestawu posortowanych plików dyskowych. Korzystając z podobnego procesu, otrzymalibyśmy na końcu jeden posortowany plik na dysku.
Następnie ostatnim zadaniem jest scalenie posortowanego pliku dyskowego z bazą danych archiwum. W zależności od wielkości bazy danych archiwum algorytm działa jak poniżej, jeśli jest wystarczająco duży:
for each record in sorted disk file
update archive database by increasing frequency
if rowcount == 0 then put the record into a list
end for
for each record in the list of having rowcount == 0
insert into archive database
end for
Intuicja jest taka, że po pewnym czasie liczba włożeń będzie coraz mniejsza. Coraz więcej operacji będzie dotyczyło tylko aktualizacji. A ta aktualizacja nie będzie karana indeksem.
Mam nadzieję, że całe to wyjaśnienie pomoże. :)
what is the most frequent item in the subsequence [2; 2; 3; 3; 3; 4; 4; 4; 4; 5; 5] of your sequence?