python - リスト内のサブリストを検索/認識し、挿入を可能にする最良の方法

Question

Pythonを使用して、特定のパターンを満たす可能性のあるリスト内のすべてのサブリストに一致させたいのですが、

例えば ​​：

 l = ['dummy', ',', 'as', 'it', 'is', 'an', 'example', '.', 
     'as', 'we', 'assume', 'it', 'is', '.', 
      'as', 'to', 'do', 'some', '.']

 sublist = ['as', '*', 'it']

と

mySub(l, sublist)提供=>[['as', 'it'], ['as', 'we', 'assume', 'it'], ['as', 'it', 'is', 'an', 'example', '.', 'as', 'we', 'assume', 'it']]

または他の例:

mySub(l, ['as', '*', 'it', '*', 'example'])提供 =>[['as', 'it', 'is', 'an', 'example'], ] mySub(l, ['as', '*', 'it', 'is'])提供 =>[['as', 'it', 'is'], ['as', 'it', 'is', 'an', 'example', '.', 'as', 'we', 'assume', 'it', 'is'], ['as', 'we', 'assume', 'it', 'is']]

l実際には、リストのリストになるため、私の問題はより複雑sublistであり、ランクベースでその一部を一致させる必要もあります。しかし、これは私が抱えている主な困難を図式化することです。それは、Python を使用してこの種の効率的なマッチングを行う方法です。（したがって、単純な正規表現マッチングでこの問題を解決しても役に立ちません）

「*」は正規表現に似ていることに注意してください。つまり、いくつかの項目をジャンプする可能性があります。また、明確でなくても、考えられるすべてのサブリストが必要です。そのため、マッチングのように貪欲に繰り返されるものもあります。

手がかり/リンク/興味深い考えがあればお願いします

よろしくお願いします

（バイオインフォマティクス/DNA配列とのマッチングに関するいくつかのアルゴリズムを覚えていますが、再び見つけることができませんでした）

Answer 1

あなたの問題は、動的計画法によって最も頻繁に解決される生物学における配列アラインメントに関連しています。また、NLP で使用されるパターン マッチング アルゴリズムを見ることもできます。Natural Language Toolkit (nltk) では、私が推測する関連する問題について説明する必要があります。

Answer 2

s1 = set(l)
s2 = set(sublist)
s1.intersection(s2)
[out]set(['as', 'it'])