Skip to content

web search done right

19.7 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 std::ops::Range;

use crate::config::SnippetConfig;
use crate::highlighted::{HighlightedFragment, HighlightedKind};
use crate::query::Query;
use crate::tokenizer::fields::{
    BigramTokenizer, DefaultTokenizer, FieldTokenizer, Stemmed, TrigramTokenizer,
};
use crate::webpage::region::Region;
use hashbrown::{HashMap, HashSet};
use lending_iter::LendingIterator;
use utoipa::ToSchema;
use web_spell::sentence_ranges;

use itertools::Itertools;
use whatlang::Lang;

// For now we use an algorithm similar to the `UnifiedHighlighter` in lucene <https://lucene.apache.org/core/7_3_1/highlighter/org/apache/lucene/search/uhighlight/UnifiedHighlighter.html>.
// The document text is treated as the entire corpus, and each passage is scored as a document in this corpus using BM25.
// The top scoring passage is used as the start of a snippet, maybe combined with the subsequent passage(s) in order to
// reach the desired snippet length.
//
// In the future we want to implement something closer to the method described in <https://cs.pomona.edu/~dkauchak/ir_project/whitepapers/Snippet-IL.pdf>.
// This might require us to store each paragraph of the webpage separately to get adequate performance (maybe we can split passages online with adequate performance
// but we need to test this).

const K1: f64 = 1.2;
const B: f64 = 0.75;

#[derive(Debug)]
struct PassageCandidate {
    score: f64,
    text: String,
    doc_terms: HashMap<String, u64>,
}

#[derive(
    Default,
    Debug,
    Clone,
    serde::Serialize,
    serde::Deserialize,
    bincode::Encode,
    bincode::Decode,
    PartialEq,
    ToSchema,
)]
#[serde(rename_all = "camelCase")]
pub struct TextSnippet {
    pub fragments: Vec<HighlightedFragment>,
}

impl TextSnippet {
    pub fn unhighlighted_string(&self) -> String {
        self.fragments
            .iter()
            .map(|f| f.text.clone())
            .collect::<Vec<_>>()
            .join("")
    }
}

struct SnippetBuilder {
    fragment: String,
    highlights: Vec<Range<usize>>,
}

impl SnippetBuilder {
    fn highlight(&mut self, terms: &HashSet<String>, lang: whatlang::Lang) {
        for mut tokenizer in [
            FieldTokenizer::Stemmed(Stemmed::with_forced_language(lang)),
            FieldTokenizer::Default(DefaultTokenizer::default()),
            FieldTokenizer::Bigram(BigramTokenizer::default()),
            FieldTokenizer::Trigram(TrigramTokenizer::default()),
        ] {
            let mut stream =
                tantivy::tokenizer::Tokenizer::token_stream(&mut tokenizer, &self.fragment);
            let mut it = tantivy::tokenizer::TokenStream::iter(&mut stream);
            while let Some(tok) = it.next() {
                if terms.contains(&tok.text) {
                    self.highlights.push(tok.offset_from..tok.offset_to);
                }
            }
        }

        // remove overlapping ranges
        self.highlights
            .sort_by(|a, b| a.start.cmp(&b.start).then(a.end.cmp(&b.end)));
        self.highlights
            .dedup_by(|a, b| a.start == b.start && a.end >= b.end);
    }

    fn build(self) -> TextSnippet {
        let mut fragments = Vec::new();

        let mut last_end = 0;

        for range in self.highlights {
            if range.start > last_end {
                fragments.push(HighlightedFragment {
                    kind: HighlightedKind::Normal,
                    text: self.fragment[last_end..range.start].to_string(),
                });
            }

            fragments.push(HighlightedFragment {
                kind: HighlightedKind::Highlighted,
                text: self.fragment[range.start..range.end].to_string(),
            });

            last_end = range.end;
        }

        if last_end < self.fragment.len() {
            fragments.push(HighlightedFragment {
                kind: HighlightedKind::Normal,
                text: self.fragment[last_end..].to_string(),
            });
        }

        TextSnippet { fragments }
    }

    fn trim_to_chars(&mut self, chars: usize) {
        self.fragment = self.fragment.chars().take(chars).collect()
    }

    fn add_passage(&mut self, passage: &PassageCandidate) {
        self.fragment.push(' ');
        self.fragment.push_str(&passage.text);
    }
}

fn passages(
    text: &str,
    mut tokenizer: FieldTokenizer,
    config: &SnippetConfig,
) -> Vec<PassageCandidate> {
    sentence_ranges(text)
        .into_iter()
        .filter(|offset| offset.end - offset.start > config.min_passage_width)
        .map(|offset| {
            let sentence = text[offset].to_string();

            let mut doc_terms = HashMap::new();

            {
                let mut stream =
                    tantivy::tokenizer::Tokenizer::token_stream(&mut tokenizer, &sentence);
                let mut it = tantivy::tokenizer::TokenStream::iter(&mut stream);
                while let Some(tok) = it.next() {
                    *doc_terms.entry(tok.text.clone()).or_insert(0) += 1;
                }
            }

            PassageCandidate {
                score: 0.0,
                text: sentence,
                doc_terms,
            }
        })
        .collect()
}

fn calculate_idf(terms: &HashSet<String>, passages: &[PassageCandidate]) -> HashMap<String, f64> {
    let mut n: HashMap<_, _> = terms.iter().map(|term| (term.to_string(), 0)).collect();

    for term in terms.iter() {
        for passage in passages.iter() {
            if passage.doc_terms.contains_key(term) {
                *n.entry(term.to_string()).or_insert(0) += 1;
            }
        }
    }

    n.into_iter()
        .map(|(term, freq)| {
            (
                term,
                (((passages.len() as f64) - (freq as f64) + 0.5) / ((freq as f64) + 0.5) + 1.0)
                    .ln(),
            )
        })
        .collect()
}

fn score_passages_with_bm25(passages: &mut [PassageCandidate], terms: &HashSet<String>) {
    let idf = calculate_idf(terms, passages);
    let mut total_d_size = 0;

    for passage in passages.iter() {
        total_d_size += passage.doc_terms.len();
    }

    let avg_d_size = total_d_size / passages.len();
    for passage in passages.iter_mut() {
        for term in terms.iter() {
            let f = *passage.doc_terms.get(term).unwrap_or(&0) as f64;
            passage.score += idf[term]
                * ((f * (K1 + 1.0))
                    / (f + K1
                        * (1.0 - B + B * (passage.doc_terms.len() as f64 / avg_d_size as f64))));
        }
    }
}

fn snippet_string_builder(
    text: &str,
    terms: &[String],
    lang: whatlang::Lang,
    config: SnippetConfig,
    mut tokenizer: FieldTokenizer,
) -> SnippetBuilder {
    let terms: HashSet<String> = terms
        .iter()
        .flat_map(|term| {
            let mut stream = tantivy::tokenizer::Tokenizer::token_stream(&mut tokenizer, term);

            let mut res = Vec::new();
            let mut it = tantivy::tokenizer::TokenStream::iter(&mut stream);
            while let Some(tok) = it.next() {
                res.push(tok.text.clone());
            }

            res.into_iter()
        })
        .collect();

    let mut passages = passages(text, tokenizer, &config);

    if passages.is_empty() {
        let mut snippet = SnippetBuilder {
            fragment: text.chars().take(config.desired_num_chars).collect(),
            highlights: Vec::new(),
        };

        snippet.highlight(&terms, lang);

        return snippet;
    }

    score_passages_with_bm25(&mut passages, &terms);

    let best_idx = passages
        .iter()
        .position_max_by(|a, b| a.score.total_cmp(&b.score))
        .expect("passages cannot be empty at this point");

    let best_passage = &passages[best_idx];
    let mut snippet = SnippetBuilder {
        fragment: best_passage.text.clone(),
        highlights: Vec::new(),
    };

    if snippet.fragment.len() > config.desired_num_chars + config.delta_num_chars {
        // TODO: find 'desired_num_chars' sized window that contains most highlights
        // instead of taking the prefix of the passage as a snippet

        snippet.trim_to_chars(config.desired_num_chars + config.delta_num_chars);
    } else {
        let mut next_passage_idx = best_idx + 1;

        while snippet.fragment.len() < config.desired_num_chars - config.delta_num_chars
            && next_passage_idx < passages.len()
        {
            snippet.add_passage(&passages[next_passage_idx]);
            next_passage_idx += 1;
        }

        if snippet.fragment.len() > config.desired_num_chars + config.delta_num_chars {
            snippet.trim_to_chars(config.desired_num_chars + config.delta_num_chars);
        }
    }
    snippet.highlight(&terms, lang);

    snippet
}

fn snippet_string(
    text: &str,
    terms: &[String],
    lang: whatlang::Lang,
    config: SnippetConfig,
) -> TextSnippet {
    let tokenizer = FieldTokenizer::Default(DefaultTokenizer::default());
    let snip = snippet_string_builder(text, terms, lang, config.clone(), tokenizer).build();

    if !snip.fragments.is_empty()
        && snip
            .fragments
            .iter()
            .any(|f| f.kind == HighlightedKind::Highlighted)
    {
        return snip;
    }

    let tokenizer = FieldTokenizer::Stemmed(Stemmed::with_forced_language(lang));
    snippet_string_builder(text, terms, lang, config, tokenizer).build()
}

pub fn generate(query: &Query, text: &str, region: &Region, config: SnippetConfig) -> TextSnippet {
    let lang = match region.lang() {
        Some(lang) => lang,
        None => match config.num_words_for_lang_detection {
            Some(num_words) => whatlang::detect_lang(
                text.split_whitespace()
                    .take(num_words)
                    .collect::<String>()
                    .as_str(),
            ),
            None => whatlang::detect_lang(text),
        }
        .unwrap_or(Lang::Eng),
    };

    if text.is_empty() {
        return TextSnippet {
            fragments: vec![HighlightedFragment {
                kind: HighlightedKind::Normal,
                text: "".to_string(),
            }],
        };
    }

    match config.max_considered_words {
        Some(num_words) => {
            let text = text.split_whitespace().take(num_words).join(" ");
            snippet_string(&text, query.simple_terms(), lang, config)
        }
        None => snippet_string(text, query.simple_terms(), lang, config),
    }
}

#[cfg(test)]
mod tests {
    use std::sync::Arc;

    use super::*;
    use crate::{
        index::Index,
        search_prettifier::Snippet,
        searcher::{LocalSearcher, SearchQuery},
        webpage::Webpage,
    };
    use proptest::prelude::*;
    use tokio::sync::RwLock;

    const TEST_TEXT: &str = r#"Rust is a systems programming language sponsored by
Mozilla which describes it as a "safe, concurrent, practical language", supporting functional and
imperative-procedural paradigms. Rust is syntactically similar to C++[according to whom?],
but its designers intend it to provide better memory safety while still maintaining
performance.
Rust is free and open-source software, released under an MIT License, or Apache License
2.0. Its designers have refined the language through the experiences of writing the Servo
web browser layout engine[14] and the Rust compiler. A large proportion of current commits
to the project are from community members.[15]
Rust won first place for "most loved programming language" in the Stack Overflow Developer
Survey in 2016, 2017, and 2018."#;

    const HIGHLIGHTEN_PREFIX: &str = "<b>";
    const HIGHLIGHTEN_POSTFIX: &str = "</b>";

    fn highlight(snippet: Snippet) -> String {
        let text = snippet.text;

        text.fragments
            .into_iter()
            .map(|HighlightedFragment { kind, text }| match kind {
                HighlightedKind::Normal => text,
                HighlightedKind::Highlighted => {
                    format!("{HIGHLIGHTEN_PREFIX}{}{HIGHLIGHTEN_POSTFIX}", text)
                }
            })
            .collect()
    }

    #[test]
    fn snippet_during_search() {
        let (mut index, _dir) = Index::temporary().expect("Unable to open index");

        index
            .insert(
                &Webpage::test_parse(
                    &format!(
                        r#"
                        <html>
                            <head>
                                <title>Website for runners</title>
                            </head>
                            <body>
                                {TEST_TEXT}
                            </body>
                        </html>
                    "#
                    ),
                    "https://www.example.com",
                )
                .unwrap(),
            )
            .expect("failed to insert webpage");
        index.commit().expect("failed to commit index");

        let searcher = LocalSearcher::builder(Arc::new(RwLock::new(index))).build();

        let result = searcher
            .search_sync(&SearchQuery {
                query: "rust language".to_string(),
                ..Default::default()
            })
            .expect("Search failed");

        assert_eq!(result.webpages.len(), 1);
        assert_eq!(highlight(result.webpages[0].snippet.clone()), format!("{HIGHLIGHTEN_PREFIX}Rust{HIGHLIGHTEN_POSTFIX} is a systems programming {HIGHLIGHTEN_PREFIX}language{HIGHLIGHTEN_POSTFIX} sponsored by Mozilla which describes it as a \"safe, concurrent, practical {HIGHLIGHTEN_PREFIX}language{HIGHLIGHTEN_POSTFIX}\", supporting functional and imperative-procedural paradigms. {HIGHLIGHTEN_PREFIX}Rust{HIGHLIGHTEN_POSTFIX} is syntactically similar to C++[according to whom?], but its designers intend it to provide better memory safety while still maintaining "));
    }

    #[test]
    fn stemmed_words_snippet_highlight() {
        let (mut index, _dir) = Index::temporary().expect("Unable to open index");

        index
            .insert(
                &Webpage::test_parse(
                    &format!(
                        r#"
                        <html>
                            <head>
                                <title>Website for runners</title>
                            </head>
                            <body>
                                {TEST_TEXT}
                            </body>
                        </html>
                    "#
                    ),
                    "https://www.example.com",
                )
                .unwrap(),
            )
            .expect("failed to insert webpage");
        index.commit().expect("failed to commit index");

        let searcher = LocalSearcher::builder(Arc::new(RwLock::new(index))).build();

        let result = searcher
            .search_sync(&SearchQuery {
                query: "describe".to_string(),
                ..Default::default()
            })
            .expect("Search failed");

        assert_eq!(result.webpages.len(), 1);
        assert_eq!(highlight(result.webpages[0].snippet.clone()), format!("Rust is a systems programming language sponsored by Mozilla which {HIGHLIGHTEN_PREFIX}describes{HIGHLIGHTEN_POSTFIX} it as a \"safe, concurrent, practical language\", supporting functional and imperative-procedural paradigms. Rust is syntactically similar to C++[according to whom?], but its designers intend it to provide better memory safety while still maintaining "));
    }

    #[test]
    fn test_stemmed_term() {
        let (mut index, _dir) = Index::temporary().expect("Unable to open index");

        index
            .insert(
                &Webpage::test_parse(
                    &format!(
                        r#"
                        <html>
                            <head>
                                <title>Website for runners</title>
                            </head>
                            <body>
                                {TEST_TEXT}
                            </body>
                        </html>
                    "#
                    ),
                    "https://www.example.com",
                )
                .unwrap(),
            )
            .expect("failed to insert webpage");
        index.commit().expect("failed to commit index");

        let searcher = LocalSearcher::builder(Arc::new(RwLock::new(index))).build();

        let result = searcher
            .search_sync(&SearchQuery {
                query: "paradigms".to_string(),
                ..Default::default()
            })
            .expect("Search failed");

        assert_eq!(result.webpages.len(), 1);
        assert_eq!(
            highlight(result.webpages[0].snippet.clone()),
            format!("Rust is a systems programming language sponsored by Mozilla which describes it as a \"safe, concurrent, practical language\", supporting functional and imperative-procedural {HIGHLIGHTEN_PREFIX}paradigms{HIGHLIGHTEN_POSTFIX}. Rust is syntactically similar to C++[according to whom?], but its designers intend it to provide better memory safety while still maintaining ")
        );
    }

    #[test]
    fn empty_query() {
        assert_eq!(
            highlight(Snippet {
                date: None,
                text: snippet_string(
                    "this is a test",
                    &[],
                    whatlang::Lang::Eng,
                    SnippetConfig::default()
                )
            })
            .as_str(),
            "this is a test"
        );
    }

    #[test]
    fn empty_text() {
        assert_eq!(
            highlight(Snippet {
                date: None,
                text: snippet_string(
                    "",
                    &["test".to_string()],
                    whatlang::Lang::Eng,
                    SnippetConfig::default()
                )
            })
            .as_str(),
            ""
        );

        assert_eq!(
            highlight(Snippet {
                date: None,
                text: snippet_string("", &[], whatlang::Lang::Eng, SnippetConfig::default())
            })
            .as_str(),
            ""
        );
    }

    #[test]
    fn compounded_terms() {
        let snip = snippet_string_builder(
            "this is a test",
            &["thisis".to_string()],
            whatlang::Lang::Eng,
            SnippetConfig::default(),
            FieldTokenizer::Default(DefaultTokenizer::default()),
        );

        let mut terms = HashSet::new();
        terms.insert("thisis".to_string());

        assert_eq!(
            highlight(Snippet {
                date: None,
                text: snip.build()
            })
            .as_str(),
            "<b>this is</b> a test"
        );
    }

    #[test]
    fn test_fuzz_infinite_loop() {
        let text = "\u{a0}";
        let query = "";

        let terms = query
            .split_whitespace()
            .map(|s| s.to_string())
            .collect::<Vec<_>>();
        let _ = snippet_string(text, &terms, whatlang::Lang::Eng, SnippetConfig::default());
    }

    proptest! {
        #[test]
        fn prop_snippet_gen(text in ".{1,100}", query in ".{1,100}") {
            let terms = query.split_whitespace().map(|s| s.to_string()).collect::<Vec<_>>();
            let _ = snippet_string(&text, &terms, whatlang::Lang::Eng, SnippetConfig::default());
        }
    }
}