<jupyter_start><jupyter_text>Levenshtein edit distance<jupyter_code>from edit_distance import levenshtein_matrix, levenshtein

print(inspect.getsource(levenshtein_matrix))
print(inspect.getsource(levenshtein))
assert levenshtein('a', 'a') == 0
assert levenshtein('a', 'b') == 1
assert levenshtein('Foo', 'Bar') == 3
assert levenshtein('', '') == 0
assert levenshtein('Foo', '') == 3
assert levenshtein('', 'Foo') == 3
assert levenshtein('Fnord', 'Food') == 2
assert levenshtein('Müll', 'Mull') == 1
assert levenshtein('Abstand', 'Sand') == 4<jupyter_output><empty_output><jupyter_text>This fails for different representations of the "same" canonically equivalent string:<jupyter_code>word1 = unicodedata.normalize('NFC', 'Schlyñ')
word2 = unicodedata.normalize('NFD', 'Schlyñ')  # Different, decomposed!
levenshtein(word1, word2)
# Same, but for grapheme clusters
from uniseg.graphemecluster import grapheme_clusters

word1 = list(grapheme_clusters(unicodedata.normalize('NFC', 'Schlyñ')))
word2 = list(grapheme_clusters(unicodedata.normalize('NFD', 'Schlyñ')))
levenshtein(word1, word2)<jupyter_output><empty_output><jupyter_text>Better. Let's define a edit distance function that uses the basic Levenshtein algorithm, but knows about Unicode normalization and grapheme clusters!<jupyter_code>from edit_distance import distance
print(inspect.getsource(distance))
word1 = unicodedata.normalize('NFC', 'Schlyñ')
word2 = unicodedata.normalize('NFD', 'Schlyñ')  # Different, decomposed!

distance(word1, word2)<jupyter_output><empty_output><jupyter_text>This should give us the correct answer of 1 for 'Schlyñ' (with LATIN SMALL LETTER N WITH TILDE) vs 'Schlym̃' (with LATIN SMALL LETTER M + COMBINING TILDE):<jupyter_code>word1 = 'Schlyñ'
word2 = 'Schlym̃'
#print('Lengths, as far as Python is concerned:', len(word1), len(word2))  # → gives 6 and 7!
distance(word1, word2)<jupyter_output><empty_output><jupyter_text>Edit operationspython-Levenshtein supports backtracing, i.e. giving a sequence of edit options that transforms a word to another word:<jupyter_code>import Levenshtein
word1 = 'Schlyñ'  # with LATIN SMALL LETTER N WITH TILDE
word2 = 'Schlym̃'  # with LATIN SMALL LETTER M + COMBINING TILDE
print(Levenshtein.editops(word1, word2))<jupyter_output>[('insert', 5, 5), ('replace', 5, 6)]<jupyter_text>Note that it does not work with grapheme clusters, but "characters", so it gives 2 operations. Defining our own `editops()`. (This looks a bit wild due to our own tail recursion handling.)<jupyter_code>from edit_distance import seq_editops, editops
print(inspect.getsource(seq_editops))
print(inspect.getsource(editops))
editops('Foo', 'Fon')
print(editops('Käptn', 'Käpt\'n'))
print(Levenshtein.editops('Käptn', 'Käpt\'n'))
print(editops('Delete something', 'Deletesomething'))
print(Levenshtein.editops('Delete something', 'Deletesomething'))
print(editops('A more difficult example', 'Amore difficült  exampl'))
print(Levenshtein.editops('A more difficult example', 'Amore difficült  exampl'))<jupyter_output>[('delete', 1, 1), ('replace', 13, 12), ('insert', 17, 16), ('delete', 23, 23)]
[('delete', 1, 1), ('replace', 13, 12), ('insert', 16, 15), ('delete', 23, 23)]<jupyter_text>XXX Note that our implementation returns different positions here for the 'insert'.  Let's try it with a difficult example that needs grapheme cluster handling:<jupyter_code>word1 = 'Schlyñ'  # with LATIN SMALL LETTER N WITH TILDE
word2 = 'Schlym̃'  # with LATIN SMALL LETTER M + COMBINING TILDE

editops(word1, word2)<jupyter_output><empty_output><jupyter_text>🎉  Character error rate[digitisation.eu](https://sites.google.com/site/textdigitisation/qualitymeasures/computingerrorrates) defines the character error rate (CER) as:$$\text{CER} = \frac{i + s + d}{n}$$where $i$ is the number of inserts, $s$ the number of substitutions, $d$ the number of deletions and $n$ is the number of characters in the reference text. (The text is not super clear about $n$ being the number of characters in the reference text, but it seems appropiate as they *are* clear about this when computing the word error rate.) Because our edit distance is equal to $i + s + d$, we can thus define:<jupyter_code>from character_error_rate import character_error_rate
print(inspect.getsource(character_error_rate))
assert character_error_rate('Foo', 'Bär') == 3/3
assert character_error_rate('Fnord', 'Food') == 2/5
assert character_error_rate('Food', 'Fnord') == 2/4
assert character_error_rate('Schlyñ', 'Schlym̃') == 1/6
# From experiments/2019-07-ocrevalUAtion: These are already preprocessed by the equivalences in equivalences-tess-frk.csv.
gt = """115 über die vielen Sorgen wegen deſſelben vergaß Hartkopf, der Frau Amtmännin das ver⸗ ſprochene zu überliefern. — Ein Erpreſſer wurde an ihn abgeſchickt, um ihn ums Him⸗ melswillen zu ſagen, daß er das Verſprochene gleich den Augenblick überbringen möchte, die Frau Amtmännin hätte ſich auf ihn verlaſſen, und nun wüßte ſie nicht, was ſie anfangen ſollte. Den Augenblick ſollte er kommen, ſonſt vergieng ſie in ihrer Angſt. — Die Gäſte wären ſchon angekommen, und es fehlte ihr doch noch an allem. — Hartkopf mußte ſich erſt beſinnen, und endlich nach langem Nachdenken fiel es ihm erſt wieder ein. — Er langte den Zettel aus dem Accisbuche heraus, und ſagte ſeiner Frau, daß ſie das, was da wäre, herbeyſchaffen möchte. Jndeß mangelten doch einige Generalia, die alſo wegfielen. — Hartkopf gieng ſelbſt mit und überbrachte es. — „<NAME>! er böſer Mann!“ — ſchrie ihm die Frau Amtmännin entgegen, und ſchlug ihn auf die Schulter und blickte den Korb, der voll gedrückt, gerüttelt und überﬂüſſig in ihren Schoos gegeben werden ſollte, mit Augen voller Freu⸗ H 2"""
tess = """emm unmit; <NAME> die vielen Sorgen wegen" deſſelben vergaß Hartkopf, der Frau! Amimännin das- ver ſprochene zu überliefeen. ==" Ein Epypreſſer- wurde an ihn abgeſchieet', um' ihn ums Hime melswillen zu ſagen, "daß er das Verſyrochene leich den Augenblick "überbringen möchte, die Frau Amtmännin hätte ſich auf ihn veriaſſen, und nun wüßte ſie- nicht, was ſie anfangen ſollte, =! 'Den Augenblick ſollte "er kommen, ſonſt vergieng ſie in ihrer Angſt. == Die Säuaſie- wären. ſchon angekommen, und es fehlte ihr do < noch an alien, === Hartfopyf mußte ſich erſt TIM und endlich mach langem Rachdenken fiel es ihm erſt wieder ein, ==. Ex langte den Zettel aus dem- Accisbuche heraus, und ſagte ſeiner Frau, daß ſie das , was da wäre, herbeyſchaffen mschte. ZIudeß „mangelten doch einige Generalia, die alſo wegfielen. == ' Havrkopf gieng ſelbſt mit und überbrachte es == | „<NAME>! er böſer Mann 1-2 ſchrie ihm die Frau Amtmännin entgegen, und ſchlug ihn auf die Schulter und blickte den Korb, der - voll gedrückt, gerüttelt und überfirfſig in ihren Ss HEILE werden ſolite, mit Augen voller EE) Fron?"""
print('{:.4f}'.format(character_error_rate(gt, tess)))<jupyter_output>0.1190<jupyter_text>XXX This gives a smaller CER than ocrevalUAtion (which gives 0.1228). Why?<jupyter_code>levenshtein(gt, tess)/len(gt)<jupyter_output><empty_output><jupyter_text>That's ~ the same, so I think it's not about the character segmentation. Check that we're only dealing with single-codepoint grapheme clusters:<jupyter_code>for w in gt, tess:
    for g in grapheme_clusters(w):
        assert len(g) == 1<jupyter_output><empty_output><jupyter_text>Maybe ocrevalUAtion doesn't count whitespace?<jupyter_code>def remove_whitespace(s):
    return s.replace(' ', '')
remove_whitespace(gt)
print('{:.4f}'.format(character_error_rate(remove_whitespace(gt), remove_whitespace(tess))))<jupyter_output>0.1324<jupyter_text>Now it's larger than ocrevalUAtion 🤷‍♂️  Word error rate  Word segmentation Naively split on spaces.(Note: ocrevalUAtion does confusing things here, like the Token splitting in a hash function, with an empty pattern?!)<jupyter_code>def naive_word_split(s):
    return s.split(' ')
example_text = "The quick (“brown”) fox can't jump 32.3 feet, right?"
naive_word_split(example_text)<jupyter_output><empty_output><jupyter_text>Let's do it the Unicode way (Appendix UAX 29 on Unicode Text Segmentation): Split on word boundaries using the uniseg libraries and ignore words that contain only whitespace, punctuation "and similar characters":<jupyter_code>from word_error_rate import words
print(inspect.getsource(words))

list(words(example_text))
list(words('Der schnelle [„braune“] Fuchs kann keine 3,14 Meter springen, oder?'))
list(words('Dies ist ein Beispielsatz. Oh, ja.'))<jupyter_output><empty_output><jupyter_text>It's probably not correct for Chinese and Japanese, but at least it doesn't rely on spaces.<jupyter_code>list(words('我很高興跟你見面'))  # "Pleased to meet you" in Mandarin, Traditional writing
list(words('医者を呼んでください。'))<jupyter_output><empty_output><jupyter_text>Word error rate For the word error rate, normalize again and compare sequences of words.<jupyter_code>from word_error_rate import word_error_rate
print(inspect.getsource(word_error_rate))
word_error_rate('Dies ist ein Beispielsatz.', 'Dies isi ein Beispielsatz,')
word_error_rate('Fnord ist verdampfter Kräutertee!', 'Fnòrd ist verdmpfter Krautertee.')
word_error_rate(gt, tess)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10636908002177463, 'fraction_numerical': 0.012738160043549265, 'mean_word_length': 6.616915422885572, 'pattern_counts': {'":': 1, '<': 61, '<?xml version=': 0, '>': 60, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '540677', 'license': 'Apache-2.0', 'n_tokens_mistral': 3431, 'n_tokens_neox': 3312, 'n_words': 1007, 'path': 'qurator/dinglehopper/notebooks/Levenshtein.ipynb', 'repo_name': 'ulb-sachsen-anhalt/dinglehopper', 'size': '9197'}