Trie Struktura danych: zaniedbany klejnot

Od pierwszych dni naszego życia jako programiści wszyscy zajmowaliśmy się strukturami danych: tablice, połączone listy, drzewa, zestawy, stosy i kolejki są naszymi codziennymi towarzyszami, a doświadczony programista wie, kiedy i dlaczego ich używać. W tym artykule zobaczymy, jak często zaniedbywana struktura danych, trie , naprawdę błyszczy w domenach aplikacji z określonymi funkcjami, takimi jak gry słowne.

Gry słowne jako przykład próbny

Na początek rozważmy prostą łamigłówkę: znajdź wszystkie poprawne słowa na tablicy 4x4, łączącej sąsiednie litery poziomo, pionowo lub ukośnie. Na przykład na następnej tablicy widzimy, jak litery „W”, „A”, „I” i „T” łączą się, tworząc słowo „CZEKAJ”.

Naiwnym rozwiązaniem znajdowania wszystkich prawidłowych słów byłoby eksplorowanie tablicy, zaczynając od lewego górnego rogu, a następnie przesuwając najpierw głębię do dłuższych sekwencji, zaczynając ponownie od drugiej litery w pierwszym rzędzie i tak dalej. Na planszy 4x4, umożliwiającej ruchy w pionie, poziomie i po przekątnej, znajduje się 12029640 sekwencji o długości od jednego do szesnastu znaków.

Teraz naszym celem jest znalezienie najlepszej struktury danych do zaimplementowania tego sprawdzania prawidłowych słów, tj. naszego słownictwa. Kilka punktów, o których należy pamiętać:

• Potrzebujemy tylko jednej kopii każdego słowa, tj. nasze słownictwo jest zbiorem, z logicznego punktu widzenia.
• Dla dowolnego słowa musimy odpowiedzieć na następujące pytania:
  • Czy bieżąca sekwencja znaków zawiera poprawne słowo?
  • Czy są dłuższe słowa, które zaczynają się tą sekwencją? Jeśli nie, możemy porzucić naszą eksplorację w głąb, ponieważ wchodzenie głębiej nie przyniesie żadnych ważnych słów.

Aby zilustrować drugi punkt, rozważ następującą planszę: Nie ma sensu badać kolejnych ruchów, ponieważ w słowniku nie ma słów zaczynających się na „ASF”.

Chcielibyśmy, aby nasza struktura danych odpowiadała na te pytania tak szybko, jak to możliwe. ~O(1) czas dostępu (do sprawdzenia sekwencji) byłby idealny!

Możemy zdefiniować interfejs słownika w ten sposób (zobacz tutaj repozytorium GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Wypróbuj strukturę danych a alternatywy

Implementacja metody Contains() wymaga pomocniczej struktury danych, która pozwala na sprawne znajdowanie elementów, podczas gdy metoda contains() isPrefix() wymaga od nas znalezienia „następnego większego elementu”, czyli musimy zachować w jakiś sposób posortowane słowniki.

Możemy łatwo wykluczyć zestawy oparte na hashach z naszej listy kandydatów: podczas gdy taka struktura zapewniłaby nam sprawdzanie w czasie ciągłym pod kątem contains() , działałaby dość słabo na isPrefix() , w najgorszym przypadku wymagałaby przeskanowania całości ustawić.

Z zupełnie przeciwnego powodu możemy również wykluczyć posortowane listy połączone, ponieważ wymagają one przeskanowania listy przynajmniej do pierwszego elementu, który jest większy lub równy wyszukiwanemu słowu lub przedrostkowi.

Dwie poprawne opcje używają posortowanej listy opartej na tablicy lub drzewa binarnego.
Na posortowanej liście opartej na tablicy możemy użyć wyszukiwania binarnego, aby znaleźć bieżącą sekwencję, jeśli jest obecny lub następny większy element, kosztem O(log2(n)) , gdzie n jest liczbą słów w słowniku.

Możemy zaimplementować słownik oparty na tablicy, który zawsze zachowuje taką kolejność, używając standardowych java.util.ArrayList i java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Gdybyśmy zdecydowali się na użycie drzewa binarnego, implementacja mogłaby być jeszcze krótsza i bardziej elegancka (tu znowu link do kodu):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

W obu przypadkach możemy oczekiwać wydajności O(log n) dla każdej metody dostępu ( contains() i isPrefix() ). Jeśli chodzi o wymagania dotyczące miejsca, zarówno implementacja oparta na tablicy, jak i implementacja oparta na drzewie, wymagają O(n+M) , gdzie n to liczba słów w słowniku, a M to rozmiar bajtu słownika, tj. suma długości ciągi w słowniku.

Wypróbuj aplikacje: kiedy i dlaczego warto korzystać z prób

Wydajność logarytmiczna i pamięć liniowa nie są złe. Ale jest jeszcze kilka cech naszej domeny aplikacji, które mogą prowadzić nas do lepszej wydajności:

• Możemy spokojnie założyć, że wszystkie słowa są pisane małymi literami.
• Akceptujemy tylko litery az – bez znaków interpunkcyjnych, łączników, akcentów itp.
• Słownik zawiera wiele form odmiennych: liczby mnogie, czasowniki odmienione, wyrazy złożone (np. dom -> gospodyni). Dlatego wiele słów ma ten sam rdzeń .
• Słowa mają ograniczoną długość. Na przykład, jeśli pracujemy na planszy 4x4, wszystkie słowa dłuższe niż 16 znaków mogą zostać odrzucone.

W tym miejscu pojawia się trie (wymawiane „try”). Ale czym dokładnie jest trie? Próby to zaniedbane struktury danych, które można znaleźć w książkach, ale rzadko w standardowych bibliotekach.

Dla motywacji rozważmy najpierw potomka plakatu informatyki: drzewo binarne. Teraz, kiedy analizujemy wydajność drzewa binarnego i mówimy, że operacja x to O(log(n)) , ciągle mówimy o podstawie logu 2. Ale co jeśli zamiast drzewa binarnego użyjemy drzewa trójskładnikowego, gdzie każdy węzeł ma troje dzieci (lub jeden z trzech). Wtedy będziemy mówić o podstawie logu 3. (Jest to poprawa wydajności, choć tylko o stały czynnik). Zasadniczo nasze drzewa stałyby się szersze, ale krótsze i moglibyśmy wykonywać mniej wyszukiwań, ponieważ nie musimy całkiem schodzić w dół tak głeboko.

Idąc krok dalej, co by było, gdybyśmy mieli drzewo z rozłożeniem równym liczbie możliwych wartości naszego typu danych?

To jest motywacja tego triumfu. I jak można się domyślić, próba jest rzeczywiście drzewem, że tak powiem, drzewem próbnym!

Ale w przeciwieństwie do większości drzew binarnych, których używałbyś do sortowania ciągów, czyli tych, które przechowują całe słowa w swoich węzłach, każdy węzeł tri przechowuje pojedynczy znak (a nawet to, jak zobaczymy wkrótce) i ma maksymalny rozrzut równy długości alfabetu. W naszym przypadku długość alfabetu wynosi 26; w związku z tym węzły tria mają maksymalny rozrzut równy 26. I chociaż zrównoważone drzewo binarne ma głębokość log2(n) , maksymalna głębokość tria jest równa maksymalnej długości słowa! (Znowu szerszy, ale krótszy.)

W ramach próby słowa z tym samym rdzeniem (prefiksem) dzielą obszar pamięci odpowiadający rdzeniowi.

Aby zobrazować różnicę, rozważmy mały słownik składający się z pięciu słów. Załóżmy, że greckie litery oznaczają wskaźniki i zauważ, że w tym przykładzie czerwone znaki oznaczają węzły zawierające prawidłowe słowa .

Implementacja wersji próbnej Javy

Jak wiemy, w drzewie wskaźniki do elementów potomnych są zwykle implementowane ze zmienną lewą i prawą, ponieważ maksymalny rozrzut jest ustalony na dwa.

W próbie indeksowania alfabetu składającego się z 26 liter, każdy węzeł ma 26 możliwych dzieci, a zatem 26 możliwych wskaźników. Każdy węzeł zawiera więc tablicę 26 (wskaźniki do) poddrzew, gdzie każda wartość może być null (jeśli nie ma takiego dziecka) lub inny węzeł.

Jak zatem sprawdzić słowo w trio? Oto metoda, która po podaniu String s zidentyfikuje węzeł odpowiadający ostatniej literze słowa, jeśli istnieje w drzewie:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

Metoda LOWERCASE.getIndex(s.charAt(i)) po prostu zwraca pozycję i-tego znaku alfabetu. W zwróconym węźle node właściwości Boolean wskazuje, że węzeł odpowiada ostatniej literze słowa, tj. literze zaznaczonej na czerwono w poprzednim przykładzie. Ponieważ każdy węzeł przechowuje licznik liczby dzieci, jeśli ten licznik jest dodatni, to w słowniku są dłuższe słowa, które mają bieżący ciąg jako prefiks. Uwaga: węzeł tak naprawdę nie musi utrzymywać odniesienia do znaku, któremu odpowiada, ponieważ jest on ukryty w jego pozycji w tri.

Analiza wydajności

To, co sprawia, że ​​struktura trików naprawdę dobrze sprawdza się w takich sytuacjach, to fakt, że koszt wyszukania słowa lub prefiksu jest stały i zależny tylko od liczby znaków w słowie, a nie od rozmiaru słownictwa.

W naszej specyficznej domenie, ponieważ mamy ciągi, które mają co najwyżej 16 znaków, dokładnie 16 kroków jest koniecznych, aby znaleźć słowo, które jest w słowniku, podczas gdy można uzyskać każdą negatywną odpowiedź, tj. słowo lub prefiks nie znajduje się w trójce w maksymalnie 16 krokach! Biorąc pod uwagę, że wcześniej zignorowaliśmy długość ciągu podczas obliczania złożoności czasu wykonywania zarówno dla posortowanej listy opartej na tablicy, jak i dla drzewa, które jest ukryte w porównaniach ciągów, możemy równie dobrze zignorować go tutaj i bezpiecznie stwierdzić, że wyszukiwanie zostało zakończone w czasie O(1) .

Biorąc pod uwagę wymagania dotyczące miejsca (i pamiętając, że wskazaliśmy jako M rozmiar bajtu słownika), próba może mieć M węzłów w najgorszym przypadku, jeśli żadne dwa łańcuchy nie mają wspólnego przedrostka. Ale ponieważ zaobserwowaliśmy, że w słowniku jest wysoki stopień nadmiarowości, trzeba zrobić dużo kompresji. Słownik angielski, który jest używany w przykładowym kodzie, ma 935 017 bajtów i wymaga 250 264 węzłów, ze współczynnikiem kompresji około 73%.

Jednak pomimo tego nawet skompresowana próba będzie zwykle wymagała więcej pamięci niż drzewo lub tablica. Dzieje się tak, ponieważ dla każdego węzła konieczne jest co najmniej 26 x sizeof(pointer) bajtów, plus trochę narzutu dla obiektu i dodatkowych atrybutów. Na maszynie 64-bitowej każdy węzeł wymaga więcej niż 200 bajtów, podczas gdy znak ciągu wymaga jednego lub dwóch bajtów, jeśli weźmiemy pod uwagę ciągi UTF.

Próby i testy wydajności

A co z wydajnością? Implementacje słownictwa zostały przetestowane w dwóch różnych sytuacjach: sprawdzenie 20 000 000 losowych ciągów i znalezienie wszystkich słów z 15 000 tablic wygenerowanych losowo z tej samej listy słów.

Przeanalizowano cztery struktury danych: posortowaną listę opartą na tablicy, drzewo binarne, trie opisane powyżej oraz trie wykorzystujące tablice bajtów odpowiadających indeksowi alfabetu samych znaków (drobna i łatwa w implementacji optymalizacja wydajności). Oto wyniki w ms:

Średnia liczba ruchów wykonywanych w celu rozwiązania planszy to 2188. Dla każdego ruchu wykonywane jest wyszukiwanie słów i wyszukiwanie prefiksów, tj. w celu sprawdzenia wszystkich płyt wykonano ponad 32M wyszukiwania słów i 32M wyszukiwania prefiksów. Uwaga: można to zrobić w jednym kroku, zachowałem je osobno dla jasności w ekspozycji. Zagęszczanie ich w jednym kroku skróciłoby czas rozwiązywania desek prawie o połowę i prawdopodobnie jeszcze bardziej sprzyjałoby tej próbie.

Jak widać powyżej, wyszukiwanie słów działa lepiej z triem, nawet przy użyciu łańcuchów, i jest jeszcze szybsze, gdy używa się indeksów alfabetycznych, przy czym ten ostatni działa ponad dwa razy szybciej niż standardowe drzewo binarne. Różnica w rozwiązywaniu tablic jest jeszcze bardziej widoczna, ponieważ szybkie rozwiązanie z trzema alfabetami jest ponad cztery razy szybsze niż lista i drzewo.

Zawijanie

Trie to bardzo wyspecjalizowana struktura danych, która wymaga znacznie więcej pamięci niż drzewa i listy. Jednak w przypadku zastosowania określonych cech domeny, takich jak ograniczony alfabet i wysoka nadmiarowość w pierwszej części ciągów, może to być bardzo skuteczne w optymalizacji wydajności.

Bibliografia

Obszerne wyjaśnienie prób i alfabetów można znaleźć w rozdziale 5 książki Roberta Sedgewicka „Algorytmy, wydanie 4”. Witryna towarzysząca w Princeton zawiera kod implementacji Alphabet i TrieST, który jest bardziej rozbudowany niż mój przykład.

Opis wersji i implementacji dla różnych języków można również znaleźć na Wikipedii, a także możesz zapoznać się z tym zasobem wersji próbnej Uniwersytetu Bostońskiego.