Skip to content
Français

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.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

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 notebookColab · Kaggle · GitHub

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 readyAbout 40 minutes

What you need to know

What you need on your computer

  • The project larkfield-match with 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 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.

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.

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.

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.

The Levenshtein table of gagne (rows) and gagnon (columns). The first row counts 0 to 6 and the first column 0 to 5. The bottom-right cell is 2. The thick cells show the cheapest path: four equal letters cost 0, then one replacement and one insertion. The distance is 2. The similarity is 1 minus 2 divided by 6, which is 0.667.
The Levenshtein table for “gagne” and “gagnon”. The bottom-right cell is the distance: 2 changes. The thick cells are the cheapest path.
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:

  1. 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.
  2. 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 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.

Left: Jaro-Winkler for tremblay and trembaly. 8 of 8 letters are in common, near the same place. 2 common letters are out of order, l-a and a-l, which is 1 transposition. Jaro = (8/8 + 8/8 + (8 - 1)/8) / 3 = 0.958. The same start, trem, gives a bonus for 4 letters (at most 4): 4 × 0.1 × (1 - 0.958). Jaro-Winkler = 0.975. Right: token set ratio. robert smith and smith robert have the words robert and smith in both, and no other words: 1.000. marie claude tremblay and marie tremblay have marie and tremblay in both, and claude only in the first: 1.000.
Jaro–Winkler forgives swapped letters near the same place. Token set ratio ignores word order and extra words.
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”.

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.

A table of 13 pairs, each scored by Levenshtein, Jaro-Winkler and token set ratio. Names: Katherine / Kathy 0.444, 0.849, 0.571 (same person, nickname). Thériault / Theriault 1, 1, 1. Jean-François / Jean Francois 1, 1, 1. Smith / Smyth 0.800, 0.893, 0.800 (maybe). Robert Smith / Smith Robert 0.000, 0.472, 1.000 (same person). Marie-Claude Tremblay / Marie Tremblay 0.667, 0.890, 1.000 (maybe, or her mother). Addresses: 12 rue des Érables / 12 r. des Erables 0.889, 0.915, 0.941. 2202 Kestrel Boulevard / 2202 Kestrel Blvd 0.773, 0.955, 0.872. 3 Elder Way Apt 4 / 4-3 Elder Way 0.529, 0.710, 1.000 (same place). 44 Juniper Dr / 21 Alder Cres 0.154, 0.510, 0.261 (different). Product titles: the hose in feet and in metres 0.154, 0.642, 0.800 (same product). The hose and its pack of 2: 0.765, 0.953, 1.000 (different). The planter 12 in and 16 in: 0.974, 0.990, 0.974 (different).
Thirteen pairs from the measurement script, scored by each measure. Dark blue: 0.9 or more. No measure is right on every pair.
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.

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)
Full names of the 5,531 true pairs and 386,135 other candidate pairs in the test split (five blocking keys), in our synthetic records. A good measure puts the blue dot far right and the orange dot far left.
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.

Add the similarity code of this module to your project.

  1. 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 its requirements.txt too:

    Terminal window
    S=../nextia-learning-labs/C39/snapshots/end-of-m04
    cp $S/larkfield_match/similarity.py larkfield_match/
    cp $S/larkfield_match/commands/similar.py larkfield_match/commands/
    cp $S/requirements.txt .

    The new requirements.txt adds two packages: rapidfuzz for the string measures, and jellyfish for the sound codes of the next lesson.

  2. Install the new packages:

    Terminal window
    python -m pip install -r requirements.txt

    The last line names them:

    Successfully installed jellyfish-1.3.0 rapidfuzz-3.14.6
  3. 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.91s

    Our laptop was busy during this run. Your time will differ.

The new command match similar scores two values with the three measures. It normalises them first, as the matcher does:

Terminal window
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 different

The last two lines are sound codes: the next lesson explains them. Now try a swap of words, and a value with accents:

Terminal window
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.

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) / 100

rapidfuzz 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.

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.

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.

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.

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.

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