PHPで類似した書式の文字セットに基づく訂正改善

Question

OCR出力で動作する英語以外の言語のスペル訂正システムを開発中です。私は非常に大規模な辞書を使用してスペルミスをチェックし、提案をします。

ほとんどのスペルミスは、類似した形の文字が原因です。例えばـجـ、ـچـ、ـحـ、ـخـまたはغ、عとなどが挙げられる。これらの文字は例I、lとu、v、yのために、あまりにも英語で存在します。

スペルチェックシステムでは、確認したい単語をいくつか提案します。例えば、我々は、入力vogaそれはこれらの単語を示唆うとします。

• volga
• boga
• yoga
• toga

vogaの長さは、我々はよ、4であるので、 4文字の提案だけを残してください。現在、OCRエンジンはvをyとして検出できるため、vogaの推奨候補としてyogaをOCR出力として選択します。

私たちの言葉では、この種の選択は非常に効果的です。例えば、我々は入力مدپر、これらの言葉が示唆されている場合：私たちのセットに基づいて

• مدارا
• مدار
• مدیر
• مراد

（この例では：ـبـ、ـپـ 、ـیـおよびز,ر,012 ,د,مـ,فـ,قـ）と語の長さمدیرは、مدپرに最適なオプションです。私は通常、PHPスクリプト言語でこの機能を実装

方法はその後、提案されているのと同じ長さの単語が（すべてのセットを置き換えることにより、同様مدپر、فدپر、قدپر、その後مذپرを誤って綴られた単語のすべての可能な組み合わせを作成しておくことです、 فذپر、قذپرなど）、その後、候補リスト内の同じ単語を検索します。しかし、この実装方法は実際には（特に大きな文脈では）遅く、ほとんど無意味になります。

この種の機能をPHPで実装するには、どのような方法やアルゴリズムが最適ですか？

更新：

提案リストを生成エンジンが最適化され、通常は候補リストで正しい単語が含まれています。問題は、私のシステムが、人工知能のない正しい単語として提案の1つを選択しなければならないことです。だから私は、この方法は文字が似た形をしている多くのセットがあり、OCRエンジンが通常誤って単語を検出するため、私の言語では良いと思います。しかし、より良い方法があれば、それらを提案することを歓迎します。

Answer 1

私はまだこの質問が広すぎてここで質問できないと思います。どのようにするかわからないような気がするので、PHPソリューションを求めてはいけません。私の意見では、この質問はプログラミングや実装についてではなく、アルゴリズム的な解決策の第一歩です。私は数多くの異なる解決策が存在すると確信しています。数年前にこの分野で科学的研究を行って以来、私はあなたがそれをどうやってできるかという手がかりを得るための1つの解決法を提案します。

無効な「OCR単語」があり、有効な単語の辞書からその単語を置き換えるには、有効な単語を選択したいとします。

1. 標準的な提案アルゴリズムから始めます。だから、あなたはいくつかの候補単語を取得します。

2. ここで、これらの単語のOCR単語への「距離」を計算します。

3. 計算距離が最小の候補を使用します。

質問は2単語の距離を計算する方法です。 Hamming distanceで始めることができますが、この古典的なアルゴリズムは状況には十分ではなく、ステップ1からすでに得られているものを上回るものではないため、より適切なものを作成する必要があります。簡単に言えば、類似の記号/文字にいくらかのボーナスを与えたいと言います。我々は、DNA解析のための全く同じ状況を解決するために、ファジィオートマトンを使用しました。詳細な情報が必要な場合は、our paperを参照してください。

また、ステップ1を完全にスキップして、類似性のある類似の単語のグローバル検索システムを作成することもできます（これについては、このホワイトペーパーで説明しています）。私はこのグローバルなアプローチに投票します。