レーベンシュタイン距離（Levenshtein Distance）というのは、大まかな意味として、編集距離というもので、ある文字列をどうにか加工した際の加工手数みたいなものを調べるものです。結果として、ある文字列とある文字列はどのくらいの加工回数で同じになるということがわかれば、文字列の類似度を考えることができるということになりますね。PHPで関数を作って使ってましたがPythonは簡単らしいので、試してみたいと思います。

Levenshtein　をインストールする

condaでインストールできる。。。と思ったらパッケージが見つからなかったので、pipでいきます。

#condaでパッケージがあるかどうかチェック
$ conda search leven

No match found for: leven. Search: *leven*

PackagesNotFoundError: The following packages are not available from current channels:

  - leven

Current channels:

  - https://repo.anaconda.com/pkgs/main/osx-64
  - https://repo.anaconda.com/pkgs/main/noarch
  - https://repo.anaconda.com/pkgs/r/osx-64
  - https://repo.anaconda.com/pkgs/r/noarch

To search for alternate channels that may provide the conda package you're
looking for, navigate to

    https://anaconda.org

and use the search bar at the top of the page.

#ないらしいので、普通に。。

$ pip install python-Levenshtein

Collecting python-Levenshtein
  Downloading https://files.pythonhosted.org/packages/42/a9/d1785c85ebf9b7dfacd08938dd028209c34a0ea3b1bcdb895208bd40a67d/python-Levenshtein-0.12.0.tar.gz (48kB)
     |████████████████████████████████| 51kB 1.8MB/s 
Requirement already satisfied: setuptools in /Users/XXXXXXXXX/anaconda3/envs/new_conda/lib/python3.7/site-packages (from python-Levenshtein) (41.0.1)
Building wheels for collected packages: python-Levenshtein
  Building wheel for python-Levenshtein (setup.py) ... done
  Created wheel for python-Levenshtein: filename=python_Levenshtein-0.12.0-cp37-cp37m-macosx_10_9_x86_64.whl size=79394 sha256=565334f302cad39212a95473a6a71dcecc4de0682e5586af7ffa4ef0ab5537b7
  Stored in directory: /Users/XXXXXXXXX/Library/Caches/pip/wheels/de/c2/93/660fd5f7559049268ad2dc6d81c4e39e9e36518766eaf7e342
Successfully built python-Levenshtein
Installing collected packages: python-Levenshtein
Successfully installed python-Levenshtein-0.12.0

Successfully！！なんて力強い言葉でしょう！英語はわかりませんが、間違いなく成功に関して語ってるとみて間違いないでしょう。

実際にレーベンシュタイン距離を求めてみよう

関数に文字列２つぶち込んだら、数値を返してくれるだけなので、そんな難しくないので気軽に実行

import Levenshtein
str1="すもももももももものうち"
str2="あいだもも"

Levenshtein.distance(str1, str2)

#実行結果
10

ふむ。。。10ですって。すもももももももものうち　という言葉を入れた時に、頭に浮かんだ言葉が「あいだもも」だったんですが、あいだももってなんやねんと思いましたが、そのまま使ってみました。

10ね。。。まぁ、似てると自分では思ってたけど、よくみたら似てませんしね。もうちょっとやってみます

import Levenshtein
str1="すもももももももものうち"
str2="すももももももももいちご"

Levenshtein.distance(str1, str2)

#実行結果
3

ふむ。。。確かに３文字。。。いじったんでしょうね。削除や追加、変更を使って。。

ん。。。？次のパターンはどうなるだろう？

import Levenshtein
str1="のうち"
str2="いちご"

Levenshtein.distance(str1, str2)

#実行結果
3

うん、これでわかった。距離はあくまで実数ですから、どのくらい似てるか？を表すものではないですね。
もともとの文字の文字数に対して、距離をあててみたらどうなるでしょう？


import Levenshtein

str1="すもももももももものうち"
str2="すももももももももいちご"

if len(str1) > len(str2):
 max_len1 = len(str1)
else:
 max_len1 = len(str2)

Levenshtein.distance(str1, str2)/max_len1

str3="のうち"
str4="いちご"

if len(str3) > len(str4):
 max_len3 = len(str3)
else:
 max_len3 = len(str4)

Levenshtein.distance(str1, str2)/max_len1
Levenshtein.distance(str3, str4)/max_len3
#実行結果
0.25
1.0

うん、結果の最大値は1 なんですけど、文字列が長い時の方が数値が小さい以上、類似度を考えるには、前者の比較の方が類似度は高いのでしょう。

ちょっと簡単にですが、類似度をレーベンシュタイン距離で考えてみました。

コメント