editdistance produces incorrect results for some inputs

[fujimotos]

Bug Report

My research team uses editdistance for ML/DL model evaluation.

During research, I noticed that sometimes error rates (computed by $\frac{EditDistance}{NumberOfCharacters}$)
are little off than expected values. After a bit of investigation, it turned out that
editdistance.eval can produce a different result than other Levenshtein libraries
for some inputs.

Attached is the minimum script to reproduce this issue. I can cofirm that
editdistance reports Levenshtein distance is 58 while other libraries say 59.

Environment

• Ubuntu 20.04
• Python 3.8.10 (default, Mar 13 2023, 10:26:41)
• editdistance 0.6.2

How to reproduce

1. Install the latest version of editdistance from PyPI.
2. Run the script attached below.

# Original text: https://www.aozora.gr.jp/cards/000329/files/18387_11946.html
import editdistance

# Levenshtein and jellyfish is for comparison purposes.
import Levenshtein
import jellyfish

text = """大そうけちんぼな和尚さんがありました。
何かよそからもらってもいつでも自分一人でばかり食べて小僧には一つもくれませんでした。
小僧はそれをくやしがっていつかすきを見つけて和尚さんからおいしいものを召し上げてやろうと考えていました。
ある日和尚さんは檀家から大そうおいしいあめをもらいました。
ある日和尚さんはそのあめをつぼの中に入れてそっと仏壇の下にかくしてないしょで独りでなめていました。
ところがある日和尚さんは用事があって外へ出て行きました。
出て行きがけに和尚さんは小僧にいいつけて「この仏壇の下のつぼにはだいじなものが入っている見かけはあめのようだけれど
ほんとうは一口でもなめたらころりとまいってしまうひどい毒薬だ。命が惜しいと思ったらけっしてなめてはならないぞ」といい置いて出て行きました。
和尚さんが出てしまうと小僧はさっそくつぼを引きずり出して残らずあめをなめてしまいました。
それから和尚さんの大切にしている茶わんをわざと真っ二つに割って自分は布団をかぶってうんうんうなりながらいまにも死にかけているようなふりをしていました。
夕方になって和尚さんが帰って来てみますと中は真っ暗で明りもついていませんでした。
和尚さんはおこってこらこら小僧何をしているとどなりました。
すると小僧は布団の中から虫の鳴くような声を出して「和尚さんごめん下さいわたしは死にます。
もうとても助かりません死んだあとはかわいそうだと思ってお経の一つも読んで下さい」といいました。
和尚さんはだしぬけに妙なことをいわれてびっくりしました。
「小僧小僧いったいどうしたのだ」
「きょう和尚さんのたいじなお湯飲みを洗っていますといきなり猫がじゃれかかって来て」"""

pred = """大層ケチンボなおしょうさんがありました。
何かよそからもらってもいつでも自分一人でばかり食べて小僧には一つもくれませんでした。
小僧はそれを悔しがっていつかすきを見つけておしょうさんからおいしいものを召し上げてやろうと考えていました。
ある日和尚さんは檀家から大そうおいしいあめをもらいました。
ある日和尚さんはそのあめをつぼの中に入れてそっと仏壇の下にかくしてないしょで独りでなめていました。
ところがある日和尚さんは用事があって外へ出て行きました。
出て行きがけに和尚さんは小僧にいいつけて「この仏壇の下のつぼにはだいじなものが入っている見かけはあめのようだけれど
ほんとうは一口でもなめたらころりとまいってしまうひどい毒薬だ。命が惜しいと思ったらけっしてなめてはならないぞ」といい置いて出て行きました。
和尚さんが出てしまうと小僧はさっそくつぼを引きずり出して残らずあめをなめてしまいました。
それから和尚さんの大切にしている茶わんをわざと真っ二つに割って自分は布団をかぶってうんうんうなりながらいまにも死にかけているようなふりをしていました。
夕方になって和尚さんが帰って来てみますと中は真っ暗で明りもついていませんでした。
和尚さんはおこってこらこら小僧何をしているとどなりました。
すると小僧は布団の中から虫の鳴くような声を出して和尚さんごめん下さいわたしは死にます。
もうとても助かりません死んだあとはかわいそうだと思ってお経の一つも読んで下さい」といいました。
和尚さんはだしぬけに妙なことをいわれてびっくりしました。
「小僧小僧いったいどうしたのだ」"""

# editdistance.eval               => 58
# Levenshtein.distance            => 59
# jellyfish.levenshtein_distance  => 59
print("editdistance.eval               => %i" % editdistance.eval(text, pred))
print("Levenshtein.distance            => %i" % Levenshtein.distance(text, pred))
print("jellyfish.levenshtein_distance  => %i" % jellyfish.levenshtein_distance(text, pred))