Podstawy autouzupełniania

Część bywalców kanału #warsztat może wiedzieć, że od jakiegoś czasu w wolnych chwilach rozwijam pewien niewielki projekt. Jest to prosty IRC-owy bot, który potrafi wykonywać różne predefiniowane czynności, dostępne za pomocą komend rozpoczynających się od kropki. Wśród nich mamy między innymi wysyłanie zapytań do wyszukiwarki Google, wyświetlanie skrótów artykułów z Wikipedii, przekazywanie wiadomości między użytkownikami i jeszcze kilka innych. W sumie jest ich już około kilkanaście, więc pomyślałem, że dobrym rozwiązaniem byłby wbudowany system pomocy oraz podpowiedzi opartych na “domyślaniu się”, jakie polecenie użytkownik chciał wydać.
Brzmi to może nieco zagadkowo, ale w gruncie rzeczy chodzi o zwykłe autouzupełnianie (autocompletion), do którego jesteśmy przyzwyczajeni w wielu innych miejscach – takich jak środowiska programistyczne czy choćby wyszukiwarki internetowe. Oczywiście tutaj mówimy o nawet miliardy razy mniejszej skali całego rozwiązania, ale ogólna zasada we wszystkich przypadkach jest – jak sądzę – bardzo podobna.

Cały mechanizm opiera się właściwie o jedną strukturę danych zwaną drzewem prefiksowym (prefix tree). Jest to całkiem pomysłowa konstrukcja, w której każde dopuszczalne słowo (zwane tradycyjnie w takich drzewach kluczem) wyznacza pewną ścieżkę od korzenia drzewa. Kolejne krawędzie etykietowane są tu znakami słowa.
Najważniejszą cechą drzewa prefiksowego jest jednak to, że wspomniane ścieżki mogą się nakładać, jeśli początkowe części danych słów się pokrywają. Stąd zresztą bierze się nazwa struktury, gdyż pozwala ona szybko znaleźć ciągi zaczynające się od podanego tekstu – czyli właśnie prefiksu.

W zrozumieniu zagadnienia powinien tutaj pomóc odpowiedni przykład. Powiedzmy, że mamy poniższą listę słów do zorganizowania w drzewo:

karmel, karmazyn, kartacz, kapok, kalendarz, karta, komar, komoda, kalka, piłka

Nietrudno zauważyć, że większość z nich ma wspólne przedrostki – dłuższe lub krótsze. Pierwsze trzy na przykład, wrzucone w drzewo, miałyby wspólny fragment ścieżki o długości 3:

Dwa z nich mają aczkolwiek dłuższy, bo czteroliterowy prefiks, co widać w powyższej poglądowej reprezentacji drzewa. Kiedy uwzględnimy jeszcze pozostałe słowa, wtedy całość oczywiście odpowiednio się rozrośnie, ale struktura pozostanie taka sama. Rozgałęzienia zawsze będą tam, gdzie słowa przestają mieć wspólny przedrostek i rozchodzą się w specyficzne dla siebie gałęzie. Głębokość drzewa zależy oczywiście od długości słów, zaś jego rozpiętość (maksymalna liczba potomków węzła) jest ograniczona liczbą znaków w alfabecie.

Gdy już mamy takie drzewo, co możemy z nim zrobić? No cóż, oczywiście to, do czego w informatyce używamy każdego drzewa, tj. do chodzenia po nim :) W przypadku autouzupełniania, podążamy tutaj za użytkownikiem wpisującym kolejne znaki i odpowiednio skręcamy w niżej położone węzły. Żeby przy okazji wygenerować jeszcze sensowną listę sugestii, musimy natomiast wybiec nieco wprzód i przejść część drzewa położoną niżej niż aktualna pozycja kursora w tekście. Szczegóły tego właśnie etapu są zapewne najważniejszą różnicą między rozwiązaniami o różnej skali. Dla listy kilkudziesięciu czy kilkuset komend (albo identyfikatorów w kodzie) jest możliwe zejście wszystkimi ścieżkami w dół drzewa i zaserwowanie użytkownikowi kompletnej listy możliwości. Dla zbiorów danych rzędu milionów konieczne są rzecz jasna dodatkowe heurystyki – częstości poszczególnych słów (czyli wagi krawędzi), ograniczenia ich długości, i tym podobne.

W praktyce z każdym kluczem w drzewie przeszukiwań – a więc także słowem w drzewie prefiksowym – są oczywiście związane jakieś dane. W moim przypadku były to funkcje realizujące czynności odpowiadające poszczególnym poleceniom, a więc np. taka, która pobiera wskazany artykuł z Wikipedii. Inaczej niż etykiety znakowe (przypisane krawędziom), te dane zapisane są w węzłach drzewa – ale zwykle nie wszystkich. Ich brak w danym węźle oznacza po prostu, że prowadząca do niego ścieżka nie reprezentuje pełnego słowa i w naszych poszukiwaniach musimy – za przeproszeniem – zejść głębiej :)
Z drugiej strony może się też tak zdarzyć, że odnajdziemy kompletne słowo przed zejściem do liścia drzewa. Będzie tak wtedy, gdy w naszym zbiorze jakiś wyraz jest przedrostkiem innego. Przypadek taki występuje zresztą w naszym przykładzie, w słowach karta i kartacz.

Tym stwierdzeniem możemy chyba zakończyć to krótkie wprowadzenie do drzewek prefiksowych i ich wykorzystania. Implementację takiej struktury starym podręcznikowym zwyczajem pozostawiam oczywiście jako ćwiczenie dla czytelnika ;]

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•