name matching algorithms from partial input

Question

There are a lot of algorithms out there that solve this particular problem. My main problem is in trying to understand how they work; where to start. Most of the algorithms are academic in nature.

There is a master list of product names. We feed in an input file into the program with product names, but the names of the products may be partial or incomplete. We would need to match the correct product from the master list.

There are solutions like clustering algorithms, naive-bayes, etc. But I am looking at some working examples to actually understand the concept. Would want to review the computations step-by-step for a small model.

Answer 1

A cheap but possibly low-precision, low-recall way is to compute something similar to Soundex or Metaphone codes for your product names and candidates. This only really accounts for misspellings, and even then not reliably or in a principled way. But it's cheap to compute.

Alternatively, for a language-independent approach, consider computing the edit distance between each candidate and all the database entries, and return the cheapest match that's under some threshold. There's worked examples of how the Levenshtein distance is computed on the Wiki page.