This is a useful discussion of both the algorithmic and implementation-level trade-offs in Levenshtein distance, particularly the two-row optimization and the distinction between pairwise comparison and dictionary search.
A few additional points may be helpful for anyone revisiting these AppleScript implementations.
1. Quadratic time is not exponential time
The classical Wagner–Fischer dynamic programming algorithm takes O(mn) time for strings of lengths m and n.
For two strings of similar length, this is O(n²), not exponential. AppleScript’s list-access overhead can make the implementation feel much slower, but that should be distinguished from the algorithm’s asymptotic complexity.
The rolling-row implementations discussed above also reduce auxiliary storage from O(mn) to O(min(m,n)) when only the distance value is required.
2. Transpositions change the distance model
The original example includes “informatoin” versus “information”, where adjacent characters have been transposed.
Under standard Levenshtein distance, an adjacent transposition is not a primitive edit. For example:
- distance(“ab”, “ba”) = 2 under standard Levenshtein;
- distance(“ab”, “ba”) = 1 when adjacent transposition is permitted.
This is worth documenting when comparing the AppleScript implementations with spell-checking software that supports Damerau–Levenshtein-style edits.
3. Indexing and edit distance are complementary
The discussion about spell checkers narrowing the dictionary before performing approximate matching raises an important distinction.
Given a query q and an edit threshold k, the goal of exact fuzzy retrieval is to find every dictionary term t satisfying:
ED(q, t) <= k
A simple safe rejection rule is:
|length(q) - length(t)| > k
because the difference in string lengths is a lower bound on the number of insertions or deletions required.
Other techniques include length-based indexing, suitable q-gram filters, trie traversal with Levenshtein automata, and banded dynamic programming.
The critical requirement is that candidate filtering must not discard a valid match if exact retrieval is intended.
There is a more detailed treatment of this distinction in indexing and filtering for exact edit-distance search.
Disclosure: I am affiliated with Levenshtein.net.
4. Character comparison semantics matter
One final consideration for AppleScript is whether comparison should be case-sensitive and how Unicode text is handled. Different choices of character representation or normalization can change the computed distance.
Overall, the two-row implementation is a solid starting point. For spell checking or autocomplete over a large dictionary, the larger performance gain may come from reducing the number of candidate comparisons rather than further optimizing the inner dynamic programming loop.
