Token sort matching, explained: when you don't need a fuzzy threshold

If two systems describe the same thing, they rarely write it the same way. Token sort fixes the most common difference, word order, in one line of code. What you do after that line is where most of the real decisions are.

What token sort does

Take a name, lower-case it, remove punctuation, split it into words, sort the words, and put them back together. Two names that differ only in order and punctuation come out identical.

import re

def token_sort_key(name: str) -> str:
    words = re.sub(r"[^a-z0-9 ]+", " ", name.lower()).split()
    return "".join(sorted(words))

token_sort_key("MSc Data Science (Full Time)")   # 'datafullmscsciencetime'
token_sort_key("Data Science MSc - Full Time")   # 'datafullmscsciencetime'

That's all of it. In our reconciliation tool, Intake Watcher, this key does most of the work of deciding whether a listing on a website is the same as a listing in our database.

How it compares to RapidFuzz

If you've used RapidFuzz or the older fuzzywuzzy, you'll know token_sort_ratio. It does the same sorting, then returns a similarity score from 0 to 100. Its sibling token_set_ratio goes further and ignores words that appear on only one side. Here are real scores from RapidFuzz 3.14, using its default processor to lower-case and strip punctuation, next to the exact-key check:

Look at row three. token_set_ratio scores "Data Science" and "Data Science and AI" a perfect 100, because every word in the shorter name appears in the longer one. Those are different courses. In a reconciliation job, that's a false match, and false matches are the worst kind of error: they hide a new listing and a deleted one at the same time.

One small trap if you try this yourself: since RapidFuzz 3.0 the scorers don't pre-process strings by default. Without processor=utils.default_process, the first row scores 79 on token sort instead of 100, because the brackets and dash stay attached to the words.

from rapidfuzz import fuzz, utils

a, b = "MSc Data Science (Full Time)", "Data Science MSc - Full Time"
fuzz.token_sort_ratio(a, b)                                   # 78.6
fuzz.token_sort_ratio(a, b, processor=utils.default_process)  # 100.0

Why I compared keys exactly

With a score you need a threshold. Pick 95 and you miss row two, which scores 91. Pick 85 and you're one odd name away from matching two different courses. Every threshold is a guess about your future data, and you only learn it was wrong after something gets matched that shouldn't have.

Our mismatches were almost all about order and punctuation. Exact keys handle those perfectly, and they fail in a safe direction: when two names don't produce the same key, the listing shows up as new or deleted, and a person looks. A missed match costs a minute of review. A false match costs a wrong record that nobody notices.

There's a second reason. When someone asks why two listings were matched, I can show them the key. "They both reduce to datafullmscsciencetime" is an answer anyone can check. "The score was 87" isn't.

The name isn't the whole key

The same course can run in two intakes, at two campuses, full-time and part-time. So the real match key is the sorted name plus the intake month and year, and then campus, study mode and duration when both sides have them.

from itertools import combinations

EXTRA = ["campus", "study_mode", "duration"]

def candidate_keys(row: dict, other_side_has) -> list[tuple]:
    """Most specific key first. A field joins only if both sides have it."""
    base = (token_sort_key(row["name"]), row["intake_month"], row["intake_year"])
    usable = [f for f in EXTRA if row.get(f) and other_side_has(f)]
    keys = []
    for n in range(len(usable), -1, -1):
        for combo in combinations(usable, n):
            keys.append(base + tuple(row[f] for f in combo))
    return keys

With three optional fields that's up to eight keys per listing, tried from strictest to loosest. A listing never matches on a vague key while a precise one is available. We also check a couple of alias name fields, because some listings get renamed and the old name lives on somewhere on the web.

When you do need fuzzy scores

Exact keys aren't always enough. Rows four and five above are real problems that token sort can't solve:

• Typos and plurals, like "Sciences" versus "Science". A score catches these; a key doesn't.
• Abbreviations, like "MSc" versus "Master of Science". Neither approach really fixes this. A small synonym table does, or an alias field.
• Extra filler words, like "in" or "and". You can drop a short list of stop words before sorting, but test it, because sometimes "and" is the whole difference.

If your data is full of typos, use scores, but send anything under a perfect score to a person rather than trusting a threshold. That keeps the speed of fuzzy matching without letting it make the final call.

Summary

• Token sort removes word order and punctuation as a difference. That's the most common difference in names.
• token_set_ratio is generous enough to match different things. Be careful with it in reconciliation.
• Exact sorted keys, tried from strictest to loosest, fail safely and are easy to explain.
• Use scores for typos, but let them suggest, not decide.

Scores computed with RapidFuzz 3.14.6 and utils.default_process. The course names are examples, not real listings. The approach is the one behind Intake Watcher, which cut manual reconciliation by about 60%.