我正在实施 Patricia 尝试进行 IP 前缀查找，我可以让代码为完整的键匹配工作，但遇到前缀搜索问题，当键是其他键的前缀时，例如：
1.2.3.0
1.2.0.0
在上述情况下，任何人都可以帮助我使用前缀搜索算法我应该将它们视为单独长度的键（即/24 和 16）吗？
问问题
9897 次
3 回答
5
看看 Net-Patricia。这是用于查找 IP 地址的 Patricia trie 的实现。接口是perl，但底层代码是C。这是一个链接，但许多CPAN档案应该有它：
http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/patricia.c
于 2009-12-18T08:51:53.180 回答
3
如果您使用此 trie 将 IP 编号存储为固定长度的元素，那么这绝对不是正确的方法。这里的重点是 PT 对于存储可变长度数据特别有用。
如果您将部分 IP 号码存储为可变长度的前缀，那么 PT 是一个不错的选择。
在这种情况下，是的，您的密钥应该具有不同的长度。
假设您将前缀“192.168”存储在二进制 0xC0 0xA8 中，您将其添加为第一个键。
然后，在搜索 192.168.1.1 之类的 IP 时，您可以获得有关您的 trie 包含 192.168 的信息，这是您要查找的内容的前缀。
您所要做的就是在遍历特里树时存储“公共部分”。
这是对this
的一个小补充执行。只需确保在走下 trie 时，您将公共部分存储在递归函数的参数中的某个位置。
为了更好地理解 Patricia trie，我建议阅读Robert Sedgewick 的算法书，这是一个很好的知识来源。
编辑：在 PT 中存储 C 字符串时存在一个问题。该 trie 旨在存储二进制数据，但您只对获取整个字节感兴趣。确保仅当前缀的大小为 8 的倍数时才存储前缀的公共部分。举个错误的例子：你的树中有键：0xC0 0xA5，你正在寻找 0xC0 0xA6。当公共部分“0xC0 0xA”时，您的遍历将停止，但您只对“0xC0”感兴趣。因此，请确保存储公共字节，而不是位。
于 2009-11-04T21:27:55.580 回答
0
LLVM 的测试代码中有一个相当可读的 C 实现：https ://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/
于 2014-11-23T20:07:27.677 回答