在 Patricia Trie 中查找最长前缀搜索的算法/步骤

Question

我正在为IP前缀查找实施Patricia尝试，我可以使代码用于完整的密钥匹配，但是当有其他键的键时，面临前缀搜索的问题，例如：

1.2.3.0
1.2.0.0

谁能帮我提供上述情况下的前缀搜索算法？ 我是否应该将这些键视为不同长度的键（即 /24 和 16）？

Answer 1

看看内特·帕特里夏。这是用于查找 IP 地址的 Patricia trie 的实现。接口是perl，但底层代码是C语言。这是一个链接，但许多 CPAN 档案应该有它：

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

Answer 2

如果使用此线索，用于存储IP号码作为固定长度的元件则它是绝对不正确的方式。这里的要点是，PT是用于存储可变长度数据是特别有用的。 搜索结果 如果存储IP号的零件，如可变长度的前缀，那么PT是一个不错的选择。 点击 在这种情况下是你的钥匙应该是不同的长度。 点击 比方说，你是存储在二进制将0xC0 0xA8前缀“192.168”，你添加为第一个关键。 点击 然后，像192.168.1.1的IP进行搜索时，你的线索包含192.168这是你要找什么前缀获取信息。 搜索结果 所有你需要做的就是存储“共同部分”，而穿越该线索。 点击 这是一个小除了这实现。只要确保同时下降线索您在递归函数的参数存储一些常用的部分。 点击 对于帕特里夏线索的很好的理解，我建议阅读罗伯特·塞奇威克的算法书这是一个伟大的知识源。

修改：在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/