3 ms·

Hi, Zoekt author here. There are a bunch of interesting replies, but they all miss the point. The reason you can't use bytes is a combination of two things:

Hi, Zoekt author here. There are a bunch of interesting replies, but they all miss the point. The reason you can't use bytes is a combination of two things: (1) code search supports case-insensitive matching. (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. With UTF-8, different case flavors of a character have different widths. For example, k (ascii k, 1 byte), K (ascii K, 1 byte) and K (unicode U+212A for Kelvin, 3 bytes). This messes up algorithm (2). The same consideration holds if you want to support searches where "a" also matches "á" and "ã". I did a talk on exactly this subject in 2017, which goes into more detail. The bit that explains it is here, https://youtu.be/_-KTAvgJYdI?t=602 https://youtu.be/_-KTAvgJYdI?t=602 . If you have more time, you can watch the entire thing, as it is entertaining, if I may say so :)

Sesse__ 5y ago
If you actually want to be UCA-compliant, though, it won't really help you to use codepoints. Different Unicode normalization, contractions and ignorables really mess up things. (In general, you can't search by case-folding if you want all the edge cases right; you have to apply the full Unicode collation algorithm.) I wonder if it's possible to store UCA weights instead of code points in the trigrams, but I haven't thought deeply about it, and it would surely affect indexing speed. In plocate, where I have this exact same issue, I solve it half-heartedly by using 3-byte trigrams and then constructing a whole bunch of alternatives, even if they differ in width. (I don't support accent-insensitive search and I don't support contractions, so locate ß won't find SS.) See https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp;h=678f520fd03cc7c11c63b3cae7f77e712196c56f;hb=HEAD#l197 https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp... — but it doesn't support the Kelvin case if it's in the filename and you give K on the command line.
kevincox 5y ago
> (1) code search supports case-insensitive matching. I'm not quite sure why this matters. Either you are case folding before you store and both cases are the same or you are expanding the query to consider all cases and both cases are the same. You are effectively storing "UTF-8" anyways. It is just whether you are storing 3 bytes or 3 characters. > (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. Could you not still measure this distance in codepoints? Or is there a benefit to tying this to the length of the trigrams? > The same consideration holds if you want to support searches where "a" also matches "á" and "ã". Well IIRC á can be two codepoints as well (if it isn't normalized) so don't you need to handle this case anyways?

Sesse__ 5y ago

If you actually want to be UCA-compliant, though, it won't really help you to use codepoints. Different Unicode normalization, contractions and ignorables really mess up things. (In general, you can't search by case-folding if you want all the edge cases right; you have to apply the full Unicode collation algorithm.) I wonder if it's possible to store UCA weights instead of code points in the trigrams, but I haven't thought deeply about it, and it would surely affect indexing speed. In plocate, where I have this exact same issue, I solve it half-heartedly by using 3-byte trigrams and then constructing a whole bunch of alternatives, even if they differ in width. (I don't support accent-insensitive search and I don't support contractions, so locate ß won't find SS.) See https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp;h=678f520fd03cc7c11c63b3cae7f77e712196c56f;hb=HEAD#l197 https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp... — but it doesn't support the Kelvin case if it's in the filename and you give K on the command line.

kevincox 5y ago

> (1) code search supports case-insensitive matching. I'm not quite sure why this matters. Either you are case folding before you store and both cases are the same or you are expanding the query to consider all cases and both cases are the same. You are effectively storing "UTF-8" anyways. It is just whether you are storing 3 bytes or 3 characters. > (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. Could you not still measure this distance in codepoints? Or is there a benefit to tying this to the length of the trigrams? > The same consideration holds if you want to support searches where "a" also matches "á" and "ã". Well IIRC á can be two codepoints as well (if it isn't normalized) so don't you need to handle this case anyways?