TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 215

WS08 221

Gegeben seien die 6 Daten A, ..., F durch die Schlüsselfolgen

A = 010010...,
B = 011101...,
C = 101100...,
D = 101011...,
E = 100110...,
F = 001010...

Konstruieren Sie den zugehörigen Trie, Patricia Trie und Digitalen Suchbaum.

Lösungsvorschlag

Trie

                           o
                        0 / \ 1
                     .---´   '---.
                    /             \
                   o               o
                0 / \ 1             \ 0
                 /   \               \
                o     o               o
             1 /   0 / \ 1         0 / \ 1
              o     o   o           o   o
           0 /   0 /    | 1      1 /  0 |\ 1
            o     o     o         o     o o
         1 /   1 /   0 /       1 /    1 |  \ 0
          o     o     o         o       o   o
       0 /   0 /    1 |      0 /      1 |    \ 0
        o     o       o       o         o     o
        F     A       B       E         D     C

Patricia Trie

Ich hab im Buch dazu nichts gefunden, deshalb aus der wikipedia: Der Patricia-Trie zeichnet sich im Gegensatz zum normalen Trie dadurch aus, dass die Daten komprimiert abgespeichert werden. Dazu werden Zeichen, bei denen keine Verzweigung im Baum entsteht, einfach übersprungen und die Anzahl der ausgelassenen Knoten vor dem nächsten auftretenden Zeichen gespeichert. Somit wird gewährleistet, dass ein Suchbegriff eindeutig zugeordnet werden kann.

oder von http://search.cpan.org/src/PLONKA/Net-Patricia-1.014/Patricia.pm: Der Patricia-Baum hat seine Bezeichnung von dem Akronym Practical Algorithm To Retrieve Information Coded In Alphanumeric. Sein Prinzip ist die Möglichkeit des "Überspringens" von Teilworten im Suchbaum. Das wird dadurch erreicht, daß Präfixinhalte in den Suchknoten selbst gespeichert werden.

                      o                                                     o                              
                     / \                                                   / \                          
               .----´   '----.                                       .----´   '----.                    
             0/               \10                                  0/               \1                 
             /                 \                                   /                 \                  
            o                   o                                 o                  [0] (präfix-inhalts-länge = 1..)                 
           / \                1/ \          oder so:(?)          / \                1/ \                
          /   \               /   \0110                         /   \               /   \0           
    01010/     \1            o     \                          0/     \1            o     \              
        /       \         100|\011  \                         /       \           1|\0    \             
       /         o           | \     \                       /         o           | \     \            
      /     0010/ \11101     |  \     \                     /        0/ \1         |  \     \       
     o         o   o         o   o     o                [1010]    [010] [101]    [00] [11]  [110]
     F         A   B         C   D     E                   o         o    o        o   o     o          
                                                           F         A    B        C   D     E  

imo, ist die angabe ein schlechtes beispiel für patricia-trie. weil eigentlich nur bei der "rechten" ableitung über 1 erkennbar ist wie sich der trie genau aufbaut. wobei ich nicht weiß ob die lösung so überhaupt stimmt..

Digitaler Suchbaum

Die Erklärungen von "Digitaler Suchbaum", die ich im Web finde, behaupten das ist nur der Überbegriff zu "Trie" und "Patricia Trie", dehalb weiß ich nicht was in der Angabe damit gemeint ist.

mfg, --W wallner

Nützliches

Erklärung von digitalen Suchbäumen