3

私は弦の大きなセットを持っています。文字列を次のようなサブセットに分割したい:

  1. サブセット内の各アイテムは、1 つ以上の連続する文字を共有します。
  2. サブセットを定義する共有連続文字は、サブセットのセットに対して一意です (つまり、共有文字は、他のサブセットと相互に排他的な関係にある文字列のサブセットを定義するのに十分です)。
  3. サブセットはほぼ同じサイズです。
  4. 結果として得られるサブセットのセットは、上記の基準に適合するために必要なサブセットの最小数です。

たとえば、次の一連の名前があるとします。

アラン、ラリー、アルフレッド、バーバラ、アルフォンス、カール

このセットを同じサイズの 2 つのサブセットに分割できます。連続する文字「AL」によって定義されるサブセット 1 は、次のようになります。

アラン、アルフレッド、アルフォンス

連続する文字 ar によって定義されるサブセット 2 は次のようになります。

ラリー、バーバラ、カール。

任意の文字列セットに対してこれを行うアルゴリズムを探しています。結果として得られるサブセットのセットは 2 である必要はありませんが、最小セットである必要があり、結果のサブセットはほぼ等しくなる必要があります。

エリオット

4

2 に答える 2

2

http://en.wikipedia.org/wiki/Suffix_arrayをご覧ください。本当にやりたいのは、ドキュメントごとに接尾辞配列を作成し、それらがすべての接尾辞配列を元のバージョンへのポインターとマージすることです。これにより、コレクションを1つとして文字列として検索できます。配列の接尾辞としてそれのために。

于 2012-04-05T04:24:45.773 に答える
2

これはトリッキーです。もっと高い目的（単語のインデックス作成など）があるのだろうか、それともこれは単なる学術的な問題なのでしょうか?

空のシーケンス (すべての単語で発生する) によって定義された単一のセットの自明な解決策を受け入れない限り、一般的に解決することはできません。たとえば、次の文字列を考えてみましょう: a, ab, b.

  1. aによって定義されたセットに入らなければなりませんa。
  2. bによって定義されたセットに入らなければなりませんb。
  3. ab両方のサブシーケンスが含まれているため、両方に入る必要があります。

あなたが扱っている言葉の種類で同様の例が発生しますか? 知らない。おそらく、複数のセットに対応する単語を処理したり、単語を配置する場所を決定するタイブレーク システムを使用したりすることができます。

これが問題ではないと仮定すると、burrows-wheeler 変換は適切な部分文字列を見つけるのに役立つかもしれません。

または次のようなものはどうですか：

  1. 単語内のすべてのサブシーケンスを生成します。
  2. サブシーケンスの干渉グラフを作成します。2 つのサブシーケンスが 1 つの単語に含まれている場合は、それらを接続するエッジを使用します。
  3. グラフに色を付けます。
  4. 各色の代表的なサブシーケンスを選択します。
  5. 各代表部分配列によって定義されたセットを作成します。その色のすべての単語がその部分文字列を持っている場合、それらすべてをそのセットに入れます。
  6. それ以外の場合は、その部分文字列をグラフから削除し、手順 3 から繰り返します。

このアルゴリズムはおそらく壊れていますが、解決策についてのアイデアが得られるかもしれません (または、少なくとも質問のトリッキーさについてのアイデア ;-)。

于 2012-04-05T01:33:17.923 に答える