ある文字列Aに対して『1文字の追加・削除・置換』を何回繰り返せば他の文字列Bになるか。このときの最小回数を、文字列A, B間の編集距離 (Levenshtein Distance)と呼ぶ。
- 花火 から 火花 までの編集距離は各文字の置換なので 2
- クワガタ から カブトムシ までの編集距離はなんかもう全文字違うので総入れ替え＆文字『シ』の追加で 5
この編集距離、文字列の“類似度”と見ることができて、なかなか便利な子である。『Job Titleの前処理＆クラスタリングをどうやって実現するか問題』では、人々の肩書きを編集距離を使って前処理（クラスタリング）している事例も紹介した。
さて、ここでは Levenshtein Distance を求めるアルゴリズムを実装して、備忘録として書き留めておく。ネット上にも多数の解説記事があり「今更ァ？」という話だが、正直どれを読んでもピンとこなかったのだ。
アルゴリズム
動的計画法 (DP) です。おわり。
Wikipedia に書かれている擬似コードをそのまま実装すると次のような感じ：
def levenshtein(s1, s2):
"""
>>> levenshtein('kitten', 'sitting')
3
>>> levenshtein('あいうえお', 'あいうえお')
0
>>> levenshtein('あいうえお', 'かきくけこ')
5
"""
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
cost = 0 if s1[i - 1] == s2[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1, # insertion
dp[i][j - 1] + 1, # deletion
dp[i - 1][j - 1] + cost) # replacement
return dp[n][m]
二次元配列 dp の中身は、たとえば levenshtein('kitten', 'sitting') を実行した後だと：
| - s i t t i n g
----------------------------
- | 0 1 2 3 4 5 6 7
k | 1 1 2 3 4 5 6 7
i | 2 2 1 2 3 4 5 6
t | 3 3 2 1 2 3 4 5
t | 4 4 3 2 1 2 3 4
e | 5 5 4 3 2 2 3 4
n | 6 6 5 4 3 3 2 3
理解
たとえば、この 4 は、文字列 ki から sitti までの編集距離を意味する：
| - s i t t i n g
----------------------------
- | .
k | .
i | . . . . . 4
t |
t |
e |
n |
アルゴリズムでは、まず dp を次のように初期化する：
| - s i t t i n g
----------------------------
- | 0 1 2 3 4 5 6 7
k | 1
i | 2
t | 3
t | 4
e | 5
n | 6
空文字列から sitting のx文字目までの編集距離と、kittenのy文字目から空文字列までの編集距離。これは自明。
そして空白をうめていく。k（kittenの一文字目）とs（sittingの一文字目）の編集距離、つまり X (= dp[i][j] ) の値はなにか：
(j)
| - s i t t i n g
----------------------------
- | 0 1 2 3 4 5 6 7
(i) k | 1 X
i | 2
t | 3
t | 4
e | 5
n | 6
最初に書いたとおり可能な操作は『1文字の追加・削除・置換』で、dp[i][j]に隣接する既知の編集距離から：
| 既知の編集距離（文字列A→B） | 操作 (+1) | 得られる編集距離 | ||
|---|---|---|---|---|
dp[i-1][j] |
'-'（空文字列）→ 's' | 文字列 A '-' に 'k' を追加 ( → 's' ) | 'k' → 's' | dp[i][j] |
dp[i][j] |
'k' → 's' | ( 'k' → ) 文字列 B 's' から 's' を削除 | 'k' → '-' | dp[i][j-1] |
dp[i-1][j-1] |
'-' → '-' | 文字列 A の次の文字 'k' を 's' に置換 | 'k' → 's' | dp[i][j] |
つまり、
dp[i-1][j]とdp[i][j]の差は追加操作1回分dp[i][j]とdp[i][j-1]の差は削除操作1回分dp[i-1][j-1]とdp[i][j]の差は置換操作1回分
とわかる。
ただし、置換操作は文字列 A と B の次の文字が既に一致していれば『何もしない』。すなわち、編集距離として dp[i-1][j-1] と dp[i][j] は等しくなる。
以上が
cost = 0 if s1[i - 1] == s2[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1, # insertion
dp[i][j - 1] + 1, # deletion
dp[i - 1][j - 1] + cost) # replacement/noop
でやっていること。編集距離は最小の操作回数なので追加・削除・置換の min をとる。
あとは同様に、隣接する既知の編集距離から表を埋めていけば、最後（右下）に kitten と sitting の編集距離が得られる。
| - s i t t i n g
----------------------------
- | 0 1 2 3 4 5 6 7
k | 1 1 2 3 4 5 6 7
i | 2 2 1 2 3 4 5 6
t | 3 3 2 1 2 3 4 5
t | 4 4 3 2 1 2 3 4
e | 5 5 4 3 2 2 3 4
n | 6 6 5 4 3 3 2 3
めでたしめでたし。
こういう応用範囲の広いシンプルなアルゴリズムは好きです。
Presto や Hive にも近年実装されました。みなさん積極的に使いましょう。（とはいえ計算量 $\mathcal{O}(nm)$ は下手に CROSS JOIN とかすると重すぎて詰むので、過去に求めた編集距離はキャッシュしておくなど、ご利用は計画的に。）
シェアする
カテゴリ
あわせて読みたい
- 2021-07-20
- 『AIアルゴリズムマーケティング』は期待ハズレだったけど手元に置いておきたい一冊
- 2017-08-09
- あのときのビールをもう一度（PostgreSQLでFuzzy Searchを試す）
- 2017-07-09
- Job Titleの前処理＆クラスタリングをどうやって実現するか問題
最終更新日: 2022-01-18
書いた人: たくち
Takuya Kitazawa（たくち）です。長野県出身、カナダ・バンクーバー在住のソフトウェアエンジニア。これまでB2B/B2Cの各領域で、Web技術・データサイエンス・機械学習のプロダクト化および顧客への導入支援・コンサルティング、そして関連分野の啓蒙活動に携わってきました。現在は主に北米（カナダ）、アジア（日本）、アフリカ（マラウイ）の個人および企業を対象にフリーランスとして活動中。詳しい経歴はレジュメ を参照ください。いろいろなまちを走って、時に自然と戯れながら、その時間その場所の「日常」を生きています。ご意見・ご感想およびお仕事のご相談は [email protected] まで。
近況 一杯のコーヒーを贈る免責事項
- Amazonのアソシエイトとして、当サイトは amazon.co.jp 上の適格販売により収入を得ています。
- 当サイトおよび関連するメディア上での発言はすべて私個人の見解であり、所属する（あるいは過去に所属した）組織のいかなる見解を代表するものでもありません。
- 当サイトのコンテンツ・情報につきまして、可能な限り正確な情報を掲載するよう努めておりますが、個人ブログという性質上、誤情報や客観性を欠いた意見が入り込んでいることもございます。いかなる場合でも、当サイトおよびリンク先に掲載された内容によって生じた損害等の一切の責任を負いかねますのでご了承ください。
- その他、記事の内容や掲載画像などに問題がございましたら、直接メールでご連絡ください。確認の後、対応させていただきます。