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
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 :)
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-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
- https://www.php.net/manual/en/function.soundex.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
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?
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.
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
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.
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?