Problem. You have a fixed vocabulary of canonical class names and a raw label typed by a person or scraped from a source. Return
the vocabulary entry with the smallest edit distance to the label, if that distance is at most k; otherwise return None (the
label needs a human).
vocab = ["electronics", "fashion", "beauty", "home & garden", "sports", "toys"]
"Fashon " → "fashion" (distance 1 after normalising)
"electronic" → "electronics" (distance 1)
"groceries" → None (nothing within k = 2)
This is lesson 12.12's edit distance used as a search: one query against many candidates. The DP per pair is fixed at O(m · n); what changes is how many pairs you compute, and how much of each table you fill. Every optimisation here is a way to prove a candidate can't win before paying for its full table.
ML context. Real datasets arrive with label noise: "Electronics", "electronic", "Electroncs" and "electronics " are one class to
a model but four to a groupby. Cleaning labels against a taxonomy before training, mapping user-entered categories to a product
catalogue, and matching entity names in data joins all run this search. The result is also a review queue: labels with no match
within k go to a person instead of being silently mislabelled (Change D).