在 Python 3.x 中为 Boggle 游戏实现带有字典子元素的 Trie 字典

Question

import typing
from typing import Optional, Dict
from collections.abc import Iterator


class TrieNode:
    
    def __init__(self):
        self.children: Dict[str, TrieNode] = {}  # maps a child letter to its TrieNode class
        self.is_word = False  # whether or not this Node is a valid word ending
        self.counter = 0  # a counter indicating how many times a word is inserted


class TrieDictionary():

    def __init__(self):
        self.root: TrieNode = TrieNode()

    def load_dictionary(self, filename: str) -> None:
        # add every word to the trie, not just the words over some length.
        node = self.root
        with open(filename) as wordsfile:
            for line in wordsfile:
                word = line.strip().lower()  # Do something with word here
                for letter in word:
                    if letter not in node.children:
                        node.children[letter] = TrieNode()
                    node = node.children[letter]
                node.is_word = True
                node.counter += 1

    def contains(self, word: str) -> bool:
        node = self.root
        for letter in word:
            if letter not in node.children:
                return False
            node = node.children[letter]
        return node.is_word


# Define the file path for the dictionary file
WORDS_FILE = "words.txt"

# Read all words from the file and store them in a list
with open(WORDS_FILE) as file:
    words = [line.strip() for line in file]

# Test the contains() method for all words in the dictionary file
def test_contains_all_example():
    # Make dictionary
    game_dict = TrieDictionary()
    game_dict.load_dictionary(WORDS_FILE)

    # Check that the contains() method returns True for all the words
    for s in words:
        assert game_dict.contains(s)


# Run the test
test_contains_all_example()

我有一个包含单词 {aa,aah,aahed,aahing,aahs,aal,aalii,aaliis,aals} 的示例文件。问题是我在运行测试时遇到断言错误。我尝试调试以找出问题所在。我发现结果全是False。在调试 load_dictionary 方法时，我发现它在读取单词时为每个字母创建一个子项，而我认为如果它们存在，它不应该重复它们。例如，如果“aa”已经存在，则只需添加“h”即可添加单词“aah”。目前，它将在第一个“aa”之后显示“aa”。 这就是我的猜测，我真的不确定是哪种方法导致了问题！ 我感谢您帮助解决这个问题。

Answer 1

您的

load_dictionary

方法在错误的位置初始化

node

。每次想要添加新单词时都需要重新初始化它，但当前的代码只执行一次。在你的 Trie 中，第一个单词之后的每个单词都会添加到前一个单词的末尾。

要解决此问题，请将

node = self.root

线移至循环内：

def load_dictionary(self, filename: str) -> None:
    with open(filename) as wordsfile:
        for line in wordsfile:
            word = line.strip().lower()
            node = self.root                 # move this line here!!!!
            for letter in word:
                if letter not in node.children:
                    node.children[letter] = TrieNode()
                node = node.children[letter]
            node.is_word = True
            node.counter += 1