Skip to content

web search done right

10.0 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

use candle_core::Tensor;
use std::{
    cmp::Reverse,
    collections::{BinaryHeap, VecDeque},
    ops::Range,
    path::Path,
};

use crate::{models::dual_encoder::DualEncoder, Result};
use itertools::{intersperse, Itertools};

use crate::ceil_char_boundary;

#[derive(Clone)]
struct CandidatePassage<'a> {
    passage: &'a str,
    range: Range<usize>,
    index: usize,
    score: f32,
}

impl PartialOrd for CandidatePassage<'_> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for CandidatePassage<'_> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.score.total_cmp(&other.score)
    }
}

impl PartialEq for CandidatePassage<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.score == other.score
    }
}

impl Eq for CandidatePassage<'_> {}

struct OverlappingSents<'a> {
    text: &'a str,
    window_size: usize,
    next_start: VecDeque<usize>,
    overlap: usize,
    prev_end: usize,
}

impl<'a> OverlappingSents<'a> {
    fn new(text: &'a str, window_size: usize, overlap: usize) -> Self {
        assert!(
            overlap < window_size,
            "overlap needs to be smaller than window size"
        );

        let next_start = VecDeque::with_capacity(overlap + 1);

        Self {
            text,
            window_size,
            overlap,
            next_start,
            prev_end: 0,
        }
    }
}

impl<'a> Iterator for OverlappingSents<'a> {
    type Item = (&'a str, Range<usize>);

    fn next(&mut self) -> Option<Self::Item> {
        if self.text.is_empty() {
            return None;
        }

        let mut end = self.text.len();
        let mut missing_words = self.window_size;
        self.next_start.clear();

        for (i, (idx, _)) in self
            .text
            .char_indices()
            .filter(|(_, c)| c.is_whitespace())
            .enumerate()
        {
            if i >= self.window_size {
                break;
            }

            missing_words -= 1;

            if self.next_start.len() > self.overlap {
                self.next_start.pop_front();
            }

            self.next_start.push_back(idx);
            end = idx;
        }

        if missing_words > 0 {
            end = self.text.len();
            for _ in 0..missing_words {
                self.next_start.pop_front();
            }
        }

        let res = &self.text[..end];
        let range = self.prev_end..self.prev_end + end;

        if let Some(next_start) = self.next_start.pop_front() {
            if next_start == 0 {
                self.text = "";
                self.prev_end += end;
            } else {
                let next_start = ceil_char_boundary(self.text, next_start + 1);

                self.text = &self.text[next_start..];
                self.prev_end += next_start;
            }
        } else {
            self.text = "";
            self.prev_end += end;
        }

        Some((res, range))
    }
}

trait PassageScorer {
    type QueryEmbedding;
    type PassageEmbedding;

    fn embed_query(&self, query: &str) -> Option<Self::QueryEmbedding>;
    fn embed_passage(&self, passage: &str) -> Option<Self::PassageEmbedding>;

    fn score(&self, query: &Self::QueryEmbedding, passage: &Self::PassageEmbedding) -> f32;
}

pub struct ExtractiveSummarizer {
    passage_scorer: DualEncoder,
    top_n_passages: usize,
    window_size: usize,
    overlap: usize,
}

impl ExtractiveSummarizer {
    pub fn open<P: AsRef<Path>>(path: P, top_n_passages: usize) -> Result<Self> {
        Ok(Self {
            passage_scorer: DualEncoder::open(path)?,
            top_n_passages,
            window_size: 64,
            overlap: 0,
        })
    }

    pub fn set_window_size(&mut self, window_size: usize) {
        self.window_size = window_size;
    }

    fn query_specific(&self, query: &str, text: &str) -> Option<String> {
        let query_vectors = self.passage_scorer.embed_query(query)?;

        let mut best_passages: BinaryHeap<Reverse<CandidatePassage<'_>>> =
            BinaryHeap::with_capacity(self.top_n_passages);

        let overlap_sents = OverlappingSents::new(text, self.window_size, self.overlap);

        for (index, (passage, range)) in overlap_sents.enumerate() {
            if let Some(passage_vec) = self.passage_scorer.embed_passage(passage) {
                let score = self.passage_scorer.score(&query_vectors, &passage_vec);

                let candidate = CandidatePassage {
                    passage,
                    index,
                    score,
                    range,
                };

                if best_passages.len() >= self.top_n_passages {
                    if let Some(mut worst) = best_passages.peek_mut() {
                        if worst.0.score < candidate.score {
                            *worst = Reverse(candidate);
                        }
                    }
                } else {
                    best_passages.push(Reverse(candidate));
                }
            }
        }

        if best_passages.is_empty() {
            return None;
        }

        let mut best_passages: Vec<_> = best_passages.into_iter().map(|r| r.0).collect();
        best_passages.sort_by_key(|a| a.index);

        let mut new_best_passages = Vec::with_capacity(best_passages.len());

        new_best_passages.push(best_passages[0].clone());

        for (a, mut b) in best_passages.into_iter().tuple_windows() {
            if a.range.end > b.range.start {
                b.range.start = ceil_char_boundary(text, a.range.end);
                b.passage = &text[b.range.clone()];
            }

            new_best_passages.push(b);
        }

        let mut res = String::new();

        res.push_str(new_best_passages[0].passage);

        for (a, b) in new_best_passages.into_iter().tuple_windows() {
            if b.index == a.index + 1 {
                res.push_str(b.passage);
            } else {
                res.push_str(". \n");
                res.push_str(b.passage);
            }
        }

        Some(res)
    }

    pub fn summarize(&self, query: &str, text: &str) -> String {
        self.query_specific(query, text)
            .unwrap_or_else(|| intersperse(text.split_whitespace().take(1000), " ").collect())
    }
}

impl PassageScorer for DualEncoder {
    type QueryEmbedding = Tensor;

    type PassageEmbedding = Tensor;

    fn embed_query(&self, query: &str) -> Option<Self::QueryEmbedding> {
        self.embed(&[query.to_string()]).ok()
    }

    fn embed_passage(&self, passage: &str) -> Option<Self::PassageEmbedding> {
        self.embed(&[passage.to_string()]).ok()
    }

    fn score(&self, query: &Self::QueryEmbedding, passage: &Self::PassageEmbedding) -> f32 {
        query
            .matmul(&passage.t().unwrap())
            .unwrap()
            .get(0)
            .unwrap()
            .squeeze(0)
            .unwrap()
            .to_dtype(candle_core::DType::F32)
            .unwrap()
            .to_vec0()
            .unwrap()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn overlapping_sentences() {
        let mut it = OverlappingSents::new("this is a test sentence", 3, 1).map(|(p, _)| p);

        assert_eq!(it.next(), Some("this is a"));
        assert_eq!(it.next(), Some("a test sentence"));
        assert_eq!(it.next(), Some("sentence"));
        assert_eq!(it.next(), None);

        let mut it = OverlappingSents::new("this is a test sentence", 3, 0).map(|(p, _)| p);

        assert_eq!(it.next(), Some("this is a"));
        assert_eq!(it.next(), Some("test sentence"));
        assert_eq!(it.next(), None);

        let mut it = OverlappingSents::new("this is a test sentence", 3, 2).map(|(p, _)| p);

        assert_eq!(it.next(), Some("this is a"));
        assert_eq!(it.next(), Some("is a test"));
        assert_eq!(it.next(), Some("a test sentence"));
        assert_eq!(it.next(), Some("sentence"));
        assert_eq!(it.next(), None);

        let mut it = OverlappingSents::new("this", 3, 1).map(|(p, _)| p);

        assert_eq!(it.next(), Some("this"));
        assert_eq!(it.next(), None);

        let mut it = OverlappingSents::new("this ", 3, 0).map(|(p, _)| p);

        assert_eq!(it.next(), Some("this ")); // this is not really great, but close enough. At least no panic
        assert_eq!(it.next(), None);

        let text = "this is a test sentence";
        let it = OverlappingSents::new(text, 3, 1);

        for (p, range) in it {
            assert_eq!(p, &text[range]);
        }
    }

    #[test]
    fn test_dual_encoder() {
        let data_path = Path::new("../../data/summarizer/dual_encoder");
        if !data_path.exists() {
            // Skip the test if the test data is not available
            return;
        }
        let model = DualEncoder::open(data_path).expect("Failed to load model");
        let query = "What is the capital of France?";
        let pos = "The capital of France is Paris.";
        let neg = "The best baguette in Paris can be found at Boulangerie Pichard.";

        let query_emb = model.embed_query(query).unwrap();
        let pos_emb = model.embed_passage(pos).unwrap();
        let neg_emb = model.embed_passage(neg).unwrap();

        assert!(model.score(&query_emb, &pos_emb) > 0.0);
        assert!(model.score(&query_emb, &pos_emb) > model.score(&query_emb, &neg_emb));
    }
}