问题标签 [patricia-trie]

在 JavaScript 中，我试图接受给定的用户输入并猜测 3 个最有可能完成用户当前（不完整）键入的单词的单词。猜测是基于用户过去的输入。我正在这里工作，在这个 JSFiddle 中。

我为记录用户过去的输入而构建的结构是修改后的基数树（AKA Patricia Trie）：

输入：“ hey”

这个数据结构构建得很完美，我认为它是实现所描述目标的最佳结构。我的问题是读取基数树数据以定义给定输入的 3 个最可能单词的功能。以上面的数据为例，如果用户输入“ h”，猜测函数应该返回一个像这样的对象：

所以这是我的代码/进度：

学习- 获取完整的输入字符串并将组合组织到基数树 ( brain) 中：

这一切都做对了。不幸的是，下一个代码，用于读取数据并猜测用户输入的单词，并不好。我在处理对我来说非常复杂的功能时遇到了麻烦。我把它分成了几个小函数，因为我知道这是最好的做法，但我担心我弄得一团糟，可能会更简单：

猜测- 获取“学习的”字符串数据并猜测用户可能正在输入的单词 3：

旁注- 虽然在字典上进行模糊字符串搜索是一种更常见的方法，但学习方法是根据用户的写作/消息传递风格定制猜测并支持用户的非标准词汇（“ heyy”，“ sup” , " :P", " lol") - 这些猜测的结果可以与标准字典结果结合（并优先于）。

在实现 ip-lookup 结构时，我试图在类似 trie 的结构中维护一组键，允许我搜索键的“地板”（即小于或等于给定的最大键钥匙）。我决定使用 Apache Collections 4 PatriciaTrie但遗憾的是，我发现floorEntry和相关方法不是public. 我目前的“肮脏”解决方案是用反射强迫他们（在 Scala 中）：

有没有什么干净的方法可以拥有相同的功能？为什么这种方法不公开？

我必须使用尝试制作字典，字母表中的字母数将从 26 增加到 120，因此叶节点的数量将成倍增加。我可以使用哪些优化来使我的查找、插入和删除时间不会成倍增加？

编辑 使问题更清楚，抱歉缺少细节我正在使用像基数树这样的多路特里树并对其进行一些修改。我的问题是，如果我知道单词大小（肯定）会从 26 增加到 120，它会增加树的深度。是否可以通过将密钥增加到 64 位以上来减少深度的增加（寄存器最多可以达到 64 位）？

据我了解（也来自这里）这些 DS 的内存复杂性可以像 Trie > Radix > Patricia 一样排序。但是时间复杂度呢？我认为它们几乎相同。

如果要提到我的问题，我想从预先构建的字典中做很多前缀搜索查询。记忆对我来说不是一个大问题。我想用最快的DS。

HAT-trie 最适合我，但实现起来太复杂了。我应该使用三元搜索树而不是上面提到的任何 DS 吗？

非常感谢！

目前 Jonathan S. 提出了一个拉取请求，根据Edward Kmett的博客文章中的想法，用本 READMEData.IntMap中解释的实现替换。

Jonathan S. 开发的基本概念是 anIntMap是一棵看起来像这样的二叉树（为了保持一致性，我对他的开发做了一些细微的改动）：

在此表示中，每个节点都有一个字段，指示IntMapNE0. 只需稍微摆弄一下，就可以将其用作 PATRICIA trie。乔纳森指出，这种结构的范围信息几乎是它需要的两倍。跟随左或右脊椎将产生所有相同lo或hi边界。因此，他通过仅包括祖先未确定的界限来消除这些：

现在每个节点都有一个左边界或右边界，但不是两者都有。右孩子只有左边界，而左孩子只有右边界。

Jonathan 进行了进一步的更改，将值从叶子移到内部节点中，这将它们准确地放置在确定的位置。他还使用幻像类型来帮助跟踪左右。最后的类型（现在，无论如何）是

这个新实现的某些方面非常有吸引力。最重要的是，许多最常用的操作要快得多。不太重要，但非常好，所涉及的位摆弄更容易理解。

但是，有一个严重的痛点：将缺失的范围信息向下传递到树中。这对于查找、插入等来说并不是那么糟糕，但是在联合和交集代码中会变得非常棘手。是否有一些抽象可以自动完成？

几个非常模糊的想法：

1. 幻像类型可以与自定义类一起使用以将治疗直接与惯用手联系起来吗？

2. “丢失的部分”性质有点让人想起一些拉链的情况。有没有办法使用那个领域的想法？

我已经开始考虑使用某种中间类型来提供结构的对称“视图”，但我有点卡住了。我可以很容易地在基本结构和花哨的结构之间来回转换，但这种转换是递归的。我需要一种只进行部分转换的方法，但我对花哨构建的类型知之甚少，无法完成它。

虽然很难找到“基数树”的一致定义，但大多数公认的基数树定义表明它是一个压缩的前缀树。我正在努力理解的是在这种情况下“基数”一词的意义。为什么压缩前缀树如此命名（即基数树）而非压缩前缀树不称为基数树？

请注意，下面的代码在控制台中显示了数组，而不是在代码段输出中

上面输出这个

但我想输出这个：

谁能帮我从我的代码中找出这个输出？我怎么能用这段代码做后缀？

我如何使用该函数的 keyup 函数来检索值？如果我按“m”，m 的所有值将显示，如果我按 s，“s”的所有值将显示在下面。谢谢

我必须通过使用 keyup 功能来做到这一点。之后我必须从数据库中检索值并保存在本地存储中以供进一步使用。

目标：

我想实现一个函数，该函数具有一系列输入“X1,...,Xn”并输出一个有序列表“Xp,..,Xq”，其中所有元素都是不同但有序的。

要求：

• 对于序列“X1,...,Xn”中的每个 Xi，它都是一个 256 位长的字符串。
• 输入序列“X1,...,Xn”可能具有相同的元素，这意味着可能存在两个元素Xi和Xj以满足Xi=Xj。
• 对于“X1,...,Xn”序列中的相同元素，我们只输出有序列表中的一个元素。
• 函数的速度应该尽可能快。函数中使用了多少存储量并不重要。
• 序列“X1,...,Xn”的大小为n，n是不超过10,000的数字。

我的想法：

• 我使用一个数组来存储最初为空的序列。

• 输入Xi的时候，首先搜索Hashtable，判断Xi是否已经在上面的数组中。如果是，就扔掉它。如果没有，请将 Xi 添加到 Hashtable 和 Array。

• 如果输入了序列“X1,...,Xn”的所有元素，我对数组进行排序并输出它。

问题：

• 对于 Merkle Patricia Tree (Ethereum) 和 Hashtable，我应该选择哪一个？
• 对于 Merkle Patricia Tree (Ethereum) 和 Hashtable，哪个搜索速度更快？
• 还是有更好的数据结构来满足这个功能？

我正在尝试查找存储在 trie 中的所有键，这些键是字符串的有效前缀。

示例：给定一个包含“ab”、“abc”、“abcd”、“bc”和“bcd”的trie。在 trie 中搜索字符串“abcdefg”应得到“abcd”、“abc”、“ab”。

我想为 java 使用 appache commons patricia trie 实现，但它似乎不支持这种查找。是否有任何替代实现或简单的解决方案来解决这个问题？