1use super::algorithm::{bm25_score, compute_idf, BM25Params};
11use super::tokenizer::Tokenizer;
12use lc_vector_stores::document_store::{ChunkDocument, ChunkedDocumentStoreTrait};
13use lc_vector_stores::{Document, VectorStoreError};
14use serde::{Deserialize, Serialize};
15use std::collections::HashMap;
16use std::path::Path;
17use std::sync::Arc;
18
19#[derive(Debug, Clone, Serialize, Deserialize)]
27pub struct AutoMergingConfig {
28 pub merge_threshold: f32,
30 pub leaf_chunk_size: usize,
32 pub parent_chunk_size: usize,
34 pub leaves_per_parent: usize,
36}
37
38impl Default for AutoMergingConfig {
39 fn default() -> Self {
40 Self {
41 merge_threshold: 0.5,
42 leaf_chunk_size: 400,
43 parent_chunk_size: 2000,
44 leaves_per_parent: 5,
45 }
46 }
47}
48
49impl AutoMergingConfig {
50 pub fn new() -> Self {
52 Self::default()
53 }
54
55 pub fn with_threshold(mut self, threshold: f32) -> Self {
57 self.merge_threshold = threshold;
58 self
59 }
60
61 pub fn with_leaf_size(mut self, size: usize) -> Self {
63 self.leaf_chunk_size = size;
64 self
65 }
66
67 pub fn with_parent_size(mut self, size: usize) -> Self {
69 self.parent_chunk_size = size;
70 self
71 }
72}
73
74#[derive(Debug, Clone)]
76pub struct ChunkedSearchResult {
77 pub merged_parent: Option<Document>,
79 pub leaf_chunks: Vec<ChunkDocument>,
81 pub score: f32,
83 pub matched_terms: Vec<String>,
85 pub parent_id: String,
87}
88
89impl ChunkedSearchResult {
90 pub fn content(&self) -> String {
92 if let Some(parent) = &self.merged_parent {
93 parent.content.clone()
94 } else {
95 self.leaf_chunks
96 .iter()
97 .map(|c| c.content.as_str())
98 .collect::<Vec<_>>()
99 .join("\n")
100 }
101 }
102
103 pub fn is_merged(&self) -> bool {
105 self.merged_parent.is_some()
106 }
107}
108
109#[derive(Debug, Clone, Serialize, Deserialize)]
111pub struct BM25ParamsData {
112 pub k1: f64,
113 pub b: f64,
114}
115
116impl From<BM25Params> for BM25ParamsData {
117 fn from(params: BM25Params) -> Self {
118 Self {
119 k1: params.k1,
120 b: params.b,
121 }
122 }
123}
124
125impl From<BM25ParamsData> for BM25Params {
126 fn from(data: BM25ParamsData) -> Self {
127 BM25Params::with_values(data.k1, data.b)
128 }
129}
130
131#[derive(Debug, Clone, Serialize, Deserialize)]
133pub struct ChunkedIndexData {
134 pub chunk_id_list: Vec<String>,
136 pub chunk_term_freqs: Vec<HashMap<String, usize>>,
138 pub term_index: HashMap<String, Vec<(usize, usize)>>,
140 pub parent_to_leaves: HashMap<String, Vec<usize>>,
142 pub doc_lengths: Vec<usize>,
144 pub avgdl: f64,
146 pub n_docs: usize,
148 pub params: BM25ParamsData,
150 pub config: AutoMergingConfig,
152}
153
154pub struct ChunkedBM25Index<S: ChunkedDocumentStoreTrait = lc_vector_stores::ChunkedDocumentStore> {
160 store: Arc<S>,
161 chunk_id_list: Vec<String>,
162 chunk_term_freqs: Vec<HashMap<String, usize>>,
163 term_index: HashMap<String, Vec<(usize, usize)>>,
164 parent_to_leaves: HashMap<String, Vec<usize>>,
165 doc_lengths: Vec<usize>,
166 avgdl: f64,
167 n_docs: usize,
168 idf_cache: HashMap<String, f64>,
169 params: BM25Params,
170 tokenizer: Tokenizer,
171 config: AutoMergingConfig,
172}
173
174impl<S: ChunkedDocumentStoreTrait> ChunkedBM25Index<S> {
175 pub fn new(store: Arc<S>) -> Self {
177 Self::with_config(store, AutoMergingConfig::default())
178 }
179
180 pub fn with_config(store: Arc<S>, config: AutoMergingConfig) -> Self {
182 Self {
183 store,
184 chunk_id_list: Vec::new(),
185 chunk_term_freqs: Vec::new(),
186 term_index: HashMap::new(),
187 parent_to_leaves: HashMap::new(),
188 doc_lengths: Vec::new(),
189 avgdl: 0.0,
190 n_docs: 0,
191 idf_cache: HashMap::new(),
192 params: BM25Params::default(),
193 tokenizer: Tokenizer::new(),
194 config,
195 }
196 }
197
198 pub fn with_params(store: Arc<S>, params: BM25Params) -> Self {
200 let mut index = Self::new(store);
201 index.params = params;
202 index
203 }
204
205 pub fn add_chunk_index(
207 &mut self,
208 chunk_id: impl Into<String>,
209 parent_id: impl Into<String>,
210 content: &str,
211 ) {
212 let chunk_idx = self.n_docs;
213 let chunk_id = chunk_id.into();
214 let parent_id = parent_id.into();
215
216 let terms = self.tokenizer.tokenize(content);
217 let term_freq = self.compute_term_freq(&terms);
218
219 for (term, freq) in &term_freq {
221 self.term_index
222 .entry(term.clone())
223 .or_default()
224 .push((chunk_idx, *freq));
225 }
226
227 self.parent_to_leaves
229 .entry(parent_id)
230 .or_default()
231 .push(chunk_idx);
232
233 self.chunk_id_list.push(chunk_id);
235 self.chunk_term_freqs.push(term_freq.clone());
236
237 let doc_length: usize = term_freq.values().sum();
238 self.doc_lengths.push(doc_length);
239 self.n_docs += 1;
240 self.update_avgdl();
241 self.idf_cache.clear();
242 }
243
244 pub fn add_chunk_indexes(&mut self, chunks: Vec<(String, String, String)>) {
246 for (chunk_id, parent_id, content) in chunks {
247 self.add_chunk_index(chunk_id, parent_id, &content);
248 }
249 }
250
251 fn compute_term_freq(&self, terms: &[String]) -> HashMap<String, usize> {
252 let mut freq = HashMap::new();
253 for term in terms {
254 *freq.entry(term.clone()).or_insert(0) += 1;
255 }
256 freq
257 }
258
259 fn update_avgdl(&mut self) {
260 if self.n_docs == 0 {
261 self.avgdl = 0.0;
262 } else {
263 let total: usize = self.doc_lengths.iter().sum();
264 self.avgdl = total as f64 / self.n_docs as f64;
265 }
266 }
267
268 fn compute_idf_for_term(&mut self, term: &str) -> f64 {
269 if let Some(idf) = self.idf_cache.get(term) {
270 return *idf;
271 }
272
273 let n = self.term_index.get(term).map(|v| v.len()).unwrap_or(0);
274 let idf = compute_idf(n, self.n_docs);
275 self.idf_cache.insert(term.to_string(), idf);
276 idf
277 }
278
279 pub fn get_chunk_id(&self, chunk_idx: usize) -> Option<&String> {
281 self.chunk_id_list.get(chunk_idx)
282 }
283
284 pub fn get_chunk_ids_for_parent(&self, parent_id: &str) -> Vec<&String> {
286 self.parent_to_leaves
287 .get(parent_id)
288 .map(|indices| {
289 indices
290 .iter()
291 .filter_map(|idx| self.chunk_id_list.get(*idx))
292 .collect()
293 })
294 .unwrap_or_default()
295 }
296
297 pub fn config(&self) -> &AutoMergingConfig {
299 &self.config
300 }
301
302 pub fn n_docs(&self) -> usize {
304 self.n_docs
305 }
306
307 pub fn store(&self) -> &Arc<S> {
309 &self.store
310 }
311
312 pub fn clear(&mut self) {
314 self.chunk_id_list.clear();
315 self.chunk_term_freqs.clear();
316 self.term_index.clear();
317 self.parent_to_leaves.clear();
318 self.doc_lengths.clear();
319 self.avgdl = 0.0;
320 self.n_docs = 0;
321 self.idf_cache.clear();
322 }
323}
324
325impl Default for ChunkedBM25Index<lc_vector_stores::ChunkedDocumentStore> {
326 fn default() -> Self {
327 Self::new(Arc::new(lc_vector_stores::ChunkedDocumentStore::new()))
328 }
329}
330
331pub struct ChunkedBM25Retriever<
337 S: ChunkedDocumentStoreTrait = lc_vector_stores::ChunkedDocumentStore,
338> {
339 index: ChunkedBM25Index<S>,
340}
341
342impl<S: ChunkedDocumentStoreTrait> ChunkedBM25Retriever<S> {
343 pub fn new(store: Arc<S>) -> Self {
345 Self {
346 index: ChunkedBM25Index::new(store),
347 }
348 }
349
350 pub fn with_config(store: Arc<S>, config: AutoMergingConfig) -> Self {
352 Self {
353 index: ChunkedBM25Index::with_config(store, config),
354 }
355 }
356
357 pub fn with_params(store: Arc<S>, k1: f64, b: f64) -> Self {
359 Self {
360 index: ChunkedBM25Index::with_params(store, BM25Params::with_values(k1, b)),
361 }
362 }
363
364 pub fn store(&self) -> &Arc<S> {
366 self.index.store()
367 }
368
369 pub fn add_chunk_index(
371 &mut self,
372 chunk_id: impl Into<String>,
373 parent_id: impl Into<String>,
374 content: &str,
375 ) {
376 self.index.add_chunk_index(chunk_id, parent_id, content);
377 }
378
379 pub fn add_chunk_indexes(&mut self, chunks: Vec<(String, String, String)>) {
381 self.index.add_chunk_indexes(chunks);
382 }
383
384 pub fn add_document(&mut self, document: Document) -> Result<(), VectorStoreError> {
386 let parent_id = document
387 .id
388 .clone()
389 .unwrap_or_else(|| uuid::Uuid::new_v4().to_string());
390
391 self.index.store.add_parent_document_blocking(
394 document.clone().with_id(parent_id.clone()),
395 self.index.config.leaf_chunk_size,
396 )?;
397
398 let chunks = self
399 .index
400 .store
401 .blocking_get_chunks_for_parent(&parent_id)?;
402
403 for chunk in chunks {
404 self.add_chunk_index(
405 chunk.chunk_id.clone(),
406 chunk.parent_id.clone(),
407 &chunk.content,
408 );
409 }
410
411 Ok(())
412 }
413
414 pub async fn add_document_async(&mut self, document: Document) -> Result<(), VectorStoreError> {
416 let parent_id = document
417 .id
418 .clone()
419 .unwrap_or_else(|| uuid::Uuid::new_v4().to_string());
420
421 self.index
422 .store
423 .add_parent_document(
424 document.clone().with_id(parent_id.clone()),
425 self.index.config.leaf_chunk_size,
426 )
427 .await?;
428
429 let chunks = self.index.store.get_chunks_for_parent(&parent_id).await?;
430
431 for chunk in chunks {
432 self.add_chunk_index(
433 chunk.chunk_id.clone(),
434 chunk.parent_id.clone(),
435 &chunk.content,
436 );
437 }
438
439 Ok(())
440 }
441
442 pub fn add_documents(&mut self, documents: Vec<Document>) -> Result<(), VectorStoreError> {
444 for doc in documents {
445 self.add_document(doc)?;
446 }
447 Ok(())
448 }
449
450 pub async fn add_documents_async(
452 &mut self,
453 documents: Vec<Document>,
454 ) -> Result<(), VectorStoreError> {
455 for doc in documents {
456 self.add_document_async(doc).await?;
457 }
458 Ok(())
459 }
460
461 pub fn search(&mut self, query: &str, k: usize) -> Vec<ChunkedSearchResult> {
463 if self.index.n_docs == 0 {
464 return Vec::new();
465 }
466
467 let query_terms = self.index.tokenizer.tokenize(query);
468 if query_terms.is_empty() {
469 return Vec::new();
470 }
471
472 let idf_values: HashMap<String, f64> = query_terms
473 .iter()
474 .map(|t| (t.clone(), self.index.compute_idf_for_term(t)))
475 .collect();
476
477 let scored_chunks = self.score_chunks(&query_terms, &idf_values);
478
479 if scored_chunks.is_empty() {
480 return Vec::new();
481 }
482
483 let top_chunks: Vec<(usize, f64)> = scored_chunks.into_iter().take(k * 2).collect();
484
485 self.auto_merge_sync(top_chunks, k)
486 }
487
488 pub async fn search_async(&mut self, query: &str, k: usize) -> Vec<ChunkedSearchResult> {
490 if self.index.n_docs == 0 {
491 return Vec::new();
492 }
493
494 let query_terms = self.index.tokenizer.tokenize(query);
495 if query_terms.is_empty() {
496 return Vec::new();
497 }
498
499 let idf_values: HashMap<String, f64> = query_terms
500 .iter()
501 .map(|t| (t.clone(), self.index.compute_idf_for_term(t)))
502 .collect();
503
504 let scored_chunks = self.score_chunks(&query_terms, &idf_values);
505
506 if scored_chunks.is_empty() {
507 return Vec::new();
508 }
509
510 let top_chunks: Vec<(usize, f64)> = scored_chunks.into_iter().take(k * 2).collect();
511
512 self.auto_merge_async(top_chunks, k).await
513 }
514
515 fn auto_merge_sync(
516 &self,
517 scored_chunks: Vec<(usize, f64)>,
518 k: usize,
519 ) -> Vec<ChunkedSearchResult> {
520 let threshold = self.index.config.merge_threshold;
521 let leaves_per_parent = self.index.config.leaves_per_parent;
522
523 let parent_stats = self.collect_parent_stats(&scored_chunks);
524
525 let mut results: Vec<ChunkedSearchResult> = Vec::new();
526
527 for (parent_id, matched_leaves) in parent_stats {
528 let ratio = matched_leaves.len() as f32 / leaves_per_parent as f32;
529
530 let avg_score =
531 matched_leaves.iter().map(|(_, s)| s).sum::<f64>() / matched_leaves.len() as f64;
532
533 let matched_terms = matched_leaves
534 .iter()
535 .filter_map(|(idx, _)| self.index.chunk_term_freqs.get(*idx))
536 .flat_map(|tf| tf.keys().cloned())
537 .collect::<Vec<_>>();
538
539 if ratio >= threshold {
540 let parent_doc = self
541 .index
542 .store()
543 .get_parent_document_blocking(&parent_id)
544 .ok()
545 .flatten();
546
547 results.push(ChunkedSearchResult {
548 merged_parent: parent_doc,
549 leaf_chunks: Vec::new(),
550 score: avg_score as f32,
551 matched_terms,
552 parent_id,
553 });
554 } else {
555 let leaf_chunks: Vec<ChunkDocument> = matched_leaves
556 .iter()
557 .filter_map(|(idx, _)| {
558 let chunk_id = self.index.get_chunk_id(*idx)?;
559 let chunk = self
560 .index
561 .store()
562 .get_chunk_blocking(chunk_id)
563 .ok()
564 .flatten()?;
565 Some(chunk)
566 })
567 .collect();
568
569 results.push(ChunkedSearchResult {
570 merged_parent: None,
571 leaf_chunks,
572 score: avg_score as f32,
573 matched_terms,
574 parent_id,
575 });
576 }
577 }
578
579 results.sort_by(|a, b| {
580 b.score
581 .partial_cmp(&a.score)
582 .unwrap_or(std::cmp::Ordering::Equal)
583 });
584 results.into_iter().take(k).collect()
585 }
586
587 async fn auto_merge_async(
588 &self,
589 scored_chunks: Vec<(usize, f64)>,
590 k: usize,
591 ) -> Vec<ChunkedSearchResult> {
592 let threshold = self.index.config.merge_threshold;
593 let leaves_per_parent = self.index.config.leaves_per_parent;
594
595 let parent_stats = self.collect_parent_stats(&scored_chunks);
596
597 let mut results: Vec<ChunkedSearchResult> = Vec::new();
598
599 for (parent_id, matched_leaves) in parent_stats {
600 let ratio = matched_leaves.len() as f32 / leaves_per_parent as f32;
601
602 let avg_score =
603 matched_leaves.iter().map(|(_, s)| s).sum::<f64>() / matched_leaves.len() as f64;
604
605 let matched_terms = matched_leaves
606 .iter()
607 .filter_map(|(idx, _)| self.index.chunk_term_freqs.get(*idx))
608 .flat_map(|tf| tf.keys().cloned())
609 .collect::<Vec<_>>();
610
611 if ratio >= threshold {
612 let parent_doc = self
613 .index
614 .store()
615 .get_parent_document(&parent_id)
616 .await
617 .ok()
618 .flatten();
619
620 results.push(ChunkedSearchResult {
621 merged_parent: parent_doc,
622 leaf_chunks: Vec::new(),
623 score: avg_score as f32,
624 matched_terms,
625 parent_id,
626 });
627 } else {
628 let mut leaf_chunks = Vec::new();
629 for (idx, _) in matched_leaves {
630 if let Some(chunk_id) = self.index.get_chunk_id(idx) {
631 match self.index.store().get_chunk(chunk_id).await {
632 Ok(Some(chunk)) => leaf_chunks.push(chunk),
633 Ok(None) => {}
634 Err(e) => {
635 log::error!(
637 "failed to read chunk `{}` during retrieval (chunk missing from results): {}",
638 chunk_id,
639 e
640 );
641 }
642 }
643 }
644 }
645
646 results.push(ChunkedSearchResult {
647 merged_parent: None,
648 leaf_chunks,
649 score: avg_score as f32,
650 matched_terms,
651 parent_id,
652 });
653 }
654 }
655
656 results.sort_by(|a, b| {
657 b.score
658 .partial_cmp(&a.score)
659 .unwrap_or(std::cmp::Ordering::Equal)
660 });
661 results.into_iter().take(k).collect()
662 }
663
664 fn score_chunks(
665 &self,
666 query_terms: &[String],
667 idf_values: &HashMap<String, f64>,
668 ) -> Vec<(usize, f64)> {
669 let mut scored = Vec::new();
670
671 for chunk_idx in 0..self.index.n_docs {
672 if let Some(term_freqs) = self.index.chunk_term_freqs.get(chunk_idx) {
673 let doc_length = *self.index.doc_lengths.get(chunk_idx).unwrap_or(&0);
674
675 let score = bm25_score(
676 query_terms,
677 term_freqs,
678 doc_length,
679 self.index.avgdl,
680 idf_values,
681 &self.index.params,
682 );
683
684 if score > 0.0 {
685 scored.push((chunk_idx, score));
686 }
687 }
688 }
689
690 scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
691 scored
692 }
693
694 fn collect_parent_stats(
695 &self,
696 scored_chunks: &[(usize, f64)],
697 ) -> HashMap<String, Vec<(usize, f64)>> {
698 let mut stats: HashMap<String, Vec<(usize, f64)>> = HashMap::new();
699
700 for (chunk_idx, score) in scored_chunks {
701 if let Some(chunk_id) = self.index.chunk_id_list.get(*chunk_idx) {
702 let parent_id = chunk_id.split("::").next().unwrap_or_default().to_string();
703 stats
704 .entry(parent_id)
705 .or_default()
706 .push((*chunk_idx, *score));
707 }
708 }
709
710 stats
711 }
712
713 pub fn get_parent_document(&self, parent_id: &str) -> Option<Document> {
715 self.index
716 .store()
717 .get_parent_document_blocking(parent_id)
718 .ok()
719 .flatten()
720 }
721
722 pub fn len(&self) -> usize {
724 self.index.n_docs()
725 }
726
727 pub fn is_empty(&self) -> bool {
729 self.index.n_docs() == 0
730 }
731
732 pub fn clear(&mut self) {
734 self.index.clear();
735 }
736
737 pub fn config(&self) -> &AutoMergingConfig {
739 self.index.config()
740 }
741
742 pub fn save(&self, path: impl AsRef<Path>) -> Result<(), Box<dyn std::error::Error>> {
745 let data = ChunkedIndexData {
746 chunk_id_list: self.index.chunk_id_list.clone(),
747 chunk_term_freqs: self.index.chunk_term_freqs.clone(),
748 term_index: self.index.term_index.clone(),
749 parent_to_leaves: self.index.parent_to_leaves.clone(),
750 doc_lengths: self.index.doc_lengths.clone(),
751 avgdl: self.index.avgdl,
752 n_docs: self.index.n_docs,
753 params: BM25ParamsData::from(self.index.params.clone()),
754 config: self.index.config.clone(),
755 };
756 let encoded = bincode::serialize(&data)?;
757 std::fs::write(path.as_ref(), encoded)?;
758 Ok(())
759 }
760}
761
762impl ChunkedBM25Retriever<lc_vector_stores::ChunkedDocumentStore> {
763 pub fn load(
765 store: Arc<lc_vector_stores::ChunkedDocumentStore>,
766 path: impl AsRef<Path>,
767 ) -> Result<Self, Box<dyn std::error::Error>> {
768 let bytes = std::fs::read(path.as_ref())?;
769 let data: ChunkedIndexData = bincode::deserialize(&bytes)?;
770 let params: BM25Params = data.params.into();
771
772 Ok(Self {
773 index: ChunkedBM25Index {
774 store,
775 chunk_id_list: data.chunk_id_list,
776 chunk_term_freqs: data.chunk_term_freqs,
777 term_index: data.term_index,
778 parent_to_leaves: data.parent_to_leaves,
779 doc_lengths: data.doc_lengths,
780 avgdl: data.avgdl,
781 n_docs: data.n_docs,
782 idf_cache: HashMap::new(),
783 params,
784 tokenizer: Tokenizer::new(),
785 config: data.config,
786 },
787 })
788 }
789}
790
791impl Default for ChunkedBM25Retriever<lc_vector_stores::ChunkedDocumentStore> {
792 fn default() -> Self {
793 Self::new(Arc::new(lc_vector_stores::ChunkedDocumentStore::new()))
794 }
795}