节省空间的内存结构,用于支持前缀搜索的排序文本

Question

我有一个问题:我需要根据文件路径前缀节省空间的文件系统数据查找.换句话说,前缀搜索已排序的文本.你说,使用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个
• 约1.8M内部节点.

叶片产生的过剩率约为15%,多余的内部节点产生率为22% - 过量创建,我的意思是在构造期间创建的叶子和内部节点,但不是在最终的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>被用于映射串块到索引到List<string>,并能特里施工后丢弃,虽然GC似乎并没有被删除它(一对夫妇明确集合了这个转储前完成) - !gcroot在SOS并不表示任何根,但我预计后来的GC会释放它.

MiniList<T>是替代List<T>使用精确尺寸(即线性增长,O(n^2)添加性能)T[]以避免空间浪费; 它是一种值类型,用于InteriorNode跟踪孩子.这T[]被添加到System.Object[]堆中.

所以,如果我把"有趣"的项目(标记为*),我得到大约270M,这比磁盘上的原始文本更好,但仍然不够接近我的目标.我认为.NET对象开销过多,并创建了一个新的"苗条"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更有效的结构的任何建议？我应该考虑的替代方法？

Answer 1

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

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