音声アルゴリズムに関する日曜大工のスペルチェッカー

テストケースで素晴らしい結果を示した、生産での形態サポートを備えた超メガ洗練されたファジー検索システムを立ち上げた開発者は、厳しい現実に直面しています。 YandexとGoogleの自動修正に甘やかされているユーザーは、間違いやタイプミスを犯します。 そして、検索結果のあるきちんとしたページの代わりに、彼らは悲しい顔文字を取得します-マシンはリクエストを理解しませんでした。



機械のスペルチェックは完全な芸術であり、検索の巨人がこのタスクに取り組むために有能な数学者を雇うことは何の役にも立ちません。 ただし、音声原理に基づいた簡単な自動修正メカニズムがあり、すでに結果を生成してユーザーエクスペリエンスを向上させることができます。 それらについては記事で説明します。 さらに、これらは何らかの方法でより複雑なソリューションの基盤となります。



記事の最後に、エラーとタイプミスがあるオープンデータセットへのリンクがあります。 そこから貴重な統計を収集し、スペルチェックアルゴリズムをテストできます。

スペルミスとタイプミス

すべての入力エラーは、スペルとタイプミスという2つの大きなクラスに分類できます。 最初の原因について以下に説明します。タイプミスの人は、指が太い、キーボードが慣れていない、十分な睡眠を得られなかった理由を明確にします（笑、笑、笑）など。



自動修正システムを構築するという観点からは、これらのエラーを分離することも、普遍的なメカニズムを構築することもできます。 ただし、ユーザーエクスペリエンスの観点から見ると、これらの2種類のエラーには根本的に異なる重みがあります。 ユーザーが自分でタイプミスをすばやく確認して修正できる場合、特にいくつかの不確実な箇所がある場合、人が修正するのははるかに困難です。 おそらく彼は物議を醸す言葉をグーグルで検索するでしょう、あなたはユーザーの注意を逃し、おそらくサイトへの訪問者を失うでしょう。

スペルミスはどこから来ますか

ロシア語の文章は音声です。 原則は単純です。文字は特定の音に結び付けられており、文字の中で単語の音を伝えます。 （もちろん、大幅に簡略化されたバージョンでは。）ビジネスのようで、文字と音の対応を学び、テキストを走り書きしました。 実際、それは元々そうでした-異なる人々は異なる方法で同じ言葉を書きました。 2つの問題があります。 まず、発音のすべての機能が書面で伝達されます。 また、他の誰かの方言をまだ理解できる場合は、話すときにイントネーションを使用します。言葉にストレスがあり、非言語が追加されます。 -そのようなテキストを読むことは非常に困難です。 以下はYanko krul albAnskayの例です 。





注意してください！ 短い単語を認識することは特に困難です-オプションの数は高速で増加し始めます。 この機能は、マシンスペルにも存在します。



「フリーライティング」の2番目の問題は、死の曖昧さが似ている法的文書で発生します。 誰もが自分のやり方で書かれたものを書いて解釈するなら、あなたが意図したことを意味していたことを証明しようとする。



一般に、人々はかなり前に手紙を統一する必要性を理解し始めました。 そして、私たちは敬意を払わなければなりません。この方向での大きな仕事はソビエト政権の下で行われました。 実際、ロシア語の現代の綴りはそれほど現代的ではありません。 いくつかの修正を加えて、私たち全員が1956年のシステムを研究して使用しています。



要約すると。 スペリングは、公式レベルで固定された人々の間の合意であり、どのような状況でも、文字で明確に言葉で表現された特定の意味を表現できます。 まれに、同等の単語のスペル（トンネルとトンネル）がありますが、それらは指で数えることができます。



どんな合意も学習曲線を意味し、ロシア語の場合、それは非常に長いです。 このため、すべての人がさまざまな程度で読み書きのできる文章を所有しており、自分自身に正直に言うと、読み書きの状況は今では最も楽観的ではありません。

音声原理

良いニュースは、手紙の単語の反射がその健全な化身に関連していることです。 したがって、1つの単語のスペルを間違える方法は限られています。



もっともっと。 すべての文字は、対応する音の音声的近接の原理に従って、同等クラスに分類できます。 各クラスの境界内には、クラスの1つの文字の代わりに、エラーを犯したユーザーが別の文字を書く可能性があります。 各クラスから1人の代表者を選択し、単語内のすべての文字をクラスの代表者に置き換えると、音声ラベルが取得されます。







小学校の学年の児童が行う音声分析を連想させる何か。 現在、この手法は非常に実用的なアプリケーションです。



アイデア自体は新しいものではありません-20世紀初頭に英語専用の同様のアルゴリズムが提案され、開発と改善が続けられています。 Soundex 、 Metaphoneを参照してください。

実装の詳細

鳥瞰図から見ると、アルゴリズムは次のようになります。

1. 辞書内の各単語に対して、いくつかのルールを適用し、出力で音声ラベルを取得します-条件付きで単純化された単語の音。
2. チェックされている単語は、同じルールに従ってタグにコンパイルされ、辞書はタグで検索されます。
3. ユーザーには、いくつかの修正オプションを選択できます。
4. 詳細な単語シーケンス（検索クエリなど）の自動修正には、アルゴリズムを使用できますが、単語の互換性に関する追加情報がないと、長いクエリで品質が低下する可能性があります。
5. このアルゴリズムは、ユーザーに修正のオプションを提供することを目的としていますが、検索システム自体に組み込む価値はありません。

音声ラベル編集規則

NBここと以下では、処理のあらゆる段階での音声記号は山括弧で囲まれます。 誤ったスペルの単語の前にはアスタリスクが付き、斜体で強調表示されます。 これにより、スペルミスのある単語で作業することによる悪影響を減らすことができます。

1.一緒に、個別に、ハイフンで

スペルミスの大規模なクラス-個別に/一緒に/ハイフンを介して書き込みます。 したがって、表音ラベルをコンパイルすると、ロシア文字を除くすべての文字が削除されます。 この句は、いくつかの単語の安定したグループである語彙エントリに適用されます（なぜなら、海外で）。



違う→

なぜなら→<理由>

中に→

海外→<海外>

2.二重子音

2番目に一般的な難易度は二重子音です。 したがって、2つ以上の同じ文字をすべて1つに置き換えます。



アート→アート。



次のようなエラーを考慮するために、最後の段階で接着を繰り返し、文字ではなく音で接着するのは理にかなっています。



*

フランス語（最も一般的なスペルミス*フランス語 ）。

3.ソフトサイン、ハードサイン

ソフト文字とハード文字は単語から削除されます。 多くの場合、これらの文字は正しい場所に置くのを忘れられるか、その逆です-本来あるべきでない場所に置かれます（ *日本語 ）。



食用→<脂っこい>

正方形→<正方形>

4.子音グループの簡素化

stn→sn：ローカル、正直、不明、熟練

nd→ns：風景、マウスピース、エンドゲーム

stl→sl：幸せ、思いやりのある、誠実な

zdn→zn：遅い、深by、休日

→→st：こんにちは、感じ、甘やかし、魔術



また、生産性も低下します。

zdts→ss：手綱の下

lnts→nts：太陽

ndc→nc：オランダ語

ntg→ng：X線

rcd→rc：ハート

rdch→rh：ハート

5.特徴的な文字の組み合わせ

統計的に有意なエラーの場合の典型的な2文字の組み合わせ：

MF、FF、FF、FF、FF、FF→ F （ * FF、FF、FF、FF、FF、FF ）

stg→cg（ * buzgaller ）

hg→g（ * buGalter、* 2年、*スリーヘッド ）

tf、dts→ts（ * deTsVto、* godTsTvo、* disputeChmen ）

6.母音

次の原則に従って母音を置き換えます。

a、o、e→a

y、y→y

i、s、およびe、e→および

7.子音のスタン

子音はびっくりします：

b→p

s→s

d→t

c→f

r→k



一部の実装では、強い位置で気絶しないことをお勧めします（つまり、文字の後に文字p、l、m、n、b、vまたは母音のいずれかが続く場合）。 実際、過剰な合併症が発生し、アルゴリズムの動作が悪化し始めます。

8.シズルとC

シューという音とCの別の話ですが、スペルの研究にそれほど注意を払っていることは無駄ではありません。

W、W、H、W、C→W

適用性と他のアルゴリズムとの比較

提案されたアルゴリズムの主な利点は、インデックスによる迅速な検索があればどこでも使用できることです。 つまり 最も古いDBMSでさえも。 2番目の重要な利点は、このようなアルゴリズムが数時間で（余裕を持って）作成および実装されることです。



その重大な欠点は、タイプミス、省略、余分な文字を扱うことができないことです。



NB一般的なレーベンシュタイン距離テストと比較した場合、音声アルゴリズムは、いくつかのスペルミスがある場合にゲインを提供します。 同時に、L。のアルゴリズムを使用すると、タイプミスをキャッチできます。 両方のアプローチの長所を組み合わせて、加重レーベンシュタインアルゴリズムに到達できます。

改善する方法

ユーザーに選択肢を提供する場合、ユーザーエクスペリエンスの観点から、元の要求への準拠の程度に応じてランク付けすることをお勧めします。 これを行うのは難しくありません。オプションにアルゴリズムを詰め込んだ後、それらを元のクエリと比較し、各置換の確率を記憶します。 次に、個々の置換の確率がそれらの間で乗算され、最終的な数字が得られます。



アルゴリズムを改善する2番目の機会は、追加のマークを作成することです。この場合、文字の1つがジョーカーシンボル（アスタリスクなど）に置き換えられます。 これにより、タイプミスや特定のエラーを処理できるようになりますが、タグの数は桁違いに増えます。

アルゴリズムの正当化

このアルゴリズムは、ロシア語の音声機能と実際の間違いに関する統計の研究に基づいた純粋な発見的手法です（データセットは記事の最後にダウンロードして、自分で実験することができます）。 さらに、置換は意図的に無作法に行われます-実験中、アルゴリズムを微調整しようとすると悪化します。



フィリグリールールが必要な場合は、機械学習を検討してください。







ヒートマップは行ごとに読み取られます。 たとえば、文字aの場合、最も可能性の高い間違いはについてです。 他のすべてのエラーの可能性は大幅に低くなります。



そして、例えば、 bについては 、タイプミスb 、 w、そしてまれにdが最も可能性が高いでしょう。 音声エラーnは 、前の3つに比べて頻度が劣ります。

結果の評価

結果の評価は、測定方法に大きく依存します。



タイプミスも含むテストデータセットL1.5（おおよそ：単語とエラーのペアのレーベンシュタイン距離は1以下）では、アルゴリズムの精度は25％です。 しかし、それはどんな長さの言葉でもあります。 最小長の5を使用すると、精度は34％になります。 7（ロシア語の平均語長）-41％。



空からの星は十分ではありませんが、単純なアルゴリズムではこれは価値のある結果以上のものです。 エンディングを切り取って粗語を追加すると、2〜3％延長できます。



テストデータセットL1.5 + PHON（音声ラベルで同等の以前のデータセット+単語とエラーのペア）では、アルゴリズムにより5％の精度向上が得られます。 統計の観点からは、アルゴリズムの結果をテストスイートに混合することは致命的な罪ですが、この図は、マルチORFエラーの割合、つまり ユーザーが同時にいくつかの場所で間違えられる場合、それほど小さくはありません。 これが音声アルゴリズムの趣味です。



上記の品質があなたに合わない場合、よりインテリジェントなアルゴリズムに投資する必要がありますが、DBMSインデックスに基づいて構築することは既に非常に簡単です。

データセット

自動修正アルゴリズムをトレーニングし、貴重な統計を収集するには、実際の人が行ったエラーに基づいてオープンデータセットを取得します。 入力ミスとスペルの両方が含まれます。



データセット：スペルミスとタイプミス

参照資料

1. Nikita SmetaninのHabrの音声アルゴリズムのレビュー
2. ロシアのメタフォン
3. Russian for Fiveプロジェクトでの音声学
4. Soundex（ウィキペディア）
5. Metaphone（ウィキペディア）
6. ペニスランド、またはスペルチェッカーの書き方