2

私はアルファベット{A, B, C}とこのアルファベットの上に（大きな）数の単語を持っています:(
AAABBCABBCCCCAA, ABBBCCC, BBBBCACAC, ...異なる長さ、異なる組み合わせ）

これらの単語を説明できる正規表現のセット（小さいほど良い）を探しています。(BC)+私はコンパクト（より）が好きBCBCです。宿題ではありません。

  1. これを行うための良い方法は何ですか？
  2. すでにこれを行っているPythonパッケージはありますか？

この質問は関連していることがわかりました。

更新：私はよりも好き(BC)+だと言ったときに急いでいたかもしれませんBCBC。私はできるだけ少ない表現を使用することを好みます（最悪の場合、文字列ごとに1つの正規表現があります）。したがって、、、または説明のいずれか（たとえば）の優先度はA+、AA他AA+のAA文字列が示すパターンに依存する必要があります。

4

2 に答える 2

1

私があなたの問題を正しく理解しているなら、あなたはアルファベットとそのアルファベットの文字列のリストを持っていて、それらの文字列に完全に一致するパターンを構築したいと思っています。

おそらく、文字列ごとに決定性有限オートマトンを構築し、それらすべてのDFAの組み合わせである非決定性有限オートマトンから構築することができます。次に、 DFAをNFAに単純化します。次に、NFAをパターンに変換するだけです。

これは、文字列の代わりにすでにパターン化されている場合でも機能します。ただし、可能な限り最小のパターンが得られるという保証はありません。

PythonでDFAまたはNFAを操作するためのライブラリを知りません。

于 2013-02-15T22:21:16.140 に答える
0

これらの単語を使用して文字列を処理する方法はいくつかありますが、正規表現が必要なのは最初の方法だけです。

strings =['AAABBCABBCCCCAA', 'ABBBCCC', 'BBBBCACAC']

import re
for string in strings:
    matches = re.findall(r'([A-C]+)', string)
    if matches:
        print matches[0]

出力：

AAABBCABBCCCCAA
ABBBCCC
BBBBCACAC

または、単語の正規表現で何をしようとしていたかに応じて、次のようなものを使用できる場合があります。

from itertools import groupby
results = [(string, [''.join(g) for k, g in groupby(string)]) for string in strings]
print
for result in results:
    print '{}: {}'.format(*result)

出力：

AAABBCABBCCCCAA: ['AAA', 'BB', 'C', 'A', 'BB', 'CCCC', 'AA']
ABBBCCC: ['A', 'BBB', 'CCC']
BBBBCACAC: ['BBBB', 'C', 'A', 'C', 'A', 'C']
于 2013-02-15T23:43:25.880 に答える