String similarity
- Lesson 12
- 40 min
- Module 4: Compare records: similarity measures
Where we are
Blocking gave us a small set of candidate pairs. Now we must say how alike two values are. In this lesson, we compare Levenshtein, Jaro–Winkler and token set ratio on the same names, addresses and product titles.
Lesson 12 of 29 · Entity Resolution and Record Matching: Is This the Same Thing?String similarity
1. The matching problem
2. Clean first, then match exactly
3. Blocking: do not compare everything
4. Compare records: similarity measures
5. Probabilistic linkage
6. Learned matching: classifiers, embeddings and language models
7. From pairs to entities
8. Run matching in production
What you will be able to do
Measure how alike two values are, with a number from 0 to 1. Compute three common measures by hand on tiny examples, then with the library rapidfuzz. See which measure suits names, addresses and product titles, and where all three fail.
NotebookCompare the three measures in a notebook
The notebook computes the Levenshtein distance by hand and scores the same pairs with three measures. Then it uses TermLarkfieldA made-up Canadian online shop for home and garden products. It is not a real company. All Nextia courses use its help desk and data as the example.Learn more Meet Larkfield’s labelled pairs to choose one measure and one threshold. Its setup cells download the data, so it needs no local setup.
Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.
Before you startWhat to know and to have ready
What you need to know
- Candidate pairs and the five blocking keys, from Blocking keys and sorted neighbourhood and What blocking loses.
- Clean names and addresses, from Normalise and Parse into parts.
What you need on your computer
- The project
larkfield-matchwith the commands of Module 3. Or use the notebook only.
Tested on macOS with Python 3.12.13. The Windows (PowerShell) commands are not tested.
A librarian reads a bad card
Section titled “A librarian reads a bad card”A librarian finds two cards in the catalogue. One says “Katherine Smyth”. The other says “Kathy Smith”. Are they the same reader?
She does not ask “are these two names exactly equal?”. The answer is no, and it does not help her. She asks “how close are they?”. “Smyth” and “Smith” differ by one letter. “Kathy” is a short form of “Katherine”. So the two cards are close, and she looks at the address next.
A matcher must ask the same question. It needs a number that says how alike two values are.
The problem: “equal or not” is too blunt
Section titled “The problem: “equal or not” is too blunt”The rules of Exact and rule-based matching compare clean values for equality. After normalising, “Thériault” and “THERIAULT” are equal. But a typing error still breaks equality:
| Value A | Value B | Equal? |
|---|---|---|
| tremblay | trembaly | no |
| tremblay | gagnon | no |
The rule gives the same answer to both pairs. But the first pair differs by two swapped letters, and the second pair is two different names. Equality throws away the difference between “almost the same” and “nothing alike”.
In our synthetic records, this is common. The error model puts a typing error in 4.5% of surnames and 3.5% of first names. It puts a nickname in 10% of first names. (These rates are our assumptions, written in the dataset card.) Each of them makes an exact rule miss a true pair.
The idea: a similarity from 0 to 1
Section titled “The idea: a similarity from 0 to 1”A string similarity is a number that says how alike two pieces of text are. A string is any piece of text: a name, an address or a product title. In this course, every similarity is between 0 and 1:
- 1 means the two values are the same.
- 0 means they have nothing in common.
- A value between means “partly alike”.
There are many ways to compute it. This lesson uses three common ones: Levenshtein, Jaro–Winkler and token set ratio. Each one looks at the text in its own way, so each one is good at different errors.
Levenshtein: count the changes
Section titled “Levenshtein: count the changes”The Levenshtein distance is the smallest number of one-letter changes that turn one value into the other. A change is one of three things:
- insert a letter,
- delete a letter, or
- replace one letter with another.
“smith” → “smyth” needs one change: replace “i” with “y”. So the distance is 1.
A worked example
Section titled “A worked example”Take two French surnames: “gagne” and “gagnon”. The first four letters are the same. Then we replace “e” with “o”, and insert “n”. That makes 2 changes.
The computer finds the smallest number with a table. Each cell holds the fewest changes for the first letters of each value. Each cell takes the smallest of three neighbours, plus the cost of one change.
Text description of the diagram
A table with the letters of “gagne” down the side and the letters of “gagnon” across the top. The first row counts 0 to 6 and the first column 0 to 5: the cost of building a value from nothing. Each other cell is the smallest of three values. They are the cell above plus 1, the cell on the left plus 1, and the cell above-left plus 0 or 1. The bottom-right cell is 2. The cheapest path goes down the diagonal for “g a g n” at no cost, replaces “e” with “o” (1), and inserts “n” (1).
A distance is not yet a similarity. Two long values with 2 changes are more alike than two short values with 2 changes. So we divide by the length of the longer value:
Levenshtein similarity = 1 − distance / length of the longer value
For “gagne” and “gagnon”: 1 − 2 / 6 = 0.667.
Levenshtein is easy to explain, and it treats every letter the same. That is also its weakness. Swapped letters cost 2 changes, so “tremblay” and “trembaly” get only 0.750.
A change of word order costs almost everything. “robert smith” and “smith robert” get 0.000.
Jaro–Winkler: letters near the same place
Section titled “Jaro–Winkler: letters near the same place”Jaro–Winkler was made for short names, such as names on a census form. It asks a different question: how many letters do the two values share, near the same place?
It has two parts:
- Jaro counts the letters that the two values have in common, near the same position. It also counts transpositions: common letters that come in a different order. Two letters that swap places count as one transposition.
- Winkler adds a bonus for the same start. People make fewer errors at the start of a name. The bonus grows with the number of equal first letters, up to 4.
Token set ratio: sets of words
Section titled “Token set ratio: sets of words”Token set ratio first splits each value into words. A token is one word. It then compares the two sets of words, so word order does not matter. It also scores high when one value has all the words of the other, plus some extra words.
The diagram shows both measures on small examples, with every number.
Text description of the diagram
Jaro–Winkler for “tremblay” and “trembaly”: all 8 letters are in common near the same place. “l” and “a” come in a different order, which is 1 transposition. Jaro is (8/8 + 8/8 + 7/8) / 3 = 0.958. The two values start with the same 4 letters, so Winkler adds 4 × 0.1 × (1 − 0.958). The result is 0.975. Token set ratio for “robert smith” and “smith robert” is 1.000, because they have the same two words. For “marie claude tremblay” and “marie tremblay”, every word of the second value is in the first. So the score is also 1.000.
Look at the last example. “Marie-Claude Tremblay” and “Marie Tremblay” get 1.000. They may be one person who sometimes drops her second first name. They may also be a daughter and her mother at the same address. Token set ratio cannot tell. A score of 1 does not mean “the same”.
The same pairs, three measures
Section titled “The same pairs, three measures”Now we score the same pairs with all three measures. The project’s measurement script ran these pairs: six names, four addresses and three product titles. The product titles are real rows of Larkfield’s two supplier feeds. Names and addresses are normalised first: lower case, no accents and no punctuation. The last column is what a person who knows the customers and products would say.
Text description of the diagram
Thirteen pairs in three groups, with a score from each measure and what a person would say. For names, Jaro–Winkler gives the highest scores to small spelling differences, and token set ratio is the only one that ignores word order. For addresses, token set ratio handles the unit written in another place. For product titles, every measure is fooled. The 12-inch and 16-inch planters score 0.97 to 0.99, and the pack of 2 scores 1.000 with token set ratio. But they are different products. The same hose written in feet and in metres gets low scores.
What does the table teach?
- No measure knows meaning. “Katherine” and “Kathy” get 0.444 to 0.849. Only a list of nicknames would know that “Kathy” is short for “Katherine”.
- Word order breaks Levenshtein. “Robert Smith” and “Smith Robert” get 0.000. Token set ratio gives 1.000.
- Jaro–Winkler likes small spelling errors in short values: “smith” / “smyth” gets 0.893, the highest of the three.
- Titles fool every measure. The planters differ in one character, “12” against “16”. They get 0.97 or more from every measure, but they are different products. A pack of 2 has every word of the single item, so token set ratio gives it 1.000. Meanwhile, the same hose in feet and in metres gets 0.154 from Levenshtein.
So numbers and units need their own fields. You cannot leave them to a string measure. We come back to this in Compare by field, then combine, and Hana’s product feeds come back to it in Module 6.
On Larkfield’s candidate pairs
Section titled “On Larkfield’s candidate pairs”Small examples can mislead. So we scored the full names of every candidate pair in the test split: the pairs that the five blocking keys make. For each measure, the chart shows the share of pairs that score 0.9 or more. Blue dots are true pairs (one customer); orange dots are pairs of two different people.
- Same person (true pairs)
- Two people (other candidate pairs)
Text description of the chart
A dot chart with six rows, two per measure. Levenshtein: 0.829 of the true pairs and 0.470 of the pairs of two people score 0.9 or more. Jaro–Winkler: 0.879 and 0.613. Token set ratio: 0.890 and 0.541.
The result is sobering. Every measure gives 0.9 or more to most true pairs. But it also gives 0.9 or more to about half of the pairs of two different people. That is 47% with Levenshtein, 54% with token set ratio and 61% with Jaro–Winkler.
Why so many? Blocking chose these pairs because their names or homes are alike. The surname key puts people with the same first letters together, and a household shares a surname. So on candidate pairs, a high name score is common, even for two people. Jaro–Winkler, the kindest measure, passes the most of them.
Run it in the project
Section titled “Run it in the project”Add the similarity code of this module to your project.
-
In your project folder, with the TermVirtual environmentA folder with its own Python and its own packages, for one project. Packages that you install there do not change other projects.Learn more Isolate dependenciesPython for Practical AI Engineering active, copy the similarity files from the snapshot
end-of-m04. Copy itsrequirements.txttoo:Terminal window S=../nextia-learning-labs/C39/snapshots/end-of-m04cp $S/larkfield_match/similarity.py larkfield_match/cp $S/larkfield_match/commands/similar.py larkfield_match/commands/cp $S/requirements.txt .Terminal window $S = "..\nextia-learning-labs\C39\snapshots\end-of-m04"Copy-Item $S\larkfield_match\similarity.py larkfield_match\Copy-Item $S\larkfield_match\commands\similar.py larkfield_match\commands\Copy-Item $S\requirements.txt .The new
requirements.txtadds two packages:rapidfuzzfor the string measures, andjellyfishfor the sound codes of the next lesson. -
Install the new packages:
Terminal window python -m pip install -r requirements.txtThe last line names them:
Successfully installed jellyfish-1.3.0 rapidfuzz-3.14.6 -
Run the tests. There are still 21: the tests of this module come in lesson 3.
Terminal window python -m pytest -q..................... [100%]21 passed in 54.91sOur laptop was busy during this run. Your time will differ.
Score two values
Section titled “Score two values”The new command match similar scores two values with the three measures. It normalises them first, as the matcher does:
match similar "Katherine" "Kathy"'katherine' / 'kathy' levenshtein distance 5 levenshtein 0.444 jaro_winkler 0.849 token_set_ratio 0.571 soundex K365 / K300 different metaphone K0RN / K0 differentThe last two lines are sound codes: the next lesson explains them. Now try a swap of words, and a value with accents:
match similar "Robert Smith" "Smith Robert"match similar "Thériault" "Theriault"match similar --raw "Thériault" "Theriault"'robert smith' / 'smith robert' levenshtein distance 12 levenshtein 0.000 jaro_winkler 0.472 token_set_ratio 1.000 ...'theriault' / 'theriault' levenshtein distance 0 levenshtein 1.000 ...'Thériault' / 'Theriault' levenshtein distance 1 levenshtein 0.889 jaro_winkler 0.941 token_set_ratio 0.889 ...With --raw, the command does not normalise. Then “é” and “e” are two different letters. Normalise first, then measure: a measure cannot fix what normalising should fix.
How the code computes it
Section titled “How the code computes it”Open larkfield_match/similarity.py. The Levenshtein distance is written out, so you can follow it. It keeps one row of the table at a time:
def levenshtein_distance(a, b): prev = list(range(len(b) + 1)) for i, ca in enumerate(a, 1): cur = [i] for j, cb in enumerate(b, 1): cur.append(min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (ca != cb))) prev = cur return prev[-1]The three measures that the matcher uses come from rapidfuzz, a fast library written in C++:
def levenshtein(a, b): return Levenshtein.normalized_similarity(a, b)
def jaro_winkler(a, b): return JaroWinkler.similarity(a, b)
def token_set_ratio(a, b): return fuzz.token_set_ratio(a, b) / 100rapidfuzz gives token set ratio from 0 to 100, so the project divides it by 100. Speed matters here: in Why all pairs is impossible, match allpairs compared names in plain Python at about 2 microseconds a pair. rapidfuzz’s Jaro–Winkler takes about 0.34 microseconds a pair.
Which measure for which field
Section titled “Which measure for which field”| Field | Good measure | Why | Watch out |
|---|---|---|---|
| First name, surname | Jaro–Winkler | short values; typing errors and swapped letters near the same place | nicknames (“Kathy”); a short name that starts like a longer one |
| Full name | token set ratio | word order changes between sources (“SURNAME, FIRST”) | an extra name gives 1.000: a parent and a child can look the same |
| Street address | token set ratio | units and numbers move around (“Apt 4”, “4-3”) | a different house number in the same street still scores high |
| Email, phone, postcode | equality after normalising | one wrong digit is a different phone | use a similarity only for the part before the @ of an email |
| Product title | token set ratio as one signal | many words in any order | sizes, units and packs need their own fields |
These are starting points, not laws. In Compare by field, then combine, we measure each field on the candidate pairs.
What does it cost? Very little. A string measure in rapidfuzz takes well under a microsecond a pair, and blocking has already cut the pairs to about one million. The real cost is in the choices: which measure, on which field, with which threshold.
Common mistake
Fuzzy matching on names is enough
Symptom: TermTomásLarkfield’s AI engineer. He often suggests a quick shortcut, and the lesson shows why it fails. says: “Names are what people type wrong. A good fuzzy measure on the full name is all we need.” He calls a pair “the same” when the token set ratio of the full names is high. The labelled pairs look good. In the notebook of this lesson, the best rule of this kind is a token set ratio of 0.86 or more. It agrees with 0.939 of Larkfield’s 3,000 labelled pairs.
Cause: the labelled pairs are not the candidate pairs. On the real candidate pairs of the test split, the same rule calls 239,633 pairs “the same”. Only 5,064 of them are right. Precision is 0.021, and recall is 0.910. Family members share a surname and an address, so blocking puts many of them together. And one person can appear with two first names, a nickname or a married name.
Fix: never decide on one field. A name similarity is one piece of evidence. Compare the email, phone, address and date of birth too, and combine them, as in Compare by field, then combine. Then measure on the candidate pairs, not only on a labelled sample.
Consequence in AI work: a sample can hide the hard cases. Measure a rule on the data that it will meet. The same lesson appears in Train, validation and test sets of the machine learning course.
Knowledge check
Section titled “Knowledge check”Check your understanding
“tremblay” and “trembaly” get 0.750 from Levenshtein and 0.975 from Jaro–Winkler. Explain the difference with the way each measure works.
Show the answer
The two values have the same letters, with “l” and “a” swapped. Levenshtein counts changes. A swap needs 2 replacements, and 1 − 2 / 8 = 0.750. Jaro–Winkler counts letters in common near the same place. All 8 are in common, and the swap is one transposition. Jaro is 0.958. The two values also start with the same 4 letters, so the Winkler bonus brings it to 0.975.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
Token set ratio gives 1.000 to “marie claude tremblay” / “marie tremblay”, and to a single hose / its pack of 2. What do the two cases have in common, and why is it a risk for a matcher?
Show the answer
In both cases, every word of one value is also in the other value; the other value only has extra words. Token set ratio compares the shared words with each value and keeps the best score, so it gives 1.000. But the extra word can change the meaning: “claude” can mark another person (a daughter and her mother), and “pack of 2” marks another product. A matcher that trusts this score alone merges them.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
A colleague wants to compare phone numbers with Jaro–Winkler, because “one wrong digit should still match”. Is that a good idea? What would you do instead?
Show the answer
Usually not. Two different phone numbers in one area share most digits and the same start (the area code and exchange: all our synthetic phones use 555). Jaro–Winkler gives them a high score, so many pairs of different people look alike. Compare the clean phone for equality, and let the other fields carry the evidence. If typing errors in phones are common, add a separate signal, for example “the same except one digit”, and measure it on the candidate pairs.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Recap
- A string similarity says how alike two values are, from 0 (nothing alike) to 1 (the same).
- Levenshtein counts one-letter changes. Similarity = 1 − distance / longer length. Swaps and word order cost a lot.
- Jaro–Winkler counts letters in common near the same place, with a bonus for the same start. It suits short names.
- Token set ratio compares sets of words. It ignores word order and extra words, so a score of 1 does not mean “the same”.
- On product titles, every measure is fooled by sizes and packs: 12 in / 16 in scores 0.97 or more.
- On Larkfield’s candidate pairs, 47% to 61% of the pairs of two people score 0.9 or more on the full name. A name alone cannot decide.
Letters are one way to compare names. People also say names aloud and write down what they hear. Next, sound codes compare names by how they sound.
Next: Sounds the same