Skip to content

Many Ways to Be Similar

Edit source

A family of string-distance metrics behind one interface, because there is no single answer to 'how close.'

Part 23 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries I carved out of Xapiand. This one measures closeness eight ways: string-similarity.

Ask “how similar are these two strings” and the honest first response is a question back: similar how? color and colour differ by one inserted letter, so they are close under edit distance. Jon and Jonathan share a prefix, which Jaro-Winkler rewards and edit distance does not. night and nacht share three of their seven distinct letters, which Jaccard measures, and one of their letter pairs, which Sørensen-Dice counts. And Smith and Schmidt are close only if you listen, which needs sound. There is no single “string similarity,” only a shelf of metrics, each one right for a different shape of data, and the mistake is picking one and using it for everything.

string-similarity is that shelf, made uniform. It is a header-only suite, Levenshtein edit distance, Jaro and Jaro-Winkler, longest common substring and subsequence, Jaccard, Sørensen-Dice, and a Soundex-backed wrapper, and its design move is to put every one of them behind the same interface so they are interchangeable.

The base is a CRTP template, StringMetric<Impl>, and every metric is a subclass that fills in one calculation. They all present the same surface: a distance(), a similarity() normalized to [0, 1], and a name() and description() so a metric can introduce itself. You use any of them two ways, and the second is the one that matters in practice:

using namespace std::string_literals; // the metrics take std::string or std::string_view
Levenshtein lev;
lev.similarity("kitten"s, "sitting"s); // compare two strings ad hoc
Levenshtein fixed("kitten"s); // bind one side once
fixed.similarity("sitting"s); // compare many others against it

Binding one string and comparing a stream of candidates against it is the real workload, fuzzy-matching a query against a column, deduplicating a list, ranking suggestions, and the uniform surface means the choice of metric is a one-line swap, not a rewrite. This is the same philosophy as compressors in the bytes chapter: when a problem has several legitimate answers with different tradeoffs, the library’s job is not to pick for you, it is to make switching between them cost nothing, so you can choose per use and change your mind cheaply. Edit distance for typos, Jaro-Winkler for names, Jaccard for shared letters, all the same shape.

Reach for it whenever “close but not equal” is a real requirement: typo-tolerant search, record linkage, autocomplete ranking, near-duplicate detection. Pick the metric that matches your data’s notion of similarity, character edits, shared prefixes, shared letters, or sound, and swap freely as you learn what works. Skip it if exact matching is enough, or if you need semantic similarity (meaning, not surface form), which is an embeddings problem, not a string-distance one.

The next familiar goes back to the lock-free chapter with a quieter kind of cleverness: a shared pointer you can swap atomically, written so that it politely deletes itself the day the standard library grows its own.