2 ms·
Because there are trigrams crossing the boundaries between characters. E.g. given the bytes ABCXYZ, the trigrams are not just ABC and XYZ but also BCX and CXY.
by roca 5y ago
Because there are trigrams crossing the boundaries between characters.
E.g. given the bytes ABCXYZ, the trigrams are not just ABC and XYZ but also BCX and CXY. Then the question is, assuming ABC, XYZ, BCX and CXY are all present in a document, what is the probability that ABCXYZ is present in the document? If it's close to 1, then the byte trigram index is about as powerful as a character bigram index.
Of course it's also true that bigrams might be inadequately selective, but the underlying alphabet is probably larger than ASCII if it encodes to 3 bytes in UTF8.
Again I'm not arguing that trigrams-over-bytes is necessarily the best option here, just that it's simpler and a decision to do trigrams over Unicode characters needs data to justify it, and I'd love to know what that data is.
- Scaevolus 5y agoTrigrams have an approximately 30% false positive rate when used as a filter for whether to skip repos.
- roca 5y agoThat's interesting, and doesn't surprise me. When I wrote an n-gram full-text search for email 20 years ago, I used 4-grams to get the required selectivity. I imagine code could be worse because of more restricted syntax and alphabet. However, this doesn't bear directly on the question of trigrams-over-UTF8-bytes vs trigrams-over-Unicode-chars.