(23-02-2026, 11:38 PM)rikforto Wrote: You are not allowed to view links. Register or Login to view.it should be possible to construct a text of some length that has word with minimum edit distance 2 apart.
A trivial solution is to ddduuppliiccaattee eevveerryy lleetteerr of every word. Then to change any valid word to any other valid word you need to replace at least two letters.
A more sophistcated trick is to append to each word a letter that serves as a "check digit". Consider the letters A-Z as digits in base 26. Take the words of any language with that alphabet. Add all the letters of each word modulo 26, and append the corresponding letter to the word. Define the result as the new lexicon of the language. Then replacing any letter of the word by a different letter changes the sum modulo 26, hence the "check letter" at the end will not match; you would have to change at least two letters, or a letter and the "check letter", to get another valid word.
With a couple of "check letters" and suitable formulas you can catch also transpositions of letters.
All the best, --stolfi