Как создать TRIE в Python
Я новичок в Python и пытаюсь учиться и развиваться. Меня интересуют TRIE и DAWG, и я много об этом читал, но не понимаю, как должен выглядеть выходной файл TRIE или DAWG.
- Должен ли TRIE быть объектом вложенных словарей? Где каждая буква делится на буквы и так далее?
- Будет ли поиск, выполняемый по такому словарю, быстрым, если в нем будет 100 или 500 тысяч записей?
- Как реализовать блоки слов, состоящие из более чем одного слова, разделенных - или пробелом?
- Как связать префикс или суффикс слова с другой частью в структуре? [для DAWG]
Я хочу понять лучшую структуру вывода, чтобы понять, как ее создать и использовать.
Я также был бы признателен за вывод DAWG вместе с TRIE.
Я не хочу видеть графические изображения с пузырьками, связанными друг с другом, я видел их много во время чтения.
Я хотел бы знать выходной объект, как только набор слов превращается в TRIE или DAWG.
Спасибо.
16 ответов
Раскрутите, по сути, правильно, что существует много разных способов реализации дерева; а для большого масштабируемого файла вложенные словари могут стать громоздкими или, по крайней мере, неэффективными в использовании. Но так как вы только начинаете, я думаю, что это самый простой подход; Вы могли бы написать простой trie всего за несколько строк. Во-первых, функция для построения дерева:
>>> _end = '_end_'
>>>
>>> def make_trie(*words):
... root = dict()
... for word in words:
... current_dict = root
... for letter in word:
... current_dict = current_dict.setdefault(letter, {})
... current_dict[_end] = _end
... return root
...
>>> make_trie('foo', 'bar', 'baz', 'barz')
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}},
'z': {'_end_': '_end_'}}},
'f': {'o': {'o': {'_end_': '_end_'}}}}
Если вы не знакомы с setdefault, он просто ищет ключ в словаре (здесь, letter или же _end). Если ключ присутствует, он возвращает соответствующее значение; если нет, он назначает значение по умолчанию для этого ключа и возвращает значение ({} или же _end). (Это похоже на версию get это также обновляет словарь.)
Далее, функция для проверки, есть ли слово в три. Это может быть более кратким, но я оставляю это подробным, чтобы логика была ясна:
>>> def in_trie(trie, word):
... current_dict = trie
... for letter in word:
... if letter in current_dict:
... current_dict = current_dict[letter]
... else:
... return False
... else:
... if _end in current_dict:
... return True
... else:
... return False
...
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba')
False
Я оставлю вставку и удаление для вас в качестве упражнения.
Конечно, предложение Размотать не будет намного сложнее. Там может быть небольшой недостаток скорости в том, что для поиска правильного подузла потребуется линейный поиск. Но поиск будет ограничен количеством возможных символов - 27, если мы включим _end, Кроме того, ничего нельзя получить, создав огромный список узлов и обращаясь к ним по индексу, как он предлагает; с тем же успехом вы можете просто вкладывать списки.
Наконец, я добавлю, что создание DAWG было бы немного сложнее, потому что вы должны обнаружить ситуации, в которых ваше текущее слово разделяет суффикс с другим словом в структуре. На самом деле, это может быть довольно сложно, в зависимости от того, как вы хотите структурировать DAWG! Возможно, вам придется узнать кое-что о расстоянии Левенштейна, чтобы сделать это правильно.
Вот список пакетов Python, которые реализуют Trie:
- marisa-trie - реализация, основанная на C++.
- Python-Trie - простая реализация на чистом Python.
- PyTrie - более продвинутая реализация чистого Python.
Посмотри на это:
https://github.com/kmike/marisa-trie
Статически эффективные структуры памяти Trie для Python (2.x и 3.x).
Строковые данные в формате MARISA могут занимать до 50-100 раз меньше памяти, чем в стандартном языке Python; сырая скорость поиска сопоставима; Trie также предоставляет быстрые расширенные методы, такие как поиск по префиксу.
Основано на библиотеке мариса-три C++.
Вот сообщение в блоге компании, успешно использующей Marisa Trie:
https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/
В Repustate большая часть наших моделей данных, которые мы используем при анализе текста, может быть представлена в виде простых пар ключ-значение или словарей в языке Python. В нашем конкретном случае наши словари имеют большой объем, несколько сотен МБ каждый, и к ним нужно постоянно обращаться. Фактически для данного HTTP-запроса могут быть доступны 4 или 5 моделей, каждая из которых выполняет 20-30 поисков. Таким образом, проблема, с которой мы сталкиваемся, заключается в том, как сделать все как можно быстрее для клиента и максимально облегчить работу сервера.
...
Я нашел этот пакет, пытается Мариса, который является оберткой Python для реализации C++ для языка Мариса. "Marisa" является аббревиатурой от алгоритма согласования с рекурсивно реализованным StorAge. Что хорошо в марисе, так это то, что механизм хранения действительно сокращает объем памяти, который вам нужен. Автор плагина Python заявляет об уменьшении размера в 50-100 раз - наш опыт аналогичен.
Что хорошо в пакете marisa trie, так это то, что базовая структура trie может быть записана на диск, а затем считана через отображенный в памяти объект. С отображением памяти Мариса Три все наши требования теперь выполнены. Использование памяти нашим сервером резко сократилось, примерно на 40%, и наша производительность не изменилась по сравнению с тем, когда мы использовали реализацию словаря Python.
Есть также пара реализаций чистого Python, хотя, если вы не находитесь на ограниченной платформе, вы бы хотели использовать выше поддерживаемую реализацию C++ для лучшей производительности:
Модифицировано из senderleметод (выше). Я обнаружил, что Питон defaultdict идеально подходит для создания дерева три или префикса.
from collections import defaultdict
class Trie:
"""
Implement a trie with insert, search, and startsWith methods.
"""
def __init__(self):
self.root = defaultdict()
# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
current = self.root
for letter in word:
current = current.setdefault(letter, {})
current.setdefault("_end")
# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
current = self.root
for letter in word:
if letter not in current:
return False
current = current[letter]
if "_end" in current:
return True
return False
# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
current = self.root
for letter in prefix:
if letter not in current:
return False
current = current[letter]
return True
# Now test the class
test = Trie()
test.insert('helloworld')
test.insert('ilikeapple')
test.insert('helloz')
print test.search('hello')
print test.startsWith('hello')
print test.search('ilikeapple')
Там нет "должен"; тебе решать. Различные реализации будут иметь разные характеристики производительности, потребовать различного количества времени для реализации, понимания и получения правильных результатов. Это типично для разработки программного обеспечения в целом, на мой взгляд.
Я, вероятно, сначала попытался бы создать глобальный список всех созданных узлов и представить дочерние указатели в каждом узле в виде списка индексов в глобальном списке. Имея словарь, просто чтобы показать, что связывание ребенка кажется мне слишком тяжелым.
Использование defaultdict и функции уменьшения.
Создать Trie
from functools import reduce
from collections import defaultdict
T = lambda : defaultdict(T)
trie = T()
reduce(dict.__getitem__,'how',trie)['isEnd'] = True
Три:
defaultdict(<function __main__.<lambda>()>,
{'h': defaultdict(<function __main__.<lambda>()>,
{'o': defaultdict(<function __main__.<lambda>()>,
{'w': defaultdict(<function __main__.<lambda>()>,
{'isEnd': True})})})})
Искать в Трие:
curr = trie
for w in 'how':
if w in curr:
curr = curr[w]
else:
print("Not Found")
break
if curr['isEnd']:
print('Found')
Вот полный код с использованием класса TrieNode. Также реализован метод auto_complete для возврата совпадающих слов с префиксом.
Поскольку мы используем словарь для хранения дочерних элементов, нет необходимости преобразовывать char в целое число и наоборот, и не нужно заранее выделять память массива.
class TrieNode:
def __init__(self):
#Dict: Key = letter, Item = TrieNode
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def build_trie(self,words):
for word in words:
self.insert(word)
def insert(self,word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.end = True
def search(self, word):
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
return False
return node.end
def _walk_trie(self, node, word, word_list):
if node.children:
for char in node.children:
word_new = word + char
if node.children[char].end:
# if node.end:
word_list.append( word_new)
# word_list.append( word)
self._walk_trie(node.children[char], word_new , word_list)
def auto_complete(self, partial_word):
node = self.root
word_list = [ ]
#find the node for last char of word
for char in partial_word:
if char in node.children:
node = node.children[char]
else:
# partial_word not found return
return word_list
if node.end:
word_list.append(partial_word)
# word_list will be created in this method for suggestions that start with partial_word
self._walk_trie(node, partial_word, word_list)
return word_list
создать Trie
t = Trie()
words = ['hi', 'hieght', 'rat', 'ram', 'rattle', 'hill']
t.build_trie(words)
Искать слово
words = ['hi', 'hello']
for word in words:
print(word, t.search(word))
hi True
hel False
поиск слов по префиксу
partial_word = 'ra'
t.auto_complete(partial_word)
['rat', 'rattle', 'ram']
from collections import defaultdict
Определить три:
_trie = lambda: defaultdict(_trie)
Создать Trie:
trie = _trie()
for s in ["cat", "bat", "rat", "cam"]:
curr = trie
for c in s:
curr = curr[c]
curr.setdefault("_end")
Уважать:
def word_exist(trie, word):
curr = trie
for w in word:
if w not in curr:
return False
curr = curr[w]
return '_end' in curr
Тестовое задание:
print(word_exist(trie, 'cam'))
Если вы хотите, чтобы TRIE был реализован как класс Python, вот что я написал после прочтения о них:
class Trie:
def __init__(self):
self.__final = False
self.__nodes = {}
def __repr__(self):
return 'Trie<len={}, final={}>'.format(len(self), self.__final)
def __getstate__(self):
return self.__final, self.__nodes
def __setstate__(self, state):
self.__final, self.__nodes = state
def __len__(self):
return len(self.__nodes)
def __bool__(self):
return self.__final
def __contains__(self, array):
try:
return self[array]
except KeyError:
return False
def __iter__(self):
yield self
for node in self.__nodes.values():
yield from node
def __getitem__(self, array):
return self.__get(array, False)
def create(self, array):
self.__get(array, True).__final = True
def read(self):
yield from self.__read([])
def update(self, array):
self[array].__final = True
def delete(self, array):
self[array].__final = False
def prune(self):
for key, value in tuple(self.__nodes.items()):
if not value.prune():
del self.__nodes[key]
if not len(self):
self.delete([])
return self
def __get(self, array, create):
if array:
head, *tail = array
if create and head not in self.__nodes:
self.__nodes[head] = Trie()
return self.__nodes[head].__get(tail, create)
return self
def __read(self, name):
if self.__final:
yield name
for key, value in self.__nodes.items():
yield from value.__read(name + [key])
Эта версия использует рекурсию
import pprint
from collections import deque
pp = pprint.PrettyPrinter(indent=4)
inp = raw_input("Enter a sentence to show as trie\n")
words = inp.split(" ")
trie = {}
def trie_recursion(trie_ds, word):
try:
letter = word.popleft()
out = trie_recursion(trie_ds.get(letter, {}), word)
except IndexError:
# End of the word
return {}
# Dont update if letter already present
if not trie_ds.has_key(letter):
trie_ds[letter] = out
return trie_ds
for word in words:
# Go through each word
trie = trie_recursion(trie, deque(word))
pprint.pprint(trie)
Выход:
Coool <algos> python trie.py
Enter a sentence to show as trie
foo bar baz fun
{
'b': {
'a': {
'r': {},
'z': {}
}
},
'f': {
'o': {
'o': {}
},
'u': {
'n': {}
}
}
}
Это очень похоже на предыдущий ответ, но его проще читать:
def make_trie(words):
trie = {}
for word in words:
head = trie
for char in word:
if char not in head:
head[char] = {}
head = head[char]
head["_end_"] = "_end_"
return trie
Класс Python для Trie
Структуру данных Trie можно использовать для хранения данных в O(L) где L - длина строки, поэтому для вставки N строк временная сложность будет O(NL) строку можно искать в O(L) только то же самое касается удаления.
Можно клонировать с https://github.com/Parikshit22/pytrie.git
class Node:
def __init__(self):
self.children = [None]*26
self.isend = False
class trie:
def __init__(self,):
self.__root = Node()
def __len__(self,):
return len(self.search_byprefix(''))
def __str__(self):
ll = self.search_byprefix('')
string = ''
for i in ll:
string+=i
string+='\n'
return string
def chartoint(self,character):
return ord(character)-ord('a')
def remove(self,string):
ptr = self.__root
length = len(string)
for idx in range(length):
i = self.chartoint(string[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
raise ValueError("Keyword doesn't exist in trie")
if ptr.isend is not True:
raise ValueError("Keyword doesn't exist in trie")
ptr.isend = False
return
def insert(self,string):
ptr = self.__root
length = len(string)
for idx in range(length):
i = self.chartoint(string[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
ptr.children[i] = Node()
ptr = ptr.children[i]
ptr.isend = True
def search(self,string):
ptr = self.__root
length = len(string)
for idx in range(length):
i = self.chartoint(string[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
return False
if ptr.isend is not True:
return False
return True
def __getall(self,ptr,key,key_list):
if ptr is None:
key_list.append(key)
return
if ptr.isend==True:
key_list.append(key)
for i in range(26):
if ptr.children[i] is not None:
self.__getall(ptr.children[i],key+chr(ord('a')+i),key_list)
def search_byprefix(self,key):
ptr = self.__root
key_list = []
length = len(key)
for idx in range(length):
i = self.chartoint(key[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
return None
self.__getall(ptr,key,key_list)
return key_list
t = trie()
t.insert("shubham")
t.insert("shubhi")
t.insert("minhaj")
t.insert("parikshit")
t.insert("pari")
t.insert("shubh")
t.insert("minakshi")
print(t.search("minhaj"))
print(t.search("shubhk"))
print(t.search_byprefix('m'))
print(len(t))
print(t.remove("minhaj"))
print(t)
Код Oputpt
Правда
Ложь
['Minakshi', 'Минхадж']
7
Minakshi
minhajsir
Pari
Парикшит
Shubh
Shubham
shubhi
class TrieNode:
def __init__(self):
self.keys = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str, node=None) -> None:
if node == None:
node = self.root
# insertion is a recursive operation
# this is base case to exit the recursion
if len(word) == 0:
node.end = True
return
# if this key does not exist create a new node
elif word[0] not in node.keys:
node.keys[word[0]] = TrieNode()
self.insert(word[1:], node.keys[word[0]])
# that means key exists
else:
self.insert(word[1:], node.keys[word[0]])
def search(self, word: str, node=None) -> bool:
if node == None:
node = self.root
# this is positive base case to exit the recursion
if len(word) == 0 and node.end == True:
return True
elif len(word) == 0:
return False
elif word[0] not in node.keys:
return False
else:
return self.search(word[1:], node.keys[word[0]])
def startsWith(self, prefix: str, node=None) -> bool:
if node == None:
node = self.root
if len(prefix) == 0:
return True
elif prefix[0] not in node.keys:
return False
else:
return self.startsWith(prefix[1:], node.keys[prefix[0]])
class Trie:
head = {}
def add(self,word):
cur = self.head
for ch in word:
if ch not in cur:
cur[ch] = {}
cur = cur[ch]
cur['*'] = True
def search(self,word):
cur = self.head
for ch in word:
if ch not in cur:
return False
cur = cur[ch]
if '*' in cur:
return True
else:
return False
def printf(self):
print (self.head)
dictionary = Trie()
dictionary.add("hi")
#dictionary.add("hello")
#dictionary.add("eye")
#dictionary.add("hey")
print(dictionary.search("hi"))
print(dictionary.search("hello"))
print(dictionary.search("hel"))
print(dictionary.search("he"))
dictionary.printf()
Вне
True
False
False
False
{'h': {'i': {'*': True}}}
С поиском по префиксу
Вот , слегка измененный, чтобы ответ @senderleразрешитьпоиск по префиксу (а не только поиск по целому слову):
_end = '_end_'
def make_trie(words):
root = dict()
for word in words:
current_dict = root
for letter in word:
current_dict = current_dict.setdefault(letter, {})
current_dict[_end] = _end
return root
def in_trie(trie, word):
current_dict = trie
for letter in word:
if _end in current_dict:
return True
if letter not in current_dict:
return False
current_dict = current_dict[letter]
t = make_trie(['hello', 'hi', 'foo', 'bar'])
print(in_trie(t, 'hello world'))
# True
В ответ на @basj
Следующий код захватит\b(конец слова) буквы.
_end = '_end_'
def make_trie(words):
root = dict()
for word in words:
current_dict = root
for letter in word:
current_dict = current_dict.setdefault(letter, {})
current_dict[_end] = _end
return root
def in_trie(trie, word):
current_dict = trie
for letter in word:
if letter not in current_dict: # Adjusted the
return False # order of letter
if _end in current_dict[letter]: # checks to capture
return True # the last letter.
current_dict = current_dict[letter]
t = make_trie(['hello', 'hi', 'foo', 'bar'])
>>> print(in_trie(t, 'hi'))
True
>>> print(in_trie(t, 'hola'))
False
>>> print(in_trie(t, 'hello friend'))
True
>>> print(in_trie(t, 'hel'))
None