Levenshtein distance
computer science metric for string similarity
Facts
10 properties- Instance of
- algorithm
- Publication date
- 1965[8]
- Subclass of
- distance, norm, string metric, edit distance
- Defining formula
- \operatorname{lev}(a,b)=\begin{cases}|a|&\text{if }|b|=0\\|b|&\text{if }|a|=0\\\operatorname{lev}(\operatorname{tail}(a),\operatorname{tail}(b))&\text{if }a[0]=b[0]\\1+\min\begin{cases}\operatorname{lev}(\operatorname{tail}(a),b)\\\operatorname{lev}(a,\operatorname{tail}(b))\\\operatorname{lev}(\operatorname{tail}(a),\operatorname{tail}(b))\\\end{cases}&\text{otherwise}\end{cases}
- Discoverer or inventor
- Vladimir Levenshtein[6]
- In defining formula
- |a|, \min
- Named after
- Vladimir Levenshtein[7]
- Studied by
- category theory[16]
- Uses
- logical negation, insert, delete, substitution[12][13][14][15]
🏷️ Also known as
en Levenshtein edit distance
en edit distance
en Levenshtein distance
cs Levenštejnova vzdálenost
de Lewenstein-Distanz
de Editierdistanz
de Levenstein-Distanz
de Levenshtein-Abstand
de Levenshtein-Distanz
de Edit-Distanz
es Distancia de edición
es Distancia de Levenshtein
fa فاصلهٔ لون اشتاین
fa فاصله لون اشتاین
fa فاصله ویرایش
fa فاصله لوناشتاین
fi Levenshtein-etäisyys
fi Levenšteinin etäisyys
fi editointietäisyys
fi Levenshteinin etäisyys
🔖 Identifiers · 8
- OpenAlex ID
- C2777515626
- Described at URL
- www.levenshtein.net
- Dictionary of Algorithms and Data Structures ID
- Levenshtein, LevenshteinStringDistance
- Freebase ID
- /m/024h6k
- GitLab.com topic ID
- levenshtein-distance
- Microsoft Academic ID (discontinued)
- 2777515626
- Quora topic ID
- Levenshtein-Distance
- Stack Exchange tag
- stackoverflow.com
🔗 Connections
Subclass of 3
Different from 2
Created notable works 1
Discoverer or inventor 1
Instance of 1
Maintained by WikiProject 1
Named after 1
Studied by 1
Uses 1
← Based on 1
← Different from 1
Press Enter · cited answer in seconds