9

誰かが以前にこれを解決したに違いないが、私の検索は空になっている。

各単語の開始位置と長さを追跡しながら、単語のリストをバッファーにパックしたいと思います。秘訣は、冗長性を排除してバッファを効率的にパックしたいということです。

例：人形のドールハウスの家

これらは、位置0から始まる4文字、0で9文字、3で5文字でdollhouseあることを思い出して、単純にバッファにパックできます。dolldollhousehouse

私がこれまでに思いついたのは：

  1. 単語を最も長いものから最も短いものに並べ替えます:(ドールハウス、家、人形）
  2. バッファをスキャンして、文字列がサブ文字列としてすでに存在するかどうかを確認します。存在する場合は、場所をメモします。
  3. まだ存在しない場合は、バッファの最後に追加します。

長い単語には短い単語が含まれていることが多いため、これはかなりうまく機能しますが、大幅に改善できるはずです。たとえば、単語リストを拡張してラグドールを含めると、私のアルゴリズムは。dollhouseragdollよりも効率が悪くなりragdollhouseます。

これは前処理のステップなので、速度についてはそれほど心配していません。O（n ^ 2）で問題ありません。一方、私の実際のリストには数万の単語が含まれているため、O（n！）はおそらく問題外です。

ちなみに、このストレージスキームは、TrueTypeフォントの「name」テーブルのデータに使用されます。http://www.microsoft.com/typography/otspec/name.htm

4

8 に答える 8

15

これは最短のスーパーストリングの問題です。サブストリングとして指定されたストリングのセットを含む最短のストリングを見つけます。このIEEEペーパー（残念ながらアクセスできない可能性があります）によると、この問題を正確に解決することはNP完全です。ただし、ヒューリスティックソリューションは利用可能です。

最初のステップとして、他の文字列のサブ文字列であるすべての文字列を見つけて削除する必要があります（もちろん、含まれている文字列に対する相対的な位置を何らかの方法で記録する必要があります）。これらの完全に含まれる文字列は、一般化された接尾辞木を使用して効率的に見つけることができます。

次に、オーバーラップが最も長い2つのストリングを繰り返しマージすることにより、長さが可能な最小長の4倍以上のソリューションを生成することが保証されます。コンラッド・ルドルフの回答に対するZifreのコメントで示唆されているように、2つの基数木を使用することで、オーバーラップサイズをすばやく見つけることができるはずです。または、一般化された接尾辞木をなんとかして使用できるかもしれません。

申し訳ありませんが、まともなリンクを掘り下げることができません。ウィキペディアのページや、この特定の問題に関する公的にアクセス可能な情報はないようです。ここでは簡単に説明しますが、推奨される解決策は提供されていません。

于 2009-05-10T14:54:06.247 に答える
1

私は大学に戻って、簡単な圧縮プログラムの実装を担当するラボを行いました。

私たちが行ったことは、これらの手法をテキストに順番に適用することでした。

  • BWT（Burrows-Wheeler変換）：文字を同一の文字のシーケンスに並べ替えるのに役立ちます（ヒント*実際に回転を行う代わりに文字を取得するための数学的な置換があります）
  • MTF（Move to front transform）：文字のシーケンスを動的リストのインデックスのシーケンスとして書き換えます。
  • ハフマン符号化：可変長コードテーブルを構築するエントロピー符号化の形式で、頻繁に遭遇するシンボルには短いコードが与えられ、まれにしか遭遇しないシンボルには長いコードが与えられます。

ここで、課題ページを見つけました。

元のテキストを元に戻すには、（1）ハフマンデコード、（2）逆MTF、（3）逆BWTを実行します。Interwebsには、これらすべてに関する優れたリソースがいくつかあります。

于 2009-05-10T14:05:11.647 に答える
1

基数木が使えると思います。リーフと親へのポインタのためにいくらかのメモリが必要ですが、文字列を一致させるのは簡単です（O（k）（kは最長の文字列サイズ）。

于 2009-05-10T13:28:00.677 に答える
1

ここでの私の最初の考えは、データ構造を使用して、文字列の一般的なプレフィックスとサフィックスを決定することです。次に、これらの接頭辞と接尾辞を考慮して単語を並べ替えます。これにより、希望の結果が得られますragdollhouse。

于 2009-05-10T13:31:58.513 に答える
1

NP完全であるナップサック問題に似ているため、「決定的な」アルゴリズムはありません。

于 2009-05-10T13:48:07.660 に答える
1

手順3を調整します。

  • 現在のリストを調べて、リスト内の単語が現在の単語の接尾辞で始まっているかどうかを確認します。（接尾辞をある長さより長く（たとえば、1より長く）維持したい場合があります）。
  • はいの場合は、既存の単語の接頭辞としてこの単語に個別の接頭辞を追加し、既存のすべての参照を適切に調整します（遅い！）
  • いいえの場合、現在のステップ3のように、リストの最後に単語を追加します。

これにより、例に保存されているデータとして「ragdollhouse」が得られます。それが常に最適に機能するかどうかは明らかではありません（たとえば、単語リストに「barbiedoll」と「dollar」が含まれている場合）。

于 2009-05-10T15:45:40.137 に答える
0

私はこのホイールをもう一度発明するつもりはありません。すでに膨大な量の人的資源が圧縮アルゴリズムに費やされています。すでに利用可能なものの1つを利用してみませんか？

ここにいくつかの良い選択があります：

Javaを使用している場合、gzipはすでに統合されています。

于 2009-05-10T15:10:25.720 に答える
0

何をしたいのかはっきりしていません。

検索などの操作を妥当な時間で可能にしながら、メモリを意識した方法で文字列を格納できるデータ構造が必要ですか？

圧縮された単語の配列が必要ですか？

最初のケースでは、パトリシアトライまたはストリングBツリーに行くことができます。

2番目のケースでは、次のようなインデックス圧縮技術を採用できます。

あなたが次のようなものを持っている場合：

aaa 
aaab
aasd
abaco
abad

次のように圧縮できます。

0aaa
3b
2sd
1baco
2ad

番号は、前の文字列との最大の共通プレフィックスの長さです。たとえば、そのスキーマを微調整できます。迅速な再構築のために、K語の後に共通プレフィックスの「再起動」を計画する

于 2009-05-10T15:23:01.483 に答える