Fuzzy Name Matching in Postgres | Hacker News Reader

Fuzzy Name Matching in Postgres

info.crunchydata.com

144 pointspolm2320 comments

I've used this stuff to good effect, for years.

SOUNDEX turns 103 this year. https://en.wikipedia.org/wiki/Soundex It's used for telephone-directory and census lookup for names in American English, and is designed for high false-positive matches. It's simplistic. But it's a snap to index. In Bayes lingo it's sensitive but not selective.

Surprised there's no mention of pg_trgm for trigram-based fuzzy match.

I guess for English names, Soundex is fairly good.

https://www.postgresql.org/docs/current/pgtrgm.html

pg_trgm is definitely what the doctor ordered when you get into more complex cases -- for us, that is pharmaceutical product names [1]. pg_trgm has really helped us with fuzzy matching on complex, multiword chemical names.

https://en.wikipedia.org/wiki/International_nonproprietary_n...

Yeah, I basically used pg_trgm to completely replace an old, non-supported version of ElasticSearch at a previous company. We basically needed to match on similar team names (e.g. Bayern München vs Bayern Munich as a simple example) and it turns out Postgres could handle all the matching requirements with ease.

is it?

> At present, the soundex, metaphone, dmetaphone, and dmetaphone_alt functions do not work well with multibyte encodings (such as UTF-8).

I#m not sure but most postgres databases use utf-8

Funny I've also came up with exactly the same way of doing it around 2008.

It was in France for the Yellow Pages (PagesJaunes) and initially we used soundex but it was too English centric. We ended up using the Double Metaphone [1] which works better for other European languages.

Our database (Oracle) didn't come with any extension to do that so we'd programmatically populate a column at the time the table was loaded, then indexed it.

We also weren't quite searching for family names but for city names and street names, so there was a fair bit of pre-processing applied to identify the list of most likely words to be useful for the match.

[1] https://en.wikipedia.org/wiki/Metaphone#Double_Metaphone

Soundex is cool, we’re using it for a game app I'm working on.

It’s a trivia game app based on a TV show. In the TV show candidates try to guess the right answer just by saying. How it’s written is not relevant (in order to score points). However in the app users need to write it down (voice support coming soon) and can make spelling mistakes. For a lot of stuff the Levenshtein distance just doesn’t cut it.

Phonex, Soundex and Levenstein distance are great algorithms that hopefully more people will find out about thanks to this great article!

I'm glad to see these built-in to Postgres, as these are the basics of fuzzy string matching.

A quantum leap would be to integrate an implementation of the symmetric delete algorithm, such as https://github.com/wolfgarbe/SymSpell

Soundex and Phonex can yield too many false negatives outside of phonetically English names. Levenshtein/Jaro-Winkler aren't indexable solutions themselves, so they require N^2 comparisons. SymSpell conceptually combines these two into an indexed string-distance solution. It has the usual index issue of being designed for many reads, few writes.

The biggest issue I can see with this approach is what happens if I’ve made a typo which changes the phonetics of the search input so that it gets excluded by the soundex prefilter, eg typing “Harrinbton” instead of “Harrington”

you can use double metaphone with postgres' text search facility directly: https://github.com/jkominek/dmetaphone

the biggest issue is postgres not having tf-idf or BM25 style relevance algorithms.

that would have been the right fit for fuzzy name matching.

How would tf-idf help fuzzy match names? You would first need to decide the term youre looking for is the term you've indexed, which is what soundex &c would do.

Soundex is a useful option for reducing the search space (the blocking stage, with aims to have a high recall).

TF-IDF is a useful option as part of a high precision pipeline _post_ blocking.

A two step pipeline is typical and necessary because the high precision pipeline, while more accurate than the blocking algorithm, suffers from being slow.

I work in non-English markets. Soundex is not a general replacement.

Similaritiy search (https://www.elastic.co/guide/en/elasticsearch/reference/curr...) is far better assuming you have some corpus already.

TF-IDF algorithms like BM25 do not come built in, but are straightforward to implement on top of postgres' text search:

https://www.alibabacloud.com/blog/keyword-analysis-with-post...

The key is you have to compute the IDF into a side table using the ts_stat function, since this is a global property (inter-document frequency) of your corpus. Once you have your IDF table you can write a ranking function based on that table.

performance. that's the issue.

the Alibaba Cloud article is nice..but we are really comparing this with Elastic

Would this be a good candidate to do address parsing (from raw addresses, perhaps OCR'd even)?

For address parsing, I've had good luck with this package: https://github.com/datamade/usaddress

Very informative and well written, it will be useful to avoid using Solr or ES for simple needs.

Reply on news.ycombinator.com