时间戳

首页 > 解决方案 > 嵌套的`defaultdict of defaultdict of defaultdict`，每个都有一个反向引用

python - 嵌套的`defaultdict of defaultdict of defaultdict`，每个都有一个反向引用

问题描述

使用tree = lambda: dedfaultdict(tree)，我可以替换以下代码：

from collections import defaultdict

END = '$'
words = ['hi', 'hello', 'hiya', 'hey']

root = {}
for word in words:
  node = root
  for ch in word:
    node = node.setdefault(ch, {}) # <---- Code that can be replaced
  node[END] = None

和：

from collections import defaultdict

END = '$'
words = ['hi', 'hello', 'hiya', 'hey']

tree = lambda: defaultdict(tree)
root = tree()
for word in words:
  node = root
  for ch in word:
    node = node[ch] # <------ Replaced code
  node[END] = None

我真正想要的是每个字典节点都有一个对其父字典节点的反向引用。我可以这样做：

from collections import defaultdict

BACKREF, END = 'BACKREF', '$'
words = ['hi', 'hello', 'hiya', 'hey']

root = {}
for word in words:
  node = root
  for ch in word:
    node = node.setdefault(ch, {BACKREF: node}) # <---- Code I want to replace
  node[END] = None

（证明这有效：链接）

所以，鉴于我能够用来tree = lambda: defaultdict(tree)替换

有没有办法我可以使用修改后的版本tree = lambda: default(tree)来替换

我试过类似的东西：

def tree():
  _ = defaultdict(tree)
  _[BACKREF] = ?
  return _
root = tree()
h = root['h']

但这需要tree知道哪个字典调用了对tree. 例如 in h = root['h']，root['h']调用对treebecause his not yet in的调用root。tree必须知道它是通过调用调用的root['h']，以便它可以执行h[BACKREF] = root. 有没有解决的办法？即使可以做到，这也是一个坏主意吗？

我知道反向引用在技术上意味着 trie 将有循环（而不是真正的树），但是我计划遍历 trie 的方式，这不会是一个问题。我想要反向引用的原因是，如果我想从 trie 中删除一个单词，它会很有用。例如，假设我有以下尝试：

特里

并且我在root['h']['e']['l']['l']['o']并且想'hello'从特里删除。我可以通过从root['h']['e']['l']['l']['o']toroot['h']['e']['l']['l']到root['h']['e']['l']to回溯 trie 来做到这一点root['h']['e']（我在这里停下来是因为len(set(root['h']['e'].keys()) - {BACKREF}) > 1. 然后我可以简单地做del root['h']['e']['l']，我将切断'llo$'从'he'trie 仍然具有的意义'hey'。虽然有替代方案，但回溯 trie 将是反向引用非常容易。

上下文开启tree = lambda: defaultdict(tree)

使用：

from collections import defaultdict

tree = lambda: defaultdict(tree)
root = tree()

可以创建任意嵌套dict的 s。例如之后：

root['h']['i']
root['h']['e']['l']['l']['o']
root['h']['i']['y']['a']
root['h']['e']['y']

root看起来像：

{'h': {'i': {'y': {'a': {}}}, 'e': {'y': {}, 'l': {'l': {'o': {}}}}}}

这表示一棵看起来像这样的树： 使用https://www.cs.usfca.edu/~galles/visualization/Trie.html进行可视化特里

标签： pythontriedefaultdictrecursive-datastructures

解决方案

您尝试实现的行为似乎更容易编写为类而不是函数。

from collections import defaultdict

class Tree(defaultdict):
    def __init__(self, backref=None):
        super().__init__(self.make_child)
        self.backref = backref
    def make_child(self):
        return Tree(backref=self)

用法：

>>> root = Tree()
>>> root['h'].backref is root
True
>>> root['h']['e'].backref is root['h']
True

推荐阅读