algorithm - 英語のスペルミス修正シーケンス

Question

私は少し検索エンジンをやっています。機能の 1 つは、何も見つからないスペルを修正する試みです。次の音声シーケンスを置き換えます: ph<->f、ee <-> i、oo<->u、ou<->o (色<->色)。そのような英語の完全なリストはどこにありますか? ありがとうございました。

Answer 1

ここ(Soundex のウィキペディア) から始めて、「参照」リンクからトレースを開始することもできます。(たとえば、Metaphone には代替品のリストがあります。)

Answer 2

検索エンジンを作成している場合は、スペルが間違っている単語を含む Web ページがたくさんあることに注意する必要があります。もちろん、そのページを検索可能にするための戦略も必要です。したがって、スペル修正プログラムを実装するための一般的な規則はありません ( Web では正確さが相対的な概念になるため)。しかし、実際にそれを行う方法がいくつかあります:-)

スペルを修正するには、 n-gram index + Levenstein distance (または同様の距離)を使用することをお勧めします。

レーベンシュタイン距離が小さい文字列は、おそらく同じ単語のバリエーションです。

「fantoma」という単語を修正したいとします。大量の単語がある場合、辞書を繰り返し処理して各単語までの距離を計算するのは非常にコストがかかります。そのため、「fantoma」までの距離がおそらく小さい単語を非常に高速に検索する必要があります。

主なアイデアは、Webページのクロールとインデックス作成中に、nグラム（バイグラムなど）のインデックス作成を別のインデックスに実行することです。各単語を n-gram に分割し、n-gram インデックスに追加します。

1) Split each word from dictionary, 
   for example: "phantom" -> ["ph", "ha", "an", "nt", "to", "om"]

2) Create index:
   ...
   "ph" -> [ "phantom", "pharmacy", "phenol", ... ]
   "ha" -> [ "phantom", "happy" ... ]
   "an" -> [ "phantom", "anatomy", ... ]
   ...

これで、インデックスが作成され、単語の候補をすばやく見つけることができます。

例えば：

1) "fantoma" -> ["fa", "an", "nt", "to", "om", "ma"]
2) get lists of words for each n-gram from index, 
   and extract most frequent words from these lists - these words are candidates
3) calculate Levenstein distance to each candidate, 
   the word with smallest distance is probably spell-corrected variant of searched word.

「情報検索入門」という本を一読されることをお勧めします。