14

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

我有相当多的数据：

  • 磁盘上的纯文本 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 的堆分析，指示使用最多内存的位置：

 [MT    ]--[Count]----[   Size]-[Class                                          ]
 03563150       11         1584 System.Collections.Hashtable+bucket[]
 03561630       24         4636 System.Char[]
 03563470        8         6000 System.Byte[]
 00193558      425        74788      Free
 00984ac8    14457       462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]
 03562b9c        6     11573372 System.Int32[]
*009835a0  1456066     23297056 StringTrie+InteriorNode
 035576dc        1     46292000 Dictionary`2+Entry[[String],[Int32]][]
*035341d0  1456085     69730164 System.Object[]
*03560a00  1747257     80435032 System.String
*00983a54  8052746     96632952 StringTrie+LeafNode

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，仅使用值类型数组来存储数据：

class SlimTrie
{
    byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data

    // indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n]
    // Indexes interior_node_index if negative (bitwise complement),
    // leaf_node_group if positive.
    int[] _interiorChildren;

    // The interior_node_index group - all arrays use same index.
    byte[] _interiorChildCount;
    int[] _interiorChildIndex; // indexes _interiorChildren
    int[] _interiorChunk; // indexes _stringData

    // The leaf_node_index group.
    int[] _leafNodes; // indexes _stringData

    // ...
}

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

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

4

3 回答 3

2

由于只有 110 万个块，因此您可以使用 24 位而不是 32 位来索引一个块并节省空间。

您也可以压缩块。也许霍夫曼编码是一个不错的选择。我还会尝试以下策略：您应该对字符转换进行编码，而不是使用字符作为符号进行编码。因此，与其查看字符出现的概率，不如查看状态为当前字符的马尔可夫链中转换的概率。

于 2009-08-31T04:53:38.357 回答
1

您可以在此处找到与您的问题相关的科学论文（作者引用：“实验表明，我们的索引支持空间占用内的快速查询，这接近通过 gzip、bzip 或 ppmdi 压缩字符串字典可实现的查询。” - 但不幸的是，该文件仅用于付款）。我不确定这些想法实施起来有多么困难。本文的作者有一个网站，您还可以在其中找到各种压缩索引算法的实现（在“索引集合”下） 。

如果您想继续您的方法，请务必查看有关Crit-bit trees和Radix tree的网站。

于 2009-08-31T12:18:35.450 回答
0

现成的想法：而不是尝试哈希表。您在内存中只有散列和字符串数据，可能是压缩的。

或者你能负担得起一页书的阅读量吗？只有哈希和文件在内存中的位置，检索与该哈希匹配的行的“页面”，大概是少量的有序行，因此在发生冲突时非常快速地搜索。

于 2009-08-30T23:15:25.010 回答