问题标签 [trie]

我需要有一组 python 对象用于创建 trie 数据结构。我需要一个结构，它像元组一样是固定长度，像列表一样是可变的。我不想使用列表，因为我希望能够确保列表的大小完全正确（如果它开始分配额外的元素，那么随着 trie 变大，内存开销可能会很快增加）。有没有办法做到这一点？我尝试创建一个对象数组：

...但这给出了一个错误：

做我想做的事情的最佳方法是什么？

我想为高棉语（一种单词之间没有空格的语言）添加一个开源 Java 分词程序。开发者很久没做这件事了，我也无法联系到他们了解详情（http://sourceforge.net/projects/khmer/files/Khmer%20Word%20Breaking/Khmer%20Word%20Breaking %20program%20V1.0/)。假设该列表是从高棉词典创建的，我想重新创建该文件以包含更多单词。

谁能确定字典的格式（我相信它是某种类型的特里）？这是前几行：

有谁知道我将如何制作一个新的（我有一个很大的词表，但我不知道如何把它变成这种格式）。

谢谢！

更新 3

完毕。下面是最终通过了我所有测试的代码。同样，这是模仿穆里洛·瓦斯康塞洛对史蒂夫·汉诺夫算法的修改版本。感谢所有帮助！

更新 2

最后，我设法使它适用于我的大多数测试用例。我的实现实际上是从Murilo 的 C++ 版本的Steve Hanov's algorithm的直接翻译。那么我应该如何重构这个算法和/或进行优化呢？下面是代码...

感谢所有为这个问题做出贡献的人。我试图让 Levenshtein Automata 工作，但我无法实现。

因此，我正在寻找有关上述代码的重构和/或优化建议。如果有任何混淆，请告诉我。与往常一样，我可以根据需要提供其余的源代码。

更新 1

所以我实现了一个简单的 Trie 数据结构，并且我一直在尝试按照 Steve Hanov 的 python 教程来计算 Levenshtein 距离。实际上，我对计算给定单词和 Trie 中的单词之间的最小Levenshtein 距离感兴趣，因此我一直在关注Murilo Vasconcelos 的 Steve Hanov 算法版本。它工作得不是很好，但这是我的 Trie 课程：

...和 ​​TrieNode 类：

现在，我尝试按照Murilo Vasconcelos的方式实现搜索，但是有些东西出了问题，我需要一些帮助来调试它。请就如何重构提出建议和/或指出错误在哪里。我想重构的第一件事是“minCost”全局变量，但这是最小的事情。无论如何，这是代码......

我为缺乏评论表示歉意。那么我做错了什么？

初始帖子

我一直在阅读一篇文章Fast and Easy Levenshtein distance using a Trie，希望找到一种有效的方法来计算两个字符串之间的Levenshtein 距离。我的主要目标是，给定大量单词，能够找到输入单词和这组单词之间的最小 Levenshtein 距离。

在我的简单实现中，我为每个输入词计算输入词和词集之间的 Levenshtein 距离，并返回最小值。它有效，但效率不高......

我一直在寻找 Java 中 Trie 的实现，并且遇到了两个看似不错的资源：

• Koders.com 版本
• code.google.com 版本 （编辑：这似乎已移至github.com/rkapsi）

但是，对于我正在尝试做的事情，这些实现似乎太复杂了。当我一直在阅读它们以了解它们如何工作以及 Trie 数据结构通常如何工作时，我只会变得更加困惑。

那么如何在 Java 中实现一个简单的 Trie 数据结构呢？我的直觉告诉我，每个 TrieNode 都应该存储它所代表的字符串以及对字母表字母的引用，不一定是所有字母。我的直觉正确吗？

一旦实现，下一个任务就是计算 Levenshtein 距离。我通读了上面文章中的 Python 代码示例，但我不会说 Python，一旦我点击递归搜索，我的 Java 实现就会耗尽堆内存。那么如何使用 Trie 数据结构计算 Levenshtein 距离？我有一个简单的实现，仿照这个源代码，但它不使用 Trie ......它效率低下。

除了您的评论和建议之外，看到一些代码真的很高兴。毕竟，这对我来说是一个学习过程……我从未实施过 Trie……所以我可以从这次经历中学到很多东西。

谢谢。

ps 如果需要，我可以提供任何源代码。另外，我已经按照Nick Johnson 的博客中的建议通读并尝试使用 BK-Tree ，但它的效率不如我想象的那么高……或者我的实现可能是错误的。

I am trying to figure out the best data structure to use for this problem. I am implementing a key value store with keys that are strings. The values get added frequently and will generally only get looked up 1 or 2 times. Initially I used an std::map, but I found the performance to be unoptimal, as the overhead of adding keys and rebalancing the red-black tree, overshadowed the decrease in time to search for a value. Currently I am using a modified single linked list. It uses a struct that contains a c string (const char *), the length in bytes, and the value stored. When I want to find a value using a key I iterate through the list and compare the size of the keys, if they match I use memcmp to check if the strings are identical. If they are identical, I return the value. I way able to achieve about 10x greater performance using this method over the std::map. I need to make it about 2x more efficient, however. Can anyone recommend a better type of data structure, for this problem?

我正在尝试在 F# 中实现一个 trie 数据结构。我遇到了一些问题。我无法调试单词插入功能。我在这个函数中的断点都没有达到崩溃，但我没有看到任何错误。我也很怀疑我是否正确地实施了这件事。无论如何这里是代码：

所以我的问题是：
1. 如何获得对 insertWord 函数的调试访问权限？为什么我现在没有收到？为什么我没有看到错误？
2. 如何让函数 insert word 返回一个 TrieNode 对象列表，这样我就不必将调用括在方括号（“[”，“]”）中。我认为这是一个错误。
3. 欢迎您就在 F# 中实现此数据结构提供任何其他建议。我知道我一定做错了很多事情，因为我对这种语言非常陌生。例如，我知道单词插入函数有缺陷，因为它不检查列表是否为空，因此它过早结束。当我到达它时，我想穿过那座桥。

先感谢您

先感谢您

我正在研究自动完成脚本，并正在考虑使用 trie。我的问题是我希望返回匹配的所有内容。因此，例如，我输入r我希望返回所有以开头的条目的字母r。然后所有以 etc 开头的条目re。这对 trie 是否可行以及它如何工作。另外，如果有更好的方法，我愿意接受建议。r我问的原因是，从分支返回所有节点似乎会很复杂，并且需要进行大量处理。

是的，我可能正在重新发明轮子，但我想了解它是如何工作的。

我正在尝试使用一种计算每个节点高度的方法在 F# 中实现一个 trie 结构。

到目前为止，这是我想出的：

现在我正在尝试编写我的高度计算功能。如果这是一棵二叉树，这将很容易编写，但是在这棵树中，每个节点都有一个子节点列表，所以我不知道如何在 F# 中反复遍历该事物。

这是我到目前为止使用列表折叠操作提出的，但它没有编译：

有什么想法可以重写此函数以使其工作吗？或者关于如何实现我的目标的任何想法如果这不是正确的想法？

先感谢您

我正在使用 aho-corasick 算法来尝试使用 F# 做得更好一些，但我遇到了 Trie 实现的问题，它们都是可变的或者不能进行尾调用优化。

我所看到的基本问题是，必须“自下而上”构建不可变数据结构，因为您无法更改它们指向的内容，因此您的选择是使它们可变，或者在进行过程中找出节点（即构造中的递归）。

有什么方法可以在构造上通过尾调用优化来制作不可变的 trie 数据结构？（并且不会因复制而降低效率。）

我需要有关可用于 URL 上“最长前缀匹配”的任何标准 python 包的信息。我已经浏览了两个标准包http://packages.python.org/PyTrie/#pytrie.StringTrie & 'http://pypi.python.org/pypi/trie/0.1.1' 但它们似乎没有对 URL 上的最长前缀匹配任务很有用。

例如，如果我的设置有这些 URL 1->http://www.google.com/mail , 2->http://www.google.com/document, 3->http://www.facebook.com ， ETC..

现在，如果我搜索“http://www.google.com/doc”，那么它应该返回 2，搜索“http://www.face”应该返回 3。

我想确认是否有任何标准的 python 包可以帮助我做到这一点，或者我应该实现一个 Trie 来进行前缀匹配。

我不是在寻找一种正则表达式的解决方案，因为它随着 URL 数量的增加而无法扩展。

非常感谢。

伙计们，我已经写了一段代码，它给出了输出。现在，这是一个尝试。现在我想以一种审美的方式展示。有人帮帮我。我的表示应该是这样的http://en.wikipedia.org/wiki/File:Trie_example.svg

但我想要的是如何将这个巨大的怪物输出转换为像这样的整洁输出 [(1,2), (1,3), (1,4), (3,4)] ????