如何跨数据结构压缩很多字符串？
我有一个500GB的索引XML文档集合。 目前我只能使用32GB的RAM索引6GB的这个集合。
我的索引结构是一个HashMap<String, PatriciaTrie<String, Integer>> ，其中第一个字符串表示一个术语，第二个字符串的格式为filepath+XPath ，最后一个整数表示出现次数。
我使用了一个trie来减少共享前缀，因为我需要对数据进行排序。 压缩有点帮助，但这还不够。
在这个数据结构中， filepath+XPath字符串的总集合在1TB到4TB之间。 我需要能够将这个数据结构完全压缩到内存中。 目标机器具有256GB RAM和16个CPU核心。 较少的内存有多个额外的好处（例如减少冷启动时间）。 索引时间并不是什么大不了的事情。
XPath代表约250个节点类型。
我目前正在使用的方法将基于接下来可能发生的标签为每个2个标签系列构建一个Huffman表。 通常，这会将选项减少到大约4或5，这使得XPath可以编码成更短的位串，然后可以将其编码为字节。
这些字符串通常是40-600字节（UTF-8），我相信这应该会将文件路径前缀（前40个字符，由trie压缩）后的所有内容都减少到最大12个字节（树上最深点大约12个节点深，每个节点最差1个字符来表示），索引有12个字节（可变字节编码，只有很少的元素包含大于256的索引），产生的字符串通常在40 -64字节。
我认为这是一个好方法，但我想我可能会错过一些东西。
我认为你最大的问题在于你为每个术语存储了太多的数据。 你不会说你有多少独特的词汇或多少个人档案，但我会举几个例子。
假设您在200个不同文件中拥有200,000个独特术语。 因此，每个唯一的术语至少包含一个文件路径的权重，即40个字节。 这是你开始索引任何东西之前。
您应该能够将此数据压缩到filepath+Xpath字符串的表中，以及一个术语列表，每个术语都包含对该表中条目的引用。 所以，例如，你可能有：
路径表格：
index Path
1 file+xpath1
2 file+xpath2
3 file+xpath3
...
999 file+xpath999
条款
term references
foo 1, 19, 27, 33, 297
bar 99, 864, 865
...
现在，你的路径表可能还是太大了。 第一个想法是建立一个文件表并使路径的第一部分输入到文件表中的一个索引。 所以你最终得到：
档
1 file1.xml
2 file2.xml
...
999 file999.xml
然后你的路径变成：
1 1,xpathA
2 1,xpathB
3 2,xpathQ
...
如果在此之后需要更多压缩，请构建一个包含xpath术语的字符串表，并且您的路径条目将成为该表中的一系列索引。 不过，这里必须小心，因为数组或列表的分配开销会使短列表非常昂贵。 如果你走这条路线，那么你需要将路径列表编码为一个大的二进制数组，并将其编入索引。 例如。
单词列表
1 the
2 quick
3 brown
4 fox
路径
index path
0 1(index of file),2(quick),4(fox),-1(terminator)
4 3(index of file),3(brown),-1(terminator)
7 etc . . .
Paths表只是一个看起来像这样的大数组：
1,2,4,-1,3,3,-1,...
这最大限度地减少了数据存储成本，因为没有字符串存储多次。 你所拥有的只是字符串表和对这些字符串的引用。 需要的空间大小如下所示：
Combined length of all file names
Combined length of all path segment terms
(number of paths) * (average path length) * (size of integer index)
(number of terms) * (average number of references per term) * (size of integer index)
在记忆中建立这个可能是可能的。 不知道你有多少个人词汇很难说。 如果您使用单词列表，则需要文件名，路径和单个路径段的字典。 但是如果你有记忆，它可以一次完成。
如果在构建过程中没有足够的内存用于整个树，则可以加载文件名并将路径表保存在内存中。 当您在文件中查找每个术语时，请将其与其路径引用一起写入磁盘。 您最终得到的磁盘文件如下所示：
term, path reference
term, path reference
...
使用外部排序程序按术语进行排序，然后通过并合并重复项。 当你完成你最终的文件包含：
File names table
Path segments table
Paths
terms
查找非常简单。 查找术语，在路径表中查找每个引用，并通过索引文件名和路径段表来解码路径。
几年前我用过这样的东西，它运行得很好。 您应该能够编写一个程序来分析您的数据以获得数字（唯一路径，文件名的数量，每个术语的平均参考数量等）。 从那里，你可以很容易地确定使用这种技术是否适合你。
链接地址: http://www.djcxy.com/p/39807.html