![見出し画像](https://assets.st-note.com/production/uploads/images/109642026/rectangle_large_type_2_6f1023d9d629b015f55a7e0e0ceda1e7.png?width=1200)
レーベンシュタイン距離について分かりやすく解説します
Google検索で、検索ワードを間違えて入力し、Googleから「こちらのワードで代わりに検索しますか?」と言われたことありませんか。
![](https://assets.st-note.com/img/1686969905536-cYbPmNljzB.png?width=1200)
検索ワードの間違いを自動で修正して、
正しい(と思われる)ワードを返してくれるなんて凄くないですか。
これ、レーベンシュタイン距離を使って実現されています。
この記事では、ビジネスでの応用例も多い、レーベンシュタイン距離について解説していきます。
また、レーベンシュタイン距離はPythonを使えば簡単に実装できます。
後半ではその実装方法もご紹介していきます。
📌レーベンシュタイン距離とは
簡単に言うと、ある文字列Aと別の文字列Bを比較した時に、二つの言葉がどの程度異なっているかを示す尺度です。
もう少し具体的に言うと、文字列Aを文字列Bに変えるために、文字の置換・削除・挿入を何回行う必要があるか?を計算し、その回数がレーベンシュタイン距離となります。
日本語では編集距離とも言います。
この呼び名の方が、しっくりくるかもしれません。
実際に例を使って見てみましょう。
orangeとgrapeの二つの文字列のレーベンシュタイン距離を考えます。
orangeをgrapeに変えるためには、何回、文字の編集を行う必要があるでしょうか?
![](https://assets.st-note.com/img/1687052380515-Hj4ucDaB4D.png?width=1200)
置換→削除→置換の計3回ですね。
orangeとgrapeのレーベンシュタイン距離は3ということになります。
文字の類似度は、レーベンシュタイン距離が小さいほど似ていて、大きいほど似ていないということになります。
📍標準化について
レーベンシュタイン距離は比較する文字数が多いほど、大きくなりやすいので注意が必要です。
例えば、二つの文字列を比較して、レーベンシュタイン距離が2だったとしても、比較する文字列が5文字だったときと、10文字だった時では意味合いがことなります。
そこで、距離を文字列の長さで割り返すことが一般的です。これを標準化とよびます。
レーベンシュタイン距離が2で、文字列が5文字だったときは0.4、文字列が10文字だったときは0.2となり、10文字の方が似ていると判断できます。
🖋️ビジネスでの活用例
レーベンシュタイン距離を使えば、単語や文章の誤りを見つけ、自動で修正する(あるいは正しいと思われる候補を表示してくれる)ことが可能です。
まだまだ、人間が手入力をしなければならない業務が多い中、その入力ミスのチェックを自動で行えるうえに、正しい用語に修正してくれれば、業務の効率化が進みますね。
🐥Pythonによる実装方法
Pythonには、レーベンシュタイン距離や類似度を1行で計算できるライブラリーがあるので、簡単に実装できます。
実装例として二つのデータフレームを用意します。
df1から見て、df2の単語の中で最も類似度が高い単語を抽出するとともに、その類似度とレーベンシュタイン距離を算出したいと思います。
![](https://assets.st-note.com/img/1686972445028-Xg80TWzKSX.png?width=1200)
GoogleColaboratoryで実装します。
ライブラリーのインストール
!pip install Levenshtein
ライブラリーのインポート
import pandas as pd
import numpy as np
from Levenshtein import ratio, distance
データフレームを用意
df1 = pd.DataFrame({"word":["appli","banana","lennon","grap","おざなり"]})
df2 = pd.DataFrame({"target":["grape", "apple", "banana", "lemon","なおざり"]})
類似度とレーベンシュタイン距離を計算する関数を作成し実行
def find_closest_word_and_similarity(word, correct_words):
if correct_words.size > 0:
# 各単語とのLevenshtein類似度を計算
similarities = [ratio(word, correct_word) for correct_word in correct_words]
# 最大類似度の単語とその類似度を返す
return
correct_words[np.argmax(similarities)],
np.max(similarities),
distance(word, correct_words[np.argmax(similarities)])
else:
return None, 0, len(word)
# 'closest_word', 'similarity'と'incorrect_count'を一度に計算
df1['closest_word'], df1['similarity'], df1['distance'] =
zip(*df1['word'].apply(lambda x: find_closest_word_and_similarity(x, df2['target'].values)))
df1
![](https://assets.st-note.com/img/1686972630451-KsmXLtoAVt.png?width=1200)
ちゃんと計算できていますね。
😊さいごに
文字列のような非構造化データは、これまで扱いにくかったところがありましたが、自然言語処理技術の発展や、Pythonライブラリーのおかげで、ずいぶん扱いやすくなりました。
このような自然言語処理系の技術は、ビジネスにどんどん取り入れていきたいものです。
よろしければサポートお願いします! いただいたサポートはクリエイターとしての活動費に使わせていただきます!