Решение на Spell Checker от Митко Чакъров

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

Към профила на Митко Чакъров

Код

/// Тази функция премахва всякакви специални символи от низа, освен:

///

/// - Азбучни символи (`char::is_alphabetical`)

/// - Празни символи (`char::is_whitespace`)

/// - Апостроф и тиренце (`'`, `-`)

///

/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се

/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.

///

/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,

/// basically).

///

pub fn clean_line(input: &str) -> String {

input.trim()

.chars()

.filter(|x| x.is_alphabetic() || x.is_whitespace() || *x == '\'' || *x == '-')

.collect()

}

use std::collections::HashMap;

pub struct WordCounter {

words : HashMap<String, u32>

}

impl WordCounter {

/// Конструира нов `WordCounter` без никакви данни.

///

pub fn new() -> Self {

WordCounter {

words : HashMap::new()

}

}

/// Прочита входния низ, ред по ред, обработва всеки ред с `clean_line`, разбива го на думи и

/// конструира нов WordCounter, който ще брои думите на този низ.

///

/// Нормализира думите по същия начин както `add` по-долу.

///

pub fn from_str(input: &str) -> Self {

let mut word_counter = WordCounter::new();

for word in clean_line(input).split_whitespace() {

word_counter.add(word);

}

word_counter

}

/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.

///

pub fn words(&self) -> Vec<&String> {

let mut v : Vec<&String> = self.words.keys().collect();

v.sort();

v

}

/// Брои думата с WordCounter-а. Очаква се входа да бъде:

///

/// - Изчистен от всякакъв начален и краен whitespace

/// - Сведен до малки букви

pub fn add(&mut self, item: &str) {

let count = self.words.entry(item.trim().to_lowercase()).or_insert(0);

*count += 1;

}

/// Връща колко пъти е бил преброена дадената дума.

///

pub fn get(&self, word: &str) -> u32 {

match self.words.get(word) {

Some(v) => return *v,

None => return 0

}

}

/// Връща колко общо думи са били преброени

pub fn total_count(&self) -> u32 {

self.words.values().sum()

}

}

use std::str;

use std::string::String;

/// Искаме да можем да напечатаме един `WordCounter` с цел дебъгване.

///

/// - Първи ред: `WordCounter, total count: {}`, форматирано с `total_count`.

/// - Останалите редове: Всяка една дума, изчистена както е описано горе с `add`, с брой на

/// срещането ѝ, примерно: "foo: 13"

///

/// Всеки ред се очаква да завършва с `\n`, включително последния. Думите трябва да са сортирани по

/// брой на срещанията, най-честите трябва да са първи.

impl std::fmt::Display for WordCounter {

fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {

let mut string = format!("WordCounter, total count: {}\n", self.total_count());

let mut entries : Vec<(&String, &u32)> = self.words.iter().collect();

entries.sort_by(|a, b| a.1.cmp(b.1).reverse());

for (k, v) in entries {

string.push_str(&format!("{}: {}\n", k, v));

}

write!(f, "{}", string)

}

}

use std::collections::HashSet;

/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги

/// използвате във вашите.

pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";

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

pub struct SpellChecker {

known_text : WordCounter,

alphabet : String

}

impl SpellChecker {

/// Създава нов SpellChecker с дадените параметри:

///

/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната

/// вероятност

/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.

/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.

///

pub fn new(corpus: &str, alphabet: &str) -> Self {

SpellChecker {

known_text: WordCounter::from_str(corpus),

alphabet : alphabet.chars().collect()

}

}

/// Най-вероятната поправка на тази дума. Както описахме по-горе:

///

/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.

/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези

/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.

/// - Пробваме всички възможни други думи на две букви разлика по същия начин.

/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.

///

/// Очакваме trim + downcase на входа, тоест

/// `spell_checker.correction(" Foo ")` е еквивалентно на

/// `spell_checker.correction("foo")`

///

/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха

/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в

/// отделен файл, so here we are.)

///

pub fn correction(&self, word: &str) -> String {

let cleared_input = word.trim().to_lowercase();

let candidates = self.candidates(&cleared_input);

let mut probabilities : Vec<(String, f64)> = Vec::new();

for candidate in candidates {

let prob = self.probability(&candidate);

probabilities.push((candidate, prob));

}

probabilities.sort_by(|a, b| a.partial_cmp(b).unwrap());

probabilities.last().cloned().unwrap().0

}

/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази

/// дума, разделен на броя думи в текста.

///

pub fn probability(&self, word: &str) -> f64 {

self.known_text.get(word) as f64 / self.known_text.total_count() as f64

}

/// Кои думи от този Set са познати (присъстват в подадения корпус)?

///

pub fn known<'a>(&'a self, words: &'a HashSet<String>) -> Vec<&'a String> {

let mut vec = Vec::new();

for word in self.known_text.words() {

if words.contains(word) {

vec.push(word);

}

}

vec

}

/// Всички познати кандидати за поправка на тази дума:

///

/// - Ако думата е позната, директно връщаме вектор с нея.

/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.

/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.

/// - Иначе, връщаме вектор с думата.

///

pub fn candidates(&self, word: &str) -> Vec<String> {

let s = String::from(word);

let mut vec_output : Vec<String> = vec![s];

if self.known_text.get(word) > 0 {

return vec_output

}

let edits_1 = self.edits1(word);

let known_1 = self.known(&edits_1);

let edits_2 = self.edits2(word);

let known_2 = self.known(&edits_2);

for known in known_1 {

vec_output.push(known.clone());

}

for known in known_2 {

vec_output.push(known.clone());

}

// vec_output.append(&mut Vec::from_iter(self.edits1(word).iter().cloned()));

vec_output

}

/// Всички думи, които са на една промяна разстояние от дадената дума:

///

/// - Една буква изтрита на коя да е позиция

/// - Две букви разменени (една до друга)

/// - Една буква от азбуката замества коя да е буква от думата

/// - Една буква от азбуката добавена в думата на която и да е позиция

///

/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,

/// а дубликати не ни интересуват.

///

pub fn edits1(&self, word: &str) -> HashSet<String> {

let mut set = HashSet::new();

let word_size = word.chars().count();

for letter in self.alphabet.chars() {

for i in 0 .. word_size {

set.insert(self.add_at(word, i, letter));

set.insert(self.replace_at(word, i, letter));

}

}

for i in 0 .. word_size {

set.insert(self.remove_at(word, i));

if i != word_size - 1 {

set.insert(self.exchange_at(word, i));

}

}

set

}

fn add_at(&self, word: &str, idx: usize, letter: char) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

if curr == idx {

s.push(letter);

}

s.push(ch);

curr += 1;

}

s

}

fn remove_at(&self, word: &str, idx: usize) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

if curr != idx {

s.push(ch);

}

curr += 1;

}

s

}

fn exchange_at(&self, word: &str, idx: usize) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

s.push(ch);

if curr == idx + 1 {

let next = s.pop().unwrap();

let prev = s.pop().unwrap();

s.push(next);

s.push(prev);

}

curr += 1;

}

s

}

fn replace_at(&self, word: &str, idx: usize, letter: char) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

if curr == idx {

s.push(letter);

}

else {

s.push(ch);

}

curr += 1;

}

s

}

/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на

/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.

///

pub fn edits2(&self, word: &str) -> HashSet<String> {

let e1 = self.edits1(word);

let mut set = HashSet::new();

for word in e1 {

let e2 = self.edits1(&word);

set = set.union(&e2).cloned().collect();

}

set

}

}

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

Compiling solution v0.1.0 (/tmp/d20200114-2173579-6044gr/solution)
    Finished test [unoptimized + debuginfo] target(s) in 4.14s
     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 ... ok
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 ... 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_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_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_edits1
    solution_test::test_edits2

test result: FAILED. 12 passed; 3 failed; 0 ignored; 0 measured; 0 filtered out

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

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

Митко качи решение на 14.01.2020 01:00 (преди над 5 години)

/// Тази функция премахва всякакви специални символи от низа, освен:

///

/// - Азбучни символи (`char::is_alphabetical`)

/// - Празни символи (`char::is_whitespace`)

/// - Апостроф и тиренце (`'`, `-`)

///

/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се

/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.

///

/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,

/// basically).

///

pub fn clean_line(input: &str) -> String {

input.trim()

.chars()

.filter(|x| x.is_alphabetic() || x.is_whitespace() || *x == '\'' || *x == '-')

.collect()

}

use std::collections::HashMap;

pub struct WordCounter {

words : HashMap<String, u32>

}

impl WordCounter {

/// Конструира нов `WordCounter` без никакви данни.

///

pub fn new() -> Self {

WordCounter {

words : HashMap::new()

}

}

/// Прочита входния низ, ред по ред, обработва всеки ред с `clean_line`, разбива го на думи и

/// конструира нов WordCounter, който ще брои думите на този низ.

///

/// Нормализира думите по същия начин както `add` по-долу.

///

pub fn from_str(input: &str) -> Self {

let mut word_counter = WordCounter::new();

for word in clean_line(input).split_whitespace() {

word_counter.add(word);

}

word_counter

}

/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.

///

pub fn words(&self) -> Vec<&String> {

let mut v : Vec<&String> = self.words.keys().collect();

v.sort();

v

}

/// Брои думата с WordCounter-а. Очаква се входа да бъде:

///

/// - Изчистен от всякакъв начален и краен whitespace

/// - Сведен до малки букви

pub fn add(&mut self, item: &str) {

let count = self.words.entry(item.trim().to_lowercase()).or_insert(0);

*count += 1;

}

/// Връща колко пъти е бил преброена дадената дума.

///

pub fn get(&self, word: &str) -> u32 {

match self.words.get(word) {

Some(v) => return *v,

None => return 0

}

}

/// Връща колко общо думи са били преброени

pub fn total_count(&self) -> u32 {

self.words.len() as u32

}

}

use std::str;

use std::string::String;

/// Искаме да можем да напечатаме един `WordCounter` с цел дебъгване.

///

/// - Първи ред: `WordCounter, total count: {}`, форматирано с `total_count`.

/// - Останалите редове: Всяка една дума, изчистена както е описано горе с `add`, с брой на

/// срещането ѝ, примерно: "foo: 13"

///

/// Всеки ред се очаква да завършва с `\n`, включително последния. Думите трябва да са сортирани по

/// брой на срещанията, най-честите трябва да са първи.

impl std::fmt::Display for WordCounter {

fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {

let mut string = format!("WordCounter, total count: {}\n", self.total_count());

let mut entries : Vec<(&String, &u32)> = self.words.iter().collect();

entries.sort_by(|a, b| a.1.cmp(b.1).reverse());

for (k, v) in entries {

string.push_str(&format!("{}: {}\n", k, v));

}

write!(f, "{}", string)

}

}

use std::collections::HashSet;

/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги

/// използвате във вашите.

pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";

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

pub struct SpellChecker {

known_text : WordCounter,

alphabet : String

}

impl SpellChecker {

/// Създава нов SpellChecker с дадените параметри:

///

/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната

/// вероятност

/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.

/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.

///

pub fn new(corpus: &str, alphabet: &str) -> Self {

SpellChecker {

known_text: WordCounter::from_str(corpus),

alphabet : alphabet.chars().collect()

}

}

/// Най-вероятната поправка на тази дума. Както описахме по-горе:

///

/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.

/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези

/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.

/// - Пробваме всички възможни други думи на две букви разлика по същия начин.

/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.

///

/// Очакваме trim + downcase на входа, тоест

/// `spell_checker.correction(" Foo ")` е еквивалентно на

/// `spell_checker.correction("foo")`

///

/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха

/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в

/// отделен файл, so here we are.)

///

pub fn correction(&self, word: &str) -> String {

let cleared_input = word.trim().to_lowercase();

let candidates = self.candidates(&cleared_input);

let mut probabilities : Vec<(String, f64)> = Vec::new();

for candidate in candidates {

let prob = self.probability(&candidate);

probabilities.push((candidate, prob));

}

probabilities.sort_by(|a, b| a.partial_cmp(b).unwrap());

probabilities.last().cloned().unwrap().0

}

/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази

/// дума, разделен на броя думи в текста.

///

pub fn probability(&self, word: &str) -> f64 {

self.known_text.get(word) as f64 / self.known_text.total_count() as f64

}

/// Кои думи от този Set са познати (присъстват в подадения корпус)?

///

pub fn known<'a>(&'a self, words: &'a HashSet<String>) -> Vec<&'a String> {

let mut vec = Vec::new();

for word in self.known_text.words() {

if words.contains(word) {

vec.push(word);

}

}

vec

}

/// Всички познати кандидати за поправка на тази дума:

///

/// - Ако думата е позната, директно връщаме вектор с нея.

/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.

/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.

/// - Иначе, връщаме вектор с думата.

///

pub fn candidates(&self, word: &str) -> Vec<String> {

let s = String::from(word);

let mut vec_output : Vec<String> = vec![s];

if self.known_text.get(word) > 0 {

return vec_output

}

let edits_1 = self.edits1(word);

let known_1 = self.known(&edits_1);

let edits_2 = self.edits2(word);

let known_2 = self.known(&edits_2);

for known in known_1 {

vec_output.push(known.clone());

}

for known in known_2 {

vec_output.push(known.clone());

}

// vec_output.append(&mut Vec::from_iter(self.edits1(word).iter().cloned()));

vec_output

}

/// Всички думи, които са на една промяна разстояние от дадената дума:

///

/// - Една буква изтрита на коя да е позиция

/// - Две букви разменени (една до друга)

/// - Една буква от азбуката замества коя да е буква от думата

/// - Една буква от азбуката добавена в думата на която и да е позиция

///

/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,

/// а дубликати не ни интересуват.

///

pub fn edits1(&self, word: &str) -> HashSet<String> {

let mut set = HashSet::new();

let word_size = word.chars().count();

for letter in self.alphabet.chars() {

for i in 0 .. word_size {

set.insert(self.add_at(word, i, letter));

set.insert(self.replace_at(word, i, letter));

}

}

for i in 0 .. word_size {

set.insert(self.remove_at(word, i));

if i != word_size - 1 {

- set.insert(self.exchnage_at(word, i));

+ set.insert(self.exchange_at(word, i));

}

}

set

}

fn add_at(&self, word: &str, idx: usize, letter: char) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

if curr == idx {

s.push(letter);

}

s.push(ch);

curr += 1;

}

s

}

fn remove_at(&self, word: &str, idx: usize) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

if curr != idx {

s.push(ch);

}

curr += 1;

}

s

}

- fn exchnage_at(&self, word: &str, idx: usize) -> String {

+ fn exchange_at(&self, word: &str, idx: usize) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

- let mut saved = self.alphabet.chars().nth(0).unwrap();

for ch in word.chars() {

- if curr == idx{

- saved = ch;

- }

- else if curr == idx + 1 {

- s.push(ch);

- s.push(saved);

- }

+

+ s.push(ch);

+

+ if curr == idx + 1 {

+ let next = s.pop().unwrap();

+ let prev = s.pop().unwrap();

+

+ s.push(next);

+ s.push(prev);

+ }

curr += 1;

}

s

}

+

fn replace_at(&self, word: &str, idx: usize, letter: char) -> String {

let mut s = String::with_capacity(word.len());

let mut curr = 0;

for ch in word.chars() {

if curr == idx {

s.push(letter);

}

else {

s.push(ch);

}

curr += 1;

}

s

}

/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на

/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.

///

pub fn edits2(&self, word: &str) -> HashSet<String> {

let e1 = self.edits1(word);

let mut set = HashSet::new();

for word in e1 {

let e2 = self.edits1(&word);

set = set.union(&e2).cloned().collect();

}

set

}

}