私は C++ でスペル チェッカーに取り組んでおり、実装の特定の段階で立ち往生しています。
正しいスペルの単語と、スペルの間違いをチェックしたい入力文字列を含むテキスト ファイルがあるとします。その文字列がスペル ミスの単語である場合、テキスト ファイル内のすべての単語をチェックし、最小の文字でそれと異なる単語を選択することで、正しい形式を簡単に見つけることができます。そのタイプの入力に対して、2 つの文字列間のレーベンシュタイン編集距離を計算する関数を実装しました。ここまでは順調ですね。
ここで難しいのは、入力された文字列がスペルミスの単語の組み合わせである場合はどうなるかということです。たとえば、「iloevcokies」です。「i」、「love」、「cookie」はテキスト ファイルに含まれる単語であることを考慮して、既に実装されているレーベンシュタイン関数を使用して、ファイルのどの単語が修正に適しているかを判断するにはどうすればよいですか? また、正しい位置に空白を挿入するにはどうすればよいですか?
どんなアイデアでも大歓迎です:)
フレーズのスペル修正は、いくつかの方法で行うことができます。1つの方法では、単語のバイグラムとトライグラムのインデックスが必要です。もちろん、これらは計り知れないものになる可能性があります。別のオプションは、スペースが挿入された単語の順列を試し、結果のフレーズの各単語を検索することです。GoogleのPeterNorvigによるスペルチェッカーの簡単な実装を見てみましょう。いずれにせよ、パフォーマンスを向上させるためにn-gramインデックスの使用を検討してください。参照用に、C++で利用可能なライブラリがあります。
Googleやその他の検索エンジンは、クエリと関連する結果セットのインデックスが大きいため、フレーズのスペル修正を行うことができます。これにより、統計的に適切な推測を計算できます。全体として、スペル修正の問題は、文脈依存の修正や音声の修正などの方法では非常に複雑になる可能性があります。可能なサブタームの順列を使用するとコストが高くなる可能性があることを考えると、特定のタイプのヒューリスティックを利用できますが、これはすぐに範囲外になる可能性があります。
また、 aspellなどの既存のスペルライブラリの使用を検討することもできます。
I will suppose that you have an existing index, on which you run your levenshtein distance (for example, a Trie, but any sorted index generally work well).
You can consider the addition of white-spaces as a regular edit operation, it's just that there is a twist: you need (then) to get back to the root of your index for the next word.
This way you get the same index, almost the same route, approximately the same traversal, and it should not even impact your running time that much.