8 ms·
> 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
by 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 agoIs 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 agoNo, the normalization algorithms require big tables of which codepoints are equivalent to what codepoint.
- asveikau 2y agoI think there is no cheap Unicode normalization. It's done with lookup tables.
- tsimionescu 2y agoThere'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.