Levenshtein Distance Calculator

Levenshtein distance counts the cheapest sequence of insertions, deletions and substitutions that turns one string into another — the metric behind spell checkers, deduplication, fuzzy joins and 'did you mean' search. This calculator gives you the distance, the full dynamic-programming matrix so you can see how the answer was reached, the exact edit path, and the numbers you would get from Damerau-Levenshtein, Hamming distance and PostgreSQL's pg_trgm similarity(). It also writes the SQL for doing the same thing in a database with fuzzystrmatch and a trigram index. Everything is computed in your browser — no text is sent anywhere.

String A

String B

CaseWhitespaceInsert costDelete costSubstitute cost

Result

Levenshtein distance:            3
Normalised similarity:           57.1%  (1 − distance / 7)
Damerau-Levenshtein (OSA):       3
Hamming distance:                n/a — strings differ in length
pg_trgm similarity() equivalent: 0.0714  (below the default 0.3 threshold)

Left  (6 chars): "kitten"
Right (7 chars): "sitting"
Costs: insert 1, delete 1, substitute 1 — the classic Levenshtein definition.

Dynamic programming matrix

    ε  s  i  t  t  i  n  g
ε   0  1  2  3  4  5  6  7
k   1  1  2  3  4  5  6  7
i   2  2  1  2  3  4  5  6
t   3  3  2  1  2  3  4  5
t   4  4  3  2  1  2  3  4
e   5  5  4  3  2  2  3  4
n   6  6  5  4  3  3  2  3

Edit path

substitute 'k' → 's'      (position 1, cost 1)
keep   'i'                 (position 2)
keep   't'                 (position 3)
keep   't'                 (position 4)
substitute 'e' → 'i'      (position 5, cost 1)
keep   'n'                 (position 6)
insert 'g'                 (before position 7, cost 1)

The same comparison in SQL

-- PostgreSQL: levenshtein() lives in the fuzzystrmatch extension
CREATE EXTENSION IF NOT EXISTS fuzzystrmatch;

SELECT levenshtein('kitten', 'sitting');                 -- 3
SELECT levenshtein_less_equal('kitten', 'sitting', 3);   -- stops early once the distance exceeds 3
SELECT levenshtein('kitten', 'sitting', 1, 1, 1); -- ins, del, sub costs

-- Trigram similarity is usually the faster way to search a whole table,
-- because unlike levenshtein() it can use an index:
CREATE EXTENSION IF NOT EXISTS pg_trgm;
SELECT similarity('kitten', 'sitting');                  -- 0.0714

CREATE INDEX products_name_trgm_idx ON products USING GIN (name gin_trgm_ops);

-- Index-backed fuzzy lookup: filter with the % operator, then rank the survivors
SELECT id, name, similarity(name, 'sitting') AS score
FROM products
WHERE name % 'sitting'
ORDER BY score DESC
LIMIT 10;

-- Tighten or loosen matching for the current session:
SET pg_trgm.similarity_threshold = 0.4;

-- Levenshtein as a second-pass re-ranker on the small candidate set only:
WITH candidates AS (
  SELECT id, name FROM products WHERE name % 'sitting' LIMIT 200
)
SELECT id, name, levenshtein(lower(name), lower('sitting')) AS edits
FROM candidates
ORDER BY edits
LIMIT 10;

-- MySQL 8 has no built-in levenshtein(); the usual substitutes are:
SELECT SOUNDEX('kitten') = SOUNDEX('sitting') AS sounds_alike;
SELECT MATCH(name) AGAINST ('sitting' IN NATURAL LANGUAGE MODE) FROM products;

Notes

• Levenshtein distance is the minimum number of single-character insertions, deletions and substitutions that turn one string into the other. The matrix above is the standard Wagner-Fischer dynamic program: each cell is the cheapest of the three moves that can reach it, and the bottom-right cell is the answer.
• Damerau-Levenshtein additionally counts a transposition of two adjacent characters as one edit instead of two. It is the better metric for typing errors, where 'teh' for 'the' is one slip, not two.
• levenshtein() in PostgreSQL cannot use an index — it has to compute the distance for every row, so it is O(rows × m × n). On tables of any size, filter first with a pg_trgm index and the % operator, then re-rank the few hundred survivors with levenshtein().
• Trigram similarity is a set comparison, not an edit count: PostgreSQL pads the string with two leading spaces and one trailing space, splits it into 3-character windows, and divides the size of the intersection by the size of the union. That is why very short strings score low even when they look close.
• levenshtein_less_equal() with a maximum abandons the computation as soon as the distance is guaranteed to exceed your bound, which is much faster than computing the exact distance and discarding it.
• Normalise before comparing: lowercasing, trimming whitespace and stripping accents with unaccent() usually matters more for match quality than the choice of algorithm.

Do more than levenshtein distance calculator — meet Chat2DB

Chat2DB is an AI-powered SQL client for Windows, macOS and Linux. Write SQL in natural language, format and optimize queries automatically, and manage MySQL, PostgreSQL, Oracle and 20+ other databases in one workspace.

How to use

Type or paste the two strings you want to compare.
Optionally change the insert, delete and substitute costs, or switch to case-insensitive comparison for a real-world match.
Read the distance and similarity, inspect the matrix and edit path to understand the result, and copy the SQL to run the same comparison in PostgreSQL.

Frequently asked questions

What is Levenshtein distance and how is it calculated?

It is the minimum number of single-character edits — insertions, deletions and substitutions — needed to change one string into another. The standard algorithm (Wagner-Fischer) fills an (m+1) × (n+1) matrix where cell [i][j] is the distance between the first i characters of one string and the first j of the other. Each cell is the smallest of three options: the cell above plus a deletion, the cell to the left plus an insertion, and the diagonal cell plus a substitution (or plus zero if the characters match). The bottom-right cell is the distance. 'kitten' to 'sitting' is 3: substitute k→s, substitute e→i, and insert g.

What is the difference between Levenshtein and Damerau-Levenshtein distance?

Damerau-Levenshtein adds a fourth operation: transposing two adjacent characters counts as one edit. Plain Levenshtein scores 'form' against 'from' as 2, because it must substitute twice; Damerau-Levenshtein scores it as 1. For human typing errors, transposition is one of the most common mistakes, so Damerau usually ranks candidates better. The variant most implementations use, including the one here, is optimal string alignment, which does not allow a substring to be edited more than once.

How do I use Levenshtein distance in PostgreSQL?

Install the fuzzystrmatch extension and call levenshtein(a, b), optionally with custom insert, delete and substitute costs, or levenshtein_less_equal(a, b, max) to abort early past a threshold. The catch is that no index can accelerate it, so a query filtering on levenshtein() scans the whole table. The practical pattern is two-stage: create a GIN index with gin_trgm_ops from pg_trgm, filter candidates with the % operator or similarity(), then re-rank that small set with levenshtein(). To run these queries and manage extensions across PostgreSQL, MySQL and 20+ other databases, use Chat2DB — download it at https://chat2db.ai/download or open https://app.chat2db.ai.