问题标签 [patricia-trie]

我有一个问题问你。我必须实现一个包含 30000 个名称的业务通讯簿。所有名称都包含名字和姓氏。我必须实现一个自动完成文本框，它不仅可以搜索输入名字，还可以搜索姓氏。在 google 上搜索我发现这个问题是使用 patricia trie 解决的，但它只做前缀搜索，所以如果我用 firstname+lastname 创建一个 trie，我如何不仅可以按名字搜索，而且可以按姓氏搜索？

我是否必须复制插入两个这样的字符串的条目？名字+姓氏和姓氏+名字

请帮我！！！

搜索必须非常有效。

谢谢。

我在使用 protobuf.net 序列化对象时遇到问题。我已经在其他课程上使用过它并且效果很好，但是使用它却不行。

能不能帮我说说原因。谢谢。

我想使用 protobuf，因为 BinaryFormatter 在序列化/反序列化方面非常慢。

这是课程：

我正在用 C++ 编写一个程序，该程序需要快速查找和存储 IP 地址（所有 IPv4）。每个 IP 地址都有一个与之关联的数据。如果它已经存在于 trie 中，我打算将 trie 中的 IP 地址数据与新地址数据合并。如果它不存在，我打算将它作为新条目添加到 trie 中。不需要删除 IP 地址。

为了实现这一点，我需要设计一个 Patricia Trie。但是，我无法想象除此之外的设计。我似乎很天真，但我想到的唯一想法是将 IP 地址更改为二进制形式，然后使用 trie。然而，我对如何实现这一点一无所知。

如果您能帮我解决这个问题，我将非常感谢您。请注意，我确实在这里找到了类似的问题。这个问题或更具体的答案超出了我的理解，因为 CPAN 网站中的代码对我来说不够清楚。

另请注意，我的数据是以下格式

10.10.100.1：“汤姆”、“杰克”、“史密斯”

192.168.12.12：“琼斯”、“莉兹”

12.124.2.1：“吉米”，“乔治”

10.10.100.1：“迈克”、“哈利”、“詹妮弗”

trie和radix trie数据结构是否相同？

如果它们不一样，那么基数特里（AKA Patricia trie）的含义是什么？

根据libstdc++ 文档的第 3 点和第 4 点，PATRICIA 尝试有两种类型的节点：

(PATRICIA) trie 类似于树，但有以下区别：

1. 它明确地将键视为一系列元素。例如，trie 可以将字符串视为字符序列；trie 可以将数字视为位序列。

2. 它不是（必然）二进制。每个节点都有 n + 1 个扇出，其中 n 是不同元素的数量。

3. 它仅在叶节点存储值。

4. 内部节点具有以下属性：A）每个都至少有两个子节点，B）每个节点都与其任何后代共享相同的前缀。

我一直在阅读的书（Algorithms in C, Parts 1-4 by Robert Sedgewick）似乎描述了一个 PATRICIA trie，它只使用 n 个节点存储 n 个值，使用内部节点来存储值：

与 DST 一样，patricia 尝试允许在只有 N 个节点的树中搜索 N 个键。...我们通过另一个简单的设备避免外部节点：我们将数据存储在内部节点中，并将指向外部节点的链接替换为指向树中正确内部节点的链接

这里似乎有两个信仰阵营：

1. 一方面，我们有一个严格、具体的定义（即 Sedgewick、Knuth、Morrison，他们似乎都将 PATRICIA 专门描述为一棵消除了单向分支的前缀压缩二叉树）；和
2. 然后我们有一些人认为该术语形成了一个松散、模糊的定义，这似乎更像是他们的意思是使用像“map”、“dictionary”或“trie”这样的词（这些实际上都是松散定义的，即 libcs​​td++ 文档）。

我想我担心我的资源的准确性。据我了解，由于常见前缀引入的问题，不可能在不将其呈现为二叉树的情况下表示只有 N 个节点的树（这似乎违反了 libcs​​td++ 文档的第 2 点，以及处理变量时的第 4 点-width 键），并且不失严格单向分支的概念（违反第 3 点和第 4 点，使“叶节点”和“子节点”的概念有些无效）。这两个功能协同工作以消除“内部节点”的困境，这将导致此类树使用超过 N 个节点（回想一下：N 个项目与 N 个节点）。

这两组参考文献不可能都正确；有太多的相互排斥。如果一个参考说 PATRICIA 是二元的，另一个说它可能不是，它们不能都被认为是事实正确的，这只是我在这里看到的不一致的一个例子。这些引用中哪些是正确的？

我正在尝试编写一个简单的搜索引擎，它使用trie（一个节点只包含一个字符）数据结构来查找单词。当它从用户那里得到“压缩”命令时，trie 应该变成一种 patricia trie的形式。（一个节点包含与他们的孩子共同的字符串）

我已经完成了连接字符串的部分，但问题是与其父级连接的子级仍然存在。（它们应该已被删除。）我想，通过编写一个“清除”方法，我可以处理它。

这是我的解决方案，但它不起作用：

这是主要和输出：

主要的：

输出：

我该如何处理这个问题？任何帮助将不胜感激。非常感谢！

我写了一个简单的函数来确定 str1 是否是 str2 的前缀。这是一个非常简单的函数，看起来像这样（在 JS 中）：

如您所见，它遍历前缀字符串的整个长度以判断它是否是候选字符串的前缀。这意味着它的复杂度是 O(N)，这还不错，但是当我有一个庞大的数据集要考虑循环以确定哪些字符串具有前缀字符串作为前缀的一部分时，这就会成为一个问题。这使得复杂度倍数为 O(M*N)，其中 M 是给定数据集中的字符串总数。不好。

我在 Internet 上进行了一些探索，以确定最佳答案是 Patricia/​​Radix trie。字符串存储为前缀的位置。即使那样，当我尝试插入/查找字符串时，如果我使用上述前缀测量功能，字符串匹配也会有相当大的开销。

假设我有一个前缀字符串“rom”和一组候选词

var dataset =["random","rapid","romance","romania","rome","rose"];

在 radix trie 中会这样：

这意味着，对于每个节点，我将使用前缀匹配函数来确定哪个节点的值与索引处的前缀字符串匹配。不知何故，这个解决方案似乎仍然很艰巨，对我来说不太合适。有没有更好的东西或者我可以改进核心前缀匹配功能？

Is there a document that will help me understand how ipv4 addresses are inserted into the patricia/radix trees? I am confused around calculating mask length and if the mask length is for the complete address or one octet in the address.

Any explaination would be appreciated.

我正在研究各种“前缀查找”数据结构，例如 Tries 和 Radix Tries (Patricia Tries)。

至此，我对 Try 和 radix Try 都有了深刻的理解，并且对它们的用例也有了很好的理解。

然而，一个问题突然出现在我身上：使用常规 trie 是否比压缩 trie（例如 radix trie）有任何优势？

常规的 trie 实现起来很简单：它为每个节点存储一个字符。Patricia Trie 实现起来有点困难：它是“压缩的”，因为每个节点都包含一个完整的字符串，并且前缀比较是使用按位匹配完成的。

由于 Patricia Trie 更节省空间，并且不会牺牲查找速度，因此是否有使用每个节点都包含一个字母的常规（非压缩）Trie 的用例？

我能想到的唯一用例是，如果您的“字符串”不是常规字符串（如更复杂对象的数组），因此无法使用逐位比较进行比较。

常规（非压缩）Trie 还有其他用例吗？

Inspired by iOS7 iMessage's next-word-prediction, I've decided to try to write a script that will learn, based on user input, which words / letters are most likely wanted to complete the user's current word or which word might most likely be desired next.

To do this, I'm going to use a data structure very similar to a Radix Tree (AKA a Patricia Trie).

Take this user input for example:

I like icecream

From that, my goal is to generate the following data structure:

This is essentially a Radix Tree, with some extra information, allowing me to weigh the probability of the learned possibilities that the user might want to type next.

From the above extremely limited data set, when the user types an "I", our best (and only) guess is that the next character will be a " ".

So now that I've explained my goal and method, here's my question:

How can I build this data structure from any given user input?

This is as far as I've gotten, but I'm not sure how to insert the next values at the proper positions recursively.