使用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
（證明這是有效的：
and that I am at root['h']['e']['l']['l']['o'] and want to delete 'hello' from the trie. I can do this by backtracking up the trie from root['h']['e']['l']['l']['o'] to root['h']['e']['l']['l'] to root['h']['e']['l'] to root['h']['e'] (I stop here because len(set(root['h']['e'].keys()) - {BACKREF}) > 1. Then I can simply do del root['h']['e']['l'] and I will have cleaved off the 'llo$' from 'he' meaning the trie will still have 'hey'. Although there are alternatives, backtracking up the trie will be very easy with the backreferences.
Context on tree = lambda: defaultdict(tree)
Using:
from collections import defaultdict
tree = lambda: defaultdict(tree)
root = tree()
one can create arbitrarily nested dicts. E.g. after:
root['h']['i']
root['h']['e']['l']['l']['o']
root['h']['i']['y']['a']
root['h']['e']['y']
root will look like:
{'h': {'i': {'y': {'a': {}}}, 'e': {'y': {}, 'l': {'l': {'o': {}}}}}}
This represents a tree that looks like this:
visualized using https://www.cs.usfca.edu/~galles/visualization/Trie.html
uj5u.com熱心網友回復：
您嘗試實作的行為似乎更容易撰寫為類而不是函式。
from collections import defaultdict
class Tree(defaultdict):
def __init__(self, backref=None):
super().__init__(self.make_child)
self.backref = backref
self.end = None
def make_child(self):
return Tree(backref=self)
用法：
>>> root = Tree()
>>> root['h'].backref is root
True
>>> root['h']['e'].backref is root['h']
True
uj5u.com熱心網友回復：
給予同樣{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] = None
該root節點有一個 backref None，如果麻煩可以洗掉。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/310942.html
標籤：python trie defaultdict recursive-datastructures