La mise en œuvre d'une Patricia Trie pour être utilisé comme un dictionnaire

Question

Je tente de mettre en œuvre une Patricia Trie avec les méthodes addWord(), isWord() et isPrefix() comme un moyen de stocker un grand dictionnaire de mots pour la récupération rapide (y compris la recherche de préfixe). Je l'ai lu sur les concepts, mais ils ne sont pas clarifiais dans une mise en œuvre. Je veux savoir (dans le code Java ou Python) comment mettre en œuvre la Trie, en particulier les nœuds (ou devrais-je mettre en œuvre récursive). J'ai vu une personne qui a mis en œuvre avec un ensemble de 26 nœuds enfants mis à null / Aucune. Y at-il une meilleure stratégie (comme le traitement des lettres que bits) et comment voulez-vous mettre en œuvre?

Answer 1

Quelqu'un d'autre a posé une question à propos de Patricia tente il y a un certain temps et je pensais à faire une implémentation de Python puis, mais cette fois j'ai décidé de donner réellement un coup de feu (Oui, cela est beaucoup trop loin, mais il semblait un peu agréable projet). Ce que j'ai fait est peut-être pas un pur Patricia mise en œuvre de Trie, mais j'aime mon chemin mieux. Autres Patricia tente (dans d'autres langues), utilisez simplement une liste pour les enfants et vérifier chaque enfant de voir qu'il ya un match, mais je pensais que cela était assez inefficace, donc j'utiliser des dictionnaires. Voici est essentiellement la façon dont je l'ai établi:

Je vais commencer au nœud racine. La racine est juste un dictionnaire. Le dictionnaire a des touches qui sont tous les caractères simples (les premières lettres des mots) conduisant à des branches. Les valeurs correspondant à chaque touche sont des listes où le premier élément est une chaîne qui donne le reste de la chaîne qui correspond à cette branche de la structure arborescente, et le deuxième élément est un dictionnaire qui conduit à d'autres branches de ce noeud. Ce dictionnaire a également des touches de caractères simples qui correspondent à la première lettre du reste du mot et le processus se poursuit sur la structure arborescente.

Une autre chose que je dois mentionner est que si un noeud donné a des branches, mais est un mot aussi dans la structure arborescente lui-même, alors que l'on désigne en ayant une touche '' dans le dictionnaire qui conduit à un nœud avec la liste ['',{}].

Voici un petit exemple qui montre comment les mots sont stockés (le nœud racine est la _d variable):

>>> 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', {}]}]}

Notez que dans le dernier cas, une « » clé a été ajouté au dictionnaire pour indiquer que « abc » est un mot en plus de « abcdef » et « abcabc ».

code source

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

Vous avez peut-être remarqué que, à la fin, je mis __getitem__ la méthode isWord. Cela signifie que

x['abc']

retournera si « abc » dans la structure arborescente ou non.

Je pense que peut-être que je devrais faire un module de ce et de le soumettre à PyPI, mais il faut plus de tests et au moins une méthode removeWord. Si vous trouvez des bugs me le faire savoir, mais il semble très bien fonctionner. En outre, si vous voyez des grandes améliorations de l'efficacité, je voudrais aussi entendre parler. Je l'ai envisagé de faire quelque chose d'avoir des dictionnaires vides en bas de chaque branche, mais je pars pour l'instant. Ces dictionnaires vides peuvent être remplacées par des données liées au mot d'étendre les utilisations de la mise en œuvre par exemple.

Quoi qu'il en soit, si vous ne l'aimez pas la façon dont je mis en œuvre, au moins peut-être cela vous donnera quelques idées sur la façon dont vous souhaitez mettre en œuvre votre propre version.

Answer 2

Voici une implémentation récursive en utilisant des méthodes plus pythonique:

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:])