Поиск проблемы через Trie - PullRequest
Новая
       13

Поиск проблемы через Trie

0 голосов
/ 01 мая 2018

Я написал код, который реализует структуру данных Trie, где он занимает список строк и их количество. 

lst = [['james',9],['chloe',20],['chlara',30]]

Строки - это имена, а целочисленное значение, за которым следует число, - это число. Как только дерево построено, оно предлагает пользователю ввести префикс, 

userinput = ch

При этом код вернет строку chlara, так как она имеет большее число по сравнению с chloe, которая также имеет префикс ch. Мне удалось построить Trie, но у меня возникли трудности с функцией поиска. 

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.end = False
        self.frequency = 0
        self.goindex = 0
        self.index = 0

class Trie:
    def __init__(self):
        self.root = Node()

    def ord_char(self,key):
        ord_rep = ord(key) - ord('a')
        return ord_rep

    def add_word(self,lst):
        word = lst[0]    #word
        freq = lst[1]    #frequency of string

        word_len = len(word)    

        current = self.root    #start from root node

        for i in range(word_len):
            position = self.ord_char(word[i])

            if current.children[position] is None:
                current.children[position] = Node()

            current = current.children[position]

            if current.frequency > freq:
                continue
            else:
                current.frequency = freq
            current.index = position

        current.end = True  #end of string


def main():
    trie = Trie()

    for i in list2:
        trie.add_word(i)
    user = input("Enter a prefix: ")
    print(trie.prefix_search(user))

if __name__ == "__main__":
    main()

Мне возвращается неполная строка 'chla', и я почти уверен, что это из-за того, что моя функция поиска неэффективна и работает неправильно.

обновлен

Проблема, с которой я сейчас сталкиваюсь, заключается в том, что если мой префикс «aberr», мне возвращается «aberration» вместо «aberr»

1 Ответ

0 голосов
/ 01 мая 2018

Вы никогда не проходите свой путь должным образом. У вас есть два вложенных цикла for, поэтому вы проходите только два дополнительных узла (символа) из вашего префикса.

Я предполагаю, что вы хотите вернуть один результат, даже если есть несколько строк с совпадающим суффиксом и соответствующим количеством.

Используйте цикл while и продолжайте следовать наибольшему значению count, пока не доберетесь до узла без дочерних элементов со значением, равным количеству текущего узла. Убедитесь, что вы end имеют значение True для этого узла, поскольку это указывает на ошибку в вашем коде добавления слов: 

def prefix_search(self, prefix):
    # traverse the prefix
    current = self.root
    for c in prefix:
        current = current.children[self.ord_char(c)]
        if current is None:
            return None  # None is a much better return value than -1

    while current is not None:
        for child in current.children:
            if child is None:
                continue
            if child.count == current.count:
                # found first child with same score, continue from here
                prefix += chr(child.index + 97)
                current = child
                break
        else:
            # no children with equal score, this is the longest match
            assert current.end, "Data structure inconsistent"
            return prefix

Демо-версия: 

>>> trie.prefix_search('ch')
'chlara'
>>> trie.prefix_search('j')
'james'

и некоторые из этих крайних случаев: 

>>> trie.add_word(('chlarissa', 9))  # longer word, lower count!
>>> trie.prefix_search('ch')
'chlara'
>>> trie.add_word(('janet', 6))  # same length and score as james, won't be found
>>> trie.prefix_search('j')
'james'

и если произошла ошибка в структуре данных; это намеренно устанавливает неправильный счет: 

>>> trie.root.children[9].children[0].count = 7  # 'ja', 7, so higher, but not an end node
>>> trie.prefix_search('j')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 59, in prefix_search
AssertionError: Data structure inconsistent
...