La mise en œuvre d'une Patricia Trie pour être utilisé comme un dictionnaire
-
18-09-2019 - |
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?
La solution
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.
Autres conseils
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:])