Решение на Spell Checker от Георги Петков
Резултати
- 13 точки от тестове
- 0 бонус точки
- 13 точки общо
- 10 успешни тест(а)
- 5 неуспешни тест(а)
Код
// Тази функция премахва всякакви специални символи от низа, освен:
//
// - Азбучни символи (`char::is_alphabetical`)
// - Празни символи (`char::is_whitespace`)
// - Апостроф и тиренце (`'`, `-`)
//
// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
//
// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
// basically).
//
pub fn clean_line(input: &str) -> String {
let mut s = String::from(input.trim());
s.retain(|s| char::is_alphabetic(s) || char::is_whitespace(s) || s=='\'' || s=='-');
s
}
#[derive(Clone)]
struct WordCounterPair {
word: String,
counter: u32,
}
pub struct WordCounter {
container: Vec<WordCounterPair>,
total: u32,
}
impl WordCounter {
// Конструира нов `WordCounter` без никакви данни.
//
pub fn new() -> Self {
WordCounter{container: Vec::<WordCounterPair>::new(), total: 0}
}
// Прочита входния низ, ред по ред, обработва всеки ред с `clean_line`, разбива го на думи и
// конструира нов WordCounter, който ще брои думите на този низ.
//
// Нормализира думите по същия начин както `add` по-долу.
//
pub fn from_str(input: &str) -> Self {
let lines: Vec<String> = input.lines().map(|s| clean_line(s)).collect();
let mut wc = WordCounter::new();
for line in lines.iter() {
for word in line.split_whitespace() {
wc.add(word);
}
}
wc
}
// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
//
pub fn words(&self) -> Vec<&String> {
let mut w: Vec<&String> = self.container.iter().map(|i| &i.word).collect();
w.sort();
w
}
// Брои думата с WordCounter-а. Очаква се входа да бъде:
//
// - Изчистен от всякакъв начален и краен whitespace
// - Сведен до малки букви
//
// Тоест:
//
// `counter.add("Foo")` е еквивалентно на
// `counter.add("foo")` е еквивалентно на
// `counter.add(" foo ")`
//
pub fn add(&mut self, item: &str) {
let mut s = String::from(item.trim());
s = s.to_lowercase();
self.total = self.total+1;
let mut found = false;
for pair in self.container.iter_mut() {
if s==pair.word {
found = true;
pair.counter = pair.counter+1;
}
}
if !found {
let p = WordCounterPair {word: s, counter: 1};
self.container.push(p);
}
}
// Връща колко пъти е бил преброена дадената дума.
//
pub fn get(&self, word: &str) -> u32 {
let mut s = String::from(word.trim());
s = s.to_lowercase();
for pair in self.container.iter() {
if pair.word==s {
return pair.counter;
}
}
0
}
// Връща колко общо думи са били преброени. Тоест:
//
// counter.add("foo");
// counter.add("foo");
// counter.add("bar");
//
// се очаква да ни даде `total_count()` 3.
//
pub fn total_count(&self) -> u32 {
self.total
}
}
// Искаме да можем да напечатаме един `WordCounter` с цел дебъгване.
//
// - Първи ред: `WordCounter, total count: {}`, форматирано с `total_count`.
// - Останалите редове: Всяка една дума, изчистена както е описано горе с `add`, с брой на
// срещането ѝ, примерно: "foo: 13"
//
// Всеки ред се очаква да завършва с `\n`, включително последния. Думите трябва да са сортирани по
// брой на срещанията, най-честите трябва да са първи. Примерно:
//
// WordCounter, total count: 25
// foo: 13
// bar: 12
//
use std::fmt;
impl std::fmt::Display for WordCounter {
fn fmt(&self, f: &mut fmt::Formatter) -> std::fmt::Result {
let mut t: std::fmt::Result;
t = writeln!(f, "WordCounter, total count: {}", self.total_count());
let mut pairs = self.container.clone();
pairs.sort_by(|a, b| b.counter.cmp(&a.counter));
for pair in pairs {
t = writeln!(f, "{}: {}", pair.word, pair.counter);
}
t
}
}
use std::collections::HashSet;
// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";
pub struct SpellChecker {
wc: WordCounter,
alphapet: String,
}
impl SpellChecker {
// Създава нов SpellChecker с дадените параметри:
//
// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
// вероятност
// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
// Примерно, да spell-check-ваме български или английски изисква различни азбуки.
//
pub fn new(corpus: &str, alphabet: &str) -> Self {
SpellChecker{wc: WordCounter::from_str(corpus), alphapet: String::from(alphabet)}
}
// Най-вероятната поправка на тази дума. Както описахме по-горе:
//
// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
// думи? Ако да, връщаме тази, която се среща най-често в корпуса.
// - Пробваме всички възможни други думи на две букви разлика по същия начин.
// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
//
// Очакваме trim + downcase на входа, тоест
// `spell_checker.correction(" Foo ")` е еквивалентно на
// `spell_checker.correction("foo")`
//
// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
// отделен файл, so here we are.)
//
pub fn correction(&self, word: &str) -> String {
let mut s = String::from(word.trim());
s = s.to_lowercase();
if self.wc.get(s.as_str())>0 {
return s;
}
let e1 = self.edits1(s.as_str());
let mut max: u32 = 0;
let mut found = s.clone();
for w in e1 {
let occurrences = self.wc.get(&w);
if occurrences>max {
found = w;
max = occurrences;
}
}
if max>0 {
return found;
}
let e2 = self.edits2(s.as_str());
for w in e2 {
let occurrences = self.wc.get(&w);
if occurrences>max {
found = w;
max = occurrences;
}
}
found
}
// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
// дума, разделен на броя думи в текста.
//
pub fn probability(&self, word: &str) -> f64 {
let total = self.wc.total_count() as f64;
let occurrences = self.wc.get(word) as f64;
occurrences/total
}
// Кои думи от този Set са познати (присъстват в подадения корпус)?
//
pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
let mut v = Vec::<&'a String>::new();
for word in words.iter() {
if self.wc.get(word)>0 {
v.push(word);
}
}
v
}
// Всички познати кандидати за поправка на тази дума:
//
// - Ако думата е позната, директно връщаме вектор с нея.
// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
// - Иначе, връщаме вектор с думата.
//
pub fn candidates(&self, word: &str) -> Vec<String> {
if self.wc.get(word) > 0 {
return vec![String::from(word)];
}
let e1 = self.edits1(word);
let mut v = Vec::<String>::new();
for w in e1.iter() {
if self.wc.get(w) > 0 {
v.push(w.to_string());
}
}
if v.len() > 0 {
return v;
}
let e2 = self.edits2(word);
for w in e2.iter() {
if self.wc.get(w) > 0 {
v.push(w.to_string());
}
}
v
}
// Всички думи, които са на една промяна разстояние от дадената дума:
//
// - Една буква изтрита на коя да е позиция
// - Две букви разменени (една до друга)
// - Една буква от азбуката замества коя да е буква от думата
// - Една буква от азбуката добавена в думата на която и да е позиция
//
// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
// а дубликати не ни интересуват.
//
pub fn edits1(&self, word: &str) -> HashSet<String> {
let mut h = HashSet::<String>::new();
let len = word.len();
for i in 0..len {
let mut s = String::from(word);
s.remove(i);
h.insert(s);
}
for i in 0..(len-1) {
let mut s = String::from(word);
let removed = s.remove(i);
s.insert(i+1, removed);
h.insert(s);
}
for ch in self.alphapet.chars() {
for i in 0..len {
let mut s = String::from(word);
s.remove(i);
s.insert(i, ch);
h.insert(s);
}
}
for ch in self.alphapet.chars() {
for i in 0..(len+1) {
let mut s = String::from(word);
s.insert(i, ch);
h.insert(s);
}
}
h
}
// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
//
pub fn edits2(&self, word: &str) -> HashSet<String> {
let edits1_hs = self.edits1(word);
let mut h = HashSet::<String>::new();
for item in edits1_hs.iter() {
let set_from_item = self.edits1(item);
for w in set_from_item.iter() {
h.insert(w.to_string());
}
}
h
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20200114-2173579-1m10dbk/solution)
Finished test [unoptimized + debuginfo] target(s) in 4.48s
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 ... ok
test solution_test::test_clean_line_removes_punctuation ... ok
test solution_test::test_clean_line_trims_the_input ... ok
test solution_test::test_correction ... FAILED
test solution_test::test_correction_fails_to_produce_new_result ... FAILED
test solution_test::test_correction_normalizes_case ... FAILED
test solution_test::test_counting ... ok
test solution_test::test_display ... ok
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_correction stdout ----
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'л' (bytes 0..2) of `либоф`', src/libcore/str/mod.rs:2068:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
---- solution_test::test_correction_fails_to_produce_new_result stdout ----
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'л' (bytes 0..2) of `либоф`', src/libcore/str/mod.rs:2068:5
---- solution_test::test_correction_normalizes_case stdout ----
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'л' (bytes 0..2) of `либоф`', src/libcore/str/mod.rs:2068:5
---- solution_test::test_edits1 stdout ----
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'т' (bytes 0..2) of `три`', src/libcore/str/mod.rs:2068:5
---- solution_test::test_edits2 stdout ----
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'т' (bytes 0..2) of `три`', src/libcore/str/mod.rs:2068:5
failures:
solution_test::test_correction
solution_test::test_correction_fails_to_produce_new_result
solution_test::test_correction_normalizes_case
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'