typescript/string/levenshtein@1 — Count the single-character insertions, deletions and substitutions that turn one string into the other, counting in Unicode code points. 23 named edge cases, settled and frozen. TypeScript source copied into your project: one file, 2 416 bytes, no dependencies. [Toopo](../../../) # typescript/string/levenshtein@1 Count the single-character insertions, deletions and substitutions that turn one string into the other, counting in Unicode code points. ``` toopo add string/levenshtein ``` One file, 2 416 bytes, copied into your project. It imports nothing. You get levenshtein. ## What it does Measures how far apart two strings are in JavaScript and TypeScript, as the smallest number of single-character edits - insert one character, delete one, replace one - that turns the first into the second. It is the classic edit distance and nothing else: a transposition costs two edits rather than one, every edit costs the same, and the result is a count rather than a similarity score between zero and one. The decision that separates implementations of it is invisible in the signature and is settled here: an edit is one Unicode code point, so a string holding one emoji is one edit away from the empty string. The widely used JavaScript implementations count UTF-16 code units instead and answer two, because JavaScript strings are stored as UTF-16 and an emoji occupies two of them. Nothing is normalised, nothing is folded to lower case and nothing is trimmed, so two strings that a person would call the same and a computer would not are one or more edits apart - which is what a caller who wants otherwise applies before calling. The result is always a non-negative whole number, and the function is a metric: zero exactly on two identical strings, the same in both directions, and never improved by a detour through a third string. The language ships no edit distance, and nothing in Intl measures the gap between two strings. ## What it is for, and what it is not Human-authored text held in memory: names, labels, search queries, product codes, identifiers, and short free text. Typo tolerance, deduplication, "did you mean", and the suggestion of a nearest match from a small set. It is not a similarity ratio, not a phonetic match, not a locale-aware comparison, and not an index: a caller ranking one query against a large corpus wants a data structure, and this function is what such a structure would call. Damerau-Levenshtein, where a transposition costs one edit, and weighted edit distances, where the operations cost different amounts, answer different questions and are separate contracts. ## Signature ``` type Levenshtein = (a: string, b: string) => number ``` ## 23 settled cases Every one of them is named, frozen with the major version, and linkable. This is what the contract decides, one input at a time. the region no axiom reaches: the arithmetic anchors, and the unit an edit counts in. ### The two ends of the scale `levenshtein('levenshtein', 'levenshtein') → 0` A string is at distance zero from itself, which is the first axiom made concrete. `levenshtein('', '') → 0` Two empty strings are the same string, so the distance is zero. It is the input an implementation indexing a matrix is most likely to fall off, since the matrix has one cell and no loop body ever runs. `levenshtein('abc', '') → 3` Turning a string into nothing costs one deletion per code point. It is the anchor that fixes the scale: without it, an implementation could halve every answer and satisfy every axiom. `levenshtein('', 'abc') → 3` The same call the other way round, and the cheapest case that can catch an implementation pricing an insertion differently from a deletion. Both directions are named rather than left to the symmetry property, because this is the pair where the price is set. ### One edit of each kind `levenshtein('abc', 'abd') → 1` Replacing one code point costs one edit and not two. An implementation offering only insertion and deletion - which is the longest common subsequence distance, and a real thing a reader may have implemented before - answers two here and is correct everywhere the lengths differ. `levenshtein('ab', 'abc') → 1` Adding one code point costs one edit. `levenshtein('abc', 'ab') → 1` Removing one code point costs one edit, at the same price as adding one. ### The anchors a reader recognises `levenshtein('kitten', 'sitting') → 3` The example every published description of this distance uses: two substitutions and an insertion. It is here so that a reader can check this contract against the definition they already know, without running anything. `levenshtein('Saturday', 'Sunday') → 3` The second example the literature uses, and the one where the shared letters are not in the same positions - an implementation comparing position by position answers six. `levenshtein('flaw', 'lawn') → 2` The shared part sits in the middle, so neither a shared prefix nor a shared suffix can be trimmed. It is the case an implementation that trims common affixes has to get right by doing the work rather than by avoiding it. ### The scope this contract does not cover `levenshtein('ab', 'ba') → 2` Two adjacent code points swapped cost two edits, not one. This is the single decision that separates this contract from Damerau-Levenshtein, where a transposition is one operation, and it is settled on the smallest input that can express it. The two are different distances - Damerau is not a metric refinement of this one, it is another function - so a caller who wants a swapped pair of letters to cost one wants a different contract, not an option here. `levenshtein('form', 'from') → 2` The same decision on the typo a reader will actually meet. It is named separately because \`ab\` and \`ba\` read as an abstract pair, and this one is the input that makes a caller ask why their spelling corrector ranks it below a single substitution. `levenshtein('Alice', 'alice') → 1` An upper-case letter and its lower-case form are two different code points, one edit apart. That is scope rather than a gap: folding the case would make two different strings zero apart, which is the discernibility axiom failing, and it would make the answer depend on the ambient locale, since \`I\` does not lower-case to \`i\` in Turkish. A caller who wants case to be ignored lower-cases both arguments, in the locale it chooses, before calling. `levenshtein('a b', 'ab') → 1` Whitespace is text like any other text: no trimming, no collapsing, no ignoring. Named because a caller comparing user input will meet it on the first day, and because the alternative - a distance that skips whitespace - is not a metric on strings. ### The unit an edit is counted in The region no axiom reaches. Every case below is answered differently by an implementation counting UTF-16 code units, which is what the widely used JavaScript implementations do - and every one of them satisfies all four axioms under either counting, so nothing but these rows decides it. `levenshtein('😀', '') → 1` One emoji is one edit away from nothing. Measured, an implementation counting UTF-16 code units answers two, because an astral character occupies two of them - so a caller who deleted one character is told that two edits happened. This is the case block 4.2 chooses the unit on, and the whole reason this contract diverges from the ecosystem. `levenshtein('a😀b', 'ab') → 1` The same decision where the astral character is surrounded by ordinary text, which is where it actually occurs. An implementation counting code units answers two here as well, and its intermediate step is a string holding half of a character. `levenshtein('😀😀', '😀') → 1` Two identical astral characters against one. It is named because it is the case where a code-unit implementation still answers a plausible number - two - rather than an obviously wrong one, so nothing but the declared unit distinguishes the two answers. `levenshtein('👩\u200D💻', '👩') → 2` A joined emoji sequence is three code points, so removing the joiner and the second symbol costs two edits. Counting grapheme clusters instead would answer one, and block 4.2 records why that unit is refused: it costs thirty times the decomposition, it reads the process default locale, and its boundaries follow whichever Unicode version the runtime carries. `levenshtein('\uD83D', '') → 1` An unpaired surrogate is a code point of its own and costs one edit. It is not a well-formed character and it reaches this function anyway, out of a truncated string or a byte-level slice, so the contract settles it rather than leaving two implementations free to disagree. `levenshtein('😀', '\uD83D') → 1` An emoji against the lone high surrogate that begins it: one substitution, because the two are one code point each. Measured, an implementation counting code units answers one as well and reaches it by a different route - deleting the trailing half - which is why this case is here beside the ones that separate the two conventions rather than instead of them. ### Normalisation is not applied `levenshtein('é', 'e\u0301') → 2` The same glyph written two ways - one precomposed code point against a letter and a combining mark - is two edits apart: one substitution and one insertion. Normalising first would answer zero, and zero for two different strings is the discernibility axiom failing. A caller who wants the two treated as equal normalises both arguments before calling; that composition is exact, and putting it inside this function would take the choice of form away from the caller who has it. `levenshtein('e', 'e\u0301') → 1` Adding a combining mark to a letter costs one edit, because the mark is a code point. It is the half of the decision above that says the two forms are not merely unequal but unequal by a measurable amount. `levenshtein('é', 'e') → 1` The precomposed form against the bare letter is one substitution, where the decomposed form against the bare letter is one insertion. Two ways of writing one glyph sit at the same distance from \`e\` and at distance two from each other, which is the whole shape of what refusing to normalise means. ## Try it on your own input This calls levenshtein on whatever you type. What you type into a field is the value, character for character, and the form opens on identical-text so there is a call that works to edit. What comes back is what the function answered, under the call it was made from — invisible characters are named there, so two inputs that look alike on screen do not print alike. The settled answer is on the case's own line above, and is deliberately not repeated here. The JavaScript this runs is string/levenshtein's own reference.ts with its types stripped. That is neither the file the registry serves nor the file its digest covers: both are TypeScript, and no browser runs TypeScript. It is also the only part of this page that needs JavaScript at all. ## Properties Every property below is checked on 1 000 generated cases per run, re-seeded each time. - `never mutates its arguments — not applicable` The signature takes two \`string\` arguments, primitives that are immutable by construction in JavaScript. No implementation, correct or broken, can violate this, so a test asserting it would be structurally incapable of failing - the same measurement \`number/parse@1\` recorded, confirmed on a second monomorphic signature over primitives. - `deterministic — checked` Violable in practice, and witnessed by L-19 of the battery: an implementation that counts the edits into an accumulator hoisted out of the function - the shape a variable reaches when it is made "reusable" - answers d on the first call and 2d on the second. It is the only witness that reddens this property on its own failure condition. Measured, one other mutant reddens it - L-15, which reads the answer out of the transposed corner of the matrix and throws when the two lengths differ - and a property that has only ever been red on a mutant that throws has not been seen red on the sentence it makes, which is the standard \`array/group-by@1\` set when it wrote M-21. That there is no third witness is a measurement rather than an omission: every other candidate was a cache, and a cache answers a repeated call from its own first answer. This property is ordered under \`no ambient input\` rather than independent of it: every mutant measured to redden it reddens that one too, and the memoise-last mutant reddens that one and not this. L-20 is that mutant here. - `no ambient input — checked` Violable in practice: this function reads no clock, no locale and no time zone, so the call history is the only ambient input it can plausibly acquire, and a cache keyed on a cheap proxy for its arguments is how it acquires it. The property interleaves a probe with an arbitrary history and requires the probe to answer identically either way. Witnessed by L-20, which remembers the last answer under the lengths of the two arguments: measured, it reddens here and leaves determinism green, which is the fourth contract on which that ordering has been measured and the first on which determinism has no independent witness of the same kind. - `no ambient output — not applicable` Not reachable by a property - a test cannot observe a write that happened before it ran, and a correct memoising cache is indistinguishable from a defect by behaviour alone. Confirmed here on a fourth shape without changing a word of it. ## Benchmark profiles The shapes of input an implementation is timed on. No figures yet: there is no reference machine, and a number produced on a developer laptop would be a number with nothing behind it. - `identical — zero` The two strings are the same. The dominant shape in deduplication, and the one a fast path is written for: an implementation that compares the two strings first answers in constant time here and in quadratic time everywhere else. - `one-edit-apart — one-edit` A typo: one character inserted, deleted or replaced. The dominant shape in spelling correction and in "did you mean", and the region a banded implementation is written for - which is why the long sample matters more here than anywhere else, since a band is exactly what turns a quadratic call on a thousand code points into a linear one. - `unrelated — far` Two strings that share no structure, so every cell of the matrix is a real choice, no band helps and no common affix can be trimmed. The worst case, and the one that says at what size an implementation stops being usable. - `against-the-empty-string — the-whole-of-one-side` One side is empty. It is the cheapest possible call that still has to look at all of one argument, and callers filtering a list against a blank query make it far more often than they expect to. - `astral-text — far` Text made of astral characters, where the decomposition into code points allocates two units of storage per unit of length. Measured separately because it is the one shape where the choice of unit has a cost, and a reader comparing implementations should see what it is. ## What you can check yourself This definition is frozen. Its canonical text hashes to 301ec17e491377c525aeb7a015c3941c5707f4f80cacf38f9823ad72c107da5c, and the 7 files of its test harness are listed inside it with their own hashes — so a copy of the harness can be checked against this definition before it is trusted, then run against any implementation, without taking our word for any of it. Written for node, browser, bun.