Python我想使用BST进行标记索引和搜索。我应该看什么包裹？

Question

我希望能够在BST中为搜索项（或最接近的匹配项）找到一个节点，并不仅返回精确的匹配项，还返回该节点的子节点。e、 我可以搜索“猫”，也可以找到“目录”和“白内障”，或得到“汽车”和“营地”时，没有前缀“猫”的钥匙存在于树。我有很多使用我自己实现的经验，我认为BST的这种怪癖是理所当然的。是否有一个Python包公开了这个功能，或者很容易修改以满足我的需要？如果我不用自己写就好了。理想情况下，这棵树应该是平衡的。谢谢

Answer 1

您最好看看http://en.wikipedia.org/wiki/Trie，它允许您所追求的排序最近匹配功能

https://pypi.python.org/pypi/marisa-trie或https://pythonhosted.org/PyTrie/就是两个例子