Building Diacritic-Insensitive Search Without Breaking Precision

#ai #machinelearning #tutorial #llm

Somebody types cafe and expects to find café. The standard answer is four characters of regex, and it works well enough on French and Spanish that most teams ship it and move on. It is wrong in a way that matters for Vietnamese, Turkish and Polish, and the failure is silent: the search returns results, just not the right ones.

What folding actually does

Diacritic-insensitive search is a folding problem. You are building a function that maps many surface forms onto one key, and then applying that same function to both the indexed text and the query. Nothing about the fold is reversible, and nothing about it is part of the stored document; it exists only so that two different strings land in the same bucket.

The reason a fold can be written at all is that Unicode defines canonical decomposition. The character é has two legitimate representations: the precomposed code point U+00E9, and the sequence U+0065 (LATIN SMALL LETTER E) followed by U+0301 (COMBINING ACUTE ACCENT). Normalisation form D rewrites the first into the second, and once the accent is a separate code point in the general category Mn (Mark, nonspacing), it can be deleted with a character-class match. That is the whole trick, and the difference between the two representations is worth understanding before you rely on it.

The four-step fold

A fold that holds up in production has four steps and they run in this order. Reordering them changes the output.

Compatibility decomposition (NFKD). Not NFD. NFKD additionally maps compatibility variants onto their base forms: the ligature ﬁ (U+FB01) becomes fi, full-width Ａ (U+FF21) becomes A, superscript ² becomes 2, and Arabic presentation forms collapse onto their normal letters. For a search index this is almost always what you want, because none of those distinctions is one a person types deliberately.
Strip nonspacing marks. In a language with Unicode property escapes this is one expression. In an engine without them you fall back to the block U+0300–U+036F, which covers Latin but misses Arabic and Hebrew marks entirely.
Apply the language exceptions. Decomposition handles nothing that is not a canonical mark. German ß (U+00DF) has no decomposition and stays ß through NFKD, so if you want strasse to find Straße you write that mapping yourself. So do ø (U+00F8), đ (U+0111), ł (U+0142) and ı (U+0131): stroked and dotless letters are single code points, not base-plus-mark.
Case fold last. After the marks are gone, because Turkish İ (U+0130) decomposes under NFD to I plus U+0307 COMBINING DOT ABOVE, which the strip step removes. Folding case first and stripping second gives a different answer for Turkish than the reverse.

// One fold, used for both the indexed text and the query.
const NONSPACING = /\p{Mn}/gu;

const EXCEPTIONS = new Map([
  ["\u00DF", "ss"],   // ß  German sharp s — no decomposition
  ["\u00F8", "o"],    // ø  Danish/Norwegian o with stroke
  ["\u0111", "d"],    // đ  Vietnamese/Croatian d with stroke
  ["\u0142", "l"],    // ł  Polish l with stroke
  ["\u0131", "i"],    // ı  Turkish dotless i
  ["\u00E6", "ae"],   // æ
  ["\u0153", "oe"],   // œ
]);

export function fold(input) {
  let out = input.normalize("NFKD").replace(NONSPACING, "");
  for (const [from, to] of EXCEPTIONS) out = out.split(from).join(to);
  return out.toLowerCase();
}

fold("Café");     // "cafe"
fold("Straße");   // "strasse"
fold("Łódź");     // "lodz"

Where the naive version breaks

Vietnamese is the case that turns this from a solved problem into a design decision, because Vietnamese uses two kinds of mark and the fold cannot tell them apart.

The first kind is a tone mark. Vietnamese has six tones and five of them are written: U+0301 acute (sắc), U+0300 grave (huyền), U+0309 hook above (hỏi), U+0303 tilde (ngã) and U+0323 dot below (nặng). Stripping these is exactly what a diacritic-insensitive search should do — a person typing ha noi should find Hà Nội.

The second kind is not a tone at all. It is part of the letter. ơ (U+01A1) decomposes under NFD into o plus U+031B COMBINING HORN, and ư (U+01B0) into u plus the same horn. ê, ô and â decompose to a base plus U+0302 circumflex, and ă to a plus U+0306 breve. In the Vietnamese alphabet, o, ô and ơ are three separate letters that a dictionary sorts separately, exactly as b and p are separate in English. The horn and the circumflex are in category Mn, so the naive fold deletes them, and twelve distinct Vietnamese vowels collapse into three.

The visible consequence is that unrelated words become the same key. tơ (silk) and to (big) fold to to. mưa (rain) and mua (buy) fold to mua. A search for one returns both, and on a corpus of Vietnamese text that is a large share of the vocabulary rather than a rare collision. Note also that đ is not a mark case at all: it is U+0111, it survives NFKD unchanged, and it needs the exception-table entry above.

There is no fold that is right for both audiences at once, so pick per index. For a Vietnamese-language index, delete only the five tone marks and keep U+031B, U+0302 and U+0306. For a mostly-Latin index that happens to contain Vietnamese names, delete everything and accept the collisions. The mistake is not choosing either one; it is running the general fold over a Vietnamese corpus and never being told.

// A tone-only fold, for a Vietnamese-language index.
// Keeps horn (031B), circumflex (0302) and breve (0306):
// those are letter identity in Vietnamese, not accents.
const TONES = /[\u0300\u0301\u0303\u0309\u0323]/gu;

export function foldVietnamese(input) {
  return input
    .normalize("NFD")
    .replace(TONES, "")
    .normalize("NFC")     // recompose ơ, ư, ê, ô, ă
    .replace(/\u0111/gu, "d")
    .toLowerCase();
}

foldVietnamese("Hà Nội");  // "ha nôi"  — tone gone, circumflex kept
foldVietnamese("tơ");      // "tơ"      — still distinct from "to"

Two fields, not one

The precision problem is separate from the correctness problem. Even where the fold is right, folding is lossy, and a reader who typed the accent told you something you have just thrown away.

The fix is to index both and rank rather than to choose. Store the original text in one field and the folded text in a second, search both, and give the exact-form field a higher weight. A query of cafe matches only the folded field and everything scores level; a query of café matches both fields on the accented documents and only the folded field on the rest, so the accented ones rise. You get recall from the fold and precision from the original at the cost of one extra field.

The same argument applies to highlighting. Never highlight against the folded text: the offsets do not line up, because NFKD changes string length (ﬁ becomes two characters, é becomes two and then one). Highlight against the stored original and map the match back, or your highlights drift by one character per accent.

The engine may already do this. PostgreSQL ships the unaccent dictionary, Elasticsearch has asciifolding and the more complete icu_folding, and SQLite has no built-in fold at all. Where a built-in exists, prefer it to hand-rolled regex, but check its Vietnamese and Turkish behaviour before you trust it: asciifolding deletes the horn.

The implementation

Decide the index language. If the corpus is predominantly one language with letter-identity marks — Vietnamese, and to a lesser degree Turkish and the Nordic languages — you need a language-specific fold, not the general one.
Write the fold as a single exported function, in one file. It must be callable from both the indexing path and the query path. The single most common production bug in this area is a fold that was updated on one side only, which makes previously-matching documents disappear.
Add a fold-version constant next to it and store that version on the index. When the fold changes, the version changes, and the index is rebuilt rather than left half-folded.
Index two fields: title (original) and title_folded. Search both, weight the original higher.
Write the test as a table of pairs that must match and pairs that must not match. The second list is the one that catches regressions: tơ against to, Peña against Pena, şen against sen. Assert the non-matches as loudly as the matches.
Sort with a collator rather than with the folded key. Folding is for matching; ordering is a different operation with different rules, as Polish makes obvious.