压缩大量相似字符串集合

Question

压缩大量相似字符串集合

4

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

这些字符串的熵值很小，因此我认为压缩它们会很好地解决问题。问题在于，我考虑的压缩库（如在Python - Compress Ascii String中讨论的那些）似乎单独压缩每个字符串（存储所有需要解压缩的信息）。常识表明，将整个字符串集合压缩成单个全局blob/dictionary，并使用某种短引用引用单个字符串，从空间上来说更加高效。

以下是一些（伪）代码以澄清这个想法：

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库，是否可以实现这个功能？

- glagolig

2

你有那么多字符串导致超过了虚拟机的限制？对于32位机器，在大约1-2GB左右就会发生这种情况...我们在谈论多少个文件名？ - nneonneo

2

字符串长度的分布情况是什么？预期的字符串数量是多少？例如，是否有许多常见前缀，或者“熵小”的分布在所有索引位置上是否更或多或少均匀？您需要使用内存方法还是可以将信息存储在磁盘上？所有字符串中出现了多少个不同的字符（即，“字母表”是什么）？ - Tim Peters

4

与其压缩列表，也许使用树形结构会更合适...... - twalberg

2

将整个字符串集压缩成单个文件的问题在于这样做可能需要一次性将它们全部存储在内存中。为了避免这种情况，您需要将它们全部写入文件，然后通过两次读取文件来进行分析和压缩。您最好的选择可能是使用另一种数据结构，比如已经建议过的分层树结构。 - martineau

2

使用字典树。每个节点是一个路径段，叶子节点是文件名。如果每个节点都有指向其父节点的指针，则可以通过沿着父链向上行走到根来轻松重构完整路径名。维基百科文章中有一个Python实现的基于字典的Trie。 - Jim Mischel

显示剩余7条评论

4个回答

2

这是我能想到的最简单的可能有效的方法。它通过仅在字典中存储每个唯一的目录路径来“压缩”数据。给定目录中的所有文件都存储在一个list中。为了测试目的，下面的示例代码只读取由每行组成的一个完整文件路径的输入文件。

from collections import defaultdict
import os

directories = defaultdict(list)

with open('log_file_paths.txt') as inf:
    for path in (line.strip() for line in inf):
        dir_path, file_name = os.path.split(path)
        directories[dir_path].append(file_name)

for path in directories:
    print path
    for file_name in directories[path]:
        print '   ', file_name

- martineau

这就是想法。但我想使用一个“真正”的压缩算法，它可以在字符串中重复使用任何模式，而不仅仅是前缀。 - glagolig

1

我没有找到现成的实现来解决这个问题，而且时间有限。目前似乎不存在这样的实现。以下是我考虑过的一些方向。

后缀数组是建议使用的字典树的当代替代品。后缀数组可以用于非常高效地实现子字符串搜索。然而，如何立即将它们用于我的问题还不清楚。后缀数组概述：Puglisi、S.J.、Smyth、W.F.和Turpin、A.H.(2007)。后缀数组构造算法的分类。ACM计算调查(CSUR)，39(2)，4。

这项研究直接适用于我的问题：Brisaboa、N.R.、Cánovas、R.、Claude、F.、Martínez-Prieto、M.A.和Navarro、G.(2011)。压缩字符串字典。在实验算法中(pp.136-147)。Springer Berlin Heidelberg。不幸的是，没有可下载和重复使用的实现。

语法基础解析器：Larsson, N. J.和Moffat, A.（2000）。离线基于字典的压缩。IEEE会议论文集，88（11），1722-1732。该实现可用。为了计算语法，所有字符串都需要保存在内存中。我可以收集前1000个字符串并计算语法；或者我可以进行完整运行（直到内存失败），记录所有字符串并计算语法。可能存在问题：字符串随时间演变（名称包括日期/时间）。压缩率不是最优的；此外，如果有一个字符串不适合预先计算的语法，那么会发生什么并不清楚。也许这样的字符串根本不会被压缩。这种解决方案不如以前的研究效率高，并且仍需要大量的编码和测试工作。

- glagolig

你能否将一小部分的URL上传到某个地方，大约200MB就可以了。在我看来，Patricia Trie会更加有用。就路径而言，你们有共同的开头，但路径在结尾处不同。我或许能够帮你找到解决方案。 - Anupam Saini

我已经在数据库记录修改方面做过类似的事情，修改路径的解决方案不应该很困难。 - Anupam Saini

谢谢。我一直在寻找像Brisaboa等人的想法实现那样长期公开并被社区积极使用的东西。我不想插入新编写的代码，也无法说服我的团队这么做。最好的办法是将测试套件分成几个部分。 - glagolig

1

目前，我只有一个Java解决方案。您可以将其用作独立脚本。请在代码中更改此处的值为您文件的路径并执行。

您可以根据需要修改搜索方法。该项目还具有Ant脚本，如果需要，您可以进行自定义。

例如，如果您正在搜索文件名：

sipproxy0-dc0-auto-node-aware-10.20131021_213407_288.snapshot.log

你需要提供完整的路径，例如：

C:\ccview\aglagole_2_cloudute\tserver_ddpsf\siptserver\CloudUte\unittest\worker_log\aglagole\logs\sipproxy0-dc0-auto-node-aware-10.20131021_213407_288.snapshot.log

为了降低内存使用，我建议你为每行中的共同部分生成哈希值（Google的Guava库有一个相当不错的实现）。

C:\ccview\aglagole_2_cloudute\tserver_ddpsf\siptserver\CloudUte\unittest\worker_log\aglagole\logs

如果遇到任何内存问题，请告诉我。

- Anupam Saini

以防我对代码进行更改后使其无用 :) 一切正常的最后一次提交为：eeb838e17bd2828988c9b5f1a1e69ffd600afd3f - Anupam Saini

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- martineau · Accepted Answer

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

下面的更新版本现在具有以下属性，与以前的版本不同，所创建的内容可以被pickle，这意味着它可以保存并稍后从文件中完整读取。

与我的其他答案一样，这并不是做你所谓的“真正”的压缩，但我认为像这样做可能会过度杀伤力，因为这将解决您的问题，速度相对较快，而且以后维护，增强和扩展也会更简单。

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