14

単語のリストを効果的にスペルチェック辞書になるものにエンコードするためのアルゴリズムおよび/またはデータ構造への特定の提案または参照を探しています。このスキームの目的は、生の単語リストをエンコードされた形式に非常に高い圧縮率で変換することです。エンコードされた辞書に関する唯一の出力要件は、提案されたターゲット単語が元の単語リストに対して存在するかどうかを比較的効率的な方法でテストできることです。たとえば、アプリケーションで 100,000 語の辞書に対して 10,000 語をチェックする場合があります。そうではないエンコードされた辞書形式を元の単語リスト形式に [簡単に] 変換できるようにするための要件 - 結果の辞書に対してテストされる各単語に必要なのは、バイナリの yes/no の結果だけです。

圧縮率を向上させるためのエンコード方式は、単数形と複数形、所有格、短縮形など、特定の言語の既知の構造を利用すると想定しています。主に英語の単語をエンコードすることに特に関心がありますが、明確にするために、スキームはすべてのASCIIテキスト「単語」をエンコードできなければなりません。

私が念頭に置いている特定のアプリケーションは、不揮発性ストレージ スペースが貴重であり、辞書がランダムにアクセス可能な読み取り専用メモリ領域である組み込みデバイス向けであると想定できます。

編集：辞書の要件を要約するには：

  • 偽陽性ゼロ
  • 偽陰性ゼロ
  • 非常に高い圧縮率
  • 減圧不要
4

9 に答える 9

13

McIlroy の「Development of a Spelling List」を彼のパブ ページで参照してください。ミニコンピューターでのスペルチェックに関する古典的な古い論文。制約は、リストしたものに驚くほどうまくマップされます。接辞の除去と 2 つの異なる圧縮方法の詳細な分析: ブルーム フィルターと関連スキーム ハフマン コーディング スパース ビットセット。おそらく彼が選んだ方法よりもブルーム フィルターを使用したいと思います。ブルーム フィルターは、大幅な速度の犠牲を払ってさらに数 kB を絞り出します。( Programming Pearlsには、この論文に関する短い章があります。)

辞書を全文検索システムに保存するために使用される方法も参照してください。たとえば、Introduction to Information Retrievalです。上記の方法とは異なり、これには誤検知がありません。

于 2009-01-01T20:30:59.110 に答える
5

ブルーム フィルター ( http://en.wikipedia.org/wiki/Bloom_filterおよびhttp://www.coolsnap.net/kevin/?p=13 ) は、辞書の単語を非常にコンパクトに格納するために使用されるデータ構造です。いくつかのスペルチェッカー。ただし、誤検知のリスクがあります。

于 2009-01-01T20:33:34.083 に答える
4

パッド入りの接尾辞木をお勧めします。ワードリストの優れた圧縮と優れたルックアップ時間。

http://en.wikipedia.org/wiki/Suffix_tree

于 2009-01-01T21:31:40.470 に答える
2

単語を7ビット形式の連続した接尾辞として保存することで、30％以上の圧縮率を得ることができます。これが何と呼ばれるかはわかりませんが、かなり効果的にツリー構造に変換されます。

例：a + n + d + s | an + d + y | and + es + roid

と比較して26文字です：

a ad as and any andes android

これは33です。

7ビットコンテンツとして保存するための12.5％の圧縮率を考慮すると、合計で約31％の圧縮率になります。もちろん、圧縮率は単語リストのサイズと内容によって異なります。

これを26ルートのツリー構造に変換すると、フラットファイルに対するプレーンテキストの部分文字列の比較よりも高速なルックアップが得られる可能性があります。

考えてみると、区切り文字に26文字と2文字しか使用していない場合、5ビットですべてを実行できます。これは、それ自体で37.5％の圧縮であり、上記の例では50％を超える圧縮率になります。

于 2009-01-01T21:10:27.470 に答える
2

あなたの最善の策はCompressed Suffix Tree / Compressed Suffix Arrayだと思います。上記のリンクで豊富な情報を見つけることができます。これは進行中の研究分野であり、非常に興味深いものです。

于 2009-01-01T22:20:12.917 に答える
2

総括する：

  • 偽陽性ゼロ
  • 偽陰性ゼロ
  • 高圧縮比
  • 逆の必要はありません（つまり、解凍は必要ありません）

ブルーム フィルターを提案するつもりでしたが、これらにはゼロ以外の誤検知があります。

代わりに、Programming Pearls では、同様の一連の要件について説明しています ( /usr/share/dict/wordsin 41K)。

これは、ステムの短縮のアプローチを取りました: 例: send はルートなので、前置および後置を追加することができます:

  • 現在
  • 代表する
  • 表現
  • 詐称
于 2009-01-01T20:38:08.037 に答える
1

私はこれに関する専門家ではありませんが、プレフィックスツリーはこれに対する標準的な解決策ではありませんか？これは、単語の一般的なプレフィックスを1回だけ保存します。

于 2009-01-01T21:26:08.047 に答える
1

純粋な圧縮の場合、MaximumCompressionサイトは4MBの英語の単語リストに対していくつかの結果を提供します。最良のプログラムは、これを約400KBに圧縮します。テキスト/単語圧縮用の他の圧縮リソースには、HutterPrizeページとLargeTextCompressionBenchmarkがあります。

于 2009-01-01T22:03:33.510 に答える
0

Knuth は The Art of Computer Programming vol. 1 で "Patricia trie" について言及しています。3 . 実際の仕事で使ったことはありませんが、役に立つかもしれません。

編集:RAMの制約は何ですか? 利用可能な RAM が ROM よりもはるかに多い場合は、おそらく ROM でのデータ圧縮 (RAM への解凍が必要) が適切な方法です。中程度のRAMを使用しているが大量ではない場合、技術的には、データ構造の一部を圧縮されたブロブとしてメモリに保存し、最近使用されていないキャッシュを使用してそれらのいくつかを保持し、適切なキャッシュにない場合はブロブします。

于 2009-01-01T21:05:15.173 に答える