在帕特里夏特里寻找最长前缀搜索的算法/步骤

Question

我正在实施帕特里夏尝试进行IP前缀查找，我可以得到 代码工作的完整密钥匹配，但面临前缀搜索的问题，当有 是关键是其他键的前缀，如：

1.2.3.0 
1.2.0.0 

谁能帮我在上述情况下 算法的前缀搜索我应该考虑这些作为单独的长度的密钥（即/ 24和16）？

Answer 1

看看Net-Patricia。这是Patricia trie查找IP地址的实现。该接口是perl的，但底层的代码是C.这里是一个链接，但许多CPAN档案应该有它：

http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/patricia.c

Answer 2

如果你使用这个trie来存储IP号码作为固定长度的元素，那么它绝对不是正确的方法。这里的要点是PT对于存储可变长度数据特别有用。

如果你存储了部分IP号码，作为可变长度的前缀，那么PT是一个不错的选择。
在这种情况下，您的钥匙应该具有不同的长度。
比方说，您将前缀“192.168”存储在二进制0xC0 0xA8中，您将其添加为第一个键。
然后，当搜索IP如192.168.1.1时，你可以得到你的trie包含192.168的信息，这是你所寻找的前缀。

您只需在遍历树时存储“公共部分”。
这是对this实现的轻微添加。只要确保在递归函数的参数中存储公共部分的某个位置时使用trie。
为了更好地理解Patricia trie，我建议您阅读Robert Sedgewick's Algorithms book这是一个很好的知识来源。

编辑：在PT中存储C字符串时存在一个问题。此特里设计用于存储二进制数据，但您只希望获取整个字节。 确保只在其位数的倍数为8时才存储前缀的公用部分。 对于错误的示例：您的树中包含键：0xC0 0xA5，并且您正在查找0xC0 0xA6。 当公共部分“0xC0 0xA”时，您的遍历将停止，但您只需要“0xC0”。所以请确保存储常用字节，而不是位。

Answer 3

有在LLVM测试代码相当可读的C实现：https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/