"""English-only hashed n-gram features for the student (input is `normalize`d). Per word: the whole word, plus 3..5-char grams with boundary markers. Between neighbouring words: a word bigram. Each feature is hashed twice (FNV-1a 64); the bucket comes from bits 20..34 so it stays well mixed for any power-of-two bucket count <= 32768, and the sign from bit 63. `hash16` returns the 15-bit raw bucket (`bucket = raw & (n_buckets - 1)`) and the sign so the prepared dataset does not depend on the final bucket count. """ from __future__ import annotations FNV_OFFSET = 0xCBF29CE484222325 FNV_PRIME = 0x100000001B3 MASK64 = (1 << 64) - 1 SEEDS = (0x9E3779B97F4A7C15, 0xC2B2AE3D27D4EB4F) N_HASHES = len(SEEDS) RAW_BITS = 15 def fnv64(s: str, seed: int) -> int: h = (FNV_OFFSET ^ seed) & MASK64 for b in s.encode("utf-8"): h = ((h ^ b) * FNV_PRIME) & MASK64 return h def features(norm_text: str) -> list[str]: words = norm_text.split() out: list[str] = [] for w in words: out.append("w:" + w) s = "<" + w + ">" for n in (3, 4, 5): for i in range(len(s) - n + 1): out.append("g:" + s[i : i + n]) for a, b in zip(words, words[1:]): out.append("b:" + a + " " + b) return out or ["w:\x00"] _CACHE: dict[str, tuple[tuple[int, int], tuple[int, int]]] = {} def hash16(feat: str) -> tuple[tuple[int, int], tuple[int, int]]: """((raw0, sign0), (raw1, sign1)) with raw in [0, 2**15).""" r = _CACHE.get(feat) if r is None: hs = [fnv64(feat, sd) for sd in SEEDS] r = tuple( (((h >> 20) & ((1 << RAW_BITS) - 1)), 1 if (h >> 63) & 1 else -1) for h in hs ) # type: ignore[assignment] _CACHE[feat] = r return r def featurize(norm_text: str, max_features: int): """-> (raw[n,2] int16, sign[n,2] int8) for the first `max_features` features.""" import numpy as np fs = features(norm_text)[:max_features] raw = np.zeros((len(fs), N_HASHES), np.int16) sign = np.zeros((len(fs), N_HASHES), np.int8) for i, f in enumerate(fs): for k, (r, s) in enumerate(hash16(f)): raw[i, k] = r sign[i, k] = s return raw, sign