File size: 2,223 Bytes
c394b65
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""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