Python でレーベンシュタイン距離を計算する方法

2 つの文字列間のレーベンシュタイン距離は、ある単語を別の単語に変換するために必要な 1 文字の変更の最小数です。

「改変」という言葉には、置換、挿入、および削除が含まれる。

たとえば、次の 2 つの単語があるとします。

• パーティーする
• 公園

2 つの単語間のレーベンシュタイン距離 (つまり、ある単語を別の単語に変換するために必要な変更の数) は2になります。

実際には、レーベンシュタイン距離は、ファジー文字列マッチング、スペル チェック、自然言語処理など、さまざまなアプリケーションで使用されます。

このチュートリアルでは、Python-Levenshtein モジュールを使用して Python で文字列間のレーベンシュタイン距離を計算する方法を説明します。

このモジュールをインストールするには、次の構文を使用できます。

 pip install python-Levenshtein

次に、レーベンシュタイン距離を計算する関数をロードできます。

 from Levenshtein import distance as lev

次の例は、この関数を実際に使用する方法を示しています。

例 1: 2 つの文字列間のレーベンシュタイン距離

次のコードは、2 つの文字列「party」と「park」の間のレーベンシュタイン距離を計算する方法を示しています。

 #calculate Levenshtein distance
lev(' party ', ' park ')

2

レーベンシュタイン距離は2であることがわかります。

例 2: 2 つのテーブル間のレーベンシュタイン距離

次のコードは、2 つの異なる配列内の文字列のペアごとの組み合わせ間のレーベンシュタイン距離を計算する方法を示しています。

 #define arrays
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

#calculate Levenshtein distance between two arrays
for i,k in zip (a,b):
  print (lev(i, k))

6
4
5
5

結果を解釈する方法は次のとおりです。

• 「マブス」と「ロケッツ」の間のレーベンシュタイン距離は6です。
• 「スパーズ」と「ペイサーズ」の間のレーベンシュタイン距離は4です。
• 「レイカーズ」と「ウォリアーズ」の間のレーベンシュタイン距離は5です。
• 「キャブス」と「セルティックス」の間のレーベンシュタイン距離は5です。

追加リソース

Python でハミング距離を計算する方法
Pythonでユークリッド距離を計算する方法
Python でマハラノビス距離を計算する方法