2

Princetonの実装を使用して接尾辞配列を作成しました。ただし、私の基本的なテキストドキュメントは非常に大きく、結果の接尾辞配列のサイズは500MBを超えます。接尾辞配列を圧縮する方法はありますか？

ありがとう！

4

2 に答える 2

4

前の回答で述べたこととは逆に、接尾辞配列を圧縮できるだけでなく、実際には接尾辞ツリーの圧縮は通常、最初に接尾辞配列を使用してツリーをエミュレートし、次にそれを圧縮することによって実装されます。

接尾辞配列圧縮のすぐに使用できる Java 実装については知りません。さまざまな既存のアルゴリズムが複雑すぎて、ここで詳しく説明することはできません。詳細な説明と比較を提供する Navarro と Mäkinen による論文 (DOI 10.1145/1216370.1216372) があります。

しかし、大まかに言えば、2 つの一般的なアプローチがあります。

アプローチ A: 配列のサイズを直接縮小する (論文のセクション 7.1 を参照)。これには、サフィックス配列のエントリの一部のみを格納し、必要に応じて不足しているエントリを補間する必要があります。補間は、関数 (この論文では ψ と呼ばれます) を使用して実行されます。この関数は、それ自体が大きな配列 (ただし、元のサフィックス配列ほど大きくはありません) とインデックス付きビット ベクトルの形式で格納されます。

アプローチ B: FM アプローチ(論文のセクション 9 を参照)。ここで、接尾辞配列は基本的に、メインの辞書編集バケット (つまり、同じ最初の文字で始まる接尾辞のグループ) の開始位置 (接尾辞配列内) を示す比較的短い配列Cに置き換えられ、別の比較的大きなデータ構造Occと組み合わされます。これにより、いわゆる後方検索が可能になります。具体的には、検索パターン p=c 1 ..cmが与えられた場合、文字 c mのバケットを文字列 c m -1 c mのより小さいバケットに繰り返し絞り込み、さらにc mのバケットに絞り込むことができます。 -2c _完全なパターン p の最終的な範囲が見つかるまで、m-1 c mなど。これを可能にするデータ構造Occは大きいですが、さまざまな手法、特にウェーブレット ツリーを使用して圧縮できます。

検索パフォーマンスへの影響
上記の論文には、慎重な分析と比較が含まれています。しかし、大まかに言えば、接尾辞配列を圧縮すると、長さ m のパターン (慎重に実装すれば、圧縮されていない接尾辞配列では O(m) になる可能性があります) の検索が、テキスト全体の長さ。さらに、ウェーブレット ツリーを使用するアプローチは、アルファベットのサイズにさらに依存することを意味します。

于 2012-02-23T05:26:52.853 に答える
0

私の知る限りでは、接尾辞配列を圧縮することはできません (私が知らないだけかもしれません) が、接尾辞ツリーを圧縮することはできます。したがって、データ構造の変更を検討するかもしれません。Google 圧縮サフィックス ツリーのみ。

それらは大量のデータを保存できるため、遺伝子配列決定や一般的な部分文字列の問題で頻繁に使用されます。

説明はここにあります: http://bioinformatics.oxfordjournals.org/content/23/5/629.abstract
下部のリンクをたどると、圧縮されたサフィックスのコードをダウンロードできるこのページに移動します。ツリー: http://www.cs.helsinki.fi/group/suds/cst/

于 2012-02-23T04:07:55.583 に答える