6 ms·

There is one property about UTF-8 that distinguishes it from opaque byte strings of unknown encoding: its codepoints are self-delimiting, so you can naively loc

There is one property about UTF-8 that distinguishes it from opaque byte strings of unknown encoding: its codepoints are self-delimiting, so you can naively locate instances of a substring (and delete them, replace them, split on them, etc.) without worrying that you've grabbed something else with the same bytes as the substring. Constrast with UTF-16, where a substring might match the bytes at an odd index in the original string, corresponding to totally different characters. Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful (e.g., it doesn't end in part of a grapheme cluster; though if you want to avoid breaking up words, you may also want a \b-like mechanism). So it does seem to refute the author's notion that you can do nothing with knowledge only of the encoding.

lmm 2y ago
> Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful Nope. Searching a UTF-8 string for a byte sequence, even one that is semantically meaningful, is not a semantically meaningful operation in most human languages. E.g. searching for the byte sequence 63 61 66 C3 A9 will not find the semantically equivalent byte sequence 63 61 66 65 CC 81, and so your program will have very annoying bugs.
- bqmjjx0kac 2y ago
  Is it possible to cheaply canonicalize UTF-8? Or is a full parse/validation unavoidable if all you need to do is a substring search? I suppose you could also generate all byte sequences that encode the desired substring and do an NFA-to-DFA trick to search in linear time.
  - remram 2y ago
    No, the normalization algorithms require big tables of which codepoints are equivalent to what codepoint.
  - asveikau 2y ago
    I think there is no cheap Unicode normalization. It's done with lookup tables.
  - tsimionescu 2y ago
    There's no such thing as "canonical UTF-8". You can ask about canonicalizing Unicode, regardless of the byte encoding, and no, there's no cheap way.
  - lmm 2y ago
    > Is it possible to cheaply canonicalize UTF-8? Or is a full parse/validation unavoidable if all you need to do is a substring search? Even if it was, it wouldn't help you. Implementing search over unicode text properly requires locale-awareness and cannot be done by comparing codepoint sequences, even after canonicalisation.
tsimionescu 2y ago
String equality is an extremely domain-dependent problem. It's so bad that it's even possible for two strings that contain identical bytes to represent different strings! (because of CJK unification, the same UTF-8 byte sequence encodes different characters in different locales). And it's extremely common in Unicode for different byte sequences to represent the same characters, in various ways (accented characters vs character+accent, different orders of character and accents, identical characters in different scripts, such as latin a and cyrillic a, etc). And beyond Unicode itself, two strings that would be displayed differently would still be expected by your users to match. Case insensitive search is the most common example for English, but other language users often expect searches to ignore accents or similar diacritics. Then, for things like addresses and even sometimes names, multiple spellings of the same name are often considered matches, e.g. when identifying a delivery address, or for many kinds of simple identity verifications. There's really no good general concept of string equality that you can bake into a language except for the byte equality one, which doesn't care for UTF-8.
- echoangle 2y ago
  I don’t agree that there is no general right way of comparing strings. I think most people would agree that strings are considered equal if they are made up of the same characters in the same sequence. That means Cyrillic characters are considered different characters than lookalike Latin characters. It also means that for string comparison, different methods if representing accented characters should be considered equal. The points you mentioned about matching strings without considering accents or matching different ways to write an address are relevant in applications but that’s not really string equality, I would call that string similarity or fuzzy search. As far as I know, the correct way to compare Unicode strings is to normalize them and then compare the bytes.
  - tsimionescu 2y ago
    Most people might agree, but most people would be wrong. I actually think that most people would agree that string comparison should be a byte by byte comparison, which I think is actually slightly better. > That means Cyrillic characters are considered different characters than lookalike Latin characters. It also means that for string comparison, different methods if representing accented characters should be considered equal. Why? I know this is how Unicode defines it, but what real world use case does this serve? Why would two strings that will be rendered identically in virtually any use case, like "Cap" and "Сар", be considered different, but other strings like "ő" and "ő", equal? Edit: > As far as I know, the correct way to compare Unicode strings is to normalize them and then compare the bytes. This is also a kind of fuzzy string match, just a different kind of fuzzyness. For example, this is an inappropriate way to compare strings if you're using it in a file diff implementation, as you would conclude a file has not changed when in fact it has, in ways which might matter to other tools. Database engines don't normally do normalization before enforcing uniqueness or creating indexes.
GuB-42 2y ago
> Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful Doesn't work with ZWJ emoji, for example, the "job" emojis are made by combining a "person" emoji and another emoji related to the job. For example the emoji for a male pilot is encoded as man+ZWJ+plane. It means the "plane" emoji (a meaningful substring) will be found in the "pilot" emoji even though it is a different thing. I don't know if the same thing happens in natural languages. Some languages use ZWJ, or combining diacritics, but I don't know how acceptable, for instance, looking for "e" and finding "é" would be.
jakobnissen 2y ago
You can also do that with invalid UTF8. You simply treat the first invalid byte of a codepoint as the first byte of a new codepoint, terminating the previous one. In this way, the self-syncronization (self-dilimiting) of UTF8 is preserved. This is what Julia does.
- LegionMammal978 2y ago
  Sure, that's one way to do it, but if the invalid byte were logically tied to the byte before it in its original encoding, then now your substring split will mangle that character.
  - Etherlord87 2y ago
    If it's invalid then you don't mangle anything, it's mangled already for whatever reason, no?
zzo38computer 2y ago
> Constrast with UTF-16, where a substring might match the bytes at an odd index in the original string, corresponding to totally different characters. This is not a problem if you have the correct alignment; since it works on 16-bit units then you would be searching/indexing/splitting on such boundaries. There are surrogates, but you can easily self-delimit them like you can with UTF-8, too.

lmm 2y ago

> Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful Nope. Searching a UTF-8 string for a byte sequence, even one that is semantically meaningful, is not a semantically meaningful operation in most human languages. E.g. searching for the byte sequence 63 61 66 C3 A9 will not find the semantically equivalent byte sequence 63 61 66 65 CC 81, and so your program will have very annoying bugs.

bqmjjx0kac 2y ago
Is it possible to cheaply canonicalize UTF-8? Or is a full parse/validation unavoidable if all you need to do is a substring search? I suppose you could also generate all byte sequences that encode the desired substring and do an NFA-to-DFA trick to search in linear time.
- remram 2y ago
  No, the normalization algorithms require big tables of which codepoints are equivalent to what codepoint.
- asveikau 2y ago
  I think there is no cheap Unicode normalization. It's done with lookup tables.
- tsimionescu 2y ago
  There's no such thing as "canonical UTF-8". You can ask about canonicalizing Unicode, regardless of the byte encoding, and no, there's no cheap way.
- lmm 2y ago
  > Is it possible to cheaply canonicalize UTF-8? Or is a full parse/validation unavoidable if all you need to do is a substring search? Even if it was, it wouldn't help you. Implementing search over unicode text properly requires locale-awareness and cannot be done by comparing codepoint sequences, even after canonicalisation.

tsimionescu 2y ago

String equality is an extremely domain-dependent problem. It's so bad that it's even possible for two strings that contain identical bytes to represent different strings! (because of CJK unification, the same UTF-8 byte sequence encodes different characters in different locales). And it's extremely common in Unicode for different byte sequences to represent the same characters, in various ways (accented characters vs character+accent, different orders of character and accents, identical characters in different scripts, such as latin a and cyrillic a, etc). And beyond Unicode itself, two strings that would be displayed differently would still be expected by your users to match. Case insensitive search is the most common example for English, but other language users often expect searches to ignore accents or similar diacritics. Then, for things like addresses and even sometimes names, multiple spellings of the same name are often considered matches, e.g. when identifying a delivery address, or for many kinds of simple identity verifications. There's really no good general concept of string equality that you can bake into a language except for the byte equality one, which doesn't care for UTF-8.

echoangle 2y ago
I don’t agree that there is no general right way of comparing strings. I think most people would agree that strings are considered equal if they are made up of the same characters in the same sequence. That means Cyrillic characters are considered different characters than lookalike Latin characters. It also means that for string comparison, different methods if representing accented characters should be considered equal. The points you mentioned about matching strings without considering accents or matching different ways to write an address are relevant in applications but that’s not really string equality, I would call that string similarity or fuzzy search. As far as I know, the correct way to compare Unicode strings is to normalize them and then compare the bytes.
- tsimionescu 2y ago
  Most people might agree, but most people would be wrong. I actually think that most people would agree that string comparison should be a byte by byte comparison, which I think is actually slightly better. > That means Cyrillic characters are considered different characters than lookalike Latin characters. It also means that for string comparison, different methods if representing accented characters should be considered equal. Why? I know this is how Unicode defines it, but what real world use case does this serve? Why would two strings that will be rendered identically in virtually any use case, like "Cap" and "Сар", be considered different, but other strings like "ő" and "ő", equal? Edit: > As far as I know, the correct way to compare Unicode strings is to normalize them and then compare the bytes. This is also a kind of fuzzy string match, just a different kind of fuzzyness. For example, this is an inappropriate way to compare strings if you're using it in a file diff implementation, as you would conclude a file has not changed when in fact it has, in ways which might matter to other tools. Database engines don't normally do normalization before enforcing uniqueness or creating indexes.

GuB-42 2y ago

> Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful Doesn't work with ZWJ emoji, for example, the "job" emojis are made by combining a "person" emoji and another emoji related to the job. For example the emoji for a male pilot is encoded as man+ZWJ+plane. It means the "plane" emoji (a meaningful substring) will be found in the "pilot" emoji even though it is a different thing. I don't know if the same thing happens in natural languages. Some languages use ZWJ, or combining diacritics, but I don't know how acceptable, for instance, looking for "e" and finding "é" would be.

jakobnissen 2y ago

You can also do that with invalid UTF8. You simply treat the first invalid byte of a codepoint as the first byte of a new codepoint, terminating the previous one. In this way, the self-syncronization (self-dilimiting) of UTF8 is preserved. This is what Julia does.

LegionMammal978 2y ago
Sure, that's one way to do it, but if the invalid byte were logically tied to the byte before it in its original encoding, then now your substring split will mangle that character.
- Etherlord87 2y ago
  If it's invalid then you don't mangle anything, it's mangled already for whatever reason, no?

zzo38computer 2y ago

> Constrast with UTF-16, where a substring might match the bytes at an odd index in the original string, corresponding to totally different characters. This is not a problem if you have the correct alignment; since it works on 16-bit units then you would be searching/indexing/splitting on such boundaries. There are surrogates, but you can easily self-delimit them like you can with UTF-8, too.