ravenrs_movie/
search.rs

1//! Finds the moment of a film that answers a question, in the words the films
2//! already hold. No model and no network: it works the same in the browser.
3
4use std::rc::Rc;
5
6use ravenrs_text::fold;
7
8use crate::movie::{HotspotKind, Movie};
9
10/// How much a word counts in each part of a moment.
11const TITLE_WEIGHT: f32 = 2.0;
12const TEXT_WEIGHT: f32 = 1.0;
13const CHAPTER_WEIGHT: f32 = 0.5;
14/// The usual BM25 constants: how fast repeating a word stops helping, and how
15/// much a long text is discounted.
16const SATURATION: f32 = 1.2;
17const LENGTH_DISCOUNT: f32 = 0.75;
18/// A chapter begins the lesson, so it goes ahead of a step that says the same.
19const CHAPTER_BONUS: f32 = 1.25;
20/// How much of the shorter word a shared start has to cover: "compra" is not
21/// "computador".
22const MOST_OF_THE_WORD: f32 = 0.7;
23/// An answer far weaker than the best one is noise.
24const FAR_BELOW_THE_BEST: f32 = 0.25;
25/// Words that say nothing about the subject, folded, in Portuguese and English.
26const STOP_WORDS: &[&str] = &[
27    "a", "ao", "aos", "as", "com", "como", "da", "das", "de", "do", "dos", "e", "em", "eu", "faco", "fazer",
28    "foi", "ha", "isso", "mais", "meu", "meus", "minha", "minhas", "na", "nas", "no", "nos", "o", "onde",
29    "os", "ou", "outra", "outras", "outro", "outros", "para", "pelo", "pela", "por", "posso", "pra", "qual",
30    "quando", "que", "quero", "se", "sem", "seu", "sua", "um", "uma", "uns", "umas", "an", "and", "are",
31    "can", "does", "for", "how", "i", "in", "is", "it", "my", "of", "on", "or", "the", "to", "what", "where",
32    "with",
33];
34
35/// What a moment of a film is.
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37#[non_exhaustive]
38#[cfg_attr(feature = "live", ravenrs_live::expose(part = "variants"))]
39pub enum MomentKind {
40    /// The start of a chapter.
41    Chapter,
42    /// A step that waits for a click.
43    Step,
44    /// A note on the screen.
45    Note,
46}
47
48/// A place in a film that can be asked for.
49#[derive(Clone, Debug, PartialEq, Eq)]
50#[cfg_attr(feature = "live", ravenrs_live::expose(part = "fields"))]
51pub struct Moment {
52    /// The film, by its position in the library.
53    pub film: usize,
54    /// When, in milliseconds of the film's timeline.
55    pub at_ms: u64,
56    /// What it is.
57    pub kind: MomentKind,
58    /// Its title.
59    pub title: String,
60    /// What it says.
61    pub text: String,
62}
63
64/// A moment that answers a question.
65#[derive(Clone, Debug, PartialEq)]
66#[cfg_attr(feature = "live", ravenrs_live::expose(part = "fields"))]
67pub struct Answer {
68    /// The moment.
69    pub moment: Moment,
70    /// How well it answers, comparable only within one search.
71    pub score: f32,
72}
73
74/// A moment with its text ready to compare.
75#[derive(Debug)]
76struct Indexed {
77    moment: Moment,
78    title: Vec<String>,
79    text: Vec<String>,
80    chapter: Vec<String>,
81}
82
83#[cfg_attr(feature = "live", ravenrs_live::expose)]
84impl Indexed {
85    fn length(&self) -> usize {
86        self.title.len() + self.text.len()
87    }
88
89    /// How much `word` appears here, counting near words for less.
90    fn presence(&self, word: &str) -> f32 {
91        let in_field = |words: &[String]| words.iter().map(|other| likeness(word, other)).sum::<f32>();
92        in_field(&self.title) * TITLE_WEIGHT
93            + in_field(&self.text) * TEXT_WEIGHT
94            + in_field(&self.chapter) * CHAPTER_WEIGHT
95    }
96}
97
98#[derive(Debug)]
99struct Library {
100    films: Vec<(String, Movie)>,
101    moments: Vec<Indexed>,
102    average_length: f32,
103}
104
105/// The films of an app, ready to be asked about. Cloning is cheap.
106///
107/// ```
108/// use ravenrs_core::{Color, Size};
109/// use ravenrs_movie::{FilmBuilder, MovieLibrary};
110///
111/// let mut film = FilmBuilder::new(Size::new(320.0, 200.0), Color::WHITE);
112/// film.frame(0, &[]);
113/// film.chapter("Pagar uma conta", "Como dar baixa no que venceu.", 0);
114/// let library = MovieLibrary::new().film("Manual", film.finish(1000)?);
115/// assert_eq!(library.ask("como pago as contas?", 3)[0].moment.title, "Pagar uma conta");
116/// # Ok::<(), ravenrs_movie::MovieError>(())
117/// ```
118#[derive(Clone, Debug)]
119#[cfg_attr(feature = "live", ravenrs_live::expose(part = "fields"))]
120pub struct MovieLibrary {
121    inner: Rc<Library>,
122}
123
124#[cfg_attr(feature = "live", ravenrs_live::expose)]
125impl MovieLibrary {
126    /// A library with no films.
127    pub fn new() -> Self {
128        Self { inner: Rc::new(Library { films: Vec::new(), moments: Vec::new(), average_length: 0.0 }) }
129    }
130
131    /// The library with one more film. Build it once: this reads all the text.
132    #[must_use]
133    pub fn film(self, title: impl Into<String>, movie: Movie) -> Self {
134        let mut films: Vec<(String, Movie)> = self.inner.films.clone();
135        films.push((title.into(), movie));
136        let moments: Vec<Indexed> =
137            films.iter().enumerate().flat_map(|(i, (_, movie))| moments_of(i, movie)).collect();
138        let total: usize = moments.iter().map(Indexed::length).sum();
139        let average_length = total as f32 / moments.len().max(1) as f32;
140        Self { inner: Rc::new(Library { films, moments, average_length }) }
141    }
142
143    /// The film at `index`, with its title.
144    pub fn get(&self, index: usize) -> Option<(&str, &Movie)> {
145        self.inner.films.get(index).map(|(title, movie)| (title.as_str(), movie))
146    }
147
148    /// How many films it has.
149    pub fn len(&self) -> usize {
150        self.inner.films.len()
151    }
152
153    /// Whether it has no films.
154    pub fn is_empty(&self) -> bool {
155        self.inner.films.is_empty()
156    }
157
158    /// The moments that best answer `question`, the best first, at most `limit`.
159    /// Accents and case do not matter, and near forms of a word count for less:
160    /// "pago" finds "pagar". With no word in common, there is no answer.
161    pub fn ask(&self, question: &str, limit: usize) -> Vec<Answer> {
162        let library = &self.inner;
163        let words = question_words(question);
164        if words.is_empty() {
165            return Vec::new();
166        }
167        let total = library.moments.len() as f32;
168        let mut scores = vec![(0.0_f32, 0_usize); library.moments.len()];
169        for word in &words {
170            let presences: Vec<f32> = library.moments.iter().map(|m| m.presence(word)).collect();
171            let having = presences.iter().filter(|p| **p > 0.0).count() as f32;
172            let rarity = (1.0 + (total - having + 0.5) / (having + 0.5)).ln();
173            for ((score, matched), (presence, moment)) in
174                scores.iter_mut().zip(presences.iter().zip(&library.moments))
175            {
176                if *presence > 0.0 {
177                    let length = moment.length() as f32 / library.average_length.max(1.0);
178                    let discount = 1.0 - LENGTH_DISCOUNT + LENGTH_DISCOUNT * length;
179                    *score += rarity * presence * (SATURATION + 1.0) / (presence + SATURATION * discount);
180                    *matched += 1;
181                }
182            }
183        }
184        let mut answers: Vec<Answer> = library
185            .moments
186            .iter()
187            .zip(scores)
188            .filter(|(_, (score, _))| *score > 0.0)
189            .map(|(indexed, (score, matched))| Answer {
190                moment: indexed.moment.clone(),
191                // Answering every word beats answering one word very well.
192                score: score * matched as f32 / words.len() as f32
193                    * if indexed.moment.kind == MomentKind::Chapter { CHAPTER_BONUS } else { 1.0 },
194            })
195            .collect();
196        // On a tie the chapter wins, and then the earlier.
197        answers.sort_by(|a, b| {
198            b.score
199                .total_cmp(&a.score)
200                .then_with(|| rank(a.moment.kind).cmp(&rank(b.moment.kind)))
201                .then_with(|| (a.moment.film, a.moment.at_ms).cmp(&(b.moment.film, b.moment.at_ms)))
202        });
203        let best = answers.first().map_or(0.0, |answer| answer.score);
204        answers.retain(|answer| answer.score >= best * FAR_BELOW_THE_BEST);
205        answers.truncate(limit);
206        answers
207    }
208}
209
210impl Default for MovieLibrary {
211    fn default() -> Self {
212        Self::new()
213    }
214}
215
216fn rank(kind: MomentKind) -> u8 {
217    match kind {
218        MomentKind::Chapter => 0,
219        MomentKind::Step => 1,
220        MomentKind::Note => 2,
221    }
222}
223
224fn moments_of(film: usize, movie: &Movie) -> Vec<Indexed> {
225    let chapters = movie.chapters().iter().map(|chapter| {
226        let moment = Moment {
227            film,
228            at_ms: chapter.at_ms,
229            kind: MomentKind::Chapter,
230            title: chapter.title.clone(),
231            text: chapter.text.clone(),
232        };
233        indexed(moment, Vec::new())
234    });
235    // A box about the whole screen says what its chapter says.
236    let spots = movie.hotspots().iter().filter(|spot| !spot.is_general()).map(|spot| {
237        let moment = Moment {
238            film,
239            at_ms: spot.from_ms,
240            kind: if spot.kind == HotspotKind::Stop { MomentKind::Step } else { MomentKind::Note },
241            title: spot.title.clone(),
242            text: spot.text.clone(),
243        };
244        let chapter = movie.chapter_at(spot.from_ms).and_then(|i| movie.chapters().get(i));
245        indexed(moment, chapter.map_or_else(Vec::new, |chapter| words_of(&chapter.title)))
246    });
247    chapters.chain(spots).collect()
248}
249
250fn indexed(moment: Moment, chapter: Vec<String>) -> Indexed {
251    let (title, text) = (words_of(&moment.title), words_of(&moment.text));
252    Indexed { moment, title, text, chapter }
253}
254
255/// The folded words of a text, leaving out the ones that say nothing.
256fn words_of(text: &str) -> Vec<String> {
257    all_words(text).into_iter().filter(|word| !STOP_WORDS.contains(&word.as_str())).collect()
258}
259
260/// The words of a question. A question made only of small words still asks.
261fn question_words(question: &str) -> Vec<String> {
262    let words = words_of(question);
263    if words.is_empty() { all_words(question) } else { words }
264}
265
266fn all_words(text: &str) -> Vec<String> {
267    let folded: String = text.chars().flat_map(fold).collect();
268    folded.split(|c: char| !c.is_alphanumeric()).filter(|w| !w.is_empty()).map(str::to_owned).collect()
269}
270
271/// How close two folded words are, from 0 to 1.
272fn likeness(a: &str, b: &str) -> f32 {
273    if a == b {
274        return 1.0;
275    }
276    let (a, b): (Vec<char>, Vec<char>) = (a.chars().collect(), b.chars().collect());
277    let (shorter, longer) = (a.len().min(b.len()), a.len().max(b.len()));
278    let singular = |word: &[char]| -> usize { word.len() - usize::from(word.last() == Some(&'s')) };
279    if a[..singular(&a)] == b[..singular(&b)] {
280        return 0.95;
281    }
282    if shorter >= 5 && one_edit_apart(&a, &b) {
283        return 0.7;
284    }
285    if root(&a) == root(&b) {
286        return 0.6;
287    }
288    // A long shared start: "pagar" and "pagamento", or a word still being typed.
289    let common = a.iter().zip(&b).take_while(|(x, y)| x == y).count();
290    if common >= 4 && common as f32 >= shorter as f32 * MOST_OF_THE_WORD {
291        0.3 + 0.5 * common as f32 / longer as f32
292    } else {
293        0.0
294    }
295}
296
297/// A word without the plural and the usual endings of verbs, so "pago", "pague"
298/// and "pagar" meet. This is not a real stemmer: it only has to bring near forms
299/// together, and a root under three letters is left alone.
300fn root(word: &[char]) -> &[char] {
301    let word = word.strip_suffix(&['s']).unwrap_or(word);
302    let ending = [
303        &['i', 'n', 'g'][..],
304        &['a', 'r'],
305        &['e', 'r'],
306        &['i', 'r'],
307        &['o', 'u'],
308        &['e', 'i'],
309        &['u', 'e'],
310        &['e', 'd'],
311        &['a'],
312        &['e'],
313        &['i'],
314        &['o'],
315    ]
316    .into_iter()
317    .find(|ending| word.ends_with(ending) && word.len() >= ending.len() + 3);
318    ending.map_or(word, |ending| &word[..word.len() - ending.len()])
319}
320
321/// One letter wrong, missing, extra, or two swapped: the usual slips of typing.
322fn one_edit_apart(a: &[char], b: &[char]) -> bool {
323    if a.len().abs_diff(b.len()) > 1 {
324        return false;
325    }
326    let start = a.iter().zip(b).take_while(|(x, y)| x == y).count();
327    let (rest_a, rest_b) = (&a[start..], &b[start..]);
328    let tail = |skip_a: usize, skip_b: usize| rest_a.get(skip_a..) == rest_b.get(skip_b..);
329    let swapped = rest_a.len() >= 2
330        && rest_b.len() >= 2
331        && rest_a[0] == rest_b[1]
332        && rest_a[1] == rest_b[0]
333        && tail(2, 2);
334    tail(1, 1) || tail(1, 0) || tail(0, 1) || swapped
335}
336
337#[cfg(test)]
338mod tests {
339    use super::{all_words, likeness, words_of};
340
341    #[test]
342    fn words_are_folded_and_small_words_go_away() {
343        assert_eq!(all_words("Lançar: uma DESPESA!"), ["lancar", "uma", "despesa"]);
344        assert_eq!(words_of("Como lançar uma despesa?"), ["lancar", "despesa"]);
345    }
346
347    #[test]
348    fn near_words_count_less_than_the_same_word() {
349        assert_eq!(likeness("conta", "conta"), 1.0);
350        assert!(likeness("conta", "contas") > 0.9);
351        assert!(likeness("despeza", "despesa") > 0.5, "one wrong letter");
352        assert!(likeness("despsea", "despesa") > 0.5, "two swapped letters");
353        assert!(likeness("pagar", "pague") > 0.0, "the same root");
354        assert!(likeness("pagar", "pagamento") > 0.0, "the same root, longer");
355        assert_eq!(likeness("carro", "conta"), 0.0);
356        assert!(likeness("salvo", "salvar") > 0.0, "the same root");
357        assert!(likeness("saving", "save") > 0.0, "the same root");
358        assert!(likeness("lanc", "lancamentos") > 0.0, "still being typed");
359        assert_eq!(likeness("saldo", "salvar"), 0.0, "sharing a start is not sharing a meaning");
360        assert_eq!(likeness("saldo", "salve"), 0.0);
361        assert_eq!(likeness("compra", "computador"), 0.0);
362    }
363}
ravenrs_movie/search.rs

ravenrs_movie/
search.rs
