Skompresowane drzewo trie


Skompresowane drzewo trie w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Przykładowe skompresowane drzewo trie

Spis treści

Koncepcja | 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 kod

Poniższe operacje na skompresowanym drzewie trie przechowującym zbiór słów S {\displaystyle S} są wykonywane w czasie O ( max s i S | s i | ) {\displaystyle {\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 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 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 | edytuj kod

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

Zobacz też | edytuj kod

Na podstawie artykułu: "Skompresowane drzewo trie" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy