extractTrigrams returns deduplicated, sorted trigrams (three-byte subsequences) from s. Trigrams are the primary index key: a document matches a query only if every query trigram appears in the document, giving O(1) candidate filtering per trigram.
(s []byte)
| 62 | // document matches a query only if every query trigram appears in |
| 63 | // the document, giving O(1) candidate filtering per trigram. |
| 64 | func extractTrigrams(s []byte) []uint32 { |
| 65 | if len(s) < 3 { |
| 66 | return nil |
| 67 | } |
| 68 | seen := make(map[uint32]struct{}, len(s)) |
| 69 | for i := 0; i <= len(s)-3; i++ { |
| 70 | b0 := toLowerASCII(s[i]) |
| 71 | b1 := toLowerASCII(s[i+1]) |
| 72 | b2 := toLowerASCII(s[i+2]) |
| 73 | gram := uint32(b0)<<16 | uint32(b1)<<8 | uint32(b2) |
| 74 | seen[gram] = struct{}{} |
| 75 | } |
| 76 | result := make([]uint32, 0, len(seen)) |
| 77 | for g := range seen { |
| 78 | result = append(result, g) |
| 79 | } |
| 80 | slices.Sort(result) |
| 81 | return result |
| 82 | } |
| 83 | |
| 84 | func extractBasename(path []byte) (offset int, length int) { |
| 85 | end := len(path) |