Tries: Drzewo Prefiksowe Podstawienie Autocomplete

Co to jest tries?

Trie (czytane jako 'try', od retrieval) to struktura danych podobna do drzewa zaprojektowana specjalnie do przechowywania ciągów znaków. W przeciwieństwie do drzewa binarnego, w którym każdy node zawiera pełny klucz, node trie zazwyczaj zawierają pojedynczy znak, a pełne słowo jest odczytywane przez śledzenie ścieżki znaków od korzenia do pewnego marked node. Kluczowe podejście polega na tym, że wspólnych prefiksów ma wspólną strukturę: jeśli wstawimy zarówno 'cat', jak i 'car', to korzeń rozgałęzia się na dziecko dla 'c', które dalej rozgałęzia się na dziecko dla 'a', a dopiero po tej wspólnej ścieżce 'ca' drzewo rozgałęzia się na oddzielne gałęzie dla 't' i 'r'. Każdy język, który zaczyna się od 'ca', przechodzi przez dokładnie te same dwa node. Każdy node również zawiera flagę oznaczającą, czy ścieżka kończąca się tam jest pełnym słowem, ponieważ jedno słowo może być prefiksem drugiego (np. 'car' i 'card'). Ta struktura oznacza, że kształt tries jest całkowicie wyznaczony przez słownictwo przechowywane w nim, a dowolne dwa ciągi, które mają wspólny prefiks długości k, będą się pokrywać dokładnie na k node przed oddzielnym przebiegiem, niezależnie od tego, jak bardzo się różnią potem.

Wstawianie: Budowanie drzewa znak po znaku

Wstawianie słowa do tries jest proste i bezpośrednie. Zaczynając od korzenia, sprawdzasz pierwszy znak słowa i sprawdzasz, czy obecny węzeł ma już dziecko dla tego znaku. Jeśli tak, przesuwasz się do istniejącego dziecka; jeśli nie, tworzysz nowy węzelek dla tego znaku i przechodzisz do niego. Powtarzasz to dla każdego znaku w słowie, rozszerzając ścieżkę tylko tam, gdzie ona jeszcze nie istniała. Po zakończeniu ostatniego znaku oznaczasz końcowy węzeł jako koniec prawidłowego słowa. Ponieważ istniejące wspólne prefiksy są ponownie używane zamiast powtarzane, wstawianie 'cat' po 'car' kosztuje tylko nowego węzła (dla 't'), ponieważ węzły 'c' i 'a' już istniały ze wcześniejszego wstawienia. Wstawianie działa w czasie proporcjonalnym do długości słowa, które jest wstawiane, a nie liczbie słów już przechowywanych, co sprawia, że tries skali się grzecznie z rozrostem słownika. Ten sam przebieg znak po znaku jest prawie niezmieniony dla operacji wyszukiwania: wyszukiwanie słowa polega tylko na sprawdzeniu, czy każdy wymagany węzeł dziecka istnieje w sekwencji i czy końcowy węzeł jest oznaczony jako pełne słowo, zwracając błąd jak tylko brakuje koniecznego znaku.

Szukanie prefiksowe: Dlaczego jest szybkie

Przynętą trzewia polega na tym, że odpowiada ono zapytanom typu 'znajdź każde słowo zaczynające się od pre' bez przeszukiwania całego słownika. Algorytm przechodzi po trzewiu, śledząc znaki prefiksu, dokładnie jak podczas wyszukiwania, aż dotrze do węzła reprezentującego ostatni znak prefiksu. Ze względu na ten pojedynczy węzeł, każde słowo zasadowe znajdujące się pod nim w poddrzewie zaczyna się od tego prefiksu, więc zbieranie wszystkich pasujących wyników polega tylko na głębokim przeszukiwaniu tego poddrzewa i zbieraniu każdego ścieżki kończącej się na węźle oznaczonej jako słowo. Rozważ trzeci mały trzewiu zbudowany z słów cat, car, card, care oraz dog. Przechodzenie przez 'ca' prowadzi do wspólnego węzła po 'c', a następnie 'a'; pod drzewem znajduje się gałąź dla 't' (cat), 'r' (car, co jest samym słownikiem), 'rd' (card) i 're' (care) – cztery pasujące wyniki znalezionych przez przeszukanie tylko jednego poddrzewa, bez dotykania nienaturalnej gałęzi 'dog'. Koszt lokalizacji poddrzewa prefiksu zależy tylko od długości prefiksu, a koszt listowania pasujących wyników zależy tylko od liczby pasujących wyników i znaków, które one zawierają, niezależnie od rozmiaru całego słownika. To strukturalna przyczyna, dlaczego szukanie prefiksowe wydaje się niewątpliwie natychmiastowe nawet nad ogromnymi skrzynkami leksykalnymi.

Przeciwstawienia dotyczące pamięci i zaciskanych wersji

Trye wymieniają pamięć na szybkość, a dla rzadkich danych ta wymiana może być słabej jakości. Prostowy tablicowy zestaw węzłów dla każdego znaku (np., 26 slotów dla małych liter) oznacza, że każdy węzeł zarezerwuje miejsce dla wszystkich możliwych kolejnych znaków, nawet jeśli tylko jeden lub dwa są kiedykolwiek używane. Dla drzewa zawierającego małą, rzadką zbiorcę długich, niepodobnych słów ta wymiana może spowodować znaczący wzrost zużycia pamięci w stosunku do prostego przechowywania tych słów w posortowanej liście lub tablicy i wyszukiwania binarnego. Nadmiar wynika z wszystkich łańcuchów o jednym dziecku: długie słowa bez braci nadal otrzymują pełny węzeł dla każdego znaku. Drzewa radiksowe (także nazywane tryami Patricia) rozwiązuje to, zmieniając łańcuchy węzłów o jednym dziecku na jedną krawędź etykietowaną całą podciągiem zamiast jednym znakiem. Unikalny sufiks, tak jak 'ardvark', staje się pojedynczą krawędzią zamiast siedmiu osobnych węzłów. To zachowuje korzyści związane z dzieleniem się prefiksem dla regionów gałęziowych, eliminując nadmierne struktury na rzadkich, niegałęziowych sekcjach. Inne implementacje wymieniają tablice o ustalonej wielkości na mapy hash lub posortowane małe tablice na każdy węzeł, wymieniając małą szybkość dla pojedynczego wyszukiwania na znacznie niższą pamięć, gdy alfabet jest duży (np., Unicode) lub większość węzłów ma bardzo mało dzieci, co jest powszechnym przypadkiem w rzeczywistych słownikach.

Zastosowania w Praktyce

Drzewa tries i ich skompresowane warianty pojawiają się wszędzie tam, gdzie szybkie dopasowanie prefiksowe ma kluczowe znaczenie. Systemy autocompletu i sugerujące wyszukiwanie wykorzystują je do natychmiastowego wyświetlenia propozycji podczas wprowadzania tekstu, często przechowując dane o częstotliwości lub popularności na każdym węźle słowa, aby ustawić priorytety. Systemy sprawdzające pisownię przegrużają drzewo tries, aby potwierdzić istnienie wprowadzonego słowa w słowniku i mogą zaproponować słowa bliskie poprawne, eksplorując gałęzie różniące się jednym znakiem. Tabele routingu IP wykorzystują specjalizowane drzewo tries nad prefiksami binarnymi adresów do wykonania dopasowania najdłuższego prefiksu, pozwalając routery na decyzję, która z wielu przewidzianych reguł sieciowych dotyczy adresu docelowego pakietu, przegrużając drzewo bit po bitu i pamiętając najbardziej głębokie dopasowanie znaleziony. T9 predykcyjny tekst, technologia za tą, która umożliwia wprowadzanie słów przy użyciu klawisza numerycznego telefonu, przyporządkowywała naciśnięcie każdego klawisza do zestawu możliwych liter i używając struktur podobnych do tries, ograniczała ona możliwe słowa zasłownika podczas wprowadzania cyfr, oferując najprawdopodobniejsze słowo przed zakończeniem wprowadzania. W każdym przypadku wykorzystywany jest taki sam podstawowy mechanizm: ponieważ powiązane ciągi mają wspólną strukturę, jedno przejście po drzewie może odpowiedzieć na całą klasę pytań dotyczące wielu ciągów naraz.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Tries: The Prefix Tree Behind Autocomplete i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.