Trie

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

Definicja trie

Trie jest to ukorzenione drzewo przeszukiwań przechowujące skończoną ilość kluczy (słów). Klucz jest postaci $ w=w_1w_2..w_m $, gdzie każde $ w_i \in w $ jest literą należącą do ustalonego alfabetu $ \Sigma $. Każdy węzeł zawiera listę krawędzi wychodzących etykietowanych literami alfabetu $ \Sigma $. Każdy węzeł reprezentuje pewien fragment (prefiks) klucza/y. Istnieje krawędź $ e $ z węzła $ v $ do $ u $ o etykiecie $ c $, jeśli prefiks klucza reprezentowanego przez $ v $ rozszerzony o literę $ c $ również jest prefiksem dla pewnego klucza (niekoniecznie tego samego).

Jest to najprostsza definicja drzewa trie jaką udało mi się wymyślić. Mimo to widać, że łatwiej było wyjaśnić konstrukcję tej struktury danych na przykładzie.

Na początek przyjmiemy dwa założenia. Pierwsze: alfabet $ \Sigma $ jest zbiorem skończonym np. alfabet języka polskiego (32 znaki). Będziemy się tego sztywno trzymali, gdyż w algorytmach tekstowych spotkamy się głównie z problemami związanymi z "prawdziwym tekstem", zrozumiałym dla czytelnika znającego dany język. Szczerze wątpię czy istnieją ludzie posługujący się językami nad nieskończonym alfabetem (choć pewny nie jestem :) ).

Drugie założenie: żadne słowo z $ S $ nie jest prefiksem innego słowa z $ S $ (inaczej słowa mogłyby się kończyć wewnątrz drzewa). Dzięki temu wskaźniki do każdego klucza z $ S $ będą się znajdowały jedynie w liściach. Jest to tymczasowe założenie, którego wkrótce się pozbędziemy. Wprowadzamy je w celu uproszczenia procedur opisanych w następnej sekcji.

Pomocne oznaczenia:

  • $ root(T) $ - wskaźnik na korzeń drzewa $ T $.
  • $ label(e) $ - etykieta krawędzi $ e $

Podstawowe operacje

Wyszukiwanie klucza

Wyszukiwanie przebiega zgodnie z algorytmem rekurencyjnym, którego idea została podana na poprzedniej stronie. Teraz przedstawimy tę procedurę w postaci pseudo-kodu:

Zwróćmy uwagę na wywołanie procedury. Pisząc $ LOOKUP(w,v) $ mamy na myśli komendę "sprawdź, czy słowo $ w $ znajduje się w drzewie trie zaczynając od wierzchołka $ v $". Z tego wynika, że początkowe wywołanie metody ma postać: $ LOOKUP(w,root(T)) $.

Dodawanie klucza

Dodawanie klucza do drzewa jest równie proste jak wyszukiwanie. Patrzymy na pierwszą literę słowa $ w $ ( $ w=cw' $ ) i sprawdzamy czy istnieje krawędź wychodząca z korzenia o etykiecie $ c $. Jeśli istnieje taka krawędź, to wywołujemy się rekurencyjnie na wierzchołku wskazywanym przez tą krawędź dla słowa $ w' $. W przeciwnym wypadku należy utworzyć nowy wierzchołek (i krawędź o etykiecie $ c $) i na nim kontynuować rekurencję. Poprawność tej metody jest oczywista.

Dodanie słowa 'okap' do trie zawierającego jeden klucz: 'oko'

Usuwanie klucza

Żeby usunąć klucz $ w $ z drzewa, oczywistym jest, że $ w $ musi w tym drzewie się znajdować. Stąd pierwszym krokiem procedury $ DELETE $ jest znalezienie liścia reprezentującego słowo $ w $. Jeśli taki liść nie istnieje, to nie ma sensu kontynuować wykonanie algorytmu.

Właściwe usunięcie klucza $ w $ zaczynamy "od końca". Idziemy w górę drzewa i usuwamy kolejne węzły dopóki nie napotkamy węzła posiadającego przynajmniej jednego syna. Dlaczego akurat tak? poniższa symulacja usunięcia słowa gniew ze słownika {gnu, gniew} powinna wyjaśnić wszelkie wątpliwości.

Z powyższego rysunku łatwo wywnioskować, że możemy usunąć tylko węzły, które nie są częścią innego klucza niż ten, który usuwamy.

Złożoność obliczeniowa podstawowych operacji

Analiza czasu działania przedstawionych powyżej procedur będzie się opierała na jednej ważnej obserwacji:

Liczba krawędzi wychodzących z dowolnego węzła w drzewie trie jest nie większa niż liczba liter w alfabecie $ \Sigma $.

Ta obserwacja jest prawdziwa, gdyż drzewo trie jest skonstruowane tak, żeby z dowolnego węzła nie wychodziły żadne dwie krawędzie o tej samej etykiecie.

Łącząc powyższą obserwację i nasze wcześniejsze założenie o rozmiarze alfabetu można wywnioskować, że:

Jeśli $ |w|=m $, to czas działania procedur $ LOOKUP(w,root(T)) $, $ INSERT(w,root(T)) $ i $ DELETE(w,T) $ wynosi $ O(m) $.

Dowód: wywołań rekurencyjnych w $ LOOKUP $ i $ INSERT $ jest co najwyżej $ m $. Czas spędzony na przejście po liście krawędzi dla dowolnego wierzchołka wynosi $ O(1) $, co kończy dowód dla tych dwóch procedur.

W procedurze $ DELETE(w,T) $ znalezienie liścia reprezentującego słowo $ w $ jest jednoznaczne z wywołaniem metody $ LOOKUP $. Czas tego kroku to $ O(m) $. Liczba usuniętych węzłów nie przekracza $ m $. Daje nam to górne ograniczenie na liczbę przebiegów pętli wewnątrz metody $ DELETE $, co kończy dowód.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com