再帰的なNグラムを使用してテキストを圧縮する

Question

ただ1つの値が残るまで、再帰的な2-Gramストレージを使用して大きなグループのテキストを1つの整数に分割するという考え方に慣れてきました。

table pair 
{ 
    id 
    first_parent_id (points to -> this.id) 
    second_parent_id (points to -> this.id) 
} 

は、例えば、次のコードに私は11ワード文（周期12）を有します。私はデータベース（ "this" + "is = ID＃1"）に各単語のペアを格納し、データベース（1 + 2 = ID＃7）に2組のワードペアを格納し、 1つの単語だけ左にセット - 番号「12」（私たちは、同じデータセットを持っている場合）、これは取るだろうが、我々は後方

------------------------12------------------------- 
----------------10---------------11---------------- 
-------7--------|--------8-------|-------9--------- 
---1---|--2-----|--3-----|-----4-|----5--|-------6- 
This is my group of words which I plan to compress. 

を動作することができますを使用して、その後12

This is my group of words which I plan to compress. 
---1---|--2-----|--3-----|-----4-|----5--|-------6- 
-------7--------|--------8-------|-------9--------- 
----------------10---------------11---------------- 
------------------------12------------------------- 

IDだろう各文字列を圧縮/解凍する膨大な作業量 - 内容を保存する必要のある種のアーカイブ作業で使用する可能性があるようですが、解凍プロセスがプロでないまれなケースを除いては決して読み込まれません傷み。

私はこれについて正しく考えていますか？単語列の可能な数はこのように格納するには大きすぎるでしょうか？ （500単語の文書を想像してみてください）。

Answer 1

なぜ圧縮を達成するために "digram words"が必要ですか？それが厳密な要件ではない場合、様々なシーンでテキストデータを圧縮するさまざまな方法があります。これらは主に辞書の前処理と呼ばれます。あなたの場合に適用できるリストは次のとおりです。

1. 頻度の出現をカウントし、降順で頻度で並べ替えます。カスタムのエンコード方法で上位N個の単語を使用できます.Nはユーザーが設定可能です。ダイナミックプログラミングなどでNを最適化することもできます。実際の符号化では、次の記号を示すためにフラグを符号化することは、辞書語か直接符号化語かを示す。

2. ジグラムまたはトリグラムの文字の組み合わせ（スペース、句読点などを含む）のヒストグラムを作成します。次に、使用されていないバイト値を使用して、頻繁に見られるdigramまたはtrigramをエンコードします。再帰的な方法を使用して何度もスキャンしてソースファイルを減らすことさえできます。

あなたの場合、上記の方法を検討すると効率が悪い場合があります。なぜなら、エンコードされたデータをデコードするためには、本当に大きなデータが必要であるとは考えていないようです。圧縮のアイデアの大部分を理解するには、出力を分析するための非常に単純なテストプログラムを書く方がよいでしょう。最終的に、より強力で安定したアルゴリズムになります。

1. XWRT：芸術辞書プリプロセッサの状態のひとつ。ここ

   は、ちょうどあなたの参照を与えるために私の心に入って来るいくつかの辞書のプリプロセッサです。

2. DICT：高性能のプリプロセッサFreeArcアーカイバ（オープンソース）です。約articleがあります。残念ながら、ロシア語です。
3. KWC：6グラムのコードを辞書コードで置き換える単純なテスト辞書プリプロセッサ。議論のためにhereを見てください。
4. bpe2 V3：これはnグラム置換に基づいています。他のバージョン：V1,V2。また、それについてのdiscussionがあります。

Answer 2

簡潔に言えば、可能な配列の数は、これを効率的に行うには大きすぎる可能性があります。より大きな問題は、それらの単語マッピングと、各マッピングに続くnグラムがどこかに格納される必要があり、実際の "圧縮"の節約よりも大幅に重要であるということです。