What is the Levenshtein distance and how can it help in analyzing your data?
Those who know me know this: I have always had a dual interest in marketing… and mathematicsTwo worlds which, at first glance, seem far apart, but which come together much more often than one might imagine once one takes a serious interest in the data.
Today, I would like to share a very concrete problem that can be found in almost all bases CRM Regardless of the sector or the maturity of the teams. A seemingly simple problem, but one that has direct consequences on the quality of marketing analyses.
Data is rarely perfect. In a customer database, the same individual can appear in several slightly different forms: a typo in a name, an abbreviated first name, or a variation in spelling. Taken individually, these discrepancies seem insignificant. But on a large scale, they complicate duplicate detection, skew segmentation, and reduce the reliability of analyses.
It is precisely at this point of friction, between operational reality and mathematical rigor, that a tool as simple as it is powerful comes into play: the Levenshtein distance.
This indicator allows us to measure to what extent two strings of characters are similar or differentIn other words, it provides a simple and quantitative way to assess the proximity between two words. This type of algorithm can help improve the quality of databases, detect duplicates, or make search systems more tolerant of typing errors.
1. Understanding Levenshtein distance
A measure of similarity between two words
La distance from Levenshtein is a measure that evaluates the difference between two strings of characters by counting the minimum number of operations required to transform one into the other.
The central idea is simple: the lower this number, the more similar the two words are. Conversely, the higher it is, the more different the words are.
This approach allows us to quantify a concept that often remains intuitive for humans: recognizing that two words are similar despite minor spelling errors. For example, "gmail" and "gmial"...
The three possible operations
To transform one word into another, the algorithm allows three types of modifications.
- The first is insertion of a character. It corresponds to the case where a letter is missing from a word and must be added.
Example : 'markting' instead of 'marketing' - The second is suppression of a character. This operation occurs when an extra letter appears in the string of characters.
Example 'markeeting' instead of 'marketing' - The third one is the substitutionThat is, the replacement of one character by another. This is the classic case of a typo.
Example 'markiting' instead of 'marketing'
Each operation has a cost of 1. The algorithm then searches for the shortest transformation path between the two words.
Who was Vladimir Levenshtein?
The Levenshtein distance is named after the Soviet scientist Vladimir Levenshtein (1935–2017), specialist in information theory, a discipline that studies the transmission and correction of data.
In the 1960s, he proposed a method for measuring the difference between two sequences of symbols in order to detect and correct errors in digital communications.
Originally designed to improve the reliability of data transmissions, this method has since become established in many fields: search engines, natural language processing, bioinformatics and data analysis.
2. The mathematical principle
A formal definition
From a mathematical point of view, the Levenshtein distance can be defined recursively. If we consider two strings of characters a et b, this distance corresponds to the minimum number of operations needed to transform one into the other.
$$d(a,b) = \min(\text{insertion},\ \text{deletion},\ \text{substitution})$$
In practice, the algorithm compares the characters of the two words a and b and then searches for the shortest combination of operations. Each modification corresponds to an elementary operation: insert a character, remove one ou replace one character with another.
In the mathematical formulation of the algorithm, each transformation operation is assigned a costthat is, a numerical value that represents the effort required to move from one character to another. When two compared characters are identical, the cost is 0, because no modification is necessary. On the other hand, when they differ, the algorithm generally assigns a cost of 1, corresponding to an insertion, a deletion, or a substitution. The objective then becomes to find the sequence of operations which the total cost is the lowest, which corresponds to the Levenshtein distance between the two words.
Understanding the idea without mathematics
However, mastering this formula is not necessary to understand the principle. In practice, the algorithm goes through the two words character by character and progressively calculates the minimum number of changes needed to go from one to the other.
This process can be imagined as a comparison grid between two words. The algorithm explores different possible paths and always retains the one that asks the fewest transformations.
3. Concrete example of calculation
Just one missing letter
Let's take a simple example with the words marketing et marketing.
In this specific case, the second version of the word simply lost the letter eTo change "marketing" to "marketing", you simply need to insert one character.
La The Levenshtein distance is therefore equal to 1.
A character substitution
Let's take a second example: Dupont et Dupond.
Here, only one letter changes. The replacement of the t by d corresponds to a single substitution.
The distance is therefore also equal to 1which indicates that the two words are very close despite their difference.
These examples illustrate the value of this measure: even when two strings are not strictly identical, the algorithm can identify that they are probably related.
4. Why this measure is useful in data analysis
The problem of imperfect data
In a marketing context, data often comes from multiple sources: online forms, file imports, manual entries, or integrations between different tools.
This diversity mechanically increases the risk of errors or variations in the data. The same customer may appear several times in a database with slight differences in spelling. For example, "Alexandre Martin" may also appear as "Alexandre Martn" or "A. Martin".
Without an automatic matching mechanism, these differences can fragment information and complicate analysis.
A valuable aid for data quality
The Levenshtein distance allows us to identify precisely this type of similarity. By automatically comparing character strings, a system can detect that two very similar inputs likely have the same origin.
This capability is particularly useful in the processes of database cleaning and standardizationIt helps to improve the quality of CRM databases, limit duplicates and obtain a more reliable view of customers or prospects.
5. Practical applications in marketing and Martech
CRM database deduplication
In databases containing thousands or millions of contacts, it is common for several records to actually correspond to the same person.
Similarity algorithms based on Levenshtein distance make it possible to automatically identify very similar records, even when the names are not strictly identical.
Error-tolerant search
Many search engines incorporate mechanisms for approximate searchWhen a user types a word with a typo, the system can still retrieve relevant results.
The Levenshtein distance is often used as a basis for determining which words are close enough to be considered equivalent.
Analysis of user requests
In marketing data analysis, it is common to work on user queries or keywords.
By grouping together expressions that are very similar in spelling, it becomes possible to better understand search intentions and more easily identify trends.
Improved forms and user experience
Some marketing platforms also use this type of algorithm to improve the user experience in forms.
When a typical error is detected, a system can automatically suggest a correction or bring the input closer to a value already known.
6. Limitations and precautions
A similarity that is only orthographic
The Levenshtein distance measures only the similarity of writing between two strings of characters. It does not take into account the meaning of the words.
Two terms can therefore be very similar in spelling while having completely different meanings. Conversely, two synonyms can be very different in their spelling.
A question of large-scale performance
When strings become very long or databases contain millions of entries, calculations can become costly in terms of computing resources.
In these contexts, systems often use variants or optimizations of the algorithm in order to maintain good performance.
Conclusion
The Levenshtein distance constitutes a A simple yet powerful tool for measuring the similarity between two strings of characters.Behind a relatively compact mathematical formula lies an intuitive principle: counting the minimum number of changes needed to transform one word into another.
For marketing teams and data professionals, understanding this mechanism allows for a better understanding of certain tools used daily, whether it be for cleaning CRM databases, detecting duplicates or improving internal search engines.
Even if it doesn't solve all data quality problems, the Levenshtein distance remains today one of the foundations of many modern text analysis and information management techniques.
