Trie

01.12.2011 - Michał Karpiński
TrudnośćTrudność

Podstawową strukturą danych wykorzystywaną w algorytmach tekstowych jest drzewo trie (czyt. tri lub traj). Jest to kolejne rozwiązanie dla problemu wyszukiwania wzorca (i nie tylko). Z drzew trie korzystamy, gdy liczba zapytań jest na tyle duża, że nie opłaca się użycie klasycznych metod takich jak KMP czy BM (szczególnie gdy tekst wejściowy składa się ze sporej liczby słów). Drzewa te nadają się np. do sprawdzania poprawności pisowni. Warto dodać, że na bazie drzew trie budowane są bardziej skomplikowane struktury danych np. drzewa sufiksowe, lecz zanim zagłębimy się w zaawansowaną algorytmikę należy najpierw zrozumieć niezbędne podstawy.

Jeśli pierwszy raz zetknąłeś się z problemami tekstowymi, to zapoznaj się wpierw z podstawowymi zagadnieniami i definicjami z dziedziny algorytmów tekstowych. Wróć tutaj, gdy przeczytasz ze zrozumieniem ten artykuł.

Uważam, że dobrym pomysłem jest zostawienie formalnej definicji drzewa trie na później, gdyż ta struktura jest na tyle prosta, że po obejrzeniu konkretnego przykładu jej budowa okaże się bardzo intuicyjna. Na początek weźmy niewielki zbiór słów. Taki zbiór będziemy nazywać słownikiem i oznaczymy go literą $ S $. Załóżmy, że w $ S $ znajdują się takie słowa: maj, byk, kot, milion, koc, mila. Trie dla zbioru $ S $ wygląda następująco:

Pytanie: Czy z przedstawionego powyżej drzewa potrafimy odczytać wszystkie słowa z $ S $?

Odpowiedź: Oczywiście, że TAK! Odczytywanie dowolnego słowa zaczynamy od korzenia (wierzchołka, który na rysunku znajduje się najwyżej i jest innego koloru niż pozostałe wierzchołki). Następnie przechodzimy dowolną ścieżką aż do liścia. Jeśli wypiszemy litery przypisane do krawędzi w kolejności ich odwiedzenia (od góry do dołu), to otrzymamy słowo należące do słownika. Dla przykładu: gdybyśmy szli cały czas "w prawo", to dostalibyśmy słowo milion. Powtarzając ten proces dla każdej ścieżki od korzenia do liścia otrzymamy cały zbiór $ S $.

Po dokładnym przeanalizowaniu powyższego przykładu każdy powinien bez trudu odgadnąć sposób budowania drzew trie. Nasuwa się jednak pytanie: dlaczego reprezentować nasz słownik w taki sposób?

Podstawową procedurą jaką będziemy chcieli wykonywać jest $ LOOKUP(w,S) $ – stwierdzenie, czy słowo $ w $ należy do słownika $ S $. Jeśli reprezentacją naszego słownika byłaby zwykła lista łączona, to w najgorszym przypadku musielibyśmy porównać wszystkie elementy z $ S $ ze słowem $ w $.

Ciekawostka: nie jest znana liczba słów w języku polskim. Źródło: link

W naszym przykładzie operujemy na niewielkiej liczbie słów, więc przejście całej listy w poszukiwaniu jakiegoś słowa (np. mak, patrz rysunek powyżej) zajmuje mało czasu. Wyobraźmy sobie jednak, że jesteśmy w posiadaniu słownika o większych rozmiarach np. słownik języka polskiego. Sprawa zaczyna się nieco komplikować, nieprawdaż?

Jeśli w ogólnym przypadku przyjmiemy, że $ |S|=n $ i $ |w|=m $, to złożoność czasowa procedury $ LOOKUP(w,S) $ wynosi $ O(mn) $ (każde z $ n $ słów słownika porównujemy z $ w $, a jedno porównanie to czas $ O(m) $).

Pytanie: jak będzie wyglądała procedura $ LOOKUP $ z wykorzystaniem drzewa trie (i jaką będzie miała złożoność czasową)?

Odpowiedź: procedurę $ LOOKUP $ można zdefiniować rekurencyjnie. Oznaczmy korzeń jako wierzchołek aktywny. Dla słowa $ w=w_1w_2...w_m $ sprawdzamy, czy istnieje krawędź wychodząca z korzenia, do której przypisana jest litera $ w_1 $. Jeśli tak, to idziemy w dół przez tą krawędź do kolejnego wierzchołka, oznaczamy go jako aktywny i powtarzamy ten krok dla słowa $ w’ = w_2w_3...w_m $ itd. Jeśli taka krawędź nie istnieje, to znaczy, że słowo nie należy do $ S $. Procedura kończy się powodzeniem, jeśli uda nam się dojść do liścia i $ w' $ będzie słowem pustym.

Przykład dla naszego słownika i $ w=mak $:

Jak się niedługo przekonamy, dzięki przeszukiwaniu drzewa trie sporo oszczędzamy na złożoności, gdyż czas zapytania jest liniowy względem długości szukanego słowa, czyli $ O(m) $. Daje nam to znacznie lepszy wynik niż przy podejściu "brutalnym".

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com