Trie Datastruktur

Ein Trie (Präfix-Baum) ist ein Baum, mit schnellem Zugriff auf Werten über einen Schlüssel, ähnlich der Funktionalität eines Python dictionary (assoziatives Array). Als Schlüssel (Keys) kommen dabei Zeichenketten (Strings) (oder Array-ähnliche Objekte) in Frage. Außerdem können über eine Präfix-Suche alle Schlüssel mit dem Präfix effizient erhalten werden.
Der Name Trie kommt von reTRIEval (Edwald Fredkin).

Aufbau eines Tries

In den Kanten des Tries ist die Information über den Zugriffschlüssel enthalten. Wobei in einer Kante jeweils ein Zeichen zugeordnet ist. Dabei ergibt sich der Key durch Lesen ((bzw. Zusammensetzen) der Kanten-Zeichen von der Wurzel aus:

caption Beispiel (aus Wikipedia: Trie):

Eine Python abstract base class für einen Trie kann folgendermaßen definiert sein:

In [12]:
import abc


class TrieI(object):
    
    __metaclass__ = abc.ABCMeta
    
    @abc.abstractmethod
    def insert(self, k, v):
        """
            Insert a key and a value into the Trie.           
        """
        return
    
    @abc.abstractmethod
    def has_key(self, k):
        """
            Check if the key was already inserted into the try. Should return a boolean value.
        """
        return
    
    @abc.abstractmethod
    def get_value(self, k):
        """
            Get the value for the key
            If the key is not present, return None.
        """
        return
    
    @abc.abstractmethod
    def start_with_prefix(self, prefix):
        """
            Give all keys (as list) with the given prefix.
            If there is no such a prefix in the trie, return empty list.
        """
        return
    
    # exercise:
    #@abc.abstractmethod
    #def delete(self, key):
        #"""
        #    Delete the Key-Value Pair from the Trie
        #"""
        #return
    
    

Hier wird eine Implementierung gezeigt. Der Standard-Typ für Keys ist String, Werte(Values) können dabei beliebige Objekte sein:

In [13]:
class TrieNode(TrieI):
    
    def __init__(self, k="", key_concatenation_func=None):
        """
            :type k: has to be the type of the key 
            :param k: empty string or list
            :type key_concatenation_func: function
            :param key_concatenation_func: operation for concatenation of the key-elements to reconstruct
                                              the key from it's elementes
        """
        self._children = {}
        self._value = None 
        self.k_init = k
        if key_concatenation_func is None:
            # standard keys are strings
            self.key_concatenation_func = lambda x,y:"".join([x, y])
        else:
            self.key_concatenation_func = key_concatenation_func
    
    # standard behaviour for the insertion of a value:
    def _update_value(self, v):
        self._value = v
        
    def insert(self, k, v):     
        if len(k) == 0: 
            self._update_value(v)
            return
        if k[0] not in self._children: 
           # type(self) get's the current type for calling the appropriate constructor in subclasses
           self._children[k[0]] = type(self)(self.k_init , key_concatenation_func=self.key_concatenation_func)
        self._children[k[0]].insert(k[1:], v)
            
    def has_key(self, k):
        if len(k) == 0:
            if self._value is not None:
                return True
            else:
                return False
        if k[0] not in self._children:
            return False
        return self._children[k[0]].has_key(k[1:])
    
    def get_value(self, k):
        if len(k) == 0 :
            return self._value
        if k[0] not in self._children:
            return None
        return self._children[k[0]].get_value(k[1:])
    
    def _subtree_keys(self, result, key):
        if self._value is not None:
            result.append(key)
        for k, v in self._children.iteritems():
            result = v._subtree_keys(result, self.key_concatenation_func(key, k))
        return result
    
    def start_with_prefix(self, prefix, key=None):
       if key==None:
            key = prefix
       if len(prefix) == 0: 
          return self._subtree_keys([], key)
       if prefix[0] not in self._children:
            return []               
       return self._children[prefix[0]].start_with_prefix(prefix[1:], key)

Übung: Implementieren Sie die Methode delete(self, k).

In [14]:
trie = TrieNode()
trie.insert('karl', 10)
trie.insert('karlchen', 13)
trie.insert('karlson', 3)
trie.insert('karlsons', 7)
trie.insert('something', 1)

assert trie.has_key('karlchen') is True
assert trie.get_value('karlchen') == 13
assert trie.has_key('nothing') is False
assert trie.get_value('nothing') == None

print trie.start_with_prefix('kar')
print trie.start_with_prefix('karls')
print trie.start_with_prefix('')
print trie.start_with_prefix('nothing')
['karl', 'karlchen', 'karlson', 'karlsons']
['karlson', 'karlsons']
['karl', 'karlchen', 'karlson', 'karlsons', 'something']
[]

Die Implementierung kann nicht nur mit String-Keys umgehen, sondern auch mir anderen Listen als Keys. Dem Konstruktor muss hierfür eine leeres Listen-Object und eine entsprechende key_concatenation_func übergeben werden.

In [15]:
def append_to_list(a, b):
    x = list(a)
    x.append(b)
    return x

ngram_trie = TrieNode(k=[], key_concatenation_func=append_to_list)

ngram_trie.insert(["ein","tag", "im"], 4) 
ngram_trie.insert(["ein","tag", "im", "mai"], 1) 

assert ngram_trie.get_value(["ein","tag", "im", "mai"]) == 1 
assert ngram_trie.has_key(["ein","tag", "im"]) is True
assert ngram_trie.has_key(["tag", "im", "mai"]) is False

print ngram_trie.start_with_prefix(['ein'])
[['ein', 'tag', 'im'], ['ein', 'tag', 'im', 'mai']]

Beispiel: Anwendung als Termlexikon

Um die Trie-Implementierung als Term-Lexikon zu verwenden, kann die _update_value-Methode überschrieben werden. In diesem Beispiel soll die Korpusfrequenz (cf) als Value gespeichert werden.

In [16]:
class TrieLexicon(TrieNode):
    
    #def __init__(self, k="", key_concatenation_func=None):
    #    super(TrieLexicon, self).__init__(k, key_concatenation_func)
    
    def _update_value(self, v):
        """
         overwrite default behaviour
        """
        if self._value == None:
            self._value = v
        else: 
            self._value += v    
In [17]:
from nltk.corpus import brown
brown_news_words = brown.words(categories='news')

lexicon = TrieLexicon()

for w in brown_news_words[0:3000] :
    # here we can do some normalization
    lexicon.insert(w, 1)
    
for k in lexicon.start_with_prefix("ad"):
    print k, ": ", lexicon.get_value(k) 
adamant :  1
adjustments :  1
adjournment :  2
administration :  2
administrators :  1
additional :  2
added :  3
advocacy :  1

Alternative Implementierung

Hier ist eine alternative Implementierung gezeigt, bei der ein verschachteltes dictionary den Trie aufbaut. Die Implementierung benutzt außerdem keine Rekursionen:

In [18]:
VALUE_MARKER = "<VALUE>"

class TrieDict(object):
    
    def __init__(self):
        self.root = {}
       
    def _find_node(self, k):
        node = self.root
        for i in k:
            if i not in node:
                return None
            node = node[i]
        return node
    
    def insert(self, k, v): 
        node = self.root
        for i in k:
            node = node.setdefault(i, {})
        node.setdefault(VALUE_MARKER, v)
        
    def has_key(self, k):
        if self._find_node(k) is None:
            return False
        return True
    
    def get_value(self, k):
        node = self._find_node(k)
        if node is None:
            return None
        return node.get(value_marker)
    
    
    def _add_nodes(self, node, key):
        r = []
        for k, v in node.iteritems():
            if k != VALUE_MARKER:
                r.append((v, "".join([key, k])))
        return r     
        
    def start_with_prefix(self, prefix):
        node = self._find_node(prefix)
        if node is None:
            return []
        result = []
        key = prefix
        nodes = []
        while True:
            if VALUE_MARKER in node:
                result.append(key)   
            nodes.extend(self._add_nodes(node, key))
            if len(nodes) == 0:
                break
            node, key = nodes.pop()
        return result        

Effiziente Implementierungen

Standard-Python Implementierungen sind für den Einsatz mit großen Datenmengen ungeeignet, da in Python kein effizienter Umgang mit dem Speicher erfolgt (siehe z.B. Python Memory Management). Hier ist C/C++ effizienter (eventuell auch mit Cython raw arrays?)

Ein Trie kann beispielsweise mit einem Double-Array implementiert werden, siehe "An Implementation of Double-Array Trie"

Für weiter effiziente Implementierungen siehe z.B.:

Die speichereffizienten C/C++ Implementierung können mit Python über Python Bindings/Wrapper (z.B. mit SWIG, ctype oder cython) genutzt werden. Siehe auch Fast Non-Standard Data Structures for Python.

Beispiele für C/C++ Implementierungen sind:

  • Cedar (hier ist auch ein Vergleich zu anderen Implementierungen dokumentiert.)
  • Marisa-Trie: Besonders Speichereffiziente Implementierung, allerdings ist ein Update des erzeugten (Patricia)-Trie (siehe unten) nicht möglich.

Patricia Trie

Ein Patricia Trie ist ein speichereffizienter Trie. Name ist ein Akronmy aus Practical Algorithm to Retrieve Information Coded in Alphanumeric. Wie aus der Graphik ersichtlich ist, müssen die Kanten nicht einem Key-Elemente (hier Chars) entsprechen. Kanten verweisen nur auf Nodes mit einem Value oder einem Verzweigungsknoten.

caption