100種類もあるもののレーベンシュタイン距離を効率的に求めたい

前提・実現したいこと

100種類ある動物の単語の中からもっとも可能性が高い単語のものを算出したい。
例えば、
”い”ね・”い”む・（　）”ぬ”　と認識された　→いぬ　に変換
”う”きぎ・”う”ちぎ、ウ”さぎ”　と認識された　→うさぎ　に変換　のようにアルゴリズムを書いて変換したい。

発生している問題・エラーメッセージ

100種類ある動物の単語の手書き文字のデータがそれぞれ１００個ずつある。今OCRのアルゴリズムを作り、それぞれの文字画像を読み込ませたところ、正常にいぬorうさぎorライオンと認識される他に、
・いぬ　の場合
いね、いむ、（　）ぬ・・・などと認識されることがある
・うさぎ　の場合
うきぎ、うちぎ、ウさぎ・・・などと認識されることがある
・ライオン　の場合
ライオソ、ライ才ソ、ラ人オン・・・などと認識されることがある。
また、例えばいぬの場合、レ | ぬのように誤認識される時、文字数が増えてしまう事もある。

該当のソースコード

import Levenshtein

#正解配列
string1 = ["いぬ","うさぎ","ライオン","カメレオン","りす","猫",など・・・１００種類ある]
#取得データの配列
string2 = ["いね","いむ","（　）ぬ","うきぎ","ライオソ","ライ才ソ","ラ人オン",など・・・２００種類ある]

#単純に総当たりで求める
for i in range(len(string1)):
　　for j in range(len(string1)):
        print Levenshtein.distance(string1[i], string2[j])

とコードを書いた。
確かに総当たりでは求められるとは思うが、効率が悪い。if文を使い、取得データの配列の先頭の文字と正解の配列の先頭の文字を比較して効率化できるかと思ったが、取得データの配列の先頭の文字が必ずしも正解しているとは限らないため手法として微妙だと感じた。

何か効率的な方法がないかどうかをお聞きしたい。

試したこと

総当たりで読み取った単語が正解の単語群のどれに近いのかを計算する事

行動規範の内容に同意します

回答3件

ベストアンサー

長さが近いものから探していくのがいいと思います。

たとえば正解の単語集合が{"いぬ","うさぎ","ライオン","カメレオン"}であり、調べたい単語が"いむ"であるとき、まず長さが等しい"いぬ"と比較し、レーベンシュタイン距離が1とわかります。

この時点で、長さの差が2以上である"ライオン"と"カメレオン"は、少なくとも距離が2あるので調べなくていいということがわかります。なので、あとは"うさぎ"を調べれば答えが分かるということになります。

この方法でやるには、予め正解の単語を長さ別に分類しておく必要があります。

ちなみにstring2にもし重複がある可能性があるなら、一度調べた単語に対する最も近い単語を(dictなどを用いて)保存し、同じ計算を繰り返すのを防ぐようにするといいと思います。

投稿2018/03/26 08:32

karamarimo

総合スコア2555

データを工夫するのが手っ取り早いように思います。

string1 に列挙されているデータを1行1項目のテキストファイルにします
string2 に列挙されているデータを、string1と対応づけるように1行にレーベンシュタイン距離を計算したい単語をカンマ区切りかタブ区切りかで記述します
それぞれをスクリプトで読み込んで、対応するデータだけを計算するようにループ回してやる

投稿2018/03/26 08:00

kazto

総合スコア7196

kaitotokai

2018/03/26 08:26

ありがとうございます。２に記載されている内容に関してですが、string2 に列挙されているデータも1行1項目のテキストファイルにするという事でしょうか？

kazto

2018/03/26 08:32

いいえ。「いね,いむ,（　）ぬ」の3つが「いぬ」と比べたいものでしょうから、この三つを1行に記載します。この辺は、すべて自動でやろうとせず、人間の目で振り分けてやるのが手っ取り早いと感じた次第です。

行動規範の内容に同意します

日本語だと単語が短いのでレーベンシュタイン距離の計算がそこまでかからないかと思われます。
100クラス程度なら普通に計算したほうが速いような…
https://stackoverflow.com/questions/4057513/levenshtein-distance-algorithm-better-than-onm

判別用のクラス間の距離をあらかじめ計算しておくことで、
例えば、
「うさぎ」に近い単語は「カメレオン」はないだろうと、計算量を減らすことが可能かもしれません。

TF-IDFで文字別にベクター化して、前処理して候補を絞ることも可能ですが。
効果はいかほどでしょうね…

https://qiita.com/nazoking@github/items/b270288fa38aed0a71bf
https://qiita.com/katryo/items/f86971afcb65ce1e7d40

http://zecl.hatenablog.com/entry/20090312/p1

投稿2018/03/26 08:42