5 ms·

This sounds like it's about the problem of: I have a column filled with the last names of lots of people and I want a text search that will find these names, bu

This sounds like it's about the problem of: I have a column filled with the last names of lots of people and I want a text search that will find these names, but, which takes into account all the various ways people end up writing that name. So, a search for 'mueller' should also find 'Müller'. However, that problem sounds nearly intractable to me. In basis it sounds like you just 'canonicalize' everything. You store, alongside 'Müller', also the string 'mueller' (the rule being: first transform all characters into their asciification, with the asciification of ü being defined as 'ue', then lowercase that. The problem is, of course.. that searching for 'MULLER' should also find this person. And now we're more into trying to get this done by first deconstructing the unicode into ascii + accent marks and then just wiping out the accent marks. But once we state that 'mueller', 'muller', and 'müller' need all be 'equal' to each other, where does it end? A last name can be from any of a thousand languages, each with their own unique conventions on how these things are asciified, and any given asciification must match any other. Sounds like a combinatorial explosion. One could disregard this notion and say that 'muller' does not match 'müller'. However, note that generally, Sjögren's syndrome tends to be asciified as 'Sjogren's syndrome', probably because Sjögren was norwegian and I assume that the norwegian asciification of ö, is o. The german asciification of ö is oe however; and I can't tell from a last name if it is germanic in origin, norwegian in origin, or from the land of fairytales and flying pandas, such as Haägen-Dazs. Just by thinking about this for a while I have concluded that it's hopeless, but perhaps I'm missing some fancy trick to at least try to make this problem dealable. So far my attempts to look for solutions tend to come down to advice to use unicode normalization and then get rid of all accents, then lowercase it, which obviously doesn't work at all (with that strategy, mueller would not find müller), or heuristic solutions (if a lot matches, good enough), which are their own can of worms. Is there a solution to this to me seemingly impossible problem?

Jedd 7y ago
This is a - if not solved, then certainly addressed - problem. Your specific example of: > So, a search for 'mueller' should also find 'Müller'. Is discussed here: https://discuss.elastic.co/t/u-umlaut-search-indexing-user-name-muller-search-fails-for-muller-but-success-for-muller/60317/2 https://discuss.elastic.co/t/u-umlaut-search-indexing-user-n... If your question is specifically "How do I use a feature that PostgreSQL 12 doesn't have?" then you've got a different problem. [EDIT] Refer the modules mentioned on slide 26 - these may help with your indexing challenges within PostgreSQL
radiowave 7y ago
There are various metaphone algorithms that produce an encoding that handles these cases, at least for English and some of the other European languages from which words and names have made there way into English. The "fancy trick" is basically that search still works pretty well if you just throw away all the vowel sounds - your examples of "mueller" and "Müller" both encode as: MLR https://en.toolpage.org/tool/metaphone https://en.toolpage.org/tool/metaphone
kilburn 7y ago
The solution is to stop trying so hard. As you said, the problem is fuzzy, so you do... a fuzzy search, return a bunch of results, and let the user pick. If the dataset is too large, then you just let the search include more details. "Mueller from Berlin" or "Muller born on july 7th" are much better queries to find a specific person than a perfectly written "Müller". In fact, if you were to crack the problem of searching by considering all applicable rules, the system would still be useless because people make mistakes all the time and the Müller guy actually wrote "Miller" while signing up ;P
murkt 7y ago
Yes, for me the solution was to stop thinking about search problems as a deterministic problems with a solution that can be (easily) found. It’s a very complex domain space, google still improves their search, with many people working on the problem for more than 20 years. So it is unreasonable for me to think that I can do a name search (I have exactly the same feature in my product) in a perfect way from scratch just by thinking hard, just because name search is narrower, hence simpler domain (lol). So I implemented something, got a round of feedback, implemented other forms that users used. My search will display Sjögurd even if user typed in Sjoegurd, despite that the name is Norwegian? Probably, and what’s the downside? My search will work imperfectly for some lesser known languages, like Georgian? Most certainly, and users from these cultures expect that, they will sigh and deal with it. I know, because I too come from a country with non-latin alphabet and we have lots of different transcriptions into it. It’s ugly, yes. Because the world is ugly :)
thom 7y ago
I'm not convinced these aren't real problems. Someone has heard a name. They type what they think it looks like. Postgres finds the right answer.
combatentropy 7y ago
Have you looked into Soundex or Metaphone? I myself have not used them. I just saw them mentioned in PHP's function list and thought they might be useful some day. - https://www.php.net/manual/en/function.soundex.php https://www.php.net/manual/en/function.soundex.php - https://www.php.net/manual/en/function.metaphone.php https://www.php.net/manual/en/function.metaphone.php PostgreSQL has an extension, fuzzystrmatch, that uses the same algorithms: - https://www.postgresql.org/docs/12/fuzzystrmatch.html https://www.postgresql.org/docs/12/fuzzystrmatch.html But it warns that the functions "do not work well with multibyte encodings (such as UTF-8)." So maybe first translate any such characters to ASCII?
- bmn__ 7y ago
  These only work with English, so not a general solution. There are more modern, better tools for the problem.
nl 7y ago
I think practical solution to this is to return all words that are within a Levenshtein distance[1] of 2*number_accented_characters of the original word, ranked by the distance. Levenshtein distance can be calculated using a trie[2] so it's fast enough for most purposes. If you wanted to get fancy you could modify the Levenshtein to reduce the distance penalty on accented characters, and/or only apply the Levenshtein calculation within 1 character of an accented character or the equivalent ASCII substitution sequence. [1] https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance [2] http://stevehanov.ca/blog/?id=114 http://stevehanov.ca/blog/?id=114
bmn__ 7y ago
> Is there a solution to this to me seemingly impossible problem? Not at all impossible, you're just not familiar with Unicode. Just use a software that implements UTS #10/UCA. Reply if you want to see code examples for the problems you stated.

Jedd 7y ago

This is a - if not solved, then certainly addressed - problem. Your specific example of: > So, a search for 'mueller' should also find 'Müller'. Is discussed here: https://discuss.elastic.co/t/u-umlaut-search-indexing-user-name-muller-search-fails-for-muller-but-success-for-muller/60317/2 https://discuss.elastic.co/t/u-umlaut-search-indexing-user-n... If your question is specifically "How do I use a feature that PostgreSQL 12 doesn't have?" then you've got a different problem. [EDIT] Refer the modules mentioned on slide 26 - these may help with your indexing challenges within PostgreSQL

radiowave 7y ago

There are various metaphone algorithms that produce an encoding that handles these cases, at least for English and some of the other European languages from which words and names have made there way into English. The "fancy trick" is basically that search still works pretty well if you just throw away all the vowel sounds - your examples of "mueller" and "Müller" both encode as: MLR https://en.toolpage.org/tool/metaphone https://en.toolpage.org/tool/metaphone

kilburn 7y ago

The solution is to stop trying so hard. As you said, the problem is fuzzy, so you do... a fuzzy search, return a bunch of results, and let the user pick. If the dataset is too large, then you just let the search include more details. "Mueller from Berlin" or "Muller born on july 7th" are much better queries to find a specific person than a perfectly written "Müller". In fact, if you were to crack the problem of searching by considering all applicable rules, the system would still be useless because people make mistakes all the time and the Müller guy actually wrote "Miller" while signing up ;P

murkt 7y ago

Yes, for me the solution was to stop thinking about search problems as a deterministic problems with a solution that can be (easily) found. It’s a very complex domain space, google still improves their search, with many people working on the problem for more than 20 years. So it is unreasonable for me to think that I can do a name search (I have exactly the same feature in my product) in a perfect way from scratch just by thinking hard, just because name search is narrower, hence simpler domain (lol). So I implemented something, got a round of feedback, implemented other forms that users used. My search will display Sjögurd even if user typed in Sjoegurd, despite that the name is Norwegian? Probably, and what’s the downside? My search will work imperfectly for some lesser known languages, like Georgian? Most certainly, and users from these cultures expect that, they will sigh and deal with it. I know, because I too come from a country with non-latin alphabet and we have lots of different transcriptions into it. It’s ugly, yes. Because the world is ugly :)

thom 7y ago

I'm not convinced these aren't real problems. Someone has heard a name. They type what they think it looks like. Postgres finds the right answer.

combatentropy 7y ago

Have you looked into Soundex or Metaphone? I myself have not used them. I just saw them mentioned in PHP's function list and thought they might be useful some day. - https://www.php.net/manual/en/function.soundex.php https://www.php.net/manual/en/function.soundex.php - https://www.php.net/manual/en/function.metaphone.php https://www.php.net/manual/en/function.metaphone.php PostgreSQL has an extension, fuzzystrmatch, that uses the same algorithms: - https://www.postgresql.org/docs/12/fuzzystrmatch.html https://www.postgresql.org/docs/12/fuzzystrmatch.html But it warns that the functions "do not work well with multibyte encodings (such as UTF-8)." So maybe first translate any such characters to ASCII?

bmn__ 7y ago
These only work with English, so not a general solution. There are more modern, better tools for the problem.

nl 7y ago

I think practical solution to this is to return all words that are within a Levenshtein distance[1] of 2*number_accented_characters of the original word, ranked by the distance. Levenshtein distance can be calculated using a trie[2] so it's fast enough for most purposes. If you wanted to get fancy you could modify the Levenshtein to reduce the distance penalty on accented characters, and/or only apply the Levenshtein calculation within 1 character of an accented character or the equivalent ASCII substitution sequence. [1] https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance [2] http://stevehanov.ca/blog/?id=114 http://stevehanov.ca/blog/?id=114

bmn__ 7y ago

> Is there a solution to this to me seemingly impossible problem? Not at all impossible, you're just not familiar with Unicode. Just use a software that implements UTS #10/UCA. Reply if you want to see code examples for the problems you stated.