9

私の質問をより明確に説明するために、私が直面している実際の事例を説明することから始めます。

文章を構成するために、選択的に点灯できる多くの単語を含む物理的なパネルを構築しています。これは私の状況です：

  1. 表示したい文章をすべて知っています
  2. すべての文を表示できる、注文された単語の最短セットを見つけたい

例：

 SENTENCES:
 "A dog is on the table"
 "A cat is on the table"
 SOLUTIONS:
 "A dog cat is on the table"
 "A cat dog is on the table"

私は、すべての文で使用されているすべての単語のセット内の各一意の単語について、その左側または右側にどの単語を配置するかを見つける「位置規則」を使用して、この問題にアプローチしようとしました。上記の例では、「on」という単語のルールセットは「left（A、dog、cat、is）+ right（the、table）」になります。

このアプローチは些細なケースでも機能しましたが、私の実際の状況には、私を立ち往生させた2つの追加の問題があり、それは両方とも言葉を繰り返す必要性と関係があります。

  1. 文中の繰り返し：「猫はテーブルの上にいます」には2つの「the」があります。
  2. 循環参照：「赤い猫」+「私の猫はテーブルの上にいます」+「そのテーブルは赤い」という3つの文のセットでは、ルールでは、REDはCATの左側にあり、CATはTABLEの左側とTABLEはREDの左側にある必要があります。

そのための私の質問は次のとおりです。

この種の問題を研究して解決するアルゴリズムのクラスは何ですか（またはさらに良い：特定のアルゴリズムは何ですか）？いくつかのリファレンスまたはそのコード例を投稿できますか？

編集：複雑さのレベル

最初の回答から、実際の複雑さのレベル（つまり、文が互いにどれだけ異なるか）が重要な要素であるように見えます。だから、ここにそれに関するいくつかの情報があります：

  1. 表現したい文が約1500あります。
  2. すべての文は、基本的に、数語だけが変更される最大10文の制限されたプールの変更です。前の例に基づいて、私のすべての文章が「家具に対する誰かのペットの位置」または「誰かの家具の物理的な説明」のいずれかについて話すのと少し似ています。
  3. すべての文を構成するために使用される一意の単語の数は100未満です。
  4. 文の長さは最大8語です。

このプロジェクトではPythonを使用していますが、適度に読みやすい言語（例：難読化されていないperl！）であれば問題ありません。

よろしくお願いします！

4

4 に答える 4

10

私の理解が正しければ、これは最短共通超配列問題に相当します。この問題は NP 完全ですが、近似アルゴリズムが存在します。Googleは、これを含むいくつかの論文を見つけました。

2 つの入力シーケンスの場合、問題は単純な DP アルゴリズムで解決できますが、これは複数のシーケンスには一般化されません。これは、各シーケンスでは基本的に DP テーブルにディメンションを追加する必要があり、指数関数的な爆発が発生するためです。

于 2011-04-26T03:40:46.910 に答える
6

私はバイオインフォマティシャンですが、これは、無限のミスマッチ ペナルティ (つまり、ミスマッチを完全に禁止する) と適度なギャップ ペナルティ (つまり、ギャップを許可しますが、より少ないギャップを好む) を使用して、すべての文のグローバルな複数配列アラインメントを実行することで解決できるように思えます。次に、ギャップレスコンセンサスシーケンスを読み取ります。

この定式化が問題と同等である場合、妥当な時間内に実行されるヒューリスティック アルゴリズムは多数存在しますが、多重配列アラインメントは NP 完全であるため、問題が実際に NP 完全であることを意味します。残念ながら、ほとんどの MSA アルゴリズムは、英語の単語ではなく、DNA またはタンパク質配列の文字を処理するように設計されています。

例

これは、OP によって与えられた 3 つの文のセットを使用して、私が説明する種類のアラインメントの例です。私が提供するアラインメントが最適かどうかはわかりませんが、考えられる解決策の 1 つです。ギャップは一連のダッシュで示されます。

文 1: ---- -- 赤い猫 -- -- --- ----- -- ---
文 2: ---- 私の - --- 猫がテーブルの上にいます -- ---
文 3: あの -- -- -- -- -- -- -- -- -- テーブルは赤い
コンセンサス：私のA赤い猫がテーブルの上にいるのは赤です

この方法の利点の 1 つは、アラインメントによって単語の完全なシーケンスが得られるだけでなく、どの単語がどの文に属しているかがわかることです。

于 2011-04-26T02:33:21.157 に答える
2

実際の証拠はありませんが、問題が NP 完全でも NP 困難でもないとしたら、非常に驚​​くでしょう。最良の答えを与えることが保証されているアルゴリズムを見つけることができます。しかし、妥当な長さの少数のセンテンス (たとえば、それぞれ 8 語の 16 センテンス) でさえ、行き詰まり、合理的な時間内に実行されません。したがって、正確な答えを探すのではなく、合理的なアルゴリズムを提供する優れたヒューリスティックを探すことをお勧めします。

私が提案するヒューリスティックは、文のペアを取り、それらに対してhttp://en.wikipedia.org/wiki/Longest_common_subsequence_problemを解決することです (解決策は Python 標準ライブラリにあります。difflib を調べてください)。競合するセクションをランダムに選択し、ペアをその 1 つの文に置き換えます。すべての文章でこれを行うと、OK ソリューションが得られます。素晴らしいものではありませんが、OKです。

賢くなりたい場合は、漸進的な改善を探したり、これを複数回実行したり、それらの違いをランダムに解決する方法を賢く試したりすることができます.

于 2011-04-26T02:13:07.097 に答える
1

1 週間のコーディング (これは趣味のプロジェクトです) の後、私は自分の質問に答えることにしました。これは、私が以前に得た回答が十分ではなかったからではなく、それらのうちの 3 つを使用して私が望む解決策をコーディングしたためであり、回答者の 1 人だけにクレジットを与えるのは間違っていると感じたからです。満足のいく解決策を考え出すために、それらの3つによって。

最後から始めましょう: 私が思いついたヒューリスティックは、非常に満足のいく結果をもたらします (少なくとも、私が使用している実際のケースでは)。それぞれ平均 6 語からなる 1440 の文があり、70 の一意の単語のセットを使用していました。このプログラムの実行には約 1 分かかり、わずか 76 語のスーパーシーケンスが得られます (問題の「物理的」[しかし「論理的」ではない] 下限よりも 10% 多い)。

ヒューリスティックは、私の実際のケース、特にほとんどの文が約10個程度の「プロトタイプ」で構成されており（質問の編集のポイント＃2を参照）、4つの連続したステップで構成されているという事実に合わせて調整されています。 :

  1. 同形収縮
  2. 類似度の縮小
  3. 大まかな冗長性の最適化
  4. 細かい冗長性の最適化

同形収縮

A を B に変換し、B を A に変換するには、まったく同じ手順が必要になるなど、「同形」の 2 つの文 A と B を定義しました。例：

'A dog is on the carpet'
'A cat is under the table'

変換では常に、最初の文字列の位置 1、3、5 の単語を、2 番目の文字列の位置 1、3、5 の単語に変更する必要があります。

"A __ is __ the __"センテンスを「同形ファミリー」にグループ化すると、位置 1、3、5 の変数要素のリストを共通ルートに挿入するだけで、最適化されたスーパーストリングを簡単に作成できます。

類似度の縮小

プロセスのこの段階で、センテンスの数は劇的に減少しました (通常、同型ファミリーからの約 50 のスーパーシーケンスと、プール内の他のどのセンテンスとも同型ではなかったオーファン センテンスが混在しています)。プログラムはこの新しいプールを分析し、2 つの最も類似した文字列をマージします。次に、マージの結果とまだマージされていない文字列で構成される新しいセットに対して手順を繰り返し、すべてが1 つの超配列。

大まかな冗長性の最適化

この段階で、元の 1440 文すべてに対する有効なスーパーシーケンスが既にありますが、多くの用語がそれを必要とせずに繰り返されるため、そのようなスーパーシーケンスは非常に最適ではありません。この最適化ステップでは、スーパーシーケンスを使用してすべての文を定式化し、使用されていないすべての用語を削除するだけで、冗長な用語の大部分を削除します。

細かい冗長性の最適化

前の最適化の結果はすでにかなり良好ですが、この最後のステップで単語 2 を削除できる場合があります。ここでの最適化は、2 回以上繰り返される単語を見つけ、スーパーシーケンス内の同じ位置に向かって収束し、それでもすべての文を作成するために 2 つの連続する繰り返しを作成できるかどうかを確認することによって機能します。例: スーパーシーケンスが与えられた場合

aaa xxx bbb ccc ddd eee xxx fff

xxxプログラムは、2 つの単語を互いに近づけようとします。

aaa bbb xxx ccc ddd eee xxx fff
aaa bbb xxx ccc ddd xxx eee fff
aaa bbb ccc xxx ddd xxx eee fff

スーパーシーケンスが到達した場合:

aaa bbb ccc xxx xxx ddd eee fff

両方の出現をxxx同時に使用する文がない場合は、2 つのうちの 1 つをxxx使用できます。

もちろん、この最後の一節はxxx、一度に複数の位置をシフトすることで最適化できます (シェルの並べ替えとバブルの並べ替えを考えてください)。この「シフト手順」は他の場所でも使用されるため、この「あまり最適化されていない」手順です。

繰り返しになりますが、元のレスポンダーの皆さんに感謝します。あなたの意見は、この解決策を考えさせる上で最も重要でした。このソリューションへのコメントも大歓迎です。

最終的な注意:プログラムが完成/プロジェクトが終了したらすぐに (最悪の場合は数か月)、GPL でリリースし、元の質問にコード リポジトリへのリンクを追加します。質問を「お気に入り」としてマークすると、マーカーに編集が通知されるはずです....もちろん、実際のコードに興味がある場合に備えて！

于 2011-05-04T00:28:05.713 に答える