Python字符串模式识别/压缩

Question

Python字符串模式识别/压缩

pythonstringcompressionpattern-recognition

8

我可以做基本正则表达式，但这里有些不同，即我不知道模式将是什么。

例如，我有一个类似的字符串列表：

lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']

在这种情况下，常见的模式是两个共同文本段：'sometxt'和'moretxt'，它们由长度可变的其他内容开头和分隔。

共同字符串和可变字符串当然可以以任何顺序和任意次数出现。

有什么好的方法可以将字符串列表压缩为它们的公共部分和各自的变化部分？

一个示例输出可能是：

c = ['sometxt', 'moretxt']

v = [('a','0'), ('b','1'), ('aa','10'), ('zz','999')]

- iCy

2

这听起来很难。如果您提供更多背景信息，例如说明为什么必须使用这种压缩方案，则可能会有所帮助。 - unwind

1

等等，你不知道sometxt和moretxt是什么，也不知道它们在哪里吗？那可真是个难题。 - SilentGhost

是的！给我们测试用例！ - codeape

抱歉如果我在问题中没有表达清楚，我不知道'sometxt'和/或'moretxt'是什么。输入是一系列用户定义的文本和机器生成的字符序列。我必须确定每个输入项中的静态字符串和动态序列是什么。 - iCy

不妨考虑寻找外部工具，例如 Frak：https://github.com/noprompt/frak - Christopher Oezbek

6个回答

3

这里有一个令人害怕的例子。

>>> import re
>>> makere = lambda n: ''.join(['(.*?)(.+)(.*?)(.+)(.*?)'] + ['(.*)(\\2)(.*)(\\4)(.*)'] * (n - 1))
>>> inp = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']
>>> re.match(makere(len(inp)), ''.join(inp)).groups()
('a', 'sometxt', '0', 'moretxt', '', 'b', 'sometxt', '1', 'moretxt', 'aa', '', 'sometxt', '10', 'moretxt', 'zz', '', 'sometxt', '999', 'moretxt', '')

我希望它丑陋的外观能激发更好的解决方案 :)

- Constantin

美丽的解决方案，速度有点慢，但我可以等待。丑陋并不影响我，好的代码价值连城。从没想过用正则表达式这种方式，但这已经超出了我的基础正则表达式知识。我正在尝试弄清楚如何将输出分成常量和变量的单独列表。 - iCy

2

@iCy，如果输入数据中从未遇到过某个字符（例如'\0'），则它的工作速度会显著提高。在这种情况下，请将两个''.join替换为'\0'.join。这还可以得到更漂亮的结果。 - Constantin

太棒了！是的，这些字符串只包含可打印字符。使用'\0'.join使它变得更快。 - iCy

是的，这大大加快了速度。不过我的解决方案仍然快200倍 :-) 如果有更多的测试用例会更好... - codeape

2

这看起来很像用于数据（文本）压缩的LZW算法。可能已经有Python实现，您可以根据自己的需求进行调整。

我假设您没有先验知识来识别这些经常重复的子字符串。

- Ber

2

这似乎是最长公共子序列问题的一个例子。一种方法是查看差异是如何生成的。Hunt-McIlroy算法似乎是第一个，也是最简单的算法，特别是因为它显然是非启发式的。

第一个链接包含详细的讨论和（伪）代码示例。当然，假设我没有完全离题。

- Mizipzor

是的，我也考虑过差异算法，只是不知道从哪里开始。 - iCy

1

我想你应该先识别在字符串中频繁出现的子串（模式）。由于在一组字符串中天真地计算子串是相当计算密集的，所以你需要想出一些聪明的方法。

我曾经使用广义后缀树（这里有一个例子）对大量数据进行了子串计数。一旦你知道了数据中最常见的子串/模式，你就可以从那里开始了。

- TC.

-1

把已知的文本替换掉，然后再分割怎么样？

import re
[re.sub('(sometxt|moretxt)', ',', x).split(',') for x in lst]
# results in
[['a', '0', ''], ['b', '1', ''], ['aa', '10', ''], ['zz', '999', '']]

- EMiller

3

OP不知道sometxt和moretxt是什么。 - SilentGhost

@SilentGhost 我不确定他是否这样做，老实说。这个问题相当不清楚。 - mavnn

@mavnn：让我们再读一遍：“也就是说，我不知道模式会是什么样子。” - SilentGhost

@SilentGhost：鉴于它遵循“我可以做基本的正则表达式...”，它可以被理解为“我不知道如何构造所需的正则表达式模式”，而不是“我不知道sometxt和moretxt的模式”。然而，在后一种情况下，这是一个更有趣的问题。 - mavnn

这就是 re.split 的用途。 - codeape

是的，我首先考虑了re.split - 但它会在结果中留下'sometxt'和'moretxt'。使用re.sub + split似乎可以更少地步骤来获得所请求的结果。 - EMiller

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

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

- codeape · Accepted Answer

这个方案找到两个最长的公共子字符串，并使用它们来分隔输入字符串：

def an_answer_to_stackoverflow_question_1914394(lst):
    """
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']
    >>> an_answer_to_stackoverflow_question_1914394(lst)
    (['sometxt', 'moretxt'], [('a', '0'), ('b', '1'), ('aa', '10'), ('zz', '999')])
    """
    delimiters = find_delimiters(lst)
    return delimiters, list(split_strings(lst, delimiters))

find_delimiters和其它函数用于查找分隔符：

import itertools

def find_delimiters(lst):
    """
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']
    >>> find_delimiters(lst)
    ['sometxt', 'moretxt']
    """
    candidates = list(itertools.islice(find_longest_common_substrings(lst), 3))
    if len(candidates) == 3 and len(candidates[1]) == len(candidates[2]):
        raise ValueError("Unable to find useful delimiters")
    if candidates[1] in candidates[0]:
        raise ValueError("Unable to find useful delimiters")
    return candidates[0:2]

def find_longest_common_substrings(lst):
    """
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']
    >>> list(itertools.islice(find_longest_common_substrings(lst), 3))
    ['sometxt', 'moretxt', 'sometx']
    """
    for i in xrange(min_length(lst), 0, -1):
        for substring in common_substrings(lst, i):
            yield substring


def min_length(lst):
    return min(len(item) for item in lst)

def common_substrings(lst, length):
    """
    >>> list(common_substrings(["hello", "world"], 2))
    []
    >>> list(common_substrings(["aabbcc", "dbbrra"], 2))
    ['bb']
    """
    assert length <= min_length(lst)
    returned = set()
    for i, item in enumerate(lst):
        for substring in all_substrings(item, length):
            in_all_others = True
            for j, other_item in enumerate(lst):
                if j == i:
                    continue
                if substring not in other_item:
                    in_all_others = False
            if in_all_others:
                if substring not in returned:
                    returned.add(substring)
                    yield substring

def all_substrings(item, length):
    """
    >>> list(all_substrings("hello", 2))
    ['he', 'el', 'll', 'lo']
    """
    for i in range(len(item) - length + 1):
        yield item[i:i+length]

split_strings 使用分隔符拆分字符串：

import re

def split_strings(lst, delimiters):
    """
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']
    >>> list(split_strings(lst, find_delimiters(lst)))
    [('a', '0'), ('b', '1'), ('aa', '10'), ('zz', '999')]
    """
    for item in lst:
        parts = re.split("|".join(delimiters), item)
        yield tuple(part for part in parts if part != '')