24

Cでスペルチェッカーを実装する必要があります。基本的に、すべての標準操作が必要です...テキストのブロックをスペルチェックし、単語の提案を行い、新しい単語を動的にインデックスに追加できる必要があります。

自分で書きたいのですが、どこから始めたらいいのかわからないです。

4

7 に答える 7

31

Tree Traversalを読んでください。基本的なコンセプトは次のとおりです。

  1. 辞書ファイルをメモリに読み込みます (このファイルには、特定の言語で使用できる/一般的な正しいスペルの単語の完全なリストが含まれています)。Oracle の例の辞書など、無料の辞書ファイルをオンラインでダウンロードできます。
  2. この辞書ファイルを検索ツリーに解析して、実際のテキスト検索を可能な限り効率的にします。このタイプのツリー構造の汚い詳細をすべて説明することはしませんが、ツリーは子ノードへの (最大) 26 個のリンク (文字ごとに 1 つ) と、子ノードへのリンクがあるかどうかを示すフラグで構成されます。現在のノードが有効な単語の末尾であるかどうか。
  3. ドキュメント内のすべての単語をループし、検索ツリーに対して各単語をチェックします。単語内の次の文字が現在のノードの有効な子ではないツリー内のノードに到達した場合、その単語は辞書にありません。また、単語の末尾に達し、そのノードで「単語の有効な末尾」フラグが設定されていない場合、その単語は辞書にありません。
  4. 単語が辞書にない場合は、ユーザーに通知します。この段階で、別のスペルを提案することもできますが、それは少し複雑になります。単語の各文字をループして代替文字に置き換え、検索ツリーに対してそれぞれをテストする必要があります。推奨される単語を見つけるためのより効率的なアルゴリズムがあるかもしれませんが、それらが何であるかはわかりません。

非常に短い例:

辞書：

apex apple 任命 任命

ツリー: (*単語の有効な末尾を示します) 更新:このデータ構造がパトリシア ツリーと呼ばれることを指摘してくれた Curt Sampson に感謝します

A -> P -> E -> X*
      \\-> P -> L -> E*
           \\-> O -> I -> N -> T* -> E -> D*

書類：

りんご appint サル

結果：

  • 「リンゴ」はツリーにあるため、正しいと見なされます。
  • 「appint」は正しくないというフラグが立てられます。ツリーをトラバースすると に従いますA -> P -> Pが、2 番目には子ノードPがないIため、検索は失敗します。
  • EのノードにA -> P -> Eは「有効な単語の終わり」フラグが設定されていない ため、「ape」も失敗します。

編集:スペル候補の詳細については、レーベンシュタイン距離を調べてください。これは、ある文字列を別の文字列に変換するために必要な変更の最小数を測定します。最適な提案は、スペルが間違っている単語までのレーベンシュタイン距離が最も小さい辞書の単語です。

于 2008-12-06T21:35:10.420 に答える
3

どこから始めればよいかわからない場合は、既存のソリューションを使用することをお勧めします。たとえば、aspell （GLPLライセンス）を参照してください。本当に自分で実装する必要がある場合は、その理由を教えてください。

于 2008-12-06T20:58:34.017 に答える
1

接頭辞と接尾辞に注目する必要があります。

突然=突然+ly。

ly を削除すると、ルート ワードだけを保存する必要がなくなります。

同様に、事前割り当て = 事前 + 割り当て。

そして、愛情を込めて = love + ing + lyは、英語のing のルールが適用されるため、もう少し複雑になります。

また、ルート ワードの綴りが正しいかどうかを判断する一定時間の方法として、ルート ワードを特定のビット マップにマッピングするために何らかのハッシュ関数を使用する可能性もあります。

スペルミスのある単語に、可能な正しいスペルの代替リストを提供しようとすると、さらに複雑になる可能性があります。いくつかのアイデアを得るために、soundex アルゴリズムを調査することができます。

小さな単語セットでプロトタイピングすることをお勧めします。多くのテストを行ってから、スケールアップします。素晴らしい教育問題です。

于 2008-12-07T02:22:11.337 に答える
0

単語を語根と接尾辞に分割することは、「Porter Stemming Algorithm」として知られています。これは、英語の辞書を驚くほど小さなメモリに収める良い方法です。
「スペルチェック」も「スペルチェック」や「スペルチェック」もしてくれるので検索にも便利です

于 2008-12-07T02:51:35.490 に答える
0

Open Office スペル チェッカー Hunspell は、出発点として適しています。ホームページはこちら: Hunspell at Sourceforge

于 2009-09-09T18:14:05.860 に答える