问题标签 [trie]

我有一个问题：我需要基于文件路径前缀的文件系统数据的节省空间的查找。换句话说，排序文本的前缀搜索。你说用特里，我也这么想。麻烦的是，尝试不够节省空间，并非没有其他技巧。

我有相当多的数据：

• 磁盘上的纯文本 Unix 格式列表中大约 450M
• 约800万行
• gzip 默认压缩到 31M
• bzip2 默认压缩到 21M

我不想在内存中接近 450M 的地方吃东西。在这一点上，我很乐意使用大约 100M 的速度，因为前缀形式有很多冗余。

我正在使用 C# 来完成这项工作，并且 trie 的直接实现仍然需要文件中的每一行都有一个叶节点。假设每个叶节点都需要对最终文本块的某种引用（32 位，例如字符串数据数组的索引以最小化字符串重复），并且 CLR 对象开销为 8 个字节（使用 windbg / SOS 验证） ，我将在结构开销上花费 >96,000,000 字节，而根本没有文本存储。

让我们看一下数据的一些统计属性。当塞进一个特里时：

• 大约 110 万个独特的文本“块”
• 文本文件中磁盘上大约 16M 的唯一块总数
• 平均块长度为 5.5 个字符，最大 136
• 如果不考虑重复，大约有 5200 万个字符块
• 内部 trie 节点平均约 6.5 个子节点，最多 44 个
• 大约 180 万个内部节点。

叶创建的超额率约为 15%，超额内部节点创建率为 22% - 超额创建是指在树构造期间创建的叶和内部节点，但不是在最终树中创建的，占每种类型的最终节点数的比例.

这是来自 SOS 的堆分析，指示使用最多内存的位置：

Dictionary<string,int>用于将字符串块映射到索引到 a中List<string>，并且可以在构建 trie 后丢弃，尽管 GC 似乎没有删除它（在此转储之前完成了几个显式收集） -!gcroot在 SOS 中并不表示任何根，但我预计以后的 GC 会释放它。

MiniList<T>是List<T>使用精确尺寸（即线性增长、O(n^2)加法性能）T[]来避免空间浪费的替代品；它是一个值类型，用于InteriorNode跟踪孩子。这T[]被添加到System.Object[]堆中。

所以，如果我把“有趣”的项目（用 标记*）加起来，我会得到大约 270M，这比磁盘上的原始文本要好，但仍然不够接近我的目标。我认为 .NET 对象开销太大，并创建了一个新的“slim”trie，仅使用值类型数组来存储数据：

这种结构已经将数据量降低到了 139M，对于只读操作来说仍然是一种高效的可遍历 trie。而且因为它非常简单，我可以轻松地将它保存到磁盘并恢复它，以避免每次都重新创建 trie 的成本。

那么，对于前缀搜索比 trie 更有效的结构有什么建议吗？我应该考虑的替代方法？

鉴于以下...

你会如何把它变成这个 trie？

在尝试学习 c++ 时，我尝试实现表示非常基本的 trie 的类。我想出了以下内容：

方法addChild检查具有相同数据的子ch是否存在于向量children中，如果没有，则将其插入那里，如果是 - 返回指向已存在子的指针。

现在，考虑这个代码片段：

如果我只有指向secondchild的指针，是否有可能以某种方式返回指向firstchild甚至t的指针？

我想知道是否可以这样做，因为我的工作代码的逻辑需要遍历 trie “up”（从较低的节点到较高的节点），到当前对象的父级。目前我只是使用递归函数向下旅行 - 但我想知道是否存在其他方式？

如果上面不清楚或者我在某个地方搞砸了，我很抱歉，我相当缺乏经验并且根据我的记忆写作，没有工作代码。

我试图找出快速支持以下操作的数据结构：

• 添加一个字符串（如果不存在，则添加它，如果存在，则为单词增加一个计数器）
• 计算给定的字符串（按字符串查找，然后读取计数器）

我在哈希表或特里之间争论。据我了解，只要避免冲突，哈希表就可以快速查找和添加。如果我不提前知道我的输入，trie 会是更好的方法吗？

（到目前为止，这在本质上是相当假设的，所以我没有太多细节可以提供。）

我有一个随机（英文）单词的平面文件，每行一个。我需要编写一个高效的程序来计算每个单词的出现次数。该文件很大（可能大约 1GB），但我有足够的 RAM 来存放所有内容。它们存储在永久媒体上，因此读取速度很慢，所以我只需要线性读取一次。

我的两个不经意间的想法是使用带有单词的哈希 => 否。发生次数，或尝试与否。在结束节点发生的次数。我有足够的 RAM 用于哈希数组，但我认为 trie 的查找速度会一样快或更快。

什么方法最好？

我必须在 c++ 映射中存储大量字符串以保持唯一字符串，并且当出现重复字符串时，我只需要增加计数器（pair.second）。我使用了 c++ map，它非常适合这种情况。由于处理的文件现在已达到 30gig，因此我试图将其保存在文件中而不是内存中。

在这种情况下，我还遇到了比 map 更快的 trie。有人知道文件支持的 trie 实现吗？我遇到了一个类似于我正在寻找的Trie实现，但似乎不是没有错误的..

我正在使用一些 Java 代码来进行快速前缀查找，使用 java.util.TreeSet，我可以改用 scala 的 TreeSet 吗？还是不同的解决方案？

假设我的文件系统中有一个目录，其中包含许多子目录和文件。该目录中的子目录和文件的数量达到数万。您将熟悉尝试查看此目录的内容时会遇到的显着延迟，即使在终端中也是如此。

我在很多地方都看到过这种解决方案：将顶级内容列表排序为 trie 样式的目录结构。因此，例如，如果原始列表是 [000000.txt ... 999999.txt]，那么要访问文件 012345.txt，我会访问 ./0/1/2/3/4/ 012345.txt 。

我一直找不到一个简短而有趣的脚本来生成这种结构。有什么东西存在还是我必须自己写？我希望它像这样工作：

在假期里，我的家人喜欢玩 Boggle。问题是，我在 Boggle 上很糟糕。所以我做了任何优秀程序员都会做的事：写一个程序来为我玩。

该算法的核心是一个简单的前缀树，其中每个节点都是dict对下一个字母的引用。

这是trie:add实现：

您可以在此处查看其余部分以及如何使用它的示例（在底部）：

http://gist.github.com/263513

现在，这是我在 Erlang 中的第一个严肃程序，我知道它可能有很多问题……但我最关心的是它使用了800 MB 的 RAM。

那么，我做错了什么？我怎样才能让它少一点错误呢？

嗨，我正在尝试为英语到西班牙语词典创建一个 trie 结构。

这是我到目前为止所拥有的：

我不知道从这里去哪里。任何帮助，将不胜感激。谢谢！