同一类的 Python `collections.defaultdict`

Question

我尝试使用 Trie 数据结构来解决一些编码问题。对于 trie 中的每个节点，您通常会放置其子节点的引用列表。因此，如果查找中不存在某些子节点，我考虑使用 defaultdict 创建默认的空 trie 节点。但是，我不知道如何使用 defaultdict 来引用包含它的类。

我尝试了两种方法，都失败了。以下是我尝试过的。

from dataclasses import dataclass
from collections import defaultdict

@dataclass   
class TrieNode():
    is_word = False
    children = defaultdict("TrieNode")

上面的代码产生

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 4, in TrieNode
TypeError: first argument must be callable or None

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 4, in TrieNode
TypeError: first argument must be callable or None

上面将产生

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 4, in TrieNode
NameError: name 'TrieNode' is not defined

我的问题是如何defaultdict优雅地实现这一点。预先非常感谢您。

Answer 1

您的第二种方法children = defaultdict(TrieNode)更接近正确，因为defaultdict需要构造函数 forTrieNode才能用TrieNodes 填充它 - 另一种方法在需要可调用的地方传递一个字符串。您的问题是由于您在TrieNode类创建完成之前访问名称而导致的NameError。要解决此问题，您可以使用children = defaultdict(lambda: TrieNode()). 这样，TrieNode只有在调用 lambda 函数时才会查找该名称。

然而，对于 trie 来说，您希望每个节点都有自己的子节点字典，并且通过这种方法，修改一个节点的子字典将会修改所有节点的子字典，因为它们的所有字典都是同一个对象。我建议您dataclass.field为每个创建一个新字典TrieNode，如下所示：

from dataclasses import dataclass, field
from collections import defaultdict

@dataclass   
class TrieNode():
    is_word = False
    children : 'TrieNode' = field(default_factory=lambda: defaultdict(TrieNode))