単語リストをエンコードするための圧縮アルゴリズム
https://stackoverflow.com/questions/405433
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
単語のリストをスペルチェック辞書に効果的になるものにエンコードするための特定の提案またはアルゴリズムやデータ構造への参照を探しています。このスキームの目的は、エンコードされた形式への生の単語リストの非常に高い圧縮率をもたらします。エンコードされた辞書に対する唯一の出力要件は、提案されたターゲットワードの存在を、比較的効率的な方法で元のワードリストに対してテストできることです。たとえば、アプリケーションは、100,000語の辞書に対して10,000語をチェックする場合があります。エンコードされた辞書フォームを元の単語リストフォームに[簡単に]変換できるようにするための要件は ではありません。結果の辞書に対してテストされた各単語に必要です。
私は、圧縮率を改善するために、単数形および複数形、所有形、縮約などの特定の言語の既知の構造を利用するエンコード方式を想定しています。主に英語の単語のエンコードに特に興味があります明確にするために、スキームはすべてのASCIIテキスト「単語」をエンコードできる必要があります。
私が想定している特定のアプリケーションは、不揮発性ストレージスペースが貴重で、辞書がランダムにアクセス可能な読み取り専用メモリ領域になる組み込みデバイス向けです。
編集 ：辞書の要件を要約するには：
- ゼロ誤検知
- ゼロの偽陰性
- 非常に高い圧縮率
- 解凍の必要なし
解決
McIlroyの＆quot;スペリングリストの開発＆quot; を参照してください。 パブのページ。ミニコンピューターでのスペルチェックに関する古典的な古紙。この制約は、リストしたものに驚くほどうまくマッピングされます。接辞のストリッピングと2つの異なる圧縮方法の詳細な分析：ブルームフィルターと関連スキームハフマン符号化スパースビットセット。ブルームフィルターは、おそらく彼が選んだ方法よりも優先します。この方法では、速度が大幅に低下しますが、さらにkBが圧縮されます。 （ Programming Pearls には、このペーパーに関する短い章があります。）
全文検索システムにレキシコンを保存するために使用される方法も参照してください。 情報検索の紹介。上記の方法とは異なり、これには誤検知はありません。
他のヒント
ブルームフィルター（ http://en.wikipedia.org/wiki/Bloom_filter および http://www.coolsnap.net/kevin/?p=13 ）は一部のスペルチェッカーで辞書の単語を非常にコンパクトに格納するために使用されるデータ構造。ただし、誤検知のリスクがあります。
パディングされたサフィックスツリーを提案します。ワードリストの優れた圧縮と優れた検索時間。
要約すると：
- ゼロ誤検知
- ゼロの偽陰性
- 高圧縮率
- 逆変換の必要はありません（つまり、圧縮解除は不要です）
ブルームフィルターを提案するつもりでしたが、これらにはゼロ以外の誤検知があります。
代わりに、Programming Pearlsは同様の一連の要件について話します（41Kの / usr / share / dict / words ）。
これは、茎の収縮のアプローチを取りました。 例：送信はルートであったため、事前修正と事後修正を追加できます。
- 現在
- 表す
- 表現
- 不実表示
単語を7ビット形式で連続したサフィックスとして保存することで、30％以上の圧縮率を得ることができます。これが何と呼ばれているのかはわかりませんが、かなり効果的にツリー構造に変換されます。
例： a + n + d + s | an + d + y | and + es + roid
と比較して、26文字です：
a と 広告 として そして どれか アンデス アンドロイド
33です。
7ビットコンテンツとして保存する場合の圧縮率は12.5％であり、これは合計で約31％の圧縮です。もちろん、圧縮率は単語リストのサイズと内容に依存します。
これを26ルートツリー構造にすると、おそらく、フラットファイルに対するプレーンテキストの部分文字列比較よりも高速なルックアップになります。
考えてみると、区切り文字に26文字と2文字しか使用していない場合、5ビットですべてを実行できます。これは、それ自体で37.5％の圧縮であり、上記の例を50％を超える圧縮にしますレート。
あなたの最善策は圧縮サフィックスツリー / 圧縮サフィックス配列。上記のリンクで豊富な情報を見つけることができます。これは現在進行中の研究分野であり、非常に興味深いものです。
私はこれに関する専門家ではありませんが、プレフィックスツリーではありませんこれに対する標準的な解決策は？単語の一般的な接頭辞を一度だけ保存します。
純粋な圧縮の場合、最大圧縮サイトは4 MBの結果を提供します英語の単語リスト、最高のプログラムはこれを約400 KBに圧縮します。テキスト/ワード圧縮用のその他の圧縮リソースには、 Hutter Prizeページと大きなテキスト圧縮ベンチマーク。
Knuthは、
編集：RAMの制約は何ですか？使用可能なROMよりも多くのRAMがある場合は、おそらくROMでのデータ圧縮（RAMへの圧縮解除が必要）が正しい方法です。大量のRAMではなく中程度のRAMがある場合、技術的にはデータ構造の一部を圧縮されたブロブとしてメモリに保存し、最近使用されていないキャッシュをいくつか保持して、適切なものを動的に解凍することもできますキャッシュにないときのblob。
