Die Implementierung eine Patricia Trie für die Verwendung als Wörterbuch

Question

Ich versuche, eine Patricia Trie mit den Methoden addWord(), isWord() und isPrefix() als Mittel zur Umsetzung ein großes Wörterbuch der Wörter für den schnellen Abruf (einschließlich Präfixsuche) zu speichern. Ich habe auf den Konzepten lesen, aber sie sind einfach nicht in eine Implementierung zu klären. Ich möchte wissen (in Java oder Python-Code), wie die Trie zu implementieren, insbesondere die Knoten (oder sollte ich es rekursiv implementieren). Ich sah eine Person, die es mit einer Reihe von 26 untergeordneten Knoten gesetzt implementiert auf null / Keine. Gibt es eine bessere Strategie (wie die Buchstaben als Bits Behandlung) und wie würden Sie es umsetzen?

Answer 1

Jemand fragte sonst eine Frage zu Patricia vor einiger Zeit versucht, und ich dachte daran, dann eine Python-Implementierung zu machen, aber dieses Mal habe ich beschlossen, es tatsächlich ein Schuss (Ja, auf diese Weise über Bord, aber es schien wie eine nette kleine Projekt). Was ich gemacht habe, ist vielleicht nicht eine reine Patricia Trie Umsetzung, aber Ich mag meine Art und Weise besser. Andere Patricia versucht (in anderen Sprachen) verwendet nur eine Liste für die Kinder und jedes Kind überprüfen, um zu sehen, dass es ein Spiel ist, aber ich dachte, das war ziemlich ineffizient, damit ich die Wörterbücher verwenden. Hier ist im Grunde, wie ich habe es ein:

Ich werde am Wurzelknoten starten. Die Wurzel ist nur ein Wörterbuch. Das Wörterbuch hat Tasten, die alle einzelnen Zeichen (die ersten Buchstaben der Worte) führen zu Zweigen. Die Werte mit jeder Taste entsprechen, sind Listen, in denen das erste Element eine Schnur ist, die den Rest der Zeichenfolge gibt, die mit diesem Zweig des Trie entspricht, und das zweite Element ist ein Wörterbuch zum weiteren zweigt von diesem Knoten führt. Dieses Wörterbuch auch einzelne Zeichentasten hat, das mit dem ersten Buchstaben des Restes des Wortes entspricht, und der Prozess geht weiter nach unten der Trie.

Eine andere Sache, die ich erwähnen sollte, ist, dass, wenn ein gegebener Knoten Zweige hat, sondern ist auch ein Wort in der Trie selbst, dann ist das, indem ein '' Schlüssel im Wörterbuch, das mit der Liste ['',{}] zu einem Knoten führt bezeichnet.

Hier ist ein kleines Beispiel, das zeigt, wie Wörter gespeichert sind (der Wurzelknoten ist die Variable _d):

>>> x = patricia()
>>> x.addWord('abcabc')
>>> x._d
{'a': ['bcabc', {}]}
>>> x.addWord('abcdef')
>>> x._d
{'a': ['bc', {'a': ['bc', {}], 'd': ['ef', {}]}]}
>>> x.addWord('abc')
{'a': ['bc', {'a': ['bc', {}], '': ['', {}], 'd': ['ef', {}]}]}

Beachten Sie, dass im letzten Fall ein ‚‘ Schlüssel wurde den Wörterbuch hinzugefügt, um anzuzeigen, dass ‚abc‘ ist ein Wort in einem Zusatz zu ‚abcdef‘ und ‚abcabc‘.

Source Code

class patricia():
    def __init__(self):
        self._data = {}

    def addWord(self, word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                if data:
                    data[word[i:i+1]] = [word[i+1:],{}]
                else:
                    if word[i:i+1] == '':
                        return
                    else:
                        if i != 0:
                            data[''] = ['',{}]
                        data[word[i:i+1]] = [word[i+1:],{}]
                return

            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            data = node[1]
                            data[''] = ['',{}]
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                ii = i
                j = 0
                while ii != len(word) and j != len(node[0]) and \
                      word[ii:ii+1] == node[0][j:j+1]:
                    ii += 1
                    j += 1
                tmpdata = {}
                tmpdata[node[0][j:j+1]] = [node[0][j+1:],node[1]]
                tmpdata[word[ii:ii+1]] = [word[ii+1:],{}]
                data[word[i-1:i]] = [node[0][:j],tmpdata]
                return

    def isWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            return False
                    return True
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                return False

    def isPrefix(self,word):
        data = self._data
        i = 0
        wordlen = len(word)
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0][:wordlen-i],i):
                if wordlen - i > len(node[0]):
                    i += len(node[0])
                    data = node[1]
                else:
                    return True
            else:
                return False

    def removeWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                print "Word is not in trie."
                return
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                            node[1].pop('')
                        except KeyError:
                            print "Word is not in trie."
                        return
                    data.pop(word[i-1:i])
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                print "Word is not in trie."
                return


    __getitem__ = isWord

Sie haben vielleicht bemerkt, dass ich am Ende __getitem__ zum isWord Verfahren eingestellt. Dies bedeutet, dass

x['abc']

kehrt ob 'abc' in der Trie oder nicht.

Ich denke, dass vielleicht sollte ich ein Modul aus dieser machen und legt ihn PyPI, aber es mehr testen muss und mindestens eine removeWord Methode. Wenn Sie irgendwelche Fehler finden lassen Sie mich wissen, aber es scheint ziemlich gut zu funktionieren. Auch wenn Sie keine großen Verbesserungen in Effizienz sehen würde ich auch über sie hören. Ich habe erwogen, etwas zu tun zu leeren Wörterbücher jede Filiale am Boden, aber ich bin es jetzt zu verlassen. Diese leeren Wörterbücher können mit Daten an das Wort gebunden ersetzt werden, um die Verwendungen der Umsetzung zum Beispiel zu erweitern.

Wie auch immer, wenn Sie den Weg nicht wie ich es umgesetzt, zumindest vielleicht wird dies Sie einige Ideen, wie Sie möchten Ihre eigene Version implementieren.

Answer 2

Hier ist eine rekursive Implementierung mehr pythonic Methoden:

def matching_prefix_index(word1, word2):
    max_len = min(len(word1),len(word2))
    for i in range(max_len):
        if word2[i] != word1[i]:
            return i
    return max_len

class PatriciaTrie(object):
    def __init__(self):
        self._storage = {}
        self._complete_prefix_flag = False

    def _find_storage_key(self, word):
        for key in self._storage:
            prefix_index = matching_prefix_index(key, word)
            if prefix_index > 0:
                return (key, prefix_index)
        return (None, None)

    def add(self, word):
        if word == '':
            self._complete_prefix_flag = True
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is not None:
            if prefix_index == len(key):
                return self._storage[key].add(word[len(key):])
            else:
                new_tree = PatriciaTrie()
                new_tree._storage[key[prefix_index:]] = self._storage.pop(key)
                self._storage[key[0:prefix_index]] = new_tree
                return new_tree.add(word[prefix_index:])
        else:
            self._storage[word] = PatriciaTrie()
            self._storage[word].add('')
            return True

    def remove(self, word):
        if word == '':
            self._complete_prefix_flag = False
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False

        subword = word[prefix_index:]
        subtrie = self._storage[key]
        if subtrie.remove(subword):
            if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0:
                self._storage.pop(key)
            return True
        else:
            return False

    def __contains__(self, word):
        if word == '':
            return self._complete_prefix_flag

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False
        else:
            return (word[prefix_index:] in self._storage[key])

    def has_prefix(self, word):
        if word == '':
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None:
            return False
        elif len(key) > len(word):
            return (prefix_index == len(word))
        elif len(key) != prefix_index:
            return False
        else:
            return self._storage[key].has_prefix(word[prefix_index:])