Skompresowane drzewo trie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Skompresowane drzewo trie (również: drzewo Patricia, drzewo pozycyjne) – w informatyce struktura danych przechowująca zbiór ciągów.

Przykładowe skompresowane drzewo trie

Koncepcja[edytuj | edytuj kod]

Skompresowane drzewo trie jest wariantem drzewa trie, w którym krawędzie mogą być etykietowane ciągami znaków, a nie tylko pojedynczymi znakami. Kompresja drzewa trie polega na „ściągnięciu” nierozgałęzionych ścieżek i oznaczeniu nowych krawędzi słowami złożonymi z liter na pierwotnych krawędziach. W rezultacie każdy węzeł wewnętrzny ma co najmniej dwóch synów.

Skompresowane drzewo trie może przechowywać łańcuchy znaków, ciągi bitów stanowiące zapis liczb naturalnych lub adresów IP lub też ciągi dowolnych elementów z porządkiem leksykograficznym.

Operacje[edytuj | edytuj kod]

Poniższe operacje na skompresowanym drzewie trie przechowującym zbiór słów S są wykonywane w czasie \mathcal{O}\left(\max\limits_{s_i \in S} |s_i|\right):

  • wyszukiwanie – informuje czy dane słowo należy do zbioru. Realizowane jak w drzewie trie, ale przejście niektórych krawędzi może oznaczać dopasowanie wielu znaków.
  • wstawienie słowa – przeszukujemy drzewo, dopóki nie możemy zejść niżej. W tym momencie albo tworzymy nową krawędź z etykietą równą pozostałemu sufiksowi słowa, albo – jeżeli istnieje krawędź, która ma wspólny z tym sufiksem prefiks, rozbijamy tę krawędź na dwie krawędzie (z których pierwsza jest etykietowana tym wspólnym prefiksem, a druga pozostałą częścią pierwotnej etykiety), a następnie do nowego wierzchołka dołączamy krawędź z pozostałą częścią wstawianego słowa.
  • usuwanie słowa – usuwamy odpowiedni liść. Jeżeli jego ojciec ma tylko jednego syna, wycinamy go, łącząc etykiety sąsiadujących z nim krawędzi.
  • znajdowanie poprzednika i następnika danego słowa w porządku leksykograficznym.

Zastosowania[edytuj | edytuj kod]

Skompresowane drzewa trie znajdują zastosowanie w konstrukcji tablic asocjacyjnych z ciągami jako kluczami. Szczególne znaczenie mają w dziedzinie trasowania IP. Szczególne drzewa Patricia, drzewa sufiksowe, są stosowane w algorytmach tekstowych.

Historia[edytuj | edytuj kod]

Drzewa Patricia po raz pierwszy wprowadził Donald R. Morrison w 1968. Nazwa drzewa pochodzi od skrótu PATRICIA: Practical Algorithm To Retrieve Information Coded in Alphanumeric (Praktyczny algorytm wyszukiwania informacji zakodowanych w formie alfanumerycznej)[1].

Przypisy

  1. Informacje o publikacji Donalda R. Morrisona w archiwum ACM [1]

Zobacz też[edytuj | edytuj kod]