5 ms·

Fuzzy Name Matching in Postgres

144 points by polm23 6y ago

1996 6y ago
Phonex, Soundex and Levenstein distance are great algorithms that hopefully more people will find out about thanks to this great article!
sandGorgon 6y ago
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.
- jimktrains2 6y ago
  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.
  - fumblebee 6y ago
    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.
  - sandGorgon 6y ago
    I work in non-English markets. Soundex is not a general replacement. Similaritiy search (https://www.elastic.co/guide/en/elasticsearch/reference/current/index-modules-similarity.html https://www.elastic.co/guide/en/elasticsearch/reference/curr...) is far better assuming you have some corpus already.
- michelpp 6y ago
  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-postgresql-cosine-and-linear-correlation-algorithms-for-text-analysis_595793 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.
  - sandGorgon 6y ago
    performance. that's the issue. the Alibaba Cloud article is nice..but we are really comparing this with Elastic
kamilafsar 6y ago
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.
conradfr 6y ago
Very informative and well written, it will be useful to avoid using Solr or ES for simple needs.
raoulj 6y ago
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”
z77dj3kl 6y ago
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 https://www.postgresql.org/docs/current/pgtrgm.html
- dfsegoat 6y ago
  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_name https://en.wikipedia.org/wiki/International_nonproprietary_n...
- ilitirit 6y ago
  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.
- merb 6y ago
  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
OliverJones 6y ago
I've used this stuff to good effect, for years. SOUNDEX turns 103 this year. https://en.wikipedia.org/wiki/Soundex 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.
sgt 6y ago
Would this be a good candidate to do address parsing (from raw addresses, perhaps OCR'd even)?
- sparklingmango 6y ago
  For address parsing, I've had good luck with this package: https://github.com/datamade/usaddress https://github.com/datamade/usaddress
sigstoat 6y ago
you can use double metaphone with postgres' text search facility directly: https://github.com/jkominek/dmetaphone https://github.com/jkominek/dmetaphone
alex_duf 6y ago
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 https://en.wikipedia.org/wiki/Metaphone#Double_Metaphone
deleted 6y ago
[deleted]
nick_ 6y ago
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 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.

144 points by polm23 6y ago

1996 6y ago

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

sandGorgon 6y ago

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.

jimktrains2 6y ago
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.
- fumblebee 6y ago
  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.
- sandGorgon 6y ago
  I work in non-English markets. Soundex is not a general replacement. Similaritiy search (https://www.elastic.co/guide/en/elasticsearch/reference/current/index-modules-similarity.html https://www.elastic.co/guide/en/elasticsearch/reference/curr...) is far better assuming you have some corpus already.
michelpp 6y ago
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-postgresql-cosine-and-linear-correlation-algorithms-for-text-analysis_595793 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.
- sandGorgon 6y ago
  performance. that's the issue. the Alibaba Cloud article is nice..but we are really comparing this with Elastic

kamilafsar 6y ago

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.

conradfr 6y ago

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

raoulj 6y ago

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”

z77dj3kl 6y ago

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 https://www.postgresql.org/docs/current/pgtrgm.html

dfsegoat 6y ago
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_name https://en.wikipedia.org/wiki/International_nonproprietary_n...
ilitirit 6y ago
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.
merb 6y ago
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

OliverJones 6y ago

I've used this stuff to good effect, for years. SOUNDEX turns 103 this year. https://en.wikipedia.org/wiki/Soundex 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.

sgt 6y ago

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

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

sigstoat 6y ago

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

alex_duf 6y ago

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 https://en.wikipedia.org/wiki/Metaphone#Double_Metaphone

deleted 6y ago

[deleted]

nick_ 6y ago

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 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.