holographic_memory/core/
encoding.rs

1// Copyright 2024-2026 WritersLogic Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Text encoders: text in, sparse hypervector out.
5//!
6//! `multiscale-words-v1` is specified by `encode_reference`: character n-grams at scales
7//! 2-5 (one hypervector per character, permuted by its offset in the window and bound by
8//! symmetric difference), word tokens permuted by position, and word bigrams, each level
9//! bundled by majority vote, the levels combined by cross-level support. That function is the
10//! contract (`docs/file-format/ENCODERS.md`: same text and dimension, same indices forever) and
11//! stays reachable for the equivalence test in `tests/ingest_encode.rs`.
12//!
13//! `TextEncoder::encode` computes the same function through per-thread memo tables and
14//! reused scratch buffers, which is where ingest spends its time (`new_deterministic` per
15//! character of every n-gram, a sort of every level's concatenated indices, and one heap
16//! allocation per intermediate vector). It produces identical indices because:
17//!
18//! 1. `EntangledHVec::new_deterministic(dim, seed)` is a pure function of `(dim, seed)`, so a
19//!    base vector is memoized by seed (`EncodeState::terms`); two words with equal seeds share
20//!    a vector in the reference as well, so keying by seed adds no collision.
21//! 2. `permute(shift)` maps a sorted index set through `(idx + shift) % dim`, a bijection; the
22//!    sorted result is the rotation `rotate_sorted` computes without sorting, and a multiset
23//!    that is only counted needs no order at all.
24//! 3. `bind` is the symmetric difference of two sorted sets: set-valued, so any correct
25//!    implementation yields the same indices. A character n-gram's bound vector depends only on
26//!    `(scale, characters)` and is memoized by that exact key (`EncodeState::ngrams`).
27//! 4. `EntangledHVec::bundle` depends on its inputs only through the ascending run-length list
28//!    `(index, count)` of the concatenated indices. `EncodeState::bundle_flat` builds the same
29//!    list from a histogram over `[0, dim)` (or by sorting when `dim` dwarfs the index total)
30//!    and then calls the identical `select_nth_unstable_by` on the identical slice; that call's
31//!    comparator has ties, so the retained set depends on input order and algorithm, both kept.
32//! 5. The cross-level selection orders by `(count desc, index asc)`, a total order, so it is a
33//!    function of the level bundles alone.
34//!
35//! The memo tables are a per-thread cache with a fixed budget (cleared when exceeded), never
36//! an input to the result: output is independent of thread, cache state and call history.
37
38use super::entangled::{hash_u64, EntangledHVec, DEFAULT_RHO_DENOM};
39use serde::{Deserialize, Serialize};
40use std::cell::RefCell;
41
42#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
43pub enum TextEncoder {
44    #[default]
45    #[serde(rename = "multiscale-words-v1")]
46    MultiscaleWordsV1,
47    /// Experimental union within each level, capped by cross-level frequency.
48    #[serde(rename = "multiscale-capped-union-v1")]
49    MultiscaleCappedUnionV1,
50    /// Sparse sketch of a local neural sentence embedding (feature `local-embed`); the store's
51    /// documents also get dense chunk embeddings from the same model.
52    #[serde(rename = "local-embed-v1")]
53    LocalEmbedV1,
54}
55
56impl TextEncoder {
57    pub fn name(self) -> &'static str {
58        match self {
59            Self::MultiscaleWordsV1 => "multiscale-words-v1",
60            Self::MultiscaleCappedUnionV1 => "multiscale-capped-union-v1",
61            Self::LocalEmbedV1 => "local-embed-v1",
62        }
63    }
64
65    /// Whether vectors come from a neural embedding instead of the text itself.
66    pub fn is_embedding(self) -> bool {
67        self == Self::LocalEmbedV1
68    }
69
70    pub(crate) fn encode(self, text: &str, dim: usize) -> EntangledHVec {
71        assert!(
72            !self.is_embedding(),
73            "embedding encoders are applied to embeddings by the engine, not to text"
74        );
75        ENCODE_STATE.with(|state| encode_cached(text, dim, self, &mut state.borrow_mut()))
76    }
77
78    /// The production path ([`Self::encode`]) for callers outside the crate, such as the
79    /// equivalence test; not part of the stable API.
80    #[doc(hidden)]
81    pub fn encode_text(self, text: &str, dim: usize) -> EntangledHVec {
82        self.encode(text, dim)
83    }
84
85    /// The reference formulation of the encoder: one `new_deterministic` per character of every
86    /// n-gram and sorting bundles, exactly as before the memoized path existed. Kept so the
87    /// equivalence test can assert bit-identical output; not part of the stable API.
88    #[doc(hidden)]
89    pub fn encode_reference(self, text: &str, dim: usize) -> EntangledHVec {
90        assert!(
91            !self.is_embedding(),
92            "embedding encoders are applied to embeddings by the engine, not to text"
93        );
94        encode_reference(text, dim, self)
95    }
96
97    fn bundle(self, vectors: &[EntangledHVec]) -> EntangledHVec {
98        match self {
99            Self::MultiscaleWordsV1 | Self::LocalEmbedV1 => EntangledHVec::bundle(vectors),
100            Self::MultiscaleCappedUnionV1 => EntangledHVec::bundle_bloom(vectors),
101        }
102    }
103
104    /// Whether a level is bundled by set union (`bundle_bloom`) rather than majority vote.
105    fn bundles_by_union(self) -> bool {
106        self == Self::MultiscaleCappedUnionV1
107    }
108}
109
110impl std::str::FromStr for TextEncoder {
111    type Err = anyhow::Error;
112
113    fn from_str(name: &str) -> Result<Self, Self::Err> {
114        match name {
115            "multiscale-words-v1" => Ok(Self::MultiscaleWordsV1),
116            "multiscale-capped-union-v1" => Ok(Self::MultiscaleCappedUnionV1),
117            "local-embed-v1" => Ok(Self::LocalEmbedV1),
118            _ => anyhow::bail!("unknown text encoder {name:?}"),
119        }
120    }
121}
122
123/// Multi-scale text encoding combining character n-grams, word tokens, and
124/// word bigrams into a single sparse hypervector.
125///
126/// Architecture (based on Rahimi et al. 2016, Joshi et al. 2020):
127///
128/// 1. **Character n-grams** at scales 2-5 capture morphological similarity.
129///    "cat" and "cats" share most bigrams/trigrams; different n-gram sizes
130///    provide redundancy and cover different morphological features.
131///
132/// 2. **Word tokens** with positional binding capture lexical identity.
133///    Each word is hashed as a unit and bound with its sentence position,
134///    so word order is partially preserved.
135///
136/// 3. **Word bigrams** capture local phrase structure.
137///    Adjacent word pairs bound together represent collocations.
138///
139/// Each level uses a unique seed space (LEVEL_CHAR, LEVEL_WORD, LEVEL_PHRASE)
140/// to prevent cross-level hash collisions. Levels are bundled with
141/// empirically-tuned weights favoring word identity (highest signal-to-noise
142/// ratio for retrieval tasks).
143///
144/// Breaking change: vectors produced by this encoder are incompatible with
145/// the previous character-trigram-only encoder. Re-encode stored data.
146const CHAR_NGRAM_SIZES: [usize; 4] = [2, 3, 4, 5];
147
148/// The largest character n-gram scale; the memo key holds this many characters.
149const MAX_CHAR_NGRAM: usize = 5;
150const _: () = assert!(CHAR_NGRAM_SIZES[CHAR_NGRAM_SIZES.len() - 1] == MAX_CHAR_NGRAM);
151
152/// Level seed offsets prevent cross-level hash collisions.
153const LEVEL_CHAR: u64 = 0x01;
154const LEVEL_WORD: u64 = 0x02;
155const LEVEL_PHRASE: u64 = 0x03;
156
157/// Per-thread budget, in `u32` slots, of memoized base vectors (words, bigram words and
158/// characters, keyed by seed): 4 MiB. The table is cleared when a new entry would exceed it.
159const TERM_ARENA_BUDGET: usize = 1 << 20;
160
161/// Per-thread budget, in `u32` slots, of memoized character n-gram vectors: 8 MiB.
162const NGRAM_ARENA_BUDGET: usize = 1 << 21;
163
164/// A level is bundled through a histogram over `[0, dim)` when `dim` is at most this many
165/// times the number of indices to count; sorting them is cheaper beyond that.
166const COUNTING_RATIO: usize = 8;
167
168pub fn encode_text_internal(text: &str, dim: usize) -> EntangledHVec {
169    TextEncoder::MultiscaleWordsV1.encode(text, dim)
170}
171
172thread_local! {
173    static ENCODE_STATE: RefCell<EncodeState> = RefCell::new(EncodeState::default());
174}
175
176/// A memoized vector's location in an arena.
177#[derive(Clone, Copy)]
178struct Span {
179    start: usize,
180    len: usize,
181}
182
183impl Span {
184    fn range(self) -> std::ops::Range<usize> {
185        self.start..self.start + self.len
186    }
187}
188
189/// Exact identity of a character n-gram: its scale and characters (unused slots are NUL,
190/// which no window at that scale can contain in those positions).
191#[derive(Clone, Copy, PartialEq, Eq, Hash)]
192struct NgramKey {
193    n: u8,
194    chars: [char; MAX_CHAR_NGRAM],
195}
196
197/// Memo tables and scratch buffers of one thread. Invariants: every span in `terms` and
198/// `ngrams` lies inside its arena; both tables hold vectors for `dim` only; `counts` is
199/// all-zero outside [`EncodeState::bundle_flat`]; scratch vectors carry no state between calls.
200#[derive(Default)]
201struct EncodeState {
202    dim: usize,
203    /// seed -> sorted indices of `EntangledHVec::new_deterministic(dim, seed)`.
204    terms: fxhash::FxHashMap<u64, Span>,
205    term_arena: Vec<u32>,
206    /// n-gram -> sorted indices of its bound vector (reference lines: permute each character
207    /// by its offset, bind left to right).
208    ngrams: fxhash::FxHashMap<NgramKey, Span>,
209    ngram_arena: Vec<u32>,
210    chars: Vec<char>,
211    /// The multiset of (already permuted) indices of every vector in the level being bundled.
212    flat: Vec<u32>,
213    acc: Vec<u32>,
214    acc_next: Vec<u32>,
215    rotated: Vec<u32>,
216    counts: Vec<u32>,
217    selected: Vec<(u32, u32)>,
218}
219
220impl EncodeState {
221    /// Points the memo tables at `dim`, dropping vectors of another dimension.
222    fn prepare(&mut self, dim: usize) {
223        if self.dim != dim {
224            self.dim = dim;
225            self.terms.clear();
226            self.term_arena.clear();
227            self.ngrams.clear();
228            self.ngram_arena.clear();
229        }
230    }
231
232    /// The bound vector of the character n-gram `window` (length `n`), memoized.
233    fn ngram_span(&mut self, n: usize, window: &[char]) -> Span {
234        let mut key = NgramKey {
235            n: n as u8,
236            chars: ['\0'; MAX_CHAR_NGRAM],
237        };
238        key.chars[..n].copy_from_slice(window);
239        if let Some(&span) = self.ngrams.get(&key) {
240            return span;
241        }
242        let dim = self.dim;
243        let first = term_span(
244            &mut self.terms,
245            &mut self.term_arena,
246            dim,
247            seeded(LEVEL_CHAR, n as u64, window[0] as u64),
248        );
249        // Copied before the next lookup, which may clear the term arena.
250        self.acc.clear();
251        self.acc.extend_from_slice(&self.term_arena[first.range()]);
252        for (i, &c) in window.iter().enumerate().skip(1) {
253            let span = term_span(
254                &mut self.terms,
255                &mut self.term_arena,
256                dim,
257                seeded(LEVEL_CHAR, n as u64, c as u64),
258            );
259            rotate_sorted(
260                &self.term_arena[span.range()],
261                (i % dim) as u32,
262                dim as u32,
263                &mut self.rotated,
264            );
265            symmetric_difference(&self.acc, &self.rotated, &mut self.acc_next);
266            std::mem::swap(&mut self.acc, &mut self.acc_next);
267        }
268        if self.ngram_arena.len() + self.acc.len() > NGRAM_ARENA_BUDGET {
269            self.ngrams.clear();
270            self.ngram_arena.clear();
271        }
272        let span = Span {
273            start: self.ngram_arena.len(),
274            len: self.acc.len(),
275        };
276        self.ngram_arena.extend_from_slice(&self.acc);
277        self.ngrams.insert(key, span);
278        span
279    }
280
281    /// The bundle (`EntangledHVec::bundle`, or `bundle_bloom` for union encoders) of `count`
282    /// vectors whose indices are concatenated in `self.flat`, in any order.
283    fn bundle_flat(&mut self, count: usize, encoder: TextEncoder) -> EntangledHVec {
284        let dim = self.dim;
285        if self.flat.is_empty() {
286            return EntangledHVec::from_indices(Vec::new(), dim);
287        }
288        let union = encoder.bundles_by_union();
289        let threshold = if union { 1 } else { (count as u32).div_ceil(2) };
290        self.selected.clear();
291        if dim <= self.flat.len().saturating_mul(COUNTING_RATIO) {
292            if self.counts.len() != dim {
293                self.counts.clear();
294                self.counts.resize(dim, 0);
295            }
296            debug_assert!(self.counts.iter().all(|&c| c == 0));
297            for &idx in &self.flat {
298                self.counts[idx as usize] += 1;
299            }
300            for (idx, slot) in self.counts.iter_mut().enumerate() {
301                let n = std::mem::take(slot);
302                if n >= threshold {
303                    self.selected.push((idx as u32, n));
304                }
305            }
306        } else {
307            self.flat.sort_unstable();
308            let mut current = self.flat[0];
309            let mut n: u32 = 1;
310            for &idx in &self.flat[1..] {
311                if idx == current {
312                    n += 1;
313                } else {
314                    if n >= threshold {
315                        self.selected.push((current, n));
316                    }
317                    current = idx;
318                    n = 1;
319                }
320            }
321            if n >= threshold {
322                self.selected.push((current, n));
323            }
324        }
325        if union {
326            let indices: Vec<u32> = self.selected.iter().map(|&(idx, _)| idx).collect();
327            return EntangledHVec::from_indices(indices, dim);
328        }
329        let target_count = (dim / DEFAULT_RHO_DENOM).max(1);
330        // Same call on the same slice as the reference: the comparator does not break ties,
331        // so a different selection algorithm or input order could retain different indices.
332        if self.selected.len() > target_count {
333            self.selected
334                .select_nth_unstable_by(target_count - 1, |a, b| b.1.cmp(&a.1));
335            self.selected.truncate(target_count);
336        }
337        let mut indices: Vec<u32> = self.selected.iter().map(|&(idx, _)| idx).collect();
338        indices.sort_unstable();
339        EntangledHVec::from_indices(indices, dim)
340    }
341}
342
343/// Sorted indices of `EntangledHVec::new_deterministic(dim, seed)`, memoized in `arena`.
344/// The returned span is valid until the next call, which may clear the arena.
345fn term_span(
346    terms: &mut fxhash::FxHashMap<u64, Span>,
347    arena: &mut Vec<u32>,
348    dim: usize,
349    seed: u64,
350) -> Span {
351    if let Some(&span) = terms.get(&seed) {
352        return span;
353    }
354    let vector = EntangledHVec::new_deterministic(dim, seed);
355    let indices = vector.indices();
356    if arena.len() + indices.len() > TERM_ARENA_BUDGET {
357        terms.clear();
358        arena.clear();
359    }
360    let span = Span {
361        start: arena.len(),
362        len: indices.len(),
363    };
364    arena.extend_from_slice(indices);
365    terms.insert(seed, span);
366    span
367}
368
369/// `permute(shift)` of the sorted index set `base`: `(idx + shift) % dim` for each index, in
370/// ascending order. Indices at or above `dim - shift` wrap to the front, so the result is a
371/// rotation of the input and needs no sort. `shift` must be below `dim`.
372fn rotate_sorted(base: &[u32], shift: u32, dim: u32, out: &mut Vec<u32>) {
373    out.clear();
374    if shift == 0 {
375        out.extend_from_slice(base);
376        return;
377    }
378    let wrap = dim - shift;
379    let split = base.partition_point(|&idx| idx < wrap);
380    out.extend(base[split..].iter().map(|&idx| idx - wrap));
381    out.extend(base[..split].iter().map(|&idx| idx + shift));
382}
383
384/// Sorted symmetric difference of two sorted index sets (`EntangledHVec::bind`).
385fn symmetric_difference(a: &[u32], b: &[u32], out: &mut Vec<u32>) {
386    out.clear();
387    let (mut i, mut j) = (0, 0);
388    while i < a.len() && j < b.len() {
389        match a[i].cmp(&b[j]) {
390            std::cmp::Ordering::Less => {
391                out.push(a[i]);
392                i += 1;
393            }
394            std::cmp::Ordering::Greater => {
395                out.push(b[j]);
396                j += 1;
397            }
398            std::cmp::Ordering::Equal => {
399                i += 1;
400                j += 1;
401            }
402        }
403    }
404    out.extend_from_slice(&a[i..]);
405    out.extend_from_slice(&b[j..]);
406}
407
408/// [`encode_reference`] computed through the thread's memo tables; see the module head for
409/// why every step yields the same indices.
410fn encode_cached(
411    text: &str,
412    dim: usize,
413    encoder: TextEncoder,
414    state: &mut EncodeState,
415) -> EntangledHVec {
416    let text = text.trim();
417    if text.is_empty() {
418        return EntangledHVec::from_indices(Vec::new(), dim);
419    }
420    state.prepare(dim);
421    state.chars.clear();
422    state.chars.extend(text.chars());
423    let words: Vec<&str> = text.split_whitespace().collect();
424    let mut level_bundles: Vec<EntangledHVec> = Vec::with_capacity(CHAR_NGRAM_SIZES.len() + 2);
425
426    // --- Character n-grams at multiple scales ---
427    for &n in &CHAR_NGRAM_SIZES {
428        let windows = match state.chars.len().checked_sub(n) {
429            Some(rest) => rest + 1,
430            None => continue,
431        };
432        state.flat.clear();
433        for start in 0..windows {
434            let mut window = ['\0'; MAX_CHAR_NGRAM];
435            window[..n].copy_from_slice(&state.chars[start..start + n]);
436            let span = state.ngram_span(n, &window[..n]);
437            state
438                .flat
439                .extend_from_slice(&state.ngram_arena[span.range()]);
440        }
441        level_bundles.push(state.bundle_flat(windows, encoder));
442    }
443
444    let d = dim as u32;
445
446    // --- Word-level encoding with positional binding ---
447    if !words.is_empty() {
448        state.flat.clear();
449        for (pos, word) in words.iter().enumerate() {
450            let span = term_span(
451                &mut state.terms,
452                &mut state.term_arena,
453                dim,
454                hash_str_seed(word, LEVEL_WORD),
455            );
456            let shift = (pos % dim) as u32;
457            state.flat.extend(
458                state.term_arena[span.range()]
459                    .iter()
460                    .map(|&idx| (idx + shift) % d),
461            );
462        }
463        level_bundles.push(state.bundle_flat(words.len(), encoder));
464    }
465
466    // --- Word bigrams for phrase structure ---
467    if words.len() >= 2 {
468        state.flat.clear();
469        for (pos, pair) in words.windows(2).enumerate() {
470            let left = term_span(
471                &mut state.terms,
472                &mut state.term_arena,
473                dim,
474                hash_str_seed(pair[0], LEVEL_PHRASE),
475            );
476            // Copied before the next lookup, which may clear the term arena.
477            state.acc_next.clear();
478            state
479                .acc_next
480                .extend_from_slice(&state.term_arena[left.range()]);
481            let right = term_span(
482                &mut state.terms,
483                &mut state.term_arena,
484                dim,
485                hash_str_seed(pair[1], LEVEL_PHRASE),
486            );
487            rotate_sorted(
488                &state.term_arena[right.range()],
489                (1 % dim) as u32,
490                d,
491                &mut state.rotated,
492            );
493            symmetric_difference(&state.acc_next, &state.rotated, &mut state.acc);
494            let shift = (pos % dim) as u32;
495            state
496                .flat
497                .extend(state.acc.iter().map(|&idx| (idx + shift) % d));
498        }
499        level_bundles.push(state.bundle_flat(words.len() - 1, encoder));
500    }
501
502    if level_bundles.is_empty() {
503        return EntangledHVec::new_deterministic(dim, seeded(LEVEL_CHAR, 1, state.chars[0] as u64));
504    }
505    combine_levels(&level_bundles, dim)
506}
507
508/// The reference formulation; see [`TextEncoder::encode_reference`].
509fn encode_reference(text: &str, dim: usize, encoder: TextEncoder) -> EntangledHVec {
510    let text = text.trim();
511    if text.is_empty() {
512        return EntangledHVec::from_indices(vec![], dim);
513    }
514
515    let chars: Vec<char> = text.chars().collect();
516    let words: Vec<&str> = text.split_whitespace().collect();
517
518    // Bundle within each level first, then equal-weight bundle across levels.
519    // This prevents any single level from dominating majority-vote thresholds.
520    let mut level_bundles: Vec<EntangledHVec> = Vec::new();
521
522    // --- Character n-grams at multiple scales ---
523    for &n in &CHAR_NGRAM_SIZES {
524        if chars.len() < n {
525            continue;
526        }
527        let ngrams: Vec<EntangledHVec> = chars
528            .windows(n)
529            .map(|window| {
530                let mut chunk = EntangledHVec::new_deterministic(
531                    dim,
532                    seeded(LEVEL_CHAR, n as u64, window[0] as u64),
533                )
534                .permute(0);
535                for (i, &c) in window.iter().enumerate().skip(1) {
536                    let next = EntangledHVec::new_deterministic(
537                        dim,
538                        seeded(LEVEL_CHAR, n as u64, c as u64),
539                    )
540                    .permute(i);
541                    chunk = chunk.bind(&next);
542                }
543                chunk
544            })
545            .collect();
546        level_bundles.push(encoder.bundle(&ngrams));
547    }
548
549    // --- Word-level encoding with positional binding ---
550    if !words.is_empty() {
551        let word_vecs: Vec<EntangledHVec> = words
552            .iter()
553            .enumerate()
554            .map(|(pos, word)| {
555                let word_hash = hash_str_seed(word, LEVEL_WORD);
556                EntangledHVec::new_deterministic(dim, word_hash).permute(pos)
557            })
558            .collect();
559        level_bundles.push(encoder.bundle(&word_vecs));
560    }
561
562    // --- Word bigrams for phrase structure ---
563    if words.len() >= 2 {
564        let phrase_vecs: Vec<EntangledHVec> = words
565            .windows(2)
566            .enumerate()
567            .map(|(pos, pair)| {
568                let h0 = hash_str_seed(pair[0], LEVEL_PHRASE);
569                let h1 = hash_str_seed(pair[1], LEVEL_PHRASE);
570                let v0 = EntangledHVec::new_deterministic(dim, h0).permute(0);
571                let v1 = EntangledHVec::new_deterministic(dim, h1).permute(1);
572                v0.bind(&v1).permute(pos)
573            })
574            .collect();
575        level_bundles.push(encoder.bundle(&phrase_vecs));
576    }
577
578    if level_bundles.is_empty() {
579        return EntangledHVec::new_deterministic(dim, seeded(LEVEL_CHAR, 1, chars[0] as u64));
580    }
581    combine_levels(&level_bundles, dim)
582}
583
584/// Combine levels by frequency-weighted selection. Each index gets a count of how many level
585/// bundles contain it; indices with cross-level support are prioritized. Output is
586/// fixed-density (dim/256 active indices) to ensure consistent Jaccard comparisons across
587/// different-length texts.
588fn combine_levels(level_bundles: &[EntangledHVec], dim: usize) -> EntangledHVec {
589    let active_count = (dim / DEFAULT_RHO_DENOM).max(1);
590    let mut freq: fxhash::FxHashMap<u32, u32> =
591        fxhash::FxHashMap::with_capacity_and_hasher(active_count * 4, Default::default());
592    for bundle in level_bundles {
593        for &idx in bundle.indices() {
594            *freq.entry(idx).or_insert(0) += 1;
595        }
596    }
597
598    let mut scored: Vec<(u32, u32)> = freq.into_iter().collect();
599    if scored.len() > active_count {
600        scored.select_nth_unstable_by(active_count - 1, |a, b| {
601            b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0))
602        });
603        scored.truncate(active_count);
604    }
605
606    let mut indices: Vec<u32> = scored.into_iter().map(|(idx, _)| idx).collect();
607    indices.sort_unstable();
608    EntangledHVec::from_indices(indices, dim)
609}
610
611fn seeded(level: u64, scale: u64, item: u64) -> u64 {
612    hash_u64(hash_u64(level, scale), item)
613}
614
615pub(crate) fn hash_str_seed(s: &str, level: u64) -> u64 {
616    let mut h = level;
617    for &byte in s.as_bytes() {
618        h = hash_u64(h, byte as u64);
619    }
620    h
621}
622
623#[cfg(test)]
624mod tests {
625    use super::*;
626
627    #[test]
628    fn test_determinism() {
629        let dim = 16384;
630        let v1 = encode_text_internal("hello world", dim);
631        let v2 = encode_text_internal("hello world", dim);
632        assert!(
633            (v1.similarity(&v2) - 1.0).abs() < f64::EPSILON,
634            "Same input must produce identical vectors"
635        );
636    }
637
638    #[test]
639    fn test_empty_input() {
640        let v = encode_text_internal("", 16384);
641        assert!(v.indices().is_empty());
642    }
643
644    #[test]
645    fn test_single_char() {
646        let v = encode_text_internal("x", 16384);
647        assert!(
648            !v.indices().is_empty(),
649            "Single char should produce a vector"
650        );
651    }
652
653    #[test]
654    fn test_morphological_similarity() {
655        let dim = 16384;
656        let cat = encode_text_internal("cat", dim);
657        let cats = encode_text_internal("cats", dim);
658        let dog = encode_text_internal("dog", dim);
659        let sim_cat_cats = cat.similarity(&cats);
660        let sim_cat_dog = cat.similarity(&dog);
661        assert!(
662            sim_cat_cats > sim_cat_dog,
663            "cat/cats ({:.4}) should be more similar than cat/dog ({:.4})",
664            sim_cat_cats,
665            sim_cat_dog
666        );
667    }
668
669    #[test]
670    fn test_word_identity_matters() {
671        let dim = 16384;
672        let v1 = encode_text_internal("the quick brown fox", dim);
673        let v2 = encode_text_internal("the quick brown fox", dim);
674        let v3 = encode_text_internal("completely different words here", dim);
675        assert!(
676            (v1.similarity(&v2) - 1.0).abs() < f64::EPSILON,
677            "Identical text must match"
678        );
679        assert!(
680            v1.similarity(&v3) < 0.3,
681            "Unrelated text should have low similarity"
682        );
683    }
684
685    #[test]
686    fn test_word_overlap_similarity() {
687        let dim = 16384;
688        let v1 = encode_text_internal("the cat sat on the mat", dim);
689        let v2 = encode_text_internal("the dog sat on the mat", dim);
690        let v3 = encode_text_internal("quantum physics is fascinating", dim);
691        let sim_close = v1.similarity(&v2);
692        let sim_far = v1.similarity(&v3);
693        assert!(
694            sim_close > sim_far,
695            "Sentences sharing most words ({:.4}) should be more similar than unrelated ({:.4})",
696            sim_close,
697            sim_far
698        );
699    }
700
701    #[test]
702    fn test_multi_scale_captures_short_text() {
703        let dim = 16384;
704        // Two-character text should still produce a meaningful vector
705        let v = encode_text_internal("hi", dim);
706        assert!(!v.indices().is_empty());
707        // Should be similar to "his" (shared bigram "hi")
708        let v2 = encode_text_internal("his", dim);
709        let v3 = encode_text_internal("xyz", dim);
710        assert!(
711            v.similarity(&v2) > v.similarity(&v3),
712            "hi/his should be more similar than hi/xyz"
713        );
714    }
715
716    #[test]
717    fn rotation_matches_permute() {
718        for dim in [1usize, 2, 255, 256, 1024] {
719            for seed in 0..32u64 {
720                let base = EntangledHVec::new_deterministic(dim, seed);
721                for shift in 0..dim.min(7) {
722                    let mut out = Vec::new();
723                    rotate_sorted(base.indices(), shift as u32, dim as u32, &mut out);
724                    assert_eq!(
725                        out,
726                        base.permute(shift).indices(),
727                        "dim {dim} shift {shift}"
728                    );
729                }
730            }
731        }
732    }
733
734    #[test]
735    fn memoized_path_matches_reference_at_density_boundaries() {
736        let texts = [
737            "x",
738            "hi",
739            "aa",
740            "aaaa aaaa aaaa",
741            "the cat sat on the mat",
742            "Café records explain backups. Restore deleted documents from verified snapshots.",
743            "ünïcödé text with punctuation!!! and NUMBERS 12345, repeated repeated repeated words",
744            "a b c d e f g h i j k l m n o p q r s t u v w x y z a b c d e f g h i j k l m n o p",
745        ];
746        for encoder in [
747            TextEncoder::MultiscaleWordsV1,
748            TextEncoder::MultiscaleCappedUnionV1,
749        ] {
750            for dim in [1usize, 2, 3, 255, 256, 257, 1024, 4096, 16384] {
751                for text in texts {
752                    let reference = encoder.encode_reference(text, dim);
753                    let cached = encoder.encode(text, dim);
754                    assert_eq!(cached.dim, reference.dim);
755                    assert_eq!(
756                        cached.indices(),
757                        reference.indices(),
758                        "{} dim {dim} text {text:?}",
759                        encoder.name()
760                    );
761                    // A second call answers from the memo tables.
762                    assert_eq!(encoder.encode(text, dim).indices(), reference.indices());
763                }
764            }
765        }
766    }
767}
holographic_memory/core/encoding.rs

holographic_memory/core/
encoding.rs
