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

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

Решение на Spell Checker от Димитър Иринков

Обратно към всички решения

Към профила на Димитър Иринков

Резултати

  • 13 точки от тестове
  • 0 бонус точки
  • 13 точки общо
  • 10 успешни тест(а)
  • 5 неуспешни тест(а)

Код

use std::collections::BTreeMap;
use std::fmt;
use std::cmp::Ordering;
/// Тази функция премахва всякакви специални символи от низа, освен:
///
/// - Азбучни символи (`char::is_alphabetical`)
/// - Празни символи (`char::is_whitespace`)
/// - Апостроф и тиренце (`'`, `-`)
///
/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
///
/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
/// basically).
pub fn clean_line(input: &str) -> String {
input.chars()
.filter( |&c|
char::is_alphabetic(c) ||
char::is_whitespace(c) ||
c == '\'' ||
c == '-'
)
.collect()
}
pub struct WordCounter {
words: BTreeMap<String, u32>,
}
impl WordCounter {
/// Конструира нов `WordCounter` без никакви данни.
///
pub fn new() -> Self {
WordCounter {
words: BTreeMap::new(),
}
}
/// Прочита входния низ, ред по ред, обработва всеки ред с `clean_line`, разбива го на думи и
/// конструира нов WordCounter, който ще брои думите на този низ.
///
/// Нормализира думите по същия начин както `add` по-долу.
///
pub fn from_str(input: &str) -> Self {
let mut word_counter = WordCounter::new();
input.lines()
.map( clean_line )
.for_each( |line|
line.split_whitespace()
.for_each( |word|
word_counter.add(word)
)
);
word_counter
}
/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
///
pub fn words(&self) -> Vec<&String> {
self.words.keys().collect()
}
/// Брои думата с WordCounter-а. Очаква се входа да бъде:
///
/// - Изчистен от всякакъв начален и краен whitespace
/// - Сведен до малки букви
///
/// Тоест:
///
/// `counter.add("Foo")` е еквивалентно на
/// `counter.add("foo")` е еквивалентно на
/// `counter.add(" foo ")`
///
pub fn add(&mut self, item: &str) {
let item = item.trim().to_lowercase();
*self.words.entry(item).or_insert(0) += 1;
}
/// Връща колко пъти е бил преброена дадената дума.
///
pub fn get(&self, word: &str) -> u32 {
*self.words.get(word).unwrap_or(&0u32)
}
/// Връща колко общо думи са били преброени. Тоест:
///
/// counter.add("foo");
/// counter.add("foo");
/// counter.add("bar");
///
/// се очаква да ни даде `total_count()` 3.
///
pub fn total_count(&self) -> u32 {
self.words.values().sum()
}
}
/// Искаме да можем да напечатаме един `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 {
write!(f, "WordCounter, total count: {}\n", self.total_count())?;
let mut v = Vec::with_capacity(self.words.len());
for pair in self.words.iter() {
v.push(pair);
}
v.sort_unstable_by(|a,b| a.1.cmp(b.1));
for pair in v {
write!(f, "{}: {}\n", pair.0, pair.1)?;
}
std::fmt::Result::Ok(())
}
}
use std::collections::HashSet;
/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
/// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";
pub struct SpellChecker {
word_counter: WordCounter,
alphabet: Vec<char>,
}
impl SpellChecker {
/// Създава нов SpellChecker с дадените параметри:
///
/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
/// вероятност
/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.
///
pub fn new(corpus: &str, alphabet: &str) -> Self {
SpellChecker {
word_counter: WordCounter::from_str(corpus),
alphabet: alphabet.chars().collect(),
}
}
/// Най-вероятната поправка на тази дума. Както описахме по-горе:
///
/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.
/// - Пробваме всички възможни други думи на две букви разлика по същия начин.
/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
///
/// Очакваме trim + downcase на входа, тоест
/// `spell_checker.correction(" Foo ")` е еквивалентно на
/// `spell_checker.correction("foo")`
///
/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
/// отделен файл, so here we are.)
//Източник:
//https://users.rust-lang.org/t/sorting-vector-of-vectors-of-f64/16264
pub fn correction(&self, word: &str) -> String {
let word_formated = word.trim().to_lowercase();
let word = word.to_owned();
let candidates = self.candidates(&word_formated);
let candidate = candidates.iter().max_by(|a,b| {
if self.probability(a) < self.probability(b) {
Ordering::Less
} else if a > b {
Ordering::Greater
} else {
Ordering::Equal
}
});
if candidate.is_some() {
candidate.unwrap().clone()
} else {
word
}
}
/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
/// дума, разделен на броя думи в текста.
///
pub fn probability(&self, word: &str) -> f64 {
let occurrence = self.word_counter.get(word);
let total_words = self.word_counter.total_count();
if occurrence == 0 || total_words == 0 {
0.0
} else {
occurrence as f64 /total_words as f64
}
}
/// Кои думи от този Set са познати (присъстват в подадения корпус)?
///
pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
words.iter()
.filter(|word| self.word_counter.get(word) != 0u32)
.collect()
}
/// Всички познати кандидати за поправка на тази дума:
///
/// - Ако думата е позната, директно връщаме вектор с нея.
/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
/// - Иначе, връщаме вектор с думата.
///
pub fn candidates(&self, word: &str) -> Vec<String> {
let mut v = vec![];
if self.word_counter.get(word) != 0u32 {
return vec![word.to_owned()];
}
for word in self.edits1(word) {
if self.word_counter.get(&word) != 0 {
v.push(word);
}
}
if !v.is_empty() {
return v;
}
for word in self.edits2(word) {
if self.word_counter.get(&word) != 0 {
v.push(word);
}
}
if !v.is_empty() {
return v;
}
vec![word.to_owned()]
}
/// Всички думи, които са на една промяна разстояние от дадената дума:
///
///
/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
/// а дубликати не ни интересуват.
pub fn edits1(&self, word: &str) -> HashSet<String> {
//Need some math to calculate capacity
let mut set :HashSet<String> = HashSet::new();
let word : Vec<char>= word.chars().collect();
// Една буква изтрита на коя да е позиция
for (index, _letter) in word.iter().enumerate() {
let mut temp = word.clone();
temp.remove(index);
set.insert(temp.iter().collect());
}
// Една буква от азбуката добавена в думата на която и да е позиция
for (index, _letter) in word.iter().enumerate() {
for &new_letter in &self.alphabet {
let mut temp = word.clone();
temp.insert(index, new_letter);
set.insert(temp.iter().collect());
}
}
// Една буква от азбуката замества коя да е буква от думата
let mut buff = word.clone();
for (index,letter) in word.iter().enumerate() {
let temp = *letter;
for &new_letter in &self.alphabet {
buff[index] = new_letter;
set.insert(buff.iter().collect());
}
buff[index] = temp;
}
// Две букви разменени (една до друга)
let mut it = word.iter().enumerate();
it.next();
let mut buff = word.clone();
for (index, _letter) in it {
buff.swap(index - 1, index);
set.insert(buff.iter().collect());
buff.swap(index - 1, index);
}
set
}
/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
///
pub fn edits2(&self, word: &str) -> HashSet<String> {
let mut set = HashSet::new();
for word in self.edits1(word).into_iter() {
set.extend(self.edits1(&word).into_iter());
}
set
}
}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20200114-2173579-oeaywv/solution)
    Finished test [unoptimized + debuginfo] target(s) in 4.84s
     Running target/debug/deps/solution-a73e64ec87929bd0

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-38971695424b36d5

running 15 tests
test solution_test::test_best_word_is_returned ... FAILED
test solution_test::test_clean_line_removes_punctuation ... ok
test solution_test::test_clean_line_trims_the_input ... FAILED
test solution_test::test_correction ... ok
test solution_test::test_correction_fails_to_produce_new_result ... ok
test solution_test::test_correction_normalizes_case ... ok
test solution_test::test_counting ... ok
test solution_test::test_display ... FAILED
test solution_test::test_edits1 ... FAILED
test solution_test::test_edits2 ... FAILED
test solution_test::test_empty_counter ... ok
test solution_test::test_from_empty_str ... ok
test solution_test::test_from_str ... ok
test solution_test::test_known_words ... ok
test solution_test::test_probability ... ok

failures:

---- solution_test::test_best_word_is_returned stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"boot"`,
 right: `"boat"`', tests/solution_test.rs:216:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

---- solution_test::test_clean_line_trims_the_input stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `" foo  "`,
 right: `"foo"`', tests/solution_test.rs:67:5

---- solution_test::test_display stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"WordCounter, total count: 3\none: 1\ntwo: 2\n"`,
 right: `"WordCounter, total count: 3\ntwo: 2\none: 1\n"`', tests/solution_test.rs:52:5

---- solution_test::test_edits1 stdout ----
thread 'main' panicked at 'assertion failed: edits.contains("трип")', tests/solution_test.rs:128:5

---- solution_test::test_edits2 stdout ----
thread 'main' panicked at 'assertion failed: edits.contains("втрий")', tests/solution_test.rs:152:5


failures:
    solution_test::test_best_word_is_returned
    solution_test::test_clean_line_trims_the_input
    solution_test::test_display
    solution_test::test_edits1
    solution_test::test_edits2

test result: FAILED. 10 passed; 5 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--test solution_test'

История (1 версия и 3 коментара)

Димитър качи първо решение на 14.01.2020 16:55 (преди над 5 години)

Базовия тест, който си написал, fail-ва и оттам нататък нашите тестове спират да се изпълняват. Ще взема да ти редактирам теста по някое време и вероятно ще получиш някакви точки.

Все пак, може би нямаше смисъл да пускаш решение, в което има тест, който fail-ва :). Смисъл, можеше да махнеш теста.