冗長正規表現を削除しますか？

Question

非常に単純な正規表現のリストが文字列として表現されているとします（「非常に単純」という意味で、.*のみを意味します）。リスト内のすべての文字列が始まり、末尾は.*です。例えば、私は私がやりたい

rs = [.*a.*, .*ab.*, .*ba.*cd.*, ...] 

何を持っている可能性があり、別のサブセットであるこれらのパターンを追跡することです。この例では.*a.*はすべて.*ab.*と一致します。したがって、私は後者のパターンが冗長であると考えます。 1 startswith他の場合

私は何を思ったことは.*に文字列を分割することでしたが、対応する要素、およびテストを一致させます。具体的には、.*a.*と.*ab.*と考えてください。 .*

a = ['', 'a', ''] 
b = ['', 'ab', ''] 

とzipのpingにこれらの分割それら一緒に、その後

c = [('', ''), ('a', 'ab'), ('', '')] 

そして、

all(elt[1].startswith(elt[0]) for elt in c) 

戻りTrueので、私は.*a.*が含まれている場合.*ab.*が実際に冗長であると結論を与えますリスト。

これは意味がありますか、それは私がやろうとしていることをしていますか？もちろん、このアプローチはいくつかの理由で複雑になるため、私の次の質問は誰も以前に遭遇したこれを行う良い方法があるということですか？

Answer 1

この問題では、正規表現と正規表現の両方について最小限のDFAを見つけて比較する必要があります。ここ
は、すべての文字の組み合わせが.*に囲まれ、途中でそれを持っていない、アプローチはほとんどうまくいくと仮定すると、同じproblem- How to tell if one regular expression matches a subset of another regular expression?

Answer 2

の議論のリンクです。しかし、startswithの代わりにcontainsをチェックする必要があります。

reglist = ['.*a.*', '.*ab.*', '.*ba.*', '.*cd.*'] 
patterns = set(x.split('.*')[1] for x in reglist) 
remove = [] 
for x in patterns: 
    for y in patterns: 
     if x in y and x != y: 
      remove.append(y) 

print (['.*{}.*'.format(x) for x in sorted(patterns - set(remove))])  

はあなたにこの中

['.*a.*', '.*cd.*']