編集距離 is 何

2つの文字列を比較する指標
以下の3つの操作を何回行うことでs1からs2へ変換できるか
- 置換
- 挿入
- 削除

大雑把な説明

s1からs2へ文字列を変換することを考える

s1 = "aaa"
s2 = "aab"

上記のような文字列だった場合編集距離は1
- 置換が1回

s1 = "aba"
s2 = "cc"

上記のような文字列だった場合編集距離は3
- 置換2回
- 挿入1回

実装

めちゃ便利なpythonモジュールpython-Levenshteinがある
公式ドキュメントはこちら

インストール

pipとかでインストール

$ pip install python-Levenshtein

プログラム

leven.py

import Levenshtein
import sys

args = sys.argv

with open(args[1], "r") as f_ans:
    with open(args[2], "r") as f_ref:
        s_ans = f_ans.read()
        s_ref = f_ref.read()

print(Levenshtein.distance(s_ans, s_ref))

コマンドライン引数に2つのテキストファイルを指定して編集距離を吐き出すだけの簡単なプログラムです.

結果

2つのテキストファイルを用意します.

tmp1.txt

Helllo worb!!

tmp2.txt

Hello world!

tmp1.txtからtmp2.txtへ変換するためには、

"Helllo"の"l"を1個削除
"worb"について
- "l"を追加
- "b"を"d"に置換
"!"を1個削除

よって編集距離は4になるはずです。

$ python leven.py tmp1.txt tmp2.txt
4

なりました。嬉しい。

所感

動的計画法で実装しようと思ったけど、モジュール落ちてるの見つけて実装面倒くさくなった人の書いた記事です。何かあればコメント欄にお願いします。