Кто-то еще задал вопрос о попытках Патриции некоторое время назад, и я подумал о том, чтобы сделать реализацию Python, но на этот раз я решил на самом деле попробовать (Да, это за бортом, но это выглядело довольно мило проект). То, что я сделал, возможно, не является чистой реализацией Patricia trie, но мне нравится мой путь лучше. Другие попытки Патрисии (на других языках) используют только список для детей и проверяют каждого ребенка на наличие совпадений, но я подумал, что это было довольно неэффективно, поэтому я использую словари. Вот как я это настроил:
Я начну с корневого узла. Корень это просто словарь. В словаре есть ключи, которые представляют собой все одиночные символы (первые буквы слов), ведущие к ветвям. Значения, соответствующие каждому ключу, представляют собой списки, в которых первый элемент представляет собой строку, в которой содержится остальная часть строки, которая соответствует этой ветви дерева, а второй элемент представляет собой словарь, ведущий к дальнейшим ветвям от этого узла. Этот словарь также имеет односимвольные клавиши, которые соответствуют первой букве остальной части слова, и процесс продолжается до конца.
Еще одна вещь, которую я должен упомянуть, это то, что если у данного узла есть ветви, но также есть слово в самом дереве, то это обозначается наличием ключа '' в словаре, который ведет к узлу со списком ['',{}].
Вот небольшой пример, который показывает, как хранятся слова (корневым узлом является переменная _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', {}]}]}
Обратите внимание, что в последнем случае в словарь был добавлен ключ для обозначения того, что abc является словом в дополнение к abcdef и abcabc.
Исходный код
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
Возможно, вы заметили, что в конце я установил __getitem__ для метода isWord. Это означает, что
x['abc']
вернется независимо от того, находится ли abc в дереве или нет.
Я думаю, что, возможно, я должен сделать из этого модуль и отправить его в PyPI, но он требует дополнительного тестирования и, по крайней мере, метода removeWord. Если вы обнаружите какие-либо ошибки, дайте мне знать, но, похоже, это работает довольно хорошо. Кроме того, если вы видите какие-либо значительные улучшения в эффективности, я также хотел бы услышать о них. Я подумал о том, чтобы сделать что-то с пустыми словарями внизу каждой ветви, но я оставляю это сейчас. Эти пустые словари могут быть заменены данными, связанными со словом, например, для расширения использования реализации.
В любом случае, если вам не нравится, как я это реализовал, по крайней мере, возможно, это даст вам некоторые идеи о том, как вы хотели бы реализовать свою собственную версию.