Мне нужно добавить возможность перечислять суффиксы для реализации нашей функции автозаполнения. Для этого я реализовал функцию в объекте TrieNode, которая будет возвращать все полные суффиксы слов, которые существуют под ним в tr ie. Например, если наш Tr ie содержит слова ["fun", "function", "factory"] и мы запрашиваем суффиксы из узла f, мы ожидаем получить ["un", "unction", "actory"] обратно от node.get_suffixes() , Вот как я начинаю:
class TrieNode:
def __init__(self):
## Initialize this node in the Trie
self.word_end = False
self.children = dict()
def insert(self, char):
## Add a child node in this Trie
if not char in self.children:
self.children[char] = TrieNode()
def get_suffixes(self):
pass
Я протестировал функцию get_suffixes отдельно, и она, кажется, работает нормально.
result = []
def get_suffixes(node, suffix=""):
if not node.children == dict():
for key in node.children:
suffix += key
if node.children[key].word_end:
result.append(suffix)
get_suffixes(node.children[key], suffix)
suffix = suffix[:-1]
return result
Как я протестировал функцию:
# Create a mock trie for the test
node = TrieNode()
node.insert("A")
node.children["A"].word_end = True
node.children["A"].insert("t")
node.children["A"].children["t"].word_end = True
node.children["A"].insert("b")
node.children["A"].children["b"].insert("a")
node.children["A"].children["b"].children["a"].insert("c")
node.children["A"].children["b"].children["a"].children["c"].insert("a")
node.children["A"].children["b"].children["a"].children["c"].children["a"].word_end = True
node.children["A"].insert("d")
node.children["A"].children["d"].insert("d")
node.children["A"].children["d"].children["d"].word_end = True
node.children["A"].children["d"].insert("m")
node.children["A"].children["d"].children["m"].insert("i")
node.children["A"].children["d"].children["m"].children["i"].insert("n")
node.children["A"].children["d"].children["m"].children["i"].children["n"].word_end = True
result = []
def get_suffixes(node, suffix=""):
if not node.children == dict():
for key in node.children:
suffix += key
if node.children[key].word_end:
result.append(suffix)
get_suffixes(node.children[key], suffix)
suffix = suffix[:-1]
return result
get_suffixes(node.children["A"]) # Returns ['t', 'baca', 'dd', 'dmin'], as expected
Проблема возникла, когда я попытался переместить функцию get_suffixes в класс TrieNode. Здесь я не знаю, как мне следует решать глобальную переменную result. Он больше не должен быть глобальной переменной. Я пробовал две версии:
Версия I: сделать result атрибут класса
class TrieNode:
def __init__(self):
## Initialize this node in the Trie
self.word_end = False
self.children = dict()
self.result = []
def insert(self, char):
## Add a child node in this Trie
if not char in self.children:
self.children[char] = TrieNode()
def get_suffixes(self, suffix=""):
if not self.children == dict():
for key in self.children:
suffix += key
if self.children[key].word_end:
self.result.append(suffix)
self.children[key].get_suffixes(suffix)
suffix = suffix[:-1]
return self.result
node.children["A"].get_suffixes() # Returns ['t'], which is wrong
Версия II: сделать result параметром функции по умолчанию
class TrieNode:
def __init__(self):
## Initialize this node in the Trie
self.word_end = False
self.children = dict()
def insert(self, char):
## Add a child node in this Trie
if not char in self.children:
self.children[char] = TrieNode()
def suffixes(self, suffix="", result=[]):
if not self.children == dict():
for key in self.children:
suffix += key
if self.children[key].word_end:
result.append(suffix)
self.children[key].suffixes(suffix)
suffix = suffix[:-1]
return result
node.children["A"].suffixes() # Returns ['t', 'baca', 'dd', 'dmin']
node.children["A"].suffixes() # Returns ['t', 'baca', 'dd', 'dmin', 't', 'baca', 'dd', 'dmin']
Результат версии II неудивителен, потому что:
def append(number, number_list=[]):
number_list.append(number)
print(number_list)
return number_list
append(5) # expecting: [5], actual: [5]
append(7) # expecting: [7], actual: [5, 7]
append(2) # expecting: [2], actual: [5, 7, 2]
Я изучаю алгоритмы и структуру данных в Python. Меня попросили сделать это с помощью рекурсивной функции. Другие подходы, такие как Реализация Tr ie для поддержки автозаполнения в Python, - это не те ответы, которые я ожидаю, хотя они сами могут решить проблему. Мне очень любопытно, почему self.result не был должным образом изменен в Версии I, но работает должным образом, если он не находится в классе.