Pythonでレーベンシュタイン距離を使う方法とコード紹介

レーベンシュタイン距離を利用すると２つの文字列を比較してどのくらい文字が離れているかを数値として算出することができます。

似たテキストを見つけたい時に有効な手段であり簡単に利用することができます。

テキスト類似率を算出する手法は分かち書きや自然言語解析などがありますが、使い方によってはレーベンシュタイン距離の方がよいものもあるのでご紹介いたします。本記事を読むことによりwindows環境でpythonを用いたレーベンシュタイン距離を扱うことができるようになります。

レーベンシュタイン距離アルゴリズムとは

レーベンシュタイン距離の由来

1965年にロシアの学者ウラジーミル・レーベンシュタインさんが考案したのでこの名前が使われております。かなり昔からある考えのアルゴリズムになります。

レーベンシュタイン距離の算出概要

レーベンシュタイン距離アルゴリズムは２つのテキストを比較してどのくらい距離が離れているか数字で算出するロジックです。

「編集距離」とも言われており、１つ目のテキストにするためには「追加・更新・削除」を何回行えばそのテキストになるかという観点で処理した数だけ足されて結果をだします。

つまり、追加２回、更新１回、削除２回ならば距離は５として表示されます。

レーベンシュタイン距離をWindowsで使う準備

python環境の準備

jupyter環境があるかたはここの章は飛ばしてください。

jupyter環境がない方はPython環境とjupyter環境の構築が必要です。Pythonの環境構築はいくつか方法があるので自分の好きな環境を過去記事のPythonとJupyterLab DesktopとAnacondaの環境構築とデメリットを参考に選んでください。

手軽に使いたい初心者ならANACONDAがおすすめ。長くPythonを使う予定で処理の軽さやスピード重視であれば公式Pythonをvenvで使う方法がおすすめです。

環境が用意できたらjupyter notebookかjupyter labをインストールしてください。ANACONDAであれば最初からインストールされております。

コマンドプロンプトでインストールする方法

pip jupyter

もしpipでインストールできない場合はセキュリティ環境の問題があるので過去記事のPythonのpip installが使えない時のプロキシとSSL無視をご覧くださいませ。

これによりインストールが可能になります。

Levenshtein（レーベンシュタイン）をpipでインストール

pipインストールします。

#コマンドプロンプトなら
pip install python-Levenshtein

#jupyter上のセルで実行なら
!pip install python-Levenshtein

もう１つインストールします。

#コマンドプロンプトなら
pip install python-Levenshtein-wheels

#jupyter上のセルで実行なら
!pip install python-Levenshtein-wheels

これで必要ライブラリのインストールは完了です。

Levenshtein（レーベンシュタイン）を使う

単純に距離を比較する場合

pipでインストールしたLevenshteinをjupyter上で読み込みます。

import Levenshtein

Levenshteinでテキスト１とテキスト２を比較したいなら下記のように書けばどのくらい距離が離れているかを数値で返してくれます。簡単ですね。

Levenshtein.distance(テキスト１,テキスト２)

a="練馬らいふ"
b="練馬Life"
c="練馬life"
d="練馬ｌｉｆｅ"


##実行
Levenshtein.distance(a,b)
#4

Levenshtein.distance(b,c)
#1

Levenshtein.distance(c,d)
#4

最初の例は「らいふ」を「LIFE」にするには４文字変換する必要があるという意味です。

その次は１文字変換すれば同じ言葉になる。先頭だけ大文字のLなので。

気を付けるべきことは最後の「練馬life」と「練馬ｌｉｆｅ」を比較した時の差異が4になっていることです。

間違いではないですがテキストクレンジング処理した後に処理すると値が変わります。

一語毎に見比べて追加・更新・削除をしていくことで何文字かかったかが文字の距離として算出されます。

テキストをクレンジングしてから比較する場合

jaconvを使って全て半角にしたあとに比較してみます。

pip install jaconv

import jaconv

c=jaconv.z2h(c,digit=True,ascii=True)
d=jaconv.z2h(d,digit=True,ascii=True)

Levenshtein.distance(c,d)
#0

半角に変換して距離比較したら０になりました。これはcもdも「練馬life」という文字に変わり同じ文字になったためです。

自分がやりたいことが何かによって事前にクレンジングすべきかがかわります。クレンジング手法を知りたい方は過去記事のPythonでテキストクレンジング全角半角ひらがなかたかな大文字小文字をあわせてご覧くださいませ。

レーベンシュタインの距離を割合にする

レーベンシュタインは文字距離を割合にして使うことも有効です。

なぜならレーベンシュタインの特徴から文字列が長ければ長い程距離が大きくでるからです。このデメリットを緩和するために文字列を足して割ってあげます。

a="練馬らいふ"
b="練馬Life"
x=Levenshtein.distance(a,b)

try:
    y=x/(len(a)) + (len(b))
except ZeroDivisionError:
    y=0
    
y
#6.8

０除算エラーを回避するためにtry～exceptで強引に０に置き換えています。

最後に

文字の距離を１行だけで抽出してしまうのですから簡単で便利ですよね。

また、文字の距離を目視確認するのはテキスト量が増えると現実的ではありませんのでこういったコードを利用して簡易化するとメリットが多いでしょう。

最後に私がPythonの勉強をして入門者から中級者までにこの本1冊あれば習得できるおすすめ本記事も書いております【本１冊で】Python入門から中級までなれるおすすめ本ご興味がある方は御覧くださいませ。