Jaki jest najskuteczniejszy sposób w języku Java, aby uzyskać 50 najczęstszych słów z ich częstotliwością poza tekstem?Najczęstsze słowa:
Chcę wyszukać około ~ 1 000 000 tekstów, z których każdy zawiera około ~ 10 000 słów i mam nadzieję, że działa w rozsądnym przedziale czasowym.
Najbardziej wydajna byłaby prawdopodobnie wersja Patricia trie, która łączy się z max-heap. Za każdym razem, gdy czytasz słowo, find to na trie, przejdź do sterty i increase-key. Jeśli nie jest w trie, add to i ustawić odpowiednio jego klucz w stercie.
Z Fibonacci heap, increase-key jest O(1).
A nie tak nieracjonalne rozwiązaniem jest użycie Map<String, Integer>, dodając Hrabia każdym razem, gdy słowo jest napotkane, a następnie zwyczaj sortowania ITS entrySet() na podstawie zliczania, aby uzyskać top 50.
Jeśli sortowanie O(N log N) jest niedopuszczalne, użyj selection algorithm, aby znaleźć 50 najlepszych w O(N).
Która technika jest lepsza naprawdę zależy co prosisz dla (tj komentarzu czy to jest bardziej pytanie niż [algorithm][java] pytanie jest bardzo wymowne).
Najbardziej przydatny jest algorytm wyboru Map<String, Integer> i algorytm wyboru, ale rozwiązanie Tria Patricia wyraźnie bije na samą wydajność przestrzenną (ponieważ wspólne przedrostki nie są przechowywane w nadmiarze).
Liczba unikalnych słów U w dużym tekście przy N słowach jest zazwyczaj bardzo niska (N >> U). Mapa wygrywa za każdym razem, ponieważ słowa w U nie są wystarczająco duże, aby PTrie świeciło i jest znacznie łatwiejsze do wdrożenia. Również O (N) >> O (U log U): sortowanie jest stosunkowo tanie. – tucuxi
Według twojej notacji, Ptrie zawierałoby słowa "U", więc nie jestem pewien, co twoja skarga. – polygenelubricants
FRAMS nie są szybsze niż Hashmaps dla małych rozmiarów napisów (= słów) i dlatego nie są warte problemów. Zdecydowanie skorzystałbym z nich, gdybym potrzebował znaleźć długie podciągi; ale ten problem można rozwiązać za pomocą gotowych pojemników. – tucuxi
Twoja najlepsza szansa to algorytm O (n), wybrałbym czytnik tekstu, który podzieliłby słowa, a następnie dodał do uporządkowanego drzewa, które zamawiałbyś według liczby przedstawień i łączył je z słowo. Następnie wykonaj 50-iteracyjny trawers, aby uzyskać najwyższe wartości.
Jak dodanie do uporządkowanego drzewa może być O (n)? –
O(n):
Oczywiście niektóre z tych etapów może być wykonane w tym samym czasie lub niepotrzebny w zależności od struktury danych będziesz używać.
Po pseudokod powinno załatwić sprawę:
build a map<word, count>
build a tokenizer that gives you a word per iteration
for each word*,
if word in map, increment its count
otherwise add with count = 1
sort words by count
for each of the first 50 words,
output word, frequency = count/total_words
Jest to zasadniczo O (N), a co jpabluz sugerowane. Jeśli jednak użyjesz tego na jakimkolwiek "dzikim" tekście, zauważysz dużo śmieci: wielkie/małe litery, interpunkcja, adresy URL, stop-słowa, takie jak "the" lub "and" z bardzo wysokimi liczy, wiele odmian tego samego słowa ...Odpowiednią metodą jest zamapowanie wszystkich słów, usunięcie wszystkich znaków interpunkcyjnych (i takich, jak adresy URL) oraz dodanie usuwania słów-stopów w punkcie oznaczonym gwiazdką w powyższym kodzie pseudokodowym.
"Zasadniczo jest to O (N)" - jeśli 'N' jest liczbą słów na wejściu. Jeśli 'U' jest liczbą unikalnych słów, to" sortuj słowa według liczby "to" O (U log U) ". W rzeczywistości można uzyskać 50 najlepszych (nieuporządkowanych) w 'O (U)' przy użyciu algorytmu wyboru. – polygenelubricants
Ponieważ N >> U dla innych niż krótkich tekstów, O (N) będzie dominować nad O (U log U). Tak, maksymalna liczba goli trochę czasu wolnego, ale zysk jest bardzo mały i nie jest wolny (dodatkowa złożoność kodu). – tucuxi
Nie zrozum mnie źle, twoja odpowiedź nie jest nierozsądna i jest bardzo praktyczna (jak wspomniałem to również jako opcja w mojej odpowiedzi), ale OP prosi o "najbardziej wydajną", i oczywiście Ptrie jest bardziej efektywny pod względem przestrzeni niż mapa przechowywanie całych słów jako kluczy. – polygenelubricants
Czy to zadanie domowe? – XpiritO
Wątpliwy komentarz do zadania domowego. –
To brzmi bardziej jak pytanie algorytmiczne niż pytanie java. –