基本的な正規表現は問題なく実行できますが、これは少し異なります。つまり、パターンがどうなるかわかりません。
たとえば、同様の文字列のリストがあります。
lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt']
この場合、共通のパターンは共通のテキストの 2 つのセグメントです:'sometxt'と'moretxt'で始まり、可変長の別の何かで区切られています。
もちろん、共通文字列と変数文字列は、任意の順序で任意の回数発生する可能性があります。
文字列のリストを共通部分と個々のバリエーションに圧縮/圧縮する良い方法は何でしょうか?
出力例は次のようになります。
c = ['sometxt', 'moretxt']
v = [('a','0'), ('b','1'), ('aa','10'), ('zz','999')]
このソリューションは、2 つの最も長い一般的な部分文字列を見つけ、それらを使用して入力文字列を区切ります。
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 != '')
これは、ボールを転がすのに恐ろしいものです。
>>> 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', '')
そのまったくの醜さがより良い解決策を刺激することを願っています:)
これは、最長共通サブシーケンスの問題の例のようです。1 つの方法は、差分がどのように生成されるかを確認することです。Hunt-McIlroy アルゴリズムは最初のアルゴリズムのようであり、特に明らかに非ヒューリスティックであるため、最も単純です。
最初のリンクには、詳細な説明と (疑似) コード例が含まれています。もちろん、私はここで完全に軌道に乗っているわけではありません。
これは、データ (テキスト) 圧縮のLZWアルゴリズムによく似ています。あなたのニーズに適応できるかもしれないPythonの実装がそこにあるはずです。
頻繁に繰り返されるこれらのサブストリングについて、アプリオリな知識はないと思います。
文字列で頻繁に発生する部分文字列 (パターン) を特定することから始めるべきだと思います。文字列のセット内の部分文字列を素朴にカウントするのはかなり計算コストがかかるため、スマートなものを考え出す必要があります。
一般化された接尾辞ツリー を使用して、大量のデータで部分文字列のカウントを行いました(例はこちら)。データ内で最も頻繁に使用される部分文字列/パターンがわかれば、そこから取得できます。
既知のテキストを下書きしてから分割するのはどうですか?
import re
[re.sub('(sometxt|moretxt)', ',', x).split(',') for x in lst]
# results in
[['a', '0', ''], ['b', '1', ''], ['aa', '10', ''], ['zz', '999', '']]