python - 压缩大量相似的字符串

Question

我正在查看维护大量字符串的 python 脚本。这些字符串实际上是来自回归测试运行的日志文件名的完整路径。文件数量太大，脚本开始达到虚拟地址空间限制。

像这样的字符串几乎没有熵，所以我认为压缩它们会很好。问题是我考虑的压缩库(如在 Python - Compress Ascii String 中讨论的那些)似乎单独压缩每个字符串(存储解压缩所需的所有信息)。常识表明，将整个字符串集压缩到单个全局 blob/字典中并使用某种短引用来引用单个字符串在空间方面效率更高。

这里有一些(伪)代码来阐明这个想法:

class TestResult:
    def __init__(self):
        self._Id         = None
        ....
        self.__appLogList = []
        return
....
    def setAppLogList(self, currentAppLogList):
        self.__appLogList = currentAppLogList
        # what I want to do here instead is 
        # for each s in currentAppLogList
        # add s to global compressed blob and
        # store reference in __appLogList

    def getAppLogList(self):
        return self.__appLogList
        self.__appLogList = currentAppLogList
        # what I want to do here instead is 
        # currentAppLogList = []
        # for each ref in __appLogList
        # decompress ref into string s and add s to currentAppLogList
        # return currentAppLogList

# for each test
# add new TestResult to result map
# setAppLogList

# for selected tests
# getAppLogList and access logs

这是否可以使用现有的公开可用的 Python 库来实现？

Answer 1

这是我之前回答的变体或扩展。主要区别在于它能够通过利用字符串实际上是可能包含一个或多个公共(public)子组件的文件路径这一事实来“压缩”字符串。通过从该信息构建树数据结构来消除这种冗余，这意味着对于任何给定级别，每个唯一的组件值仅存储一次。树数据结构本身是使用本质上是字典的字典来实现的。由于使用了内置的 reduce() 函数，它的创建应该相对较快。

下面的更新版本现在有一个属性——与以前的版本不同——创建的内容可以被腌制，这意味着它可以保存并在以后从文件中原封不动地读回。

和我一样answer ，这不是你所谓的“真正的”压缩，但是我认为做类似的事情对于你想要完成的事情来说可能有点矫枉过正，因为这会解决你的问题，相对较快，而且维护起来会更简单，增强，并在以后扩展。

import collections
import cPickle as pickle  # use C version for performance
import operator
import os

class DefaultDict(collections.defaultdict):
    """  pickle-able defaultdict """
    def __reduce__(self):
        args = (self.default_factory,) if self.default_factory else tuple()
        return type(self), args, None, None, self.iteritems()

def Tree(): return DefaultDict(Tree)
class Leaf(object): pass

def print_tree(d, level=0, indent=' '*4):
    """ Tree structure pretty printer """
    if not d:
        print indent * level + '<empty>'
    else:
        for key, value in sorted(d.iteritems()):
            print indent * level + str(key)
            if isinstance(value, dict):
                print_tree(value, level+1, indent)
            elif not isinstance(value, Leaf):
                print indent * (level+1) + str(value)

# create Tree structure from paths
tree = Tree()
LEAF = Leaf()
with open('log_file_paths.txt') as inf:
    for line in inf:
        path = line.strip().split(os.sep)
        reduce(operator.getitem, path[:-1], tree)[path[-1]] = LEAF
print_tree(tree)

# save tree to a file
with open('file_tree.pk', 'wb') as outf:
    pickle.dump(tree, outf, pickle.HIGHEST_PROTOCOL)

# try reading it back in
del tree
with open('file_tree.pk', 'rb') as inf:
    tree = pickle.load(inf)
print_tree(tree)  # display reconstituted tree

所以如果输入文件由这些文件路径组成:

tests/first/set1.log
tests/first/set2.log
tests/first/subfirst/set3.log
tests/first/subfirst/set4.log
tests/second/set5.log
tests/second/subsecond/set6.log
tests/second/subsecond/subsubsecond/set7.log
tests/third/set8.log

以下树结构是在内存中创建并显示(然后写入、回读和重新显示)以保存它们的内容:

tests
    first
        set1.log
        set2.log
        subfirst
            set3.log
            set4.log
    second
        set5.log
        subsecond
            set6.log
            subsubsecond
                set7.log
    third
        set8.log