5 ms·
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 g
by 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 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.