編集距離配布ページ

2つの文字列の編集距離（Edit Distance、Levenshtein Distance、レーベンシュタイン距離）を計算して出力します。

http://books.google.com/books?id=fZmj5UNK8AQC&pg=PA76&lpg=PA76&dq=levenshtein+distance+backtrace&source=bl&ots=LqSd37JHQE&sig=N15ghl7M6oEaCIjUP18mU-02-1w&hl=en&ei=zmVESsi1F46GkAXMpJClDw&sa=X&oi=book_result&ct=result&resnum=1

計算に用いたマトリックスと編集スクリプトも出力できます。

C++で高速に処理します。

説明書
圧縮ファイル

スクリプト 1

intexecuntion

delete i
delete n
delete t
insert x
insert e
insert c
insert u
delete n

スクリプト 2

exintecuntion

insert e
insert x
delete i
delete n
delete t
insert c
insert u
delete n

スクリプト 3

eixntecuntion

insert e
delete i
insert x
delete n
delete t
insert c
insert u
delete n

スクリプト 4

iexntecuntion

delete i
insert e
insert x
delete n
delete t
insert c
insert u
delete n

スクリプト 5

iexntecuntion

substitute i by e
insert x
delete n
delete t
insert c
insert u
delete n

スクリプト 6

eixntecuntion

insert e
substitute i by x
delete n
delete t
insert c
insert u
delete n

スクリプト 7

einxtecuntion

insert e
delete i
delete n
insert x
delete t
insert c
insert u
delete n

スクリプト 8

ienxtecuntion

delete i
insert e
delete n
insert x
delete t
insert c
insert u
delete n

スクリプト 9

ienxtecuntion

substitute i by e
delete n
insert x
delete t
insert c
insert u
delete n

スクリプト 10

inextecuntion

delete i
delete n
insert e
insert x
delete t
insert c
insert u
delete n

スクリプト 11

inextecuntion

delete i
substitute n by e
insert x
delete t
insert c
insert u
delete n

スクリプト 12

einxtecuntion

insert e
delete i
substitute n by x
delete t
insert c
insert u
delete n

スクリプト 13

ienxtecuntion

delete i
insert e
substitute n by x
delete t
insert c
insert u
delete n

スクリプト 14

ienxtecuntion

substitute i by e
substitute n by x
delete t
insert c
insert u
delete n

スクリプト 15

eintxecuntion

insert e
delete i
delete n
delete t
insert x
insert c
insert u
delete n

スクリプト 16

ientxecuntion

delete i
insert e
delete n
delete t
insert x
insert c
insert u
delete n

スクリプト 17

ientxecuntion

substitute i by e
delete n
delete t
insert x
insert c
insert u
delete n

スクリプト 18

inetxecuntion

delete i
delete n
insert e
delete t
insert x
insert c
insert u
delete n

スクリプト 19

inetxecuntion

delete i
substitute n by e
delete t
insert x
insert c
insert u
delete n

スクリプト 20

intexecuntion

delete i
delete n
delete t
insert e
insert x
insert c
insert u
delete n