嵌套的“defaultdict的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)替换
node = node.setdefault(ch, {})- 用
node = node[ch]
我是否可以使用修改后的tree = lambda: default(tree)版本来替换
node = node.setdefault(ch, {BACKREF: node})- 使用一些更简单的东西，比如
node = node[ch]？
我试过这样的方法：
def tree():
_ = defaultdict(tree)
_[BACKREF] = ?
return _
root = tree()
h = root['h']但这需要tree知道哪个字典调用了tree。例如，在h = root['h']中，root['h']调用tree，因为h还没有在root中。tree必须知道它是通过调用root['h']调用的，这样它才能执行h[BACKREF] = root。有办法绕道吗？这是一个坏主意，即使它可以做到？
我知道反向引用在技术上意味着trie将有周期(而不是真正的树)，但是我计划遍历trie的方式，这将不是一个问题。我想要反向引用的原因是，如果我想从trie中删除一个单词，它将是有用的。例如，假设我有以下trie：
我在root['h']['e']['l']['l']['o']，想从trie中删除'hello'。我可以通过回溯从root['h']['e']['l']['l']['o']到root['h']['e']['l']['l']到root['h']['e']['l']到root['h']['e']的trie来实现这一点(我在这里停止，因为len(set(root['h']['e'].keys()) - {BACKREF}) > 1 )。然后，我可以简单地做del root['h']['e']['l']，我将从'he'中分离出'llo$'，这意味着trie仍然有'hey'。尽管有其他的选择，但是回溯trie将非常容易使用反向引用。
tree = lambda: defaultdict(tree)上的上下文
使用：
from collections import defaultdict
tree = lambda: defaultdict(tree)
root = tree()可以创建任意嵌套的dict。例如，在以下之后：
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/%7Egalles/visualization/Trie.html可视化
回答 2
Stack Overflow用户
发布于 2021-10-13 02:29:23
解决方案1
将相同的{BACKREF: node}提供给defaultdict
from collections import defaultdict
BACKREF, END = 'BACKREF', '$'
words = ['hi', 'hello', 'hiya', 'hey']
tree = lambda: defaultdict(tree, {BACKREF: node})
node = None
root = tree()
for word in words:
node = root
for ch in word:
node = node[ch]
node[END] = Noneroot节点有一个backref None，如果麻烦的话可以删除。
解决方案2
如果该代码是创建树节点的唯一代码，那么上面的代码工作得很好(从我自己构建树的时间来判断，这在我看来是可能的)。否则，需要确保node指向正确的父节点。如果这是一个问题，下面是一个带有dict (而不是defaultdict)子类的替代方法，该子类实现__missing__，以便在需要时自动创建带有回退的子级：
BACKREF, END = 'BACKREF', '$'
words = ['hi', 'hello', 'hiya', 'hey']
class Tree(dict):
def __missing__(self, key):
child = self[key] = Tree({BACKREF: self})
return child
root = Tree()
for word in words:
node = root
for ch in word:
node = node[ch]
node[END] = None也不会给根回退，作为一个dict，它的字符串表示要比defaultdict少得多，因此它的可读性更强：
>>> import pprint
>>> pprint.pp(root)
{'h': {'BACKREF': <Recursion on Tree with id=2494556270320>,
'i': {'BACKREF': <Recursion on Tree with id=2494556270400>,
'$': None,
'y': {'BACKREF': <Recursion on Tree with id=2494556270480>,
'a': {'BACKREF': <Recursion on Tree with id=2494556340608>,
'$': None}}},
'e': {'BACKREF': <Recursion on Tree with id=2494556270400>,
'l': {'BACKREF': <Recursion on Tree with id=2494556340288>,
'l': {'BACKREF': <Recursion on Tree with id=2494556340368>,
'o': {'BACKREF': <Recursion on Tree with id=2494556340448>,
'$': None}}},
'y': {'BACKREF': <Recursion on Tree with id=2494556340288>,
'$': None}}}}用于比较的默认结果：
>>> pprint.pp(root)
defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': None,
'h': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930855152>,
'i': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930855312>,
'$': None,
'y': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930912832>,
'a': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930913232>,
'$': None})})}),
'e': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930855312>,
'l': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930912912>,
'l': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930912992>,
'o': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930913072>,
'$': None})})}),
'y': defaultdict(<function <lambda> at 0x000001A13760BE50>,
{'BACKREF': <Recursion on defaultdict with id=1791930912912>,
'$': None})})})})Stack Overflow用户
发布于 2021-10-13 02:12:19
您试图实现的行为似乎更容易编写为类，而不是函数。
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']
Truehttps://stackoverflow.com/questions/69548477
复制相似问题
腾讯云开发者
