无法在 Python 中打印 Trie 中的节点

Question

我对下面的 trie 数据结构的实现有两个疑问。

疑问1：

我很难理解 trie 中的插入函数。这是插词功能：

def add(self, word):
    cur = self.head
    for ch in word:
        if ch not in cur:
            cur[ch] = {}
        cur = cur[ch]
    # * denotes the Trie has this word as item
    # if * doesn't exist, Trie doesn't have this word but as a path to longer word
    cur['*'] = True

为什么在if语句之后会启动一个空字典？

另外，cur = cur[ch]有什么意义？

请帮助我理解代码中 if 语句中的那些行。

疑问二：

我正在尝试打印 trie 中存在的所有节点，但它打印为一个对象，如 <__main__.Trie object at 0x7f655de1c9e8>。有人可以帮我打印 trie 的节点吗？

下面是代码。

class Trie:
    head = {}

    def add(self, word):
        cur = self.head
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        # * denotes the Trie has this word as item
        # if * doesn't exist, Trie doesn't have this word but as a path to longer word
        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
dictionary = Trie()
dictionary.add("hi")
dictionary.add("hello")
print((dictionary)) # <__main__.Trie object at 0x7f655de1c9e8>

Answer 1

1) if语句是检查给定字符在当前深度是否还没有自己的字典，然后创建一个空字典。其中cur = cur[ch]就是将cur的深度加1，试图找到放置word

的地方

2) 要显示Trie的内容，在Trie中添加__str__方法

例如：

def __str__(self):
    #code

Answer 2

疑问1

最初，您有一个普通的旧空字典，head = {}。你的第一个词是 "cat"。您创建了一个名为 cur 的对 head 的引用。这是必要的，因为如果我们不使用临时变量，我们将遍历结构并且将丢失对最外层头部的引用。对 cur 所做的修改将反映在 head 上。我们需要在空字典中添加一个 ch = "c" 键作为 "cat" 的第一个字母，但不幸的是，这个键不存在。所以我们创造它。 head/cur 现在看起来像：

head = {"c": {}}
cur = head

然后，cur = cur[ch] 行执行。 ch 是 "c"，所以这与 cur = cur["c"] 相同。 cur 刚刚向下移动了 trie 的一个级别，我们将 for 循环步进到下一个字符，即 "a"。我们回到相同的场景：cur = {} 并且我们需要添加 "a" 键，所以我们这样做：

head = {"c": {"a": {}}}
cur = head["c"]

cur = cur["a"] 运行并在下一次迭代中重复同样的事情：

head = {"c": {"a": {"t": {}}}}
cur = head["c"]["a"]

最后循环结束，我们设置标志字符"*"我们完成添加"cat"。我们的结果是：

head = {"c": {"a": {"t": {"*": True}}}}

现在，我们打电话给trie.add("cart")。我只显示更新：

head = {"c": {"a": {"t": {"*": True}}}}
cur = head

head = {"c": {"a": {"t": {"*": True}}}}
cur = head["c"]

head = {"c": {"a": {"t": {"*": True}}}}
cur = head["c"]["a"]

head = {
    "c": {
        "a": {
            "r": {},
            "t": {"*": True}                
        }
    }
}
cur = head["c"]["a"]["r"]

head = {
    "c": {
        "a": {
            "r": {
                "t": {}
            },
            "t": {"*": True}                 
        }
    }
}
cur = head["c"]["a"]["r"]["t"]

最后：

head = {
    "c": {
        "a": {
            "r": {
                "t": {"*": True}
            },
            "t": {"*": True}                 
        }
    }
}

我们创建了一个n-ary tree-like数据结构（因为有多个"roots"，它不完全是一棵树，而是通过添加一个虚拟根节点head 的内容作为其 children 它将是一棵合法的树）。

希望这是有道理的。接下来尝试添加 "car"，看看会发生什么。

疑问2

当您打印 object 时，print 会尝试调用 object 的魔法 __str__ 方法。如果它不存在，它会继承默认的 __str__，它只是打印 object 的内存位置。这对于快速比较 object 引用很有用，但是如果你想显示 object 的数据，你需要实现它。可能最简单的方法是将 head dict 转储到 string:

import json

class Trie:
    def __str__(self):
        return json.dumps(self.head, sort_keys=True, indent=4)

具有讽刺意味的是，如果您能够 pretty-print 特里树，通过将结构转储到循环中，疑问 1 会更容易解决。

其他备注

给Trie一个初始化器，这样head就不是所有实例共享的静态变量。

代码如

if '*' in cur:
    return True
else:
    return False

风格很差。只需 return '*' in cur.

cur['*'] = True 是一种脆弱的设计，会导致包含 "*" 个字符的单词出现错误。首选像 None 这样的键，它不可能是字符串中的单个字符。

清理

import json

class Trie:
    end_mark = None

    def __init__(self):
        self.head = {}

    def add(self, word):
        cur = self.head

        for ch in word:
            if not ch in cur:
                cur[ch] = {}

            cur = cur[ch]

        cur[Trie.end_mark] = True

    def __contains__(self, word):
        cur = self.head

        for ch in word:
            if ch not in cur:
                return False

            cur = cur[ch]

        return Trie.end_mark in cur

    def __str__(self):
        return json.dumps(self.head, sort_keys=True, indent=4)

if __name__ == "__main__":
    trie = Trie()
    trie.add("cat")
    trie.add("cart")
    print(trie)
    print("cat" in trie)
    print("car" in trie)

无法在 Python 中打印 Trie 中的节点

Unable to print nodes in a Trie in Python

python

dictionary

data-structures

trie

疑问1

疑问2

其他备注

清理