Spell Checker

Краен срок:: 14.01.2020 17:00
Точки:: 20

Срокът за предаване на решения е отминал

Spell Checker

В тази задачка ще имплементираме простия spell checker на Peter Norvig: цък. На питон кода е 30тина реда, но в Rust ще ни се наложи да попишем малко повече.

В линка може да намерите по-дълго обяснение на това как работи, но краткия вариант се свежда до:

Вземаме някакъв дълъг текст, разбиваме го на думи и броим колко пъти се среща всяка дума. По-често срещаните думи ще бъдат по-вероятно правилни. Този текст ще наричаме "корпус" по-надолу. Думите, които се срещат в корпуса ще наричаме "познати" (known).
Получаваме дума, която искаме да коригираме.
Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези думи? Ако да, връщаме тази, която се среща най-често в корпуса.
Пробваме всички възможни други думи на две букви разлика по същия начин.
В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.

Приемаме, че няма да се подават празни низове или невалидни думи.

Ще започнем имплементацията с една помощна функция:

/// Тази функция премахва всякакви специални символи от низа, освен:
///
/// - Азбучни символи (`char::is_alphabetical`)
/// - Празни символи (`char::is_whitespace`)
/// - Апостроф и тиренце (`'`, `-`)
///
/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
///
/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
/// basically).
///
pub fn clean_line(input: &str) -> String {
    unimplemented!()
}

Ще ни трябва и имплементация на Counter класа, който идва със питонската стандартна библиотека. Или поне нещо подобно.

pub struct WordCounter {
    // ...
}

impl WordCounter {
    /// Конструира нов `WordCounter` без никакви данни.
    ///
    pub fn new() -> Self {
        unimplemented!()
    }

    /// Прочита входния низ, ред по ред, обработва всеки ред с `clean_line`, разбива го на думи и
    /// конструира нов WordCounter, който ще брои думите на този низ.
    ///
    /// Нормализира думите по същия начин както `add` по-долу.
    ///
    pub fn from_str(input: &str) -> Self {
        unimplemented!()
    }

    /// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
    ///
    pub fn words(&self) -> Vec<&String> {
        unimplemented!()
    }

    /// Брои думата с WordCounter-а. Очаква се входа да бъде:
    ///
    /// - Изчистен от всякакъв начален и краен whitespace
    /// - Сведен до малки букви
    ///
    /// Тоест:
    ///
    /// `counter.add("Foo")` е еквивалентно на
    /// `counter.add("foo")` е еквивалентно на
    /// `counter.add(" foo ")`
    ///
    pub fn add(&mut self, item: &str) {
        unimplemented!()
    }

    /// Връща колко пъти е бил преброена дадената дума.
    ///
    pub fn get(&self, word: &str) -> u32 {
        unimplemented!()
    }

    /// Връща колко общо думи са били преброени. Тоест:
    ///
    ///     counter.add("foo");
    ///     counter.add("foo");
    ///     counter.add("bar");
    ///
    /// се очаква да ни даде `total_count()` 3.
    ///
    pub fn total_count(&self) -> u32 {
        unimplemented!()
    }
}

/// Искаме да можем да напечатаме един `WordCounter` с цел дебъгване.
///
/// - Първи ред: `WordCounter, total count: {}`, форматирано с `total_count`.
/// - Останалите редове: Всяка една дума, изчистена както е описано горе с `add`, с брой на
/// срещането ѝ, примерно: "foo: 13"
///
/// Всеки ред се очаква да завършва с `\n`, включително последния. Думите трябва да са сортирани по
/// брой на срещанията, най-честите трябва да са първи. Примерно:
///
///     WordCounter, total count: 25
///     foo: 13
///     bar: 12
///
impl std::fmt::Display for WordCounter {
    fn fmt(&self, f: &mut fmt::Formatter) -> std::fmt::Result {
        unimplemented!()
    }
}

Накрая, стигаме до самия spell checker:

use std::collections::HashSet;

/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
/// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";

pub struct SpellChecker {
    // ...
}

impl SpellChecker {
    /// Създава нов SpellChecker с дадените параметри:
    ///
    /// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
    ///   вероятност
    /// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
    ///   Примерно, да spell-check-ваме български или английски изисква различни азбуки.
    ///
    pub fn new(corpus: &str, alphabet: &str) -> Self {
        unimplemented!()
    }

    /// Най-вероятната поправка на тази дума. Както описахме по-горе:
    ///
    /// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
    /// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
    ///   думи? Ако да, връщаме тази, която се среща най-често в корпуса.
    /// - Пробваме всички възможни други думи на две букви разлика по същия начин.
    /// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
    ///
    /// Очакваме trim + downcase на входа, тоест
    /// `spell_checker.correction(" Foo ")` е еквивалентно на
    /// `spell_checker.correction("foo")`
    ///
    /// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
    /// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
    /// отделен файл, so here we are.)
    ///
    pub fn correction(&self, word: &str) -> String {
        unimplemented!()
    }

    /// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
    /// дума, разделен на броя думи в текста.
    ///
    pub fn probability(&self, word: &str) -> f64 {
        unimplemented!()
    }

    /// Кои думи от този Set са познати (присъстват в подадения корпус)?
    ///
    pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
        unimplemented!()
    }

    /// Всички познати кандидати за поправка на тази дума:
    ///
    /// - Ако думата е позната, директно връщаме вектор с нея.
    /// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
    /// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
    /// - Иначе, връщаме вектор с думата.
    ///
    pub fn candidates(&self, word: &str) -> Vec<String> {
        unimplemented!()
    }

    /// Всички думи, които са на една промяна разстояние от дадената дума:
    ///
    /// - Една буква изтрита на коя да е позиция
    /// - Две букви разменени (една до друга)
    /// - Една буква от азбуката замества коя да е буква от думата
    /// - Една буква от азбуката добавена в думата на която и да е позиция
    ///
    /// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
    /// а дубликати не ни интересуват.
    ///
    pub fn edits1(&self, word: &str) -> HashSet<String> {
        unimplemented!()
    }

    /// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
    /// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
    ///
    pub fn edits2(&self, word: &str) -> HashSet<String> {
        unimplemented!()
    }
}

Бележки:

Тествайте с кирилица.
Забележете, че f64 не имплементира Ord, което е мега досадно, но е fact of life. Възможно е едно от числата да е NaN (примерно ако разделите 0 на 0), което за целите на домашното приемаме, че няма да се случи. Типа имплементира PartialOrd, обаче.

Имате reference имплементация в горния питонски код, което би трябвало да ви улесни. Ако видите нещо в питона, което не се съгласува с това условие, питайте.

Базов тест (доста базов, колкото да провери, че се компилират нещата): https://github.com/fmi/rust-homework/blob/master/03/test_basic.rs

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Spell Checker

Spell Checker