Akbar Fardi Ответов: 1

Как мне исправить эту проблему Python(имплементация структуры данных trie)?


class Node:
	def __init__(self,lable=None, data=None):
		self.lable = lable
		self.data = data
		self.children = dict()
	def addChild(self, key, data = None):
		if not isinstance(key, Node):
			self.children[key] = Node(key, data)
		else:
			self.children[key.lable] = key
			
	def __getitem__(self,key):
		return self.children[key]
		
class Trie:
	def __init__(self):
		self.head = Node()
		self.bottom = Node()
	def __getitem__(self,key):
		return self.head.children[key],self.bottom.children[key]
	def add(self, word, pair):
		current_node = self.head
		word_finished = True
		current_node_2 = self.bottom
		pair_finished = True
		
		for i in range(len(word)):
			if word[i] in current_node.children:
				current_node = current_node.children[word[i]]
			else:
				word_finished = False
				break
		if not word_finished:
			while i < len(word):
				current_node.addChild(word[i])
				current_node = current_node.children[word[i]]
				i+=1
				
		for j in range(len(pair)):
			if pair[j] in current_node_2.children:
				current_node_2 = current_node_2.children[word[j]]
			else:
				pair_finished = False
				break
		if not pair_finished:
			while j < len(pair):
				current_node_2.addChild(pair[j])
				current_node_2 = current_node_2.children[word[j]]
				j+=1
		
	def has_word(self, word):
		if word == '':
			return False
		if word ==None:
			raise ValueError('Trie.has_word require not null string')
		
		current_node = self.head
		exists = True
		for letter in word:
			if letter in current_node.children:
				current_node = current_node.children[letter]
			else:
				exists = False
				break
		if exists:
			if current_node.data == None:
				exists = False
		return exists
		
	def start_with_prefix(self,prefix):
		words = list()
		if prefix == None:
			raise ValueError('reqire not null prefix')
		top_node = self.head
		bot_node = self.bottom
		
		for letter in prefix:
			if letter in top_node.children:
				top_node = top_node.children[letter]
			else:
				return words
		if top_node == self.head:
			queue = [node for key, node in top_node.children.iteritems()]
		else:
			queue = [top_node]
		
		while queue:
			current_node = queue.pop()
			if current_node.data !=None:
				words.append(current_node.data)
			
			queue = [node for key, node in current_node.children.iteritems()]+queue
			
			
			
			
		return words
		
		
	def getData(self, word, pair):
		if not self.has_word(word):
			raise ValueError('{} not found in trie'.fromat(word))
		current_node = self.head
		for letter in word:
			current_node = current_node[letter]
			
		if not self.has_word(pair):
			raise ValueError('{} not found in trie'.format(pair))
		current_node_2 = self.bottom
		for letter in pair:
			current_node_2 = current_node_2[letter]
	
		return current_node.data,current_node_2.data
		
		
if __name__ == '__main__':
    """ Example use """
    trie = Trie()
    words = 'hello goodbye help gerald gold tea ted team to too tom stan standard money'
    for word in words.split():
        trie.add(word,word)
    print "'goodbye' in trie: ", trie.has_word('goodbye')
    print trie.start_with_prefix('g')
    print trie.start_with_prefix('to')


Что я уже пробовал:

пожалуйста, помогите мне исправить это.
ошибка у меня есть :


когда я хочу увидеть слова, которые я ввел с префиксом, там ничего не отображается.
например: я добавляю ("go", " move")
если я наберу, что хочу видеть все слова с префиксом "g", я должен увидеть go, move, но это не сработало.

Patrice T

И у вас есть план, чтобы объяснить, в чем проблема ?

Akbar Fardi

я не могу связать это слово с его парой

Patrice T

дайте подробную информацию, такую как сообщение об ошибке, позиция по ошибке.
Воспользуйся Улучшить вопрос чтобы обновить ваш вопрос.

Akbar Fardi

ладно

1 Ответов

Рейтинг:
0

Richard MacCutchan

Потому что Trie предполагается наследовать Node, но Python не знает этого, пока вы не скажете ему. Измените свой оператор класса на:

class Trie(Node):

Кроме того, в будущем при публикации сообщений об ошибках с номерами строк, пожалуйста, укажите в своем исходном коде, на какие строки ссылаются. Попытка сосчитать до 68 в приведенном выше коде чрезвычайно утомительна.