xxUTF - SIMD Unicode Normalization

[patent sigil]

https://github.com/dzfrias/xxUTF

This is a project I have been working on for a long time, and I've finally felt good enough to release 0.1.0 to put the project into the alpha stage. There's a lot to do still, but I hope the performance gains are appealing (7-33x faster NFD normalization than the next fastest open source implementation)!

The routines are written in C but the project uses the Zig build system. I can confidently say that it is by far the best option for building C projects. All testing and benchmarking for the project is also done in Zig thanks to the great interop capabilities. Also, the xxu command line tool (fast normalization and case folding from the command line) is written in Zig.

[wicked stump]

wow, that is great. I have been using copy paste folding from Java lucene for indexing and search so I can convert and lowercase text before indexing, and also before searching. I am not even aware of different normalizations.

I am from Croatia, my interest was mostly local for balkan ČĆŠĐ and austria germany ümlaut

what would you suggest I should use form your experience ?

until now, I just had a piece of code I move from project to project, but seing your project, now I am curious to know more 🙂 any hints for noobs in this area ?

[patent sigil]

For indexing and search, there are a few options. If you want to strip diacritics (the accent symbols over characters like "Č"), I'd recommend the following:

1. Normalize to NFKD
2. Remove diacritic characters (my library does not have algorithms for this yet, but essentially it involves iterating over all Unicode characters and filtering out the ones that have a certain character category. Here is a link to the categories. You want to filter out characters in the category "M")
3. Case fold

This will match "Č" to "c", for example. It will also have the bonus of matching characters like "①" to "1", which is usually what people want for searching/indexing. Lowercase folding also works most of the time, but can lead to problems in specific languages (like the German "ß").

If you don't want to strip diacritics, you could do:

1. Normalize to NFKC
2. Case fold

This will match "Č" to "č" but not to "c".

[patent sigil]

I wrote a blog post that explains the project and goes in depth into how normalization works (and also what the different normalization forms do). https://dzfrias.dev/blog/xxutf

[candid gale]

very cool work! you should get it into postgres!

[wicked stump]

for me it is very useful to fold to ASCII and lowercase in one pass. As usesr also write woth or without diacritics, so it is best to fold them and lowercase before indexing or searching theindex

Čačić -> cacic

[wicked stump]

maybe you already have:

• unaccent pg 13+
• CASEFOLD - pg 18+

[candid gale]

oh. you can do it. I meant the optimization work

[wicked stump]

I prefer not to depend on special things like that, so move this type of thing to code away from database.
In my cases it was fine to sacrifice some space by bloating each row with special textSearch column where app puts all filds from table I want text search, and do in-app folding and diacritics removal. That way it works on any database 🙂

[patent sigil]

Thank you! I definitely want to see if there are projects like postgres that are interested in my work

[candid gale]

yes, iirc citext is extension only, could get it into there. but i was wondering if it is semantically identical to e.g. lower functional index comparisons or what have you. not sure the details. would be interested to know though!

blogging your adventures in trying to do so would be nice too

[patent sigil]

citext is not semantically identical to what I have since it handles case-insensitivity via lowercasing. I think this is a design issue since it isn't correctly case-insensitive for certain characters. Postgres mentions it as a limitation in the docs, too. Also, lowercasing is a locale-dependent operation (in postgres, they read locale off of LC_CTYPE). Unicode case folding is locale-independent case insensitivity that correctly handles the characters that lowercasing can't. So I probably won't be able to get it into citext unfortunately, unless I write locale-dependent algorithms into xxUTF, which requires a lot of locale data. I think that could be an interesting future target for the project, though. I'd just have to be careful about binary size using feature flags and whatnot

But I did take a look at postgres source code and they internally use Unicode normalization, which I do have algorithms for in xxUTF. It would be interesting to try to get it into there but definitely a lot harder since it's not an extension.

[candid gale]

interesting. TIL. but i am surprised - sounds like yours would be an improvement. maybe you should write your own extension!

[patent sigil]

Oh yeah I actually haven't thought about that! I'll look into it, thanks for the suggestion