Распознавание / сжатие паттерна Python

Question

Я могу сделать базовое регулярное выражение, но это немного отличается, а именно, я не знаю, каким будет шаблон.

Например, у меня есть список похожих строк:

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

В этом случае общим шаблоном являются два сегмента общего текста: 'sometxt' и 'moretxt', начинающиеся и разделенные чем-то другим, имеющим переменную длину.

Общая строка и переменная строка могут, конечно, встречаться в любом порядке и в любом количестве случаев.

Что было бы хорошим способом сжать / сжать список строк в их общие части и отдельные варианты?

Пример вывода может быть:

c = ['sometxt', 'moretxt']

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

Answer 1

Это решение находит две самые длинные общие подстроки и использует их для разделения входных строк:

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 != '')

Answer 2

Вот страшный момент, чтобы заставить мяч катиться.

>>> 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', '')

Я надеюсь, что ее безобразие вдохновит на лучшие решения :)

Answer 3

Это, похоже, пример самой длинной общей последовательности подпоследовательностей . Один из способов - посмотреть, как генерируются diffs . Алгоритм Ханта-Макилроя , кажется, был первым, и он настолько прост, тем более, что он, по-видимому, не эвристический.

Первая ссылка содержит подробное обсуждение и (псевдо) примеры кода. Предположим, конечно, что я не совсем в курсе.

Answer 4

Это похоже на алгоритм LZW для сжатия данных (текста). Там должны быть реализации Python, которые вы можете адаптировать к вашим потребностям.

Полагаю, у вас нет априорных знаний об этих подстроках, которые часто повторяются.

Answer 5

Полагаю, вам следует начать с определения подстрок (шаблонов), которые часто встречаются в строках. Поскольку наивный подсчет подстрок в наборе строк довольно затратен в вычислительном отношении, вам нужно придумать что-нибудь умное.

Я сделал подсчет подстрок для большого количества данных, используя обобщенные суффиксные деревья (пример здесь) . Как только вы узнаете наиболее часто встречающиеся подстроки / шаблоны в данных, вы можете взять их оттуда.

Answer 6

Как насчет замены известного текста, а затем разделения?

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