4 ms·

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 differen

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.
  - echoangle 2y ago
    Im pretty sure we both agree that equality should not depend on the look of the character, as you said you prefer byte comparison. Treating different byte encodings of the same character as equal makes sense to me, because the different possibilities of representing the characters are just an artifact of the encoding. It’s like comparing negative and positive zero floats. It’s the same value, but the encoding allows multiple equivalent representations. I wouldn’t call the matching after normalization fuzzy, because the thing you want to compare is the actual characters, not the way they are encoded. You’re right that doing normalization when diffing files would be wrong, but that’s because you don’t want to compare strings when doing diffs, you want to compare binary representation. Edit: to make my point more clear: If I give my string comparison function different strings containing the same characters, but encoded in different ways (for example UTF-8 and UTF-16), I would expect the function to tell me they are equal, because the function is supposed to compare the string content, not the way it is encoded in memory.
    - tsimionescu 2y ago
      > Im pretty sure we both agree that equality should not depend on the look of the character, as you said you prefer byte comparison. My position is that "string equality" is a meaningless term on its own, that different contexts require different notions of equality and that none of these is fundamentally better than any other. "the strings look the same to a human", "the strings are represented by the same bytes on a wire/disk", "the strings represent the same characters even if encoded differently", "the strings represent the same word to a native", "the strings represent the same street name to a native", "the strings represent the same human name", etc are all just as valid concepts of "string equality" and are useful in different more or less narrow contexts. Your point that the need for normalization is just an artifact of the encoding is fair enough, but there are still valid contexts, even beyond pure byte comparisons, that require these to be considered different - if nothing else, then at least in posts explaining this very difference. > If I give my string comparison function different strings containing the same characters, but encoded in different ways (for example UTF-8 and UTF-16), I would expect the function to tell me they are equal, because the function is supposed to compare the string content, not the way it is encoded in memory. A perfectly valid equality, just like many others I mentioned.
- samatman 2y ago
  "Correct" isn't quite, well, correct here ;) For a starting point, case-insensitive comparison is comparison, and is locale-specific. The general name for the task we're discussion is "collation". Unicode defines a standard collation algorithm: https://www.unicode.org/reports/tr10/ https://www.unicode.org/reports/tr10/ This is designed (because it has to be) to work with locale data, also provided by Unicode https://cldr.unicode.org https://cldr.unicode.org I would say that the minimum a language's standard library should provide is: all the normalization forms, and a lexicographical sort. "Fancy Unicode" (there's a lot!) is better off as a library of its own, or perhaps several: covering every single base is a monumental achievement, and a rather large codebase. There are valid sorts not defined by Unicode, involving abbreviations, standard corrections of misspellings, and much more: these are needed for tasks like address normalization.
Etherlord87 2y ago
You mentioned quite a lot of things here. Not really a spectrum, but on one side you have a comparison of bits (bytes), where only maybe byte order may cause issues, and on the other you have such high-level problems like comparing synonyms "begin" == "start" (or you could go further and compare sentences if they convey the same information). Somewhere between those extremes you have characters, glyphs, "confusables", normalization... I don't follow on your CJK unification argument... How are strings different if they share the same codepoint? Is there software that analyzes the language used, or otherwise context, and prints the codepoint differently based on the context? Or is there a recommendation to do so?
- tsimionescu 2y ago
  > Not really a spectrum, but on one side you have a comparison of bits (bytes), where only maybe byte order may cause issues, and on the other you have such high-level problems like [...] Yes, and my point is that various real-world problems will require various solutions from this spectrum. > How are strings different if they share the same codepoint? Is there software that analyzes the language used, or otherwise context, and prints the codepoint differently based on the context? Or is there a recommendation to do so? Yes, any renderer is supposed to choose a (slightly) different glyph for those codepoints based on the user's chosen locale. Wikipedia has a table of examples [0] of various codepoints that are supposed to be slightly different in Chinese (Simplified), Chinese (Traditional), Japanese, Korean, or Vietnamese. It of course depends on your use case if you'd care beyond that. For example, if the problem you're solving is "are these two strings going to render identically", then the code points don't help, you also need to know that you need to take into account locale. I can imagine some (very niche, to be sure) use cases like this in the area of OCR or of web page comparison. [0] https://en.m.wikipedia.org/wiki/Han_unification#Examples_of_language-dependent_glyphs https://en.m.wikipedia.org/wiki/Han_unification#Examples_of_...
zzo38computer 2y ago
> Why would "the path name you entered is not valid Unicode/UTF-8" be a good error message, if the path actually exists on the system? On Windows NT (which uses Unicode file names), it is a good error message (although it should allow UTF-8 with possible mismatched surrogates, which is called WTF-8). However, on UNIX, and other systems that don't use Unicode file names, it is not a good error message; the program should not care if the path is valid UTF-8 and should just use it as is. (If the system disallows certain bytes in file names (or if the user entered a file name that is too long for the file system in use) then the error message can say that, if that is the case, though) > 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. I agree. How you compare text (or other data) would depend on the application-specific details, and Unicode makes it especially complicated (and probably even impossible to do "correctly" in any way other than just comparing bytes, anyways). (Even, in my own operating system design, which does not use Unicode but uses Extended TRON Code instead (it also supports arbitrary 8-bit character sets, which in some contexts are much more useful than large character sets), I had considered that comparing text still depends on application-specific details (and other details); while many of the problems of Unicode are avoided, there are still problems, including some of its own, although they are not as complicated to deal with than Unicode, and I had considered how to deal with them.)

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.
- echoangle 2y ago
  Im pretty sure we both agree that equality should not depend on the look of the character, as you said you prefer byte comparison. Treating different byte encodings of the same character as equal makes sense to me, because the different possibilities of representing the characters are just an artifact of the encoding. It’s like comparing negative and positive zero floats. It’s the same value, but the encoding allows multiple equivalent representations. I wouldn’t call the matching after normalization fuzzy, because the thing you want to compare is the actual characters, not the way they are encoded. You’re right that doing normalization when diffing files would be wrong, but that’s because you don’t want to compare strings when doing diffs, you want to compare binary representation. Edit: to make my point more clear: If I give my string comparison function different strings containing the same characters, but encoded in different ways (for example UTF-8 and UTF-16), I would expect the function to tell me they are equal, because the function is supposed to compare the string content, not the way it is encoded in memory.
  - tsimionescu 2y ago
    > Im pretty sure we both agree that equality should not depend on the look of the character, as you said you prefer byte comparison. My position is that "string equality" is a meaningless term on its own, that different contexts require different notions of equality and that none of these is fundamentally better than any other. "the strings look the same to a human", "the strings are represented by the same bytes on a wire/disk", "the strings represent the same characters even if encoded differently", "the strings represent the same word to a native", "the strings represent the same street name to a native", "the strings represent the same human name", etc are all just as valid concepts of "string equality" and are useful in different more or less narrow contexts. Your point that the need for normalization is just an artifact of the encoding is fair enough, but there are still valid contexts, even beyond pure byte comparisons, that require these to be considered different - if nothing else, then at least in posts explaining this very difference. > If I give my string comparison function different strings containing the same characters, but encoded in different ways (for example UTF-8 and UTF-16), I would expect the function to tell me they are equal, because the function is supposed to compare the string content, not the way it is encoded in memory. A perfectly valid equality, just like many others I mentioned.
samatman 2y ago
"Correct" isn't quite, well, correct here ;) For a starting point, case-insensitive comparison is comparison, and is locale-specific. The general name for the task we're discussion is "collation". Unicode defines a standard collation algorithm: https://www.unicode.org/reports/tr10/ https://www.unicode.org/reports/tr10/ This is designed (because it has to be) to work with locale data, also provided by Unicode https://cldr.unicode.org https://cldr.unicode.org I would say that the minimum a language's standard library should provide is: all the normalization forms, and a lexicographical sort. "Fancy Unicode" (there's a lot!) is better off as a library of its own, or perhaps several: covering every single base is a monumental achievement, and a rather large codebase. There are valid sorts not defined by Unicode, involving abbreviations, standard corrections of misspellings, and much more: these are needed for tasks like address normalization.

Etherlord87 2y ago

You mentioned quite a lot of things here. Not really a spectrum, but on one side you have a comparison of bits (bytes), where only maybe byte order may cause issues, and on the other you have such high-level problems like comparing synonyms "begin" == "start" (or you could go further and compare sentences if they convey the same information). Somewhere between those extremes you have characters, glyphs, "confusables", normalization... I don't follow on your CJK unification argument... How are strings different if they share the same codepoint? Is there software that analyzes the language used, or otherwise context, and prints the codepoint differently based on the context? Or is there a recommendation to do so?

tsimionescu 2y ago
> Not really a spectrum, but on one side you have a comparison of bits (bytes), where only maybe byte order may cause issues, and on the other you have such high-level problems like [...] Yes, and my point is that various real-world problems will require various solutions from this spectrum. > How are strings different if they share the same codepoint? Is there software that analyzes the language used, or otherwise context, and prints the codepoint differently based on the context? Or is there a recommendation to do so? Yes, any renderer is supposed to choose a (slightly) different glyph for those codepoints based on the user's chosen locale. Wikipedia has a table of examples [0] of various codepoints that are supposed to be slightly different in Chinese (Simplified), Chinese (Traditional), Japanese, Korean, or Vietnamese. It of course depends on your use case if you'd care beyond that. For example, if the problem you're solving is "are these two strings going to render identically", then the code points don't help, you also need to know that you need to take into account locale. I can imagine some (very niche, to be sure) use cases like this in the area of OCR or of web page comparison. [0] https://en.m.wikipedia.org/wiki/Han_unification#Examples_of_language-dependent_glyphs https://en.m.wikipedia.org/wiki/Han_unification#Examples_of_...

zzo38computer 2y ago

> Why would "the path name you entered is not valid Unicode/UTF-8" be a good error message, if the path actually exists on the system? On Windows NT (which uses Unicode file names), it is a good error message (although it should allow UTF-8 with possible mismatched surrogates, which is called WTF-8). However, on UNIX, and other systems that don't use Unicode file names, it is not a good error message; the program should not care if the path is valid UTF-8 and should just use it as is. (If the system disallows certain bytes in file names (or if the user entered a file name that is too long for the file system in use) then the error message can say that, if that is the case, though) > 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. I agree. How you compare text (or other data) would depend on the application-specific details, and Unicode makes it especially complicated (and probably even impossible to do "correctly" in any way other than just comparing bytes, anyways). (Even, in my own operating system design, which does not use Unicode but uses Extended TRON Code instead (it also supports arbitrary 8-bit character sets, which in some contexts are much more useful than large character sets), I had considered that comparing text still depends on application-specific details (and other details); while many of the problems of Unicode are avoided, there are still problems, including some of its own, although they are not as complicated to deal with than Unicode, and I had considered how to deal with them.)