Trie (drzewo prefiksów) w Pythonie

Question

Nie wiem, czy to jest miejsce, aby zapytać o algorytmy. Ale zobaczmy, czy dostaję jakieś odpowiedzi ... :)

Jeśli coś jest niejasne, bardzo chętnie wyjaśniam rzeczy.

Właśnie zaimplementowałem Trie w python. Jednak jeden kawałek wydawał się być bardziej skomplikowany, niż powinien (jako ktoś, kto kocha prostotę). Być może ktoś miał podobny problem?

Moim celem było zminimalizowanie liczby węzłów poprzez przechowywanie największego wspólnego przedrostka podrzędnego w jego katalogu głównym. Na przykład, jeśli mieliśmy słowa stackoverflow, stackbase i stackbased, to drzewo będzie wyglądać mniej więcej tak:

   [s]tack 
[o]verflow ______/ \_______ [b]ase 
            \___ [d] 

Zauważ, że można jeszcze myśleć o krawędziach o jeden znak (the pierwszy z węzła potomnego).

Znajdź -query jest prosty w realizacji. Insertion nie jest trudne, ale nieco bardziej skomplikowane niż chcę .. :(

Mój pomysł polegał na włożeniu klucze jedna po drugiej (od pustej trie), najpierw szukając to-be -podstawiony klucz k (Znajdź (k)), a następnie przestawia/dzieli węzły lokalnie w miejscu, w którym kończy się procedura znalezienia.Okazuje się, że są 4 przypadki: (Niech k będzie kluczem, który chcemy wstawić i k 'być kluczem węzła, gdzie poszukiwanie zakończony)

1. k jest identyczna jak k'
2. k jest "właściwym" prefiksem k '
3. k' jest "właściwym" prefiksem k
4. k i k 'mają wspólny przedrostek, ale żaden z przypadków (1), (2) lub (3) wystąpić.

Wygląda na to, że każdy z tych przypadków jest niepowtarzalny, co sugeruje różne modyfikacje Trie. ALE: czy to naprawdę takie skomplikowane? Czy czegoś brakuje? Czy istnieje lepsze podejście?

Dzięki :)

Answer 1

W skrócie brzmi to tak, jakby zaimplementować wersję Patricia Trie. To podejście jest również nazywane kompresją ścieżek w niektórych publikacjach. Powinny istnieć kopie tego papieru, które nie są objęte zapłatą ACM, które będą zawierać algorytm wstawiania.

Istnieje również inna metoda kompresji, na którą możesz spojrzeć: kompresja poziomu. Ideą kompresji ścieżek jest zamiana łańcuchów pojedynczych węzłów podrzędnych na pojedynczy super węzeł, który ma wartość "pominięcia".Ideą kompresji poziomu jest zastąpienie pełnego lub prawie pełnego poddrzewa super węzłem z "stopniem" określającym liczbę cyfr klucza, który węzeł dekoduje. Istnieje również trzecia metoda zwana kompresją szerokości, ale obawiam się, że moja pamięć mnie zawiodła i nie mogłem znaleźć jej opisu z szybkim googlowaniem.

Kompresja poziomu może znacznie skrócić średnią ścieżkę, ale algorytmy wstawiania i usuwania stają się dość skomplikowane, ponieważ muszą zarządzać węzłami trie podobnie jak dynamicznymi tablicami. W przypadku właściwych zestawów danych poziomy skompresowanych drzew mogą być następujące: fast. Z tego, co pamiętam, są to 2 najszybsze podejście do przechowywania tabel routingu IP, najszybszy jest jakikolwiek skrót.

Answer 2

Nie widzę niczego złego w twoim podejściu. Jeśli szukasz rozwiązania spajania, być może akcja podjęta w przypadku 4 jest faktycznie możliwa do wykonania w pierwszych trzech przypadkach, znajdź wspólny prefiks k i k' i przebuduj węzeł mając to na uwadze. Jeśli zdarza się, że klucze są przedrostkami jednego drugiego, wynikowy trie będzie nadal poprawny, tylko implementacja wykonała nieco więcej pracy, niż naprawdę musiała. ale z drugiej strony, bez żadnego kodu, na który trudno byłoby ocenić, czy to działa w twoim przypadku.

Answer 3

Nieco stycznej, ale jeśli jesteś bardzo zaniepokojony liczbą węzłów w Twoim Trie, możesz również rozważyć dołączenie swoich sufiksów. Chciałbym rzucić okiem na pomysł DAWG (Directed Acyclic Word Graph): http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

Minusem jest to, że nie są one bardzo dynamiczne, a ich tworzenie może być trudne. Ale jeśli twój słownik jest statyczny, mogą być bardzo kompaktowe.

Answer 4

Mam pytanie dotyczące Twojego wdrożenia. Jaki jest poziom szczegółowości, w którym zdecydujesz się podzielić łańcuchy, aby utworzyć drzewo prefiksu. Możesz podzielić stos jako s, t, a, c, k lub st, ta, ac, ck i wiele innych ngramów tego. Większość implementacji drzewa prefiksów uwzględnia alfabet dla tego języka, w oparciu o ten alfabet, dokonujesz podziału.

Jeśli budowali implementację drzewa prefiks dla Pythona potem twoi alfabetów byłoby takie rzeczy def,:, jeśli jeszcze ... itd

Wybór odpowiedniego alfabetu robi ogromną różnicę w budowaniu efektywnych drzew prefiks. Jeśli chodzi o twoje odpowiedzi, możesz poszukać pakietów PERL na CPAN, które najdłużej używają wspólnego podciągu przy użyciu trie. Możesz mieć trochę szczęścia, ponieważ większość ich implementacji jest dość solidna.

Answer 5

Spójrz: Judy-tablic i interfejs Pythona na http://www.dalkescientific.com/Python/PyJudy.html