c# - 支持前缀搜索的排序文本的节省空间的内存结构

Question

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

我有相当多的数据:

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

我不想占用接近 450M 的内存。在这一点上，我很乐意使用大约 100M 的空间，因为有很多前缀形式的冗余。

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

让我们看一下数据的一些统计属性。当塞进 trie 中时:

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

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

这是来自 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> 用于将字符串 block 映射到 List<string> 中的索引，并且可以在 trie 构建之后丢弃，尽管 GC 似乎没有删除它(在这个转储之前完成了几个显式收集)- !gcroot在 SOS 中不表示任何根，但我预计稍后的 GC 会释放它。

MiniList<T> 是 List<T> 的替代品，使用精确大小(即线性增长，O(n^2) 添加性能)的 T[] 来避免空间浪费；它是一种值类型，InteriorNode 使用它来跟踪 child 。此 T[] 被添加到 System.Object[] 堆中。

所以，如果我将“有趣”的项目(用 * 标记)加起来，我得到大约 270M，这比磁盘上的原始文本要好，但仍然离我的目标还不够近。我认为 .NET 对象的开销太大，因此创建了一个新的“超薄”特里​​树，仅使用值类型数组来存储数据:

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 更有效的前缀搜索结构有什么建议吗？我应该考虑其他方法吗？

Answer 1

由于只有 110 万个 block ，您可以使用 24 位而不是 32 位对 block 进行索引并节省空间。

您还可以压缩 block 。也许Huffman coding是个不错的选择。我还会尝试以下策略:您应该对字符转换进行编码，而不是使用字符作为符号进行编码。因此，与其查看字符出现的概率，不如查看 Markov chain 中转换的概率。其中状态是当前字符。