Częstotliwość wyrazów z uporządkowaniem w złożoności O (n)

Podczas wywiadu na stanowisko programisty Java zapytano mnie:

Napisz funkcję, która przyjmuje dwa parametry:

1. ciąg znaków reprezentujący dokument tekstowy i
2. liczba całkowita podająca liczbę elementów do zwrócenia.

Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych według częstotliwości słów, najczęściej występujących jako pierwsze słowo. Twoje rozwiązanie powinno działać w czasie gdzie to liczba znaków w dokumencie.$O(n)$$n$

Oto, na co odpowiedziałem (w pseudokodzie), nie jest to czas a raczej czas powodu tego rodzaju. Nie mogę wymyślić, jak to zrobić czas. $O(n)$$O(n \log n)$$O(n)$

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Czy ktoś wie lub może ktoś mi podpowiedzieć?

Proponuję wariant liczenia dystrybucji:

1. Przeczytaj tekst i wstaw wszystkie napotkane słowa do trie , zachowując w każdym węźle liczbę, jak często występowało słowo reprezentowane przez ten węzeł. Dodatkowo śledź najwyższą liczbę słów do powiedzenia maxWordCound. -$O(n)$
2. Zainicjuj tablicę rozmiarów maxWordCount. Typ wpisu to listy ciągów. -$O(n)$, ponieważ liczba nie może być wyższa.
3. Przejdź przez trie i dla każdego węzła dodaj odpowiedni ciąg do wpisu tablicy wskazanego przez liczbę. -$O(n)$, ponieważ całkowita długość ciągów jest ograniczona przez $n$.
4. Przejdź przez tablicę w kolejności malejącej i wyślij żądaną liczbę łańcuchów. -$O(n)$, ponieważ jest to związane zarówno z wielkością, jak i ilością danych w tablicy.

Prawdopodobnie możesz zastąpić trie innymi strukturami danych w pierwszej fazie.

Zliczanie liczby wystąpień to O (n), więc sztuczka polega na znalezieniu tylko największej liczby wystąpień.

Kupa jest powszechnym sposobem agregacji najwyższych wartości k, chociaż można użyć innych metod (patrz https://en.wikipedia.org/wiki/Partial_sorting ).

Zakładając, że k jest drugim parametrem powyżej i że jest stałą w opisie problemu (wydaje się, że tak):

1. Zbuduj zestaw słów z liczbą wystąpień w każdym węźle.
2. Zainicjuj stertę wielkości k.
3. Przejdź przez trie i min-sondę / włóż każdą parę (liść, liczba wystąpień) do sterty o najwyższym k.
4. Wypisuj górne k liści i się liczy (jest to w rzeczywistości rodzaj bólu, ponieważ potrzebujesz wskaźników nadrzędnych, aby mapować każdy liść z powrotem na słowo).

Ponieważ rozmiar sterty jest stały, operacje sterty są O (1), więc krok 3 to O (n).

Stertę można również utrzymywać dynamicznie podczas budowania trie.

Twój algorytm nie działa nawet w czasie $O(n \log n)$; wstawianie$\Theta(n)$ rzeczy w hashtable kosztują czas $\Omega(n^2)$ już (najgorszy przypadek).

To, co następuje, jest złe ; Na razie zostawiam go tutaj w celach ilustracyjnych.

Poniższy algorytm działa w najgorszym przypadku $O(n)$ (zakładając alfabet $\Sigma$ o stałym rozmiarze), $n$ liczba znaków w tekście.

1. Skonstruuj drzewo sufiksów tekstu, np. Za pomocą algorytmu Ukkonen .

   Jeśli konstrukcja jeszcze tego nie robi, dodaj liczbę dostępnych liści do każdego (wewnętrznego) węzła.

2. Przejdź przez drzewo od korzenia i odetnij wszystkie gałęzie na pierwszej (białej) przestrzeni.

3. Przejdź przez drzewo i posortuj listę dzieci każdego węzła według liczby liści.

4. Wydajność drzewa (liście od lewej do prawej) jest teraz listą wszystkich słów posortowanych według częstotliwości.

Jeśli chodzi o środowisko wykonawcze:

1. Algorytm Ukkonena (w ulepszonej formie) działa w czasie $O(n)$; utrzymywanie liczby liści nie zwiększa$\Theta$-koszt algorytmu.
2. Musimy przejść jeden węzeł na znak każdego słowa występującego w tekście. Ponieważ są co najwyżej$n$ różne pary słów i znaków, które odwiedzamy co najwyżej $n$ węzły
3. Odwiedzamy co najwyżej $n$ węzły (por. 2) i spędzać czas $O(|\Sigma| \cdot \log |\Sigma|) = O(1)$ na węzeł.
4. Możemy uzyskać wydajność (która oczywiście ma rozmiar $O(n)$) przez proste przejście w czasie $O(n)$ (por. 2).

Bardziej precyzyjne granice można uzyskać przez parametryzowanie środowiska wykonawczego liczbą różnych słów; jeśli jest ich mało, drzewo jest małe po 2.

Użyj tabeli skrótów (np. HashMap), Aby zebrać wszystkie słowa i ich częstotliwości. Następnie użyj sortowania zliczającego, aby posortować słowa w kolejności malejącej częstotliwości. Ponieważ wszystkie częstotliwości są liczbami całkowitymi w zakresie$1..n$, sortowanie według liczenia trwa $O(n)$czas. Całkowity oczekiwany czas działania wynosi$O(n)$, co jest więcej niż prawdopodobne dla wszystkich praktycznych celów (chyba że ankieter wspomniał o czymś, co zostało pominięte w twoim pytaniu). Pamiętaj, aby wspomnieć, że jest to oczekiwany czas działania, a nie najgorszy czas działania.

To może nie być odpowiedź, której nauczyciel szukałby w klasie algorytmów, ponieważ jest to oczekiwane $O(n)$ czas pracy zamiast $O(n)$najgorszy czas działania. Jeśli chcesz zdobyć dodatkowe punkty w pytaniu na rozmowę kwalifikacyjną, możesz od czasu do czasu wspomnieć odręcznie, że oczywiście jest to oczekiwany czas trwania, ale można to również zrobić w$O(n)$ najgorszy czas działania, zastępując tabelę skrótów bardziej wyrafinowaną strukturą danych - i chętnie opracujesz sposób wyboru algorytmów w takiej sytuacji.

Lub, jeśli chcesz zagrać nieco bezpieczniej, zanim udzielisz odpowiedzi, najpierw zapytaj: „czy zależy Ci na różnicy między oczekiwanymi $O(n)$ czas pracy i najgorszy przypadek $O(n)$czas trwania? ”. Następnie odpowiednio dostosuj swoją odpowiedź. Przygotuj się na to, by osoba przeprowadzająca wywiad zapytała cię, jak wybierzesz w praktyce. (Jeśli tak, zdobądź punkty!

Rozwiązanie oparte na haszcie

Nie jestem pewien, dlaczego hashtable sprawia, że ​​złożoność $\Omega(n^2)$ gdyby $n$to liczba znaków (nie słów).

Jeśli wykonujesz iterację po każdym znaku w dokumencie i podczas iteracji, oblicz kod skrótu tego słowa, przejdziesz $n$postacie. Oznacza to, że zaraz po napotkaniu litery zaczyna się słowo, więc zacznij obliczać skrót aż do końca słowa (istnieją specjalne przypadki interpunkcji, ale nie mają one wpływu na złożoność). Dla każdego słowa, po obliczeniu skrótu, dodaj je do tablicy skrótów. Ma to na celu uniknięcie dwukrotnego przejścia do każdego słowa, tzn. Najpierw iterację dokumentu w celu znalezienia słów, a następnie wstawienie ich do tablicy haszującej, chociaż w takim przypadku złożoność może być również$\Omega(n)$.

Zderzenia w tablicy hashującej z pewnością stanowią problem, a w zależności od tego, jak duży był oryginalny hashtable i jak dobry jest algorytm hashujący, można zbliżyć się do $O(1)$ do wstawiania i liczenia, a tym samym $O(n)$dla algorytmu, choć kosztem pamięci. Nadal jednak nie potrafię docenić, jak najgorszy przypadek można stwierdzić$O(n^2)$ gdyby $n$ to liczba znaków.

Zakłada się, że algorytm mieszający jest liniowy w czasie w stosunku do liczby znaków.

Rozwiązanie oparte na sortowaniu Radix

Alternatywnie, zakładając, że angielski, ponieważ długość słów jest dobrze znana, zamiast tego utworzę siatkę i zastosuję sortowanie radix, które jest $O(kN)$ gdzie $k$ będzie maksymalną długością słowa w języku angielskim, oraz $N$to łączna liczba słów. Dany$n$ to liczba znaków w dokumencie, oraz $k$ jest stałą, asymptotycznie to kwoty $O(n)$.

Teraz policz częstotliwość każdego słowa. Ponieważ słowa są posortowane, będziemy porównywać każde słowo z poprzednim słowem, aby sprawdzić, czy jest to to samo, czy inne. Jeśli jest taki sam, usuwamy słowo i dodajemy liczbę do poprzedniego. Jeśli jest inny, po prostu policz 1 i przejdź dalej. To wymaga$2n$ porównania gdzie $n$ to liczba znaków, a zatem $O(n)$ w złożoności jako całości.

Kilka najdłuższych słów w języku angielskim jest absurdalnie długie , ale potem można ograniczyć długość słowa do rozsądnej liczby (np. 30 lub mniejszej) i obciąć słowa, przyjmując margines błędu, który może z tym wynikać.