Skip to main content

rustai_core/
chunk.rs

1//! Group units into pieces an embedding model will accept.
2//!
3//! [`Unit`](crate::parse::Unit) is a block: one paragraph, one list item, one
4//! heading. That is the right grain for ranking, where a single sentence can
5//! be the reason a source was worth reading, and the wrong grain for a vector
6//! store. Measured on MDN's `Promise` reference, the median unit is 37 tokens
7//! and 36% of them are under 30 -- embed those and you get 125 vectors that
8//! each know almost nothing.
9//!
10//! Chunking walks the units in order and accumulates them until the next one
11//! would overrun `target_tokens`, then starts again. A heading begins a new
12//! chunk rather than being swallowed by the end of the previous one, so a
13//! chunk opens with the thing that says what it is about. `overlap_tokens`
14//! repeats whole units from the tail of one chunk at the head of the next,
15//! which is what keeps an answer that straddles a boundary retrievable from
16//! either side.
17
18use crate::parse::{Article, Unit, UnitKind};
19
20/// A run of units, sized for embedding.
21#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
22pub struct Chunk {
23    /// Stable within one article: `{position of first unit}`.
24    pub index: usize,
25    /// Source URL, carried so a retrieved chunk can cite itself.
26    pub url: Option<String>,
27    /// Document title.
28    pub title: Option<String>,
29    /// Enclosing headings for the first unit, outermost first.
30    pub heading_path: Vec<String>,
31    /// Rendered Markdown for the whole run.
32    pub markdown: String,
33    /// Plain text, which is what you embed.
34    pub text: String,
35    /// Estimated LLM tokens for [`Chunk::text`].
36    pub tokens: usize,
37    /// Positions of the units this covers, for tracing back.
38    pub units: Vec<usize>,
39}
40
41/// How to size chunks.
42#[derive(Debug, Clone, Copy)]
43pub struct ChunkConfig {
44    /// Aim for this many tokens. A single unit longer than this is emitted
45    /// whole rather than split -- cutting a paragraph mid-sentence costs more
46    /// than an oversized chunk.
47    pub target_tokens: usize,
48    /// Repeat units from the previous chunk's tail, up to this many tokens.
49    pub overlap_tokens: usize,
50    /// Drop chunks below this. A stray "Read more" is noise in a vector store.
51    pub min_tokens: usize,
52}
53
54impl Default for ChunkConfig {
55    fn default() -> Self {
56        // 512 is what the common sentence-transformer families accept without
57        // truncating; 64 of overlap is an eighth, enough to carry a sentence
58        // across a boundary without inflating the store by much.
59        ChunkConfig { target_tokens: 512, overlap_tokens: 64, min_tokens: 24 }
60    }
61}
62
63/// Group one article's units into embedding-sized chunks.
64pub fn chunk(article: &Article, cfg: &ChunkConfig) -> Vec<Chunk> {
65    let mut out: Vec<Chunk> = Vec::new();
66    let mut run: Vec<&Unit> = Vec::new();
67    let mut tokens = 0usize;
68
69    for unit in &article.units {
70        let starts_section = unit.kind == UnitKind::Heading && !run.is_empty();
71        let would_overrun = tokens + unit.tokens > cfg.target_tokens && !run.is_empty();
72        if starts_section || would_overrun {
73            emit(&mut out, &run, article, cfg);
74            run = tail(&run, cfg.overlap_tokens);
75            tokens = run.iter().map(|u| u.tokens).sum();
76        }
77        tokens += unit.tokens;
78        run.push(unit);
79    }
80    emit(&mut out, &run, article, cfg);
81
82    // `min_tokens` is there to drop a trailing "Read more", not to discard a
83    // page for being short. An article that produced nothing still gets one
84    // chunk: a small source is still a source, and losing it silently is
85    // worse than storing a thin vector.
86    if out.is_empty() && !article.units.is_empty() {
87        let all: Vec<&Unit> = article.units.iter().collect();
88        emit(&mut out, &all, article, &ChunkConfig { min_tokens: 0, ..*cfg });
89    }
90    out
91}
92
93/// The trailing units worth repeating in the next chunk.
94///
95/// Whole units only: half a sentence at the head of a chunk helps nobody.
96fn tail<'a>(run: &[&'a Unit], budget: usize) -> Vec<&'a Unit> {
97    if budget == 0 {
98        return Vec::new();
99    }
100    let mut kept = Vec::new();
101    let mut total = 0;
102    for unit in run.iter().rev() {
103        if total + unit.tokens > budget {
104            break;
105        }
106        total += unit.tokens;
107        kept.push(*unit);
108    }
109    kept.reverse();
110    kept
111}
112
113fn emit(out: &mut Vec<Chunk>, run: &[&Unit], article: &Article, cfg: &ChunkConfig) {
114    if run.is_empty() {
115        return;
116    }
117    let tokens: usize = run.iter().map(|u| u.tokens).sum();
118    if tokens < cfg.min_tokens {
119        return;
120    }
121    let first = run[0];
122    out.push(Chunk {
123        index: first.position,
124        url: article.url.clone(),
125        title: article.title().map(str::to_string),
126        heading_path: first.heading_path.clone(),
127        markdown: run.iter().map(|u| u.markdown.as_str()).collect::<Vec<_>>().join("\n\n"),
128        text: run.iter().map(|u| u.text.as_str()).collect::<Vec<_>>().join("\n"),
129        tokens,
130        units: run.iter().map(|u| u.position).collect(),
131    });
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137    use crate::parse::extract;
138
139    fn article(body: &str) -> Article {
140        extract(&format!("<html><body><article>{body}</article></body></html>"), None).unwrap()
141    }
142
143    fn long(word: &str, times: usize) -> String {
144        format!("<p>{}</p>", format!("{word} ").repeat(times))
145    }
146
147    #[test]
148    fn small_units_are_grouped_up() {
149        let body: String =
150            (0..40).map(|i| format!("<p>Sentence number {i} of the body text.</p>")).collect();
151        let doc = article(&body);
152        let chunks = chunk(&doc, &ChunkConfig::default());
153        assert!(chunks.len() < doc.units.len(), "grouping should reduce the count");
154        assert!(chunks.iter().all(|c| c.tokens >= 24));
155    }
156
157    #[test]
158    fn a_heading_opens_a_chunk() {
159        let doc =
160            article(&format!("{}<h2>Second section</h2>{}", long("alpha", 30), long("omega", 30)));
161        let chunks = chunk(&doc, &ChunkConfig { overlap_tokens: 0, ..Default::default() });
162        let opener = chunks.iter().find(|c| c.text.contains("Second section"));
163        assert!(opener.is_some_and(|c| c.text.starts_with("Second section")));
164    }
165
166    #[test]
167    fn an_oversized_unit_is_emitted_whole() {
168        let doc = article(&long("verylongword", 400));
169        let chunks = chunk(&doc, &ChunkConfig { target_tokens: 50, ..Default::default() });
170        assert_eq!(chunks.len(), 1, "a paragraph is never cut mid-sentence");
171        assert!(chunks[0].tokens > 50);
172    }
173
174    #[test]
175    fn overlap_repeats_whole_units_and_zero_means_none() {
176        let body: String = (0..30)
177            .map(|i| format!("<p>Paragraph {i} carrying enough words to count.</p>"))
178            .collect();
179        let doc = article(&body);
180        let with = chunk(
181            &doc,
182            &ChunkConfig { target_tokens: 60, overlap_tokens: 30, ..Default::default() },
183        );
184        let without = chunk(
185            &doc,
186            &ChunkConfig { target_tokens: 60, overlap_tokens: 0, ..Default::default() },
187        );
188        let sum = |cs: &[Chunk]| cs.iter().map(|c| c.tokens).sum::<usize>();
189        assert!(sum(&with) > sum(&without), "overlap repeats text");
190        let seen: Vec<usize> = without.iter().flat_map(|c| c.units.clone()).collect();
191        let mut sorted = seen.clone();
192        sorted.dedup();
193        assert_eq!(seen, sorted, "without overlap no unit appears twice");
194    }
195
196    #[test]
197    fn a_short_article_still_yields_one_chunk() {
198        // Dropping it would lose the source, which is worse than a thin vector.
199        let doc = article("<p>Short but real, and the only thing on the page.</p>");
200        let chunks = chunk(&doc, &ChunkConfig { min_tokens: 500, ..Default::default() });
201        assert_eq!(chunks.len(), 1);
202    }
203
204    #[test]
205    fn chunks_carry_where_they_came_from() {
206        let doc = extract(
207            "<html><head><title>T</title></head><body><article><h2>H</h2>\
208             <p>Body text long enough to survive the block gate here, and then \
209             some more of it so the chunk clears the minimum.</p></article></body></html>",
210            Some("https://e.com/p"),
211        )
212        .unwrap();
213        let chunks = chunk(&doc, &ChunkConfig::default());
214        assert_eq!(chunks[0].url.as_deref(), Some("https://e.com/p"));
215        assert!(chunks[0].title.is_some());
216        assert!(!chunks[0].units.is_empty());
217    }
218}