Title matching against human input

Question

I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known. Ideally I'd also have some way to suggest the human input of a truly novel title matches no known title as well.

As an example, I have a list of titles like this:

The Conspirators
The Count of Monte Cristo
The Three Musketeers
The Fencing Master

Only, my real list of titles is on the order of tens of millions long, and includes titles in different languages, including non Latin based languages.

And, as a human enters titles like these, I am attempt to find the proper name, here are examples of what humans might enter for The Three Musketeers:

The Three Musketeers
The 3 Musketeers
Three Musketeers, The
The.Three.Musketeers
the-three-musketeers
thethreemusketeers
The Three Musketeers-1844
Three Musketeers
THE THREE MUSKETEERS

For lack of a better term, at present, I'm attempting to "normalize" the titles. For instance, that means I:

• Convert input to a known case
• Remove why whitespace (or characters acting like whitespace, like the - and . above)
• Remove extraneous information (like 1844 above)
• Fix up common issues, like replace and with &
• Other domain specific fix-ups

This is done once on the known good titles, and whenever a user enters a title, a simple database lookup is done. In the case of multiple titles matching, domain specific guesses are made (for instance, a book with more reviews wins over other options).

This works, but it requires a lot of custom logic in the string normalization, and what's worse, it requires knowledge of multiple languages. And if users suddenly start following a new trend, like as a made up example, use = instead of spaces, then there needs to be a feedback loop where someone reviews common "misses" in the search and updates the string normalization logic.

Some other options I've briefly looked into:

• Phonetic matching algorithms, like Soundex. These sometimes work, but some of the human input doesn't sound like the target word, and these systems tend to require I know the target language, which I don't always know.
• Machine Learning. I'm at a loss here, most of the systems I've read about require cleaning of human input, which if I can do, I can match without any ML systems.
• n-gram based fuzzy matching. Much like the phonetic matching systems, this requires knowing the language, and cleaning up the text to some degree beforehand. Also, most of the systems seem to require a lot of compute power to perform the lookup, which is a concern.

Are there better techniques to apply to this problem to find the real title from the human input?

Answer 1

First preprocess the string to normalize it (casing, no digits, unique separators...). You do this for the database of known titles, and for the input string to be matched. It might also be of interest to discard the articles/prepositions/connectors as they convey little semantic information.

Now you can use the string edit distance on two levels:

• word level, to deal with spelling variants or mistakes; an input word can result in several matching candidates;

• sentence level: you only need to accept the very short edit distances; but you should try with all candidates found at the word level.

Answer 2

One plausible approach is to use edit distance to measure the similarity of two titles. You might want to adjust it to reduce the penalty for capitalization (e.g., changing x to X might cost 0, or some very small amount).

Then, given a human-entered title, you need a way to find the closest match in the database. There are various data structures and techniques for this. See, e.g., shingling, BK trees, metric trees, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, https://cstheory.stackexchange.com/q/4165/5038, http://norvig.com/spell-correct.html.

Another heuristic might be to extract each word from the human-entered title, canonicalize it (e.g., spelling correction, lower-case it, etc.), then look it up to find the first 1000 titles in the database that contain this word. Take the union of those titles from the database, compare each to the human-entered title using edit distance, and keep the closest match.