Unicode sorting is hard and why browsers added special emoji matching to regexp
devlog.hexops.com
devlog.hexops.com
But... is complicated enough to implement that many environments apparently haven't felt there was enough demand to do so?
Unicode is overly complex at grapheme cluster level.
not only that: it's different depending on locale and sometimes context (in Germany there's a distinction of whether you sort for a phone book listing or not).
Doing it right requires basically shipping a huge database with locale specific information which is seen as "bloat" by many projects and thus made optional or not available at all.
>and it's pretty amazing that unicode gives us a standard collation algorithm including localizations, that works remarkably well.
it's not good enough in many cases. Thankfully there's ICU, but many environments frown upon that because it's seen as bloated. If sorting works "fine" for US-ASCII, why link to a 60MB library?
ICU stands for "International Components for Unicode." ICU collation is an implementation of the Unicode Collation Algorithm (which is really a suite of algorithms, or an algorithm with various parameterized branches), using the Unicode Common Locale Data Repository for localization -- that's also unicode, the CLDR is a unicode thing too, part of unicode. It's all unicode.
There are other implementations than ICU -- although maybe none as complete, because it is a lot/expensive, indeed. But ICU is an implementation of unicode algorithms. But for instance, unicode collation is also implemented -- in a way that will be the same as ICU modulo bugs or details the standard leaves up to implementations to vary -- in pure ruby by https://github.com/twitter/twitter-cldr-rb#sorting-collation
NSString would occasionally come up in performance analysis as being strangely slow compared with other languages, but this was because various operations like comparisons followed unicode.
Which is how you implement high-performance unicode collation sorting in say a db.
Unicode is a very well-designed thing!
As an example of a conflicting locale, Swedish would have Äpfel after Käsen!
Just like ae for æ.
"Ä" is a separate letter in the Swedish alphabet: https://en.wikipedia.org/wiki/Swedish_alphabet
In German on the other hand, "Ä" is part of the language but not part of the alphabet and it is simply expanded to "AE" as in the previous comment.
> In German on the other hand, "Ä" is part of the language but not part of the alphabet
Some people claim that, but I wouldn't take that as an authoritative statement. Plenty language authorities disagree, since "ä" and "ae" are not interchangeable.
> it is simply expanded to "AE" as in the previous comment
Only in some contexts (lists of names predominantly), generally "ä" is sorted after "a". E.g. the Duden dictionary goes "zahlen", "zählen", "Zahlenangabe".
However, in 2006 the arguably authorative dictionary changed to sort w after v. Gnu tools have yet to catch up with this, what I can see. :)
That's just it, right? Unicode support has always been a tradeoff between precise coverage/larger binaries and loose coverage/smaller binaries. I'd be excited to see the data size for collation+normalization get under 1MB.
[1] https://www.unicode.org/Public/UCA/13.0.0/allkeys.txt
[2] Encodes `XXXX; [.AAAA.BBBB.CCCC] [*DDDD.EEEE.FFFF] ...` into three-byte code point and seven bytes per each collation element (`.` encoded as 0x01, `*` encoded as 0x02, the end of elements signalled with 0x00); everything is in big endian and sorted by code point. This is not suitable for direct access as is but close. (The only reason I've used a naive encoding here is that, I have never tried to compress DUCET in a directly-accessible form so I couldn't give an educated guess at all.)
1) Not support character encodings outside of ASCII, utf-8 and utf-16
2) Ship a huge wasm bundle or
3) Call back into javascript from my wasm module and use the javascript wrappers around libicu. This would make it harder to use the library outside of javascript.
I'm not sure what the right solution is here. If the character conversion databases can be shrunk to <500kb then I could just ship them with the module. Or if wasm had a better standard library, I could use that. But right now the whole situation is unfortunately awkward.
List<String> sorted = Stream.of("Bären",
"Käfer",
"küssen",
"Ähnlich",
"Äpfel")
.sorted(Collator.getInstance(Locale.ROOT))
.collect(Collectors.toList());
// [Ähnlich, Äpfel, Bären, Käfer, küssen]
It's not a bug, it's by design.
Uh, no? Most if not all scripts do have letter order, CJK(V) "ideographs" included. The actual problem is twofold: the letter order might not be unique, and the word order might be completely different from the letter order. CJK(V) "ideographs" exhibit both problems---their word order is phonetic, while letter order is based on shapes and different dictionaries use different rules---and it is very common in Chinese and Japanese that the string meant to be sortable has pronunciation attached (e.g. Wikipedia).
Also, believe it or not, even emojis do have order too [1], albeit arbitrary one.
Even in Latin scripts, sorting order is language-specific and can even be domain specific (e.g. some languages sort phone books differently from dictionaries).
For "CJKV" systems there are ordering methods such as radicals and, as in European languages, ordering can depend on what you want to accomplish.
https://en.m.wikipedia.org/wiki/Goj%C5%ABon
Eg. Words starting with 一人 can be read as both いちにん (ichinin as in 一人前 - food for one person) or ひとり (hitori - 一人暮らし - living alone)
(2) 大人気 (だいにんき, daininki) - very popular
(not enumerable as in written text as strokes can be combined and invented on the fly, enumerable if you think it's a finite charset on computers)
It can also be sorted using the radical and stroke count, although then you can't enumerate it in order because there's an infinite number of possible characters for each radical.
There might also be an issue if old Hanja-only texts need to be handled differently from Hanzi rendering/processing. That would not surprise me.
Still, I agree it seems pretty weird.
Buuuut historically, there have been several ways to arrange Hangul linearly, and the prevailing sorting in dictionaries differes between North and South Korea.
ASCII ordering is just an arbitrary standard that mapped numbers to letters so people could make computer hardware interoperate. It's not always a sensible sort ordering.
E.G. of sorting how English humans tend to:
`A string with non-letters ignores the non-letters.
Ace
This isn't really true; there are well-defined, standardized answers to all of those:
- For purposes of alphabetizing, punctuation marks are completely ignored, as if they weren't present. "Stop me!" and "Stop, me!" are identical strings.
- Case is also ignored. "AAAAAGH" and "aaaAagh" are identical strings.
- Spaces are not ignored. Sort order is determined by the text before the first space. Shorter sorts before longer. "A bird", "a cat", and "a deer" all sort under "a" and above "ab".
Note that these are rules for English, not rules for arbitrary sequences of binary data. They look the way they do because they model the data as a sequence of English words.
You can't just say "Stop me!" and "Stop, me!" are identical. You have to define which comes first.
Why? All real-world applications of sorting must handle sorting identical objects. Saying that "Stop me!" and "Stop, me!" are identical doesn't cause any problems that aren't also caused by saying "Stop me!" and "Stop me!" are identical.
It's a desired feature of sorting algorithms that they should be deterministic, in which case arbitrarily ordered input should produce identical output.
Otherwise, having non-deterministic output just makes everything harder -- harder to make comparisons, more work to write tests, etc.
This makes as much sense as saying that "Stop me!" and "Stop me!" aren't identical, because one of them is first and the other is second.
It's true, but it's not relevant to sorting them.
Your "desired feature of sorting algorithms" is most commonly realized as the question of whether the algorithm provides a "stable" sort -- that is, whether two values that compare equal are guaranteed to occur in the same order in the (sorted) output that they did in the (unsorted) input. There are applications where this is considered desirable, and many other applications where it isn't. But there are no applications in which it's not possible for two values to compare equal. For the question of stable sorting to arise in the first place, you have to have already realized that you're going to be sorting things that compare equal.
Stability is about preserving the order of items that compare equally. That's a different topic.
I'm talking about it being desirable not to underspecify the comparison function (sorting rules), so that unequal items are never compared as equal.
How would you sort ["О", "Е", "Ζ", "Р", "Η", "С", "Κ"], for example?
Anyway, if you sort in German, Korean names will not be sorted as when you sort in Korean, but then German names will be somewhere else. Ç'est la vie. How else are you going to sort? By mapping everything to phonemes first? And what's the proper sorting order of phonemes? I'm sure German names will on average come either before or after Korean names in that case, too.
All my literal wat. This is absolutely not the expected nor the preferred behaviour.