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

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

Решение на Spell Checker от Любослав Карев

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

Към профила на Любослав Карев

Резултати

  • 9 точки от тестове
  • 0 бонус точки
  • 9 точки общо
  • 7 успешни тест(а)
  • 8 неуспешни тест(а)

Код

use std::collections::{HashSet, HashMap};
use std::fmt;
/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
/// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";
/// Тази функция премахва всякакви специални символи от низа, освен:
///
/// - Азбучни символи (`char::is_alphabetical`)
/// - Празни символи (`char::is_whitespace`)
/// - Апостроф и тиренце (`'`, `-`)
///
/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
///
/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
/// basically).
///
pub fn clean_line(input: &str) -> String {
let mut result: String = String::from("");
for letter in input.trim().chars()
{
if letter.is_alphabetic() || letter.is_whitespace()
{
result.push(letter);
}
}
result
}
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 result: WordCounter = WordCounter { words: HashMap::new() };
let lines: Vec<&str> = input.split('\n').collect();
for line in lines {
let line_clean: String = clean_line(line);
let words: Vec<&str> = line_clean.split(' ').collect();
for word in words {
if word.len() > 0{
result.add(word.to_lowercase().as_str());
}
}
}
result
}
/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
///
pub fn words(&self) -> Vec<&String> {
let mut result: Vec<&String> = Vec::new();
for item in self.words.keys() {
result.push(item)
}
result.sort();
result
}
/// Брои думата с WordCounter-а. Очаква се входа да бъде:
///
/// - Изчистен от всякакъв начален и краен whitespace
/// - Сведен до малки букви
///
/// Тоест:
///
/// `counter.add("Foo")` е еквивалентно на
/// `counter.add("foo")` е еквивалентно на
/// `counter.add(" foo ")`
///
pub fn add(&mut self, item: &str) {
let items_as_string = String::from(item.trim().to_lowercase());
match self.words.get_mut(items_as_string.as_str()) {
Some(count) => {
*count = *count + 1
}
None => {
self.words.insert(items_as_string, 1);
}
};
}
/// Връща колко пъти е бил преброена дадената дума.
///
pub fn get(&self, word: &str) -> u32 {
match self.words.get(word) {
Some(count) => *count,
None => 0
}
}
/// Връща колко общо думи са били преброени. Тоест:
///
/// `counter.add("foo");`
/// `counter.add("foo");`
/// `counter.add("bar");`
///
/// се очаква да ни даде `total_count()` 3.
///
pub fn total_count(&self) -> u32 {
self.words.len() as u32
}
}
/// Искаме да можем да напечатаме един `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 {
let mut to_write: String = String::from("");
to_write.push_str(self.total_count().to_string().as_str());
to_write.push_str("\n");
for word in self.words.keys() {
to_write.push_str((word.clone() + ":" + word.to_string().as_str().clone() + "\n").as_str().clone());
};
write!(f, "WordCounter, total count: {}", to_write)
}
}
pub struct SpellChecker {
corpus: String,
alphabet: String,
counter: WordCounter,
}
/// - Една буква от азбуката добавена в думата на която и да е позиция
fn removed_letter(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len(){
let removed_letter = word_as_vec[index];
word_as_vec.remove(index);
result.insert(word_as_vec.iter().collect());
word_as_vec.insert(index, removed_letter);
}
result
}
fn swapped_letters(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len() - 1{
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
result.insert(word_as_vec.iter().collect());
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
}
result
}
fn letter_changed(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
let original_letter = word_as_vec[position_to_be_changed];
for new_letter in &alphabet_vector{
word_as_vec[position_to_be_changed] = new_letter.clone();
result.insert(word_as_vec.iter().collect());
}
word_as_vec[position_to_be_changed] = original_letter;
}
result
}
fn add_letter(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
for new_letter in &alphabet_vector{
word_as_vec.insert(position_to_be_changed, new_letter.clone());
result.insert(word_as_vec.iter().collect());
word_as_vec.remove(position_to_be_changed);
}
}
result
}
impl SpellChecker {
/// Създава нов SpellChecker с дадените параметри:
///
/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
/// вероятност
/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.
///
pub fn new(corpus: &str, alphabet: &str) -> Self {
let result = SpellChecker {
corpus: String::from(corpus),
alphabet: String::from(alphabet),
counter: WordCounter::from_str(corpus),
};
result
}
/// Най-вероятната поправка на тази дума. Както описахме по-горе:
///
/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.
/// - Пробваме всички възможни други думи на две букви разлика по същия начин.
/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
///
/// Очакваме trim + downcase на входа, тоест
/// `spell_checker.correction(" Foo ")` е еквивалентно на
/// `spell_checker.correction("foo")`
///
/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
/// отделен файл, so here we are.)
///
pub fn correction(&self, word: &str) -> String {
let corrections:Vec<String> = self.candidates(clean_line(word).as_str());
let mut corrections_probability: Vec<(String, f64)> = vec![];
for corrected_word in corrections{
corrections_probability.push((corrected_word.clone(), self.probability(corrected_word.as_str())));
}
corrections_probability.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
corrections_probability[corrections_probability.len() - 1].0.clone()
}
/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
/// дума, разделен на броя думи в текста.
///
pub fn probability(&self, word: &str) -> f64 {
match self.counter.words.get(word) {
Some(count) => return *count as f64 / self.counter.words.len() as f64,
None => return 0 as f64
}
}
/// Кои думи от този Set са познати (присъстват в подадения корпус)?
///
pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
let mut result: Vec<&'a String> = vec![];
for word in words{
if self.counter.words.contains_key(word){
result.push(word);
}
}
result
}
/// Всички познати кандидати за поправка на тази дума:
///
/// - Ако думата е позната, директно връщаме вектор с нея.
/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
/// - Иначе, връщаме вектор с думата.
///
pub fn candidates(&self, word: &str) -> Vec<String> {
let mut result:Vec<String> = vec![];
let mut word_only:HashSet<String> = HashSet::new();
word_only.insert(word.to_string());
for candidate in self.known(&word_only){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits1(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits2(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
result.push(word.to_string());
result
}
/// Всички думи, които са на една промяна разстояние от дадената дума:
///
/// - Една буква изтрита на коя да е позиция
/// - Две букви разменени (една до друга)
/// - Една буква от азбуката замества коя да е буква от думата
/// - Една буква от азбуката добавена в думата на която и да е позиция
///
/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
/// а дубликати не ни интересуват.
///
pub fn edits1(&self, word: &str) -> HashSet<String> {
let mut result:HashSet<String> = HashSet::new();
result.extend(removed_letter(word));
result.extend(swapped_letters(word));
result.extend(letter_changed(word, self.alphabet.as_str()));
result.extend(add_letter(word, self.alphabet.as_str()));
result
}
/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
///
pub fn edits2(&self, word: &str) -> HashSet<String> {
let edit_1: HashSet<String> = self.edits1(word);
let mut result:HashSet<String> = HashSet::new();
for edited in edit_1{
result.extend(removed_letter(edited.as_str()));
result.extend(swapped_letters(edited.as_str()));
result.extend(letter_changed(edited.as_str(), self.alphabet.as_str()));
result.extend(add_letter(edited.as_str(), self.alphabet.as_str()));
}
result
}
}
#[cfg(test)]
mod tests {
use crate::*;
use std::fs;
#[test]
fn test_basic() {
let line = String::from(" Foo Bar ");
assert_eq!("Foo Bar", clean_line(&line));
let mut counter = WordCounter::new();
assert_eq!(counter.words(), WordCounter::from_str("").words());
assert_eq!(counter.get("word"), 0);
assert_eq!(counter.total_count(), 0);
assert_eq!(format!("{}", counter), "WordCounter, total count: 0\n");
counter.add("word");
let spell_checker = SpellChecker::new("foo bar", ALPHABET_EN);
assert_eq!(spell_checker.correction("foo"), "foo");
assert!(spell_checker.probability("foo") > 0.0);
assert_eq!(spell_checker.known(&HashSet::new()).len(), 0);
assert!(spell_checker.candidates("foo").len() > 0);
assert!(spell_checker.edits1("foo").len() > 0);
assert!(spell_checker.edits2("foo").len() > 0);
}
//Тези тестове имат нужда от допълнителни файлове
/*#[test]
fn test_advanced() {
//Този тест ще използва файла big.txt -> https://norvig.com/big.txt
//Този тест е копиран от https://norvig.com/spell-correct.html
let contents = fs::read_to_string("big.txt")
.expect("Something went wrong reading the file");
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_EN);
assert_eq!(spell_checker.known(&spell_checker.edits1("somthing")).len(), 2);
assert_eq!(spell_checker.known(&spell_checker.edits2("somthing")).len(), 8);
assert_eq!(spell_checker.correction("speling"), "spelling");
assert_eq!(spell_checker.correction("korrectud"), "corrected");
assert_eq!(spell_checker.correction("bycycle"), "bicycle");
assert_eq!(spell_checker.correction("inconvient"), "inconvenient");
assert_eq!(spell_checker.correction("arrainged"), "arranged");
assert_eq!(spell_checker.correction("peotry"), "poetry");
assert_eq!(spell_checker.correction("peotryy"), "poetry");
assert_eq!(spell_checker.correction("word"), "word");
}
#[test]
fn test_bg()
{
//За корпус е използвана следната книга
//Andi_Ueyr_-_Marsianetsyt.txt
let contents = fs::read_to_string("Andi_Ueyr_-_Marsianetsyt.txt")
.expect("Something went wrong reading the file");
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_BG);
assert_eq!(spell_checker.correction("грежка"), "грешка");
assert_eq!(spell_checker.correction("търссене"), "търсене");
assert_eq!(spell_checker.correction("тои"), "той");
assert_eq!(spell_checker.correction("въда"), "вода");
assert_eq!(spell_checker.correction("Мерс"), "марс");
assert_eq!(spell_checker.correction(" св "), "се");
assert_eq!(spell_checker.correction("дума"), "дума");
}*/
}

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

Compiling solution v0.1.0 (/tmp/d20200114-2173579-tsyolt/solution)
warning: field is never used: `corpus`
   --> src/lib.rs:158:5
    |
158 |     corpus: String,
    |     ^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: unused import: `std::fs`
   --> src/lib.rs:387:9
    |
387 |     use std::fs;
    |         ^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: field is never used: `corpus`
   --> src/lib.rs:158:5
    |
158 |     corpus: String,
    |     ^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

    Finished test [unoptimized + debuginfo] target(s) in 6.00s
     Running target/debug/deps/solution-a73e64ec87929bd0

running 1 test
test tests::test_basic ... ok

test result: ok. 1 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 ... FAILED
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 ... FAILED
test solution_test::test_correction_normalizes_case ... FAILED
test solution_test::test_counting ... FAILED
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 ... FAILED

failures:

---- solution_test::test_clean_line_removes_punctuation stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"ала  баланица"`,
 right: `"ала  бала\'ница"`', tests/solution_test.rs:61: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 'assertion failed: `(left == right)`
  left: `"Либоф"`,
 right: `"либоф"`', tests/solution_test.rs:198:5

---- solution_test::test_correction_normalizes_case stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"Либоф"`,
 right: `"любов"`', tests/solution_test.rs:188:5

---- solution_test::test_counting stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `3`,
 right: `6`', tests/solution_test.rs:40:5

---- solution_test::test_display stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"WordCounter, total count: 1\none:one\n"`,
 right: `"WordCounter, total count: 1\none: 1\n"`', tests/solution_test.rs:49: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

---- solution_test::test_probability stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `1.0`,
 right: `0.5`', tests/solution_test.rs:94:5


failures:
    solution_test::test_clean_line_removes_punctuation
    solution_test::test_correction_fails_to_produce_new_result
    solution_test::test_correction_normalizes_case
    solution_test::test_counting
    solution_test::test_display
    solution_test::test_edits1
    solution_test::test_edits2
    solution_test::test_probability

test result: FAILED. 7 passed; 8 failed; 0 ignored; 0 measured; 0 filtered out

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

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

Любослав качи първо решение на 14.01.2020 11:58 (преди над 5 години)

Любослав качи решение на 14.01.2020 12:56 (преди над 5 години)

use std::collections::{HashSet, HashMap};
use std::fmt;
use std::borrow::Borrow;
use std::cmp::{min, max};
use std::mem::swap;
use std::hash::Hash;
/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
/// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";
/// Тази функция премахва всякакви специални символи от низа, освен:
///
/// - Азбучни символи (`char::is_alphabetical`)
/// - Празни символи (`char::is_whitespace`)
/// - Апостроф и тиренце (`'`, `-`)
///
/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
///
/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
/// basically).
///
pub fn clean_line(input: &str) -> String {
let mut result: String = String::from("");
for letter in input.trim().chars()
{
if letter.is_alphabetic() || letter.is_whitespace()
{
result.push(letter);
}
}
result
}
fn convert_word_to_numbers(word: &str, alphabet: &str) -> Vec<u32>
{
let mut letter_number_map: HashMap<char, u32> = HashMap::new();
let mut index: u32 = 0;
for letter in alphabet.chars() {
letter_number_map.insert(letter, index);
index += 1;
}
let mut result: Vec<u32> = vec![];
for letter in word.chars() {
match letter_number_map.get(&letter) {
Some(val) => result.push(*val),
None => {}
}
}
result
}
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 result: WordCounter = WordCounter { words: HashMap::new() };
let lines: Vec<&str> = input.split('\n').collect();
for line in lines {
let line_clean: String = clean_line(line);
let words: Vec<&str> = line_clean.split(' ').collect();
for word in words {
if word.len() > 0{
- result.add(word);
+ result.add(word.to_lowercase().as_str());
}
}
}
result
}
/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
///
pub fn words(&self) -> Vec<&String> {
let mut result: Vec<&String> = Vec::new();
for item in self.words.keys() {
result.push(item)
}
result.sort();
result
}
/// Брои думата с WordCounter-а. Очаква се входа да бъде:
///
/// - Изчистен от всякакъв начален и краен whitespace
/// - Сведен до малки букви
///
/// Тоест:
///
/// `counter.add("Foo")` е еквивалентно на
/// `counter.add("foo")` е еквивалентно на
/// `counter.add(" foo ")`
///
pub fn add(&mut self, item: &str) {
let items_as_string = String::from(item);
items_as_string.trim();
items_as_string.to_lowercase();
match self.words.get_mut(items_as_string.as_str()) {
Some(count) => {
*count = *count + 1
}
None => {
self.words.insert(items_as_string, 1);
}
};
}
/// Връща колко пъти е бил преброена дадената дума.
///
pub fn get(&self, word: &str) -> u32 {
match self.words.get(word) {
Some(count) => *count,
None => 0
}
}
/// Връща колко общо думи са били преброени. Тоест:
///
/// `counter.add("foo");`
/// `counter.add("foo");`
/// `counter.add("bar");`
///
/// се очаква да ни даде `total_count()` 3.
///
pub fn total_count(&self) -> u32 {
self.words.len() as u32
}
}
/// Искаме да можем да напечатаме един `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 {
let mut to_write: String = String::from("");
to_write.push_str(self.total_count().to_string().as_str());
to_write.push_str("\n");
for word in self.words.keys() {
to_write.push_str((word.clone() + ":" + word.to_string().as_str().clone() + "\n").as_str().clone());
};
write!(f, "WordCounter, total count: {}", to_write)
}
}
pub struct SpellChecker {
corpus: String,
alphabet: String,
counter: WordCounter,
}
/// - Една буква от азбуката добавена в думата на която и да е позиция
fn removed_letter(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
+ let mut word_as_vec: Vec<char> = word.chars().collect();
- for index in 0..word.len(){
- let parts = word.split_at(index);
- let mut new_word = String::from(parts.0);
- new_word.push_str(parts.1.split_at(1).1);
- result.insert(new_word);
+ for index in 0..word_as_vec.len(){
+ let removed_letter = word_as_vec[index];
+ word_as_vec.remove(index);
+ result.insert(word_as_vec.iter().collect());
+ word_as_vec.insert(index, removed_letter);
}
result
}
fn swapped_letters(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len() - 1{
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
result.insert(word_as_vec.iter().collect());
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
}
result
}
fn letter_changed(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
let original_letter = word_as_vec[position_to_be_changed];
for new_letter in &alphabet_vector{
word_as_vec[position_to_be_changed] = new_letter.clone();
result.insert(word_as_vec.iter().collect());
}
word_as_vec[position_to_be_changed] = original_letter;
}
result
}
fn add_letter(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
for new_letter in &alphabet_vector{
word_as_vec.insert(position_to_be_changed, new_letter.clone());
result.insert(word_as_vec.iter().collect());
word_as_vec.remove(position_to_be_changed);
}
}
result
}
impl SpellChecker {
/// Създава нов SpellChecker с дадените параметри:
///
/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
/// вероятност
/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.
///
pub fn new(corpus: &str, alphabet: &str) -> Self {
let result = SpellChecker {
corpus: String::from(corpus),
alphabet: String::from(alphabet),
counter: WordCounter::from_str(corpus),
};
result
}
/// Най-вероятната поправка на тази дума. Както описахме по-горе:
///
/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.
/// - Пробваме всички възможни други думи на две букви разлика по същия начин.
/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
///
/// Очакваме trim + downcase на входа, тоест
/// `spell_checker.correction(" Foo ")` е еквивалентно на
/// `spell_checker.correction("foo")`
///
/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
/// отделен файл, so here we are.)
///
pub fn correction(&self, word: &str) -> String {
- let corrections:Vec<String> = self.candidates(word);
+ let corrections:Vec<String> = self.candidates(clean_line(word).as_str());
let mut corrections_probability: Vec<(String, f64)> = vec![];
for corrected_word in corrections{
corrections_probability.push((corrected_word.clone(), self.probability(corrected_word.as_str())));
}
corrections_probability.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
- corrections_probability[0].0.clone()
+ corrections_probability[corrections_probability.len() - 1].0.clone()
}
/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
/// дума, разделен на броя думи в текста.
///
pub fn probability(&self, word: &str) -> f64 {
match self.counter.words.get(word) {
Some(count) => return *count as f64 / self.counter.words.len() as f64,
None => return 0 as f64
}
}
/// Кои думи от този Set са познати (присъстват в подадения корпус)?
///
pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
let mut result: Vec<&'a String> = vec![];
for word in words{
if self.counter.words.contains_key(word){
result.push(word);
}
}
result
}
/// Всички познати кандидати за поправка на тази дума:
///
/// - Ако думата е позната, директно връщаме вектор с нея.
/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
/// - Иначе, връщаме вектор с думата.
///
pub fn candidates(&self, word: &str) -> Vec<String> {
let mut result:Vec<String> = vec![];
let mut word_only:HashSet<String> = HashSet::new();
word_only.insert(word.to_string());
for candidate in self.known(&word_only){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits1(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits2(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
result.push(word.to_string());
result
}
/// Всички думи, които са на една промяна разстояние от дадената дума:
///
/// - Една буква изтрита на коя да е позиция
/// - Две букви разменени (една до друга)
/// - Една буква от азбуката замества коя да е буква от думата
/// - Една буква от азбуката добавена в думата на която и да е позиция
///
/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
/// а дубликати не ни интересуват.
///
pub fn edits1(&self, word: &str) -> HashSet<String> {
let mut result:HashSet<String> = HashSet::new();
result.extend(removed_letter(word));
result.extend(swapped_letters(word));
result.extend(letter_changed(word, self.alphabet.as_str()));
result.extend(add_letter(word, self.alphabet.as_str()));
result
}
/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
///
pub fn edits2(&self, word: &str) -> HashSet<String> {
let edit_1: HashSet<String> = self.edits1(word);
let mut result:HashSet<String> = HashSet::new();
for edited in edit_1{
result.extend(removed_letter(edited.as_str()));
result.extend(swapped_letters(edited.as_str()));
result.extend(letter_changed(edited.as_str(), self.alphabet.as_str()));
result.extend(add_letter(edited.as_str(), self.alphabet.as_str()));
}
result
}
}
#[cfg(test)]
mod tests {
use crate::*;
use std::fs;
#[test]
fn test_basic() {
let line = String::from(" Foo Bar ");
assert_eq!("Foo Bar", clean_line(&line));
let mut counter = WordCounter::new();
assert_eq!(counter.words(), WordCounter::from_str("").words());
assert_eq!(counter.get("word"), 0);
assert_eq!(counter.total_count(), 0);
assert_eq!(format!("{}", counter), "WordCounter, total count: 0\n");
counter.add("word");
let spell_checker = SpellChecker::new("foo bar", ALPHABET_EN);
assert_eq!(spell_checker.correction("foo"), "foo");
assert!(spell_checker.probability("foo") > 0.0);
assert_eq!(spell_checker.known(&HashSet::new()).len(), 0);
assert!(spell_checker.candidates("foo").len() > 0);
assert!(spell_checker.edits1("foo").len() > 0);
assert!(spell_checker.edits2("foo").len() > 0);
}
#[test]
- fn test_advanced(){
+ fn test_advanced() {
//Този тест ще използва файла big.txt -> https://norvig.com/big.txt
//Този тест е копиран от https://norvig.com/spell-correct.html
let contents = fs::read_to_string("big.txt")
.expect("Something went wrong reading the file");
- let word_counter = WordCounter::from_str(contents.as_str());
-
- println!("arraigned - {}", word_counter.words["arraigned"]);
- println!("arraigned - {}", word_counter.words["arranged"]);
-
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_EN);
assert_eq!(spell_checker.known(&spell_checker.edits1("somthing")).len(), 2);
assert_eq!(spell_checker.known(&spell_checker.edits2("somthing")).len(), 8);
assert_eq!(spell_checker.correction("speling"), "spelling");
assert_eq!(spell_checker.correction("korrectud"), "corrected");
- assert_eq!(spell_checker.correction("bycycle") , "bicycle");
- // assert_eq!(spell_checker.correction("inconvient"),"inconvenient");
+ assert_eq!(spell_checker.correction("bycycle"), "bicycle");
+ assert_eq!(spell_checker.correction("inconvient"), "inconvenient");
assert_eq!(spell_checker.correction("arrainged"), "arranged");
assert_eq!(spell_checker.correction("peotry"), "poetry");
assert_eq!(spell_checker.correction("peotryy"), "poetry");
assert_eq!(spell_checker.correction("word"), "word");
+ }
+ #[test]
+ fn test_bg()
+ {
+ //За корпус е използвана следната книга
+ //Andi_Ueyr_-_Marsianetsyt.txt
+ let contents = fs::read_to_string("Andi_Ueyr_-_Marsianetsyt.txt")
+ .expect("Something went wrong reading the file");
+
+ let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_BG);
+ let word_counter = WordCounter::from_str(contents.as_str());
+
+ assert_eq!(spell_checker.correction("грежка"), "грешка");
+ assert_eq!(spell_checker.correction("търссене"), "търсене");
+ assert_eq!(spell_checker.correction("тои"), "той");
+ assert_eq!(spell_checker.correction("въда"), "вода");
+ assert_eq!(spell_checker.correction("Мерс"), "марс");
+ assert_eq!(spell_checker.correction(" св "), "се");
+ assert_eq!(spell_checker.correction("дума"), "дума");
}
}

Любослав качи решение на 14.01.2020 13:10 (преди над 5 години)

use std::collections::{HashSet, HashMap};
use std::fmt;
-use std::borrow::Borrow;
-use std::cmp::{min, max};
-use std::mem::swap;
-use std::hash::Hash;
/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
/// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";
/// Тази функция премахва всякакви специални символи от низа, освен:
///
/// - Азбучни символи (`char::is_alphabetical`)
/// - Празни символи (`char::is_whitespace`)
/// - Апостроф и тиренце (`'`, `-`)
///
/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
///
/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
/// basically).
///
pub fn clean_line(input: &str) -> String {
let mut result: String = String::from("");
for letter in input.trim().chars()
{
if letter.is_alphabetic() || letter.is_whitespace()
{
result.push(letter);
}
}
result
}
-fn convert_word_to_numbers(word: &str, alphabet: &str) -> Vec<u32>
-{
- let mut letter_number_map: HashMap<char, u32> = HashMap::new();
- let mut index: u32 = 0;
- for letter in alphabet.chars() {
- letter_number_map.insert(letter, index);
- index += 1;
- }
- let mut result: Vec<u32> = vec![];
- for letter in word.chars() {
- match letter_number_map.get(&letter) {
- Some(val) => result.push(*val),
- None => {}
- }
- }
-
- result
-}
-
-
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 result: WordCounter = WordCounter { words: HashMap::new() };
let lines: Vec<&str> = input.split('\n').collect();
for line in lines {
let line_clean: String = clean_line(line);
let words: Vec<&str> = line_clean.split(' ').collect();
for word in words {
if word.len() > 0{
result.add(word.to_lowercase().as_str());
}
}
}
result
}
/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
///
pub fn words(&self) -> Vec<&String> {
let mut result: Vec<&String> = Vec::new();
for item in self.words.keys() {
result.push(item)
}
result.sort();
result
}
/// Брои думата с WordCounter-а. Очаква се входа да бъде:
///
/// - Изчистен от всякакъв начален и краен whitespace
/// - Сведен до малки букви
///
/// Тоест:
///
/// `counter.add("Foo")` е еквивалентно на
/// `counter.add("foo")` е еквивалентно на
/// `counter.add(" foo ")`
///
pub fn add(&mut self, item: &str) {
- let items_as_string = String::from(item);
- items_as_string.trim();
- items_as_string.to_lowercase();
+ let items_as_string = String::from(item.trim().to_lowercase());
match self.words.get_mut(items_as_string.as_str()) {
Some(count) => {
*count = *count + 1
}
None => {
self.words.insert(items_as_string, 1);
}
};
}
/// Връща колко пъти е бил преброена дадената дума.
///
pub fn get(&self, word: &str) -> u32 {
match self.words.get(word) {
Some(count) => *count,
None => 0
}
}
/// Връща колко общо думи са били преброени. Тоест:
///
/// `counter.add("foo");`
/// `counter.add("foo");`
/// `counter.add("bar");`
///
/// се очаква да ни даде `total_count()` 3.
///
pub fn total_count(&self) -> u32 {
self.words.len() as u32
}
}
/// Искаме да можем да напечатаме един `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 {
let mut to_write: String = String::from("");
to_write.push_str(self.total_count().to_string().as_str());
to_write.push_str("\n");
for word in self.words.keys() {
to_write.push_str((word.clone() + ":" + word.to_string().as_str().clone() + "\n").as_str().clone());
};
write!(f, "WordCounter, total count: {}", to_write)
}
}
pub struct SpellChecker {
corpus: String,
alphabet: String,
counter: WordCounter,
}
/// - Една буква от азбуката добавена в думата на която и да е позиция
fn removed_letter(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len(){
let removed_letter = word_as_vec[index];
word_as_vec.remove(index);
result.insert(word_as_vec.iter().collect());
word_as_vec.insert(index, removed_letter);
}
result
}
fn swapped_letters(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len() - 1{
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
result.insert(word_as_vec.iter().collect());
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
}
result
}
fn letter_changed(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
let original_letter = word_as_vec[position_to_be_changed];
for new_letter in &alphabet_vector{
word_as_vec[position_to_be_changed] = new_letter.clone();
result.insert(word_as_vec.iter().collect());
}
word_as_vec[position_to_be_changed] = original_letter;
}
result
}
fn add_letter(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
for new_letter in &alphabet_vector{
word_as_vec.insert(position_to_be_changed, new_letter.clone());
result.insert(word_as_vec.iter().collect());
word_as_vec.remove(position_to_be_changed);
}
}
result
}
impl SpellChecker {
/// Създава нов SpellChecker с дадените параметри:
///
/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
/// вероятност
/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.
///
pub fn new(corpus: &str, alphabet: &str) -> Self {
let result = SpellChecker {
corpus: String::from(corpus),
alphabet: String::from(alphabet),
counter: WordCounter::from_str(corpus),
};
result
}
/// Най-вероятната поправка на тази дума. Както описахме по-горе:
///
/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.
/// - Пробваме всички възможни други думи на две букви разлика по същия начин.
/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
///
/// Очакваме trim + downcase на входа, тоест
/// `spell_checker.correction(" Foo ")` е еквивалентно на
/// `spell_checker.correction("foo")`
///
/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
/// отделен файл, so here we are.)
///
pub fn correction(&self, word: &str) -> String {
let corrections:Vec<String> = self.candidates(clean_line(word).as_str());
let mut corrections_probability: Vec<(String, f64)> = vec![];
for corrected_word in corrections{
corrections_probability.push((corrected_word.clone(), self.probability(corrected_word.as_str())));
}
corrections_probability.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
corrections_probability[corrections_probability.len() - 1].0.clone()
}
/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
/// дума, разделен на броя думи в текста.
///
pub fn probability(&self, word: &str) -> f64 {
match self.counter.words.get(word) {
Some(count) => return *count as f64 / self.counter.words.len() as f64,
None => return 0 as f64
}
}
/// Кои думи от този Set са познати (присъстват в подадения корпус)?
///
pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
let mut result: Vec<&'a String> = vec![];
for word in words{
if self.counter.words.contains_key(word){
result.push(word);
}
}
result
}
/// Всички познати кандидати за поправка на тази дума:
///
/// - Ако думата е позната, директно връщаме вектор с нея.
/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
/// - Иначе, връщаме вектор с думата.
///
pub fn candidates(&self, word: &str) -> Vec<String> {
let mut result:Vec<String> = vec![];
let mut word_only:HashSet<String> = HashSet::new();
word_only.insert(word.to_string());
for candidate in self.known(&word_only){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits1(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits2(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
result.push(word.to_string());
result
}
/// Всички думи, които са на една промяна разстояние от дадената дума:
///
/// - Една буква изтрита на коя да е позиция
/// - Две букви разменени (една до друга)
/// - Една буква от азбуката замества коя да е буква от думата
/// - Една буква от азбуката добавена в думата на която и да е позиция
///
/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
/// а дубликати не ни интересуват.
///
pub fn edits1(&self, word: &str) -> HashSet<String> {
let mut result:HashSet<String> = HashSet::new();
result.extend(removed_letter(word));
result.extend(swapped_letters(word));
result.extend(letter_changed(word, self.alphabet.as_str()));
result.extend(add_letter(word, self.alphabet.as_str()));
result
}
/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
///
pub fn edits2(&self, word: &str) -> HashSet<String> {
let edit_1: HashSet<String> = self.edits1(word);
let mut result:HashSet<String> = HashSet::new();
for edited in edit_1{
result.extend(removed_letter(edited.as_str()));
result.extend(swapped_letters(edited.as_str()));
result.extend(letter_changed(edited.as_str(), self.alphabet.as_str()));
result.extend(add_letter(edited.as_str(), self.alphabet.as_str()));
}
result
}
}
#[cfg(test)]
mod tests {
use crate::*;
use std::fs;
#[test]
fn test_basic() {
let line = String::from(" Foo Bar ");
assert_eq!("Foo Bar", clean_line(&line));
let mut counter = WordCounter::new();
assert_eq!(counter.words(), WordCounter::from_str("").words());
assert_eq!(counter.get("word"), 0);
assert_eq!(counter.total_count(), 0);
assert_eq!(format!("{}", counter), "WordCounter, total count: 0\n");
counter.add("word");
let spell_checker = SpellChecker::new("foo bar", ALPHABET_EN);
assert_eq!(spell_checker.correction("foo"), "foo");
assert!(spell_checker.probability("foo") > 0.0);
assert_eq!(spell_checker.known(&HashSet::new()).len(), 0);
assert!(spell_checker.candidates("foo").len() > 0);
assert!(spell_checker.edits1("foo").len() > 0);
assert!(spell_checker.edits2("foo").len() > 0);
}
#[test]
fn test_advanced() {
//Този тест ще използва файла big.txt -> https://norvig.com/big.txt
//Този тест е копиран от https://norvig.com/spell-correct.html
let contents = fs::read_to_string("big.txt")
.expect("Something went wrong reading the file");
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_EN);
-
assert_eq!(spell_checker.known(&spell_checker.edits1("somthing")).len(), 2);
assert_eq!(spell_checker.known(&spell_checker.edits2("somthing")).len(), 8);
assert_eq!(spell_checker.correction("speling"), "spelling");
assert_eq!(spell_checker.correction("korrectud"), "corrected");
assert_eq!(spell_checker.correction("bycycle"), "bicycle");
assert_eq!(spell_checker.correction("inconvient"), "inconvenient");
assert_eq!(spell_checker.correction("arrainged"), "arranged");
assert_eq!(spell_checker.correction("peotry"), "poetry");
assert_eq!(spell_checker.correction("peotryy"), "poetry");
assert_eq!(spell_checker.correction("word"), "word");
}
#[test]
fn test_bg()
{
//За корпус е използвана следната книга
//Andi_Ueyr_-_Marsianetsyt.txt
let contents = fs::read_to_string("Andi_Ueyr_-_Marsianetsyt.txt")
.expect("Something went wrong reading the file");
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_BG);
- let word_counter = WordCounter::from_str(contents.as_str());
assert_eq!(spell_checker.correction("грежка"), "грешка");
assert_eq!(spell_checker.correction("търссене"), "търсене");
assert_eq!(spell_checker.correction("тои"), "той");
assert_eq!(spell_checker.correction("въда"), "вода");
assert_eq!(spell_checker.correction("Мерс"), "марс");
assert_eq!(spell_checker.correction(" св "), "се");
assert_eq!(spell_checker.correction("дума"), "дума");
}
}

Любослав качи решение на 14.01.2020 14:08 (преди над 5 години)

use std::collections::{HashSet, HashMap};
use std::fmt;
/// Тези две константи са за удобство -- ще ги използваме в тестовете, свободни сте да ги
/// използвате във вашите.
pub const ALPHABET_EN: &'static str = "abcdefghijklmnopqrstuvwxyz";
pub const ALPHABET_BG: &'static str = "абвгдежзийклмнопрстуфхцчшщъьюя";
/// Тази функция премахва всякакви специални символи от низа, освен:
///
/// - Азбучни символи (`char::is_alphabetical`)
/// - Празни символи (`char::is_whitespace`)
/// - Апостроф и тиренце (`'`, `-`)
///
/// Тоест, целта е да сведе един низ до само думи и празни разстояния между тях. Казва се
/// `clean_line`, защото се очаква да бъде викана с по един ред at a time, без нови редове.
///
/// Функцията също се очаква да премахне начален и краен whitespace от низа (Използвайте `.trim`,
/// basically).
///
pub fn clean_line(input: &str) -> String {
let mut result: String = String::from("");
for letter in input.trim().chars()
{
if letter.is_alphabetic() || letter.is_whitespace()
{
result.push(letter);
}
}
result
}
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 result: WordCounter = WordCounter { words: HashMap::new() };
let lines: Vec<&str> = input.split('\n').collect();
for line in lines {
let line_clean: String = clean_line(line);
let words: Vec<&str> = line_clean.split(' ').collect();
for word in words {
if word.len() > 0{
result.add(word.to_lowercase().as_str());
}
}
}
result
}
/// Връща (references към) всички съхранени думи във вектор, сортиран по азбучен ред.
///
pub fn words(&self) -> Vec<&String> {
let mut result: Vec<&String> = Vec::new();
for item in self.words.keys() {
result.push(item)
}
result.sort();
result
}
/// Брои думата с WordCounter-а. Очаква се входа да бъде:
///
/// - Изчистен от всякакъв начален и краен whitespace
/// - Сведен до малки букви
///
/// Тоест:
///
/// `counter.add("Foo")` е еквивалентно на
/// `counter.add("foo")` е еквивалентно на
/// `counter.add(" foo ")`
///
pub fn add(&mut self, item: &str) {
let items_as_string = String::from(item.trim().to_lowercase());
match self.words.get_mut(items_as_string.as_str()) {
Some(count) => {
*count = *count + 1
}
None => {
self.words.insert(items_as_string, 1);
}
};
}
/// Връща колко пъти е бил преброена дадената дума.
///
pub fn get(&self, word: &str) -> u32 {
match self.words.get(word) {
Some(count) => *count,
None => 0
}
}
/// Връща колко общо думи са били преброени. Тоест:
///
/// `counter.add("foo");`
/// `counter.add("foo");`
/// `counter.add("bar");`
///
/// се очаква да ни даде `total_count()` 3.
///
pub fn total_count(&self) -> u32 {
self.words.len() as u32
}
}
/// Искаме да можем да напечатаме един `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 {
let mut to_write: String = String::from("");
to_write.push_str(self.total_count().to_string().as_str());
to_write.push_str("\n");
for word in self.words.keys() {
to_write.push_str((word.clone() + ":" + word.to_string().as_str().clone() + "\n").as_str().clone());
};
write!(f, "WordCounter, total count: {}", to_write)
}
}
pub struct SpellChecker {
corpus: String,
alphabet: String,
counter: WordCounter,
}
/// - Една буква от азбуката добавена в думата на която и да е позиция
fn removed_letter(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len(){
let removed_letter = word_as_vec[index];
word_as_vec.remove(index);
result.insert(word_as_vec.iter().collect());
word_as_vec.insert(index, removed_letter);
}
result
}
fn swapped_letters(word: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let mut word_as_vec: Vec<char> = word.chars().collect();
for index in 0..word_as_vec.len() - 1{
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
result.insert(word_as_vec.iter().collect());
let temp = word_as_vec[index];
word_as_vec[index] = word_as_vec[index + 1];
word_as_vec[index + 1] = temp;
}
result
}
fn letter_changed(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
let original_letter = word_as_vec[position_to_be_changed];
for new_letter in &alphabet_vector{
word_as_vec[position_to_be_changed] = new_letter.clone();
result.insert(word_as_vec.iter().collect());
}
word_as_vec[position_to_be_changed] = original_letter;
}
result
}
fn add_letter(word: &str, alphabet: &str) -> HashSet<String>{
let mut result: HashSet<String> = HashSet::new();
let alphabet_vector: Vec<char> = alphabet.chars().collect();
let mut word_as_vec: Vec<char> = word.chars().collect();
for position_to_be_changed in 0..word_as_vec.len(){
for new_letter in &alphabet_vector{
word_as_vec.insert(position_to_be_changed, new_letter.clone());
result.insert(word_as_vec.iter().collect());
word_as_vec.remove(position_to_be_changed);
}
}
result
}
impl SpellChecker {
/// Създава нов SpellChecker с дадените параметри:
///
/// - corpus: големия текст, който ще се използва за проверяване на познати думи и тяхната
/// вероятност
/// - alphabet: буквите, които ще добавяме или заместваме, за да получим нови потенциални думи.
/// Примерно, да spell-check-ваме български или английски изисква различни азбуки.
///
pub fn new(corpus: &str, alphabet: &str) -> Self {
let result = SpellChecker {
corpus: String::from(corpus),
alphabet: String::from(alphabet),
counter: WordCounter::from_str(corpus),
};
result
}
/// Най-вероятната поправка на тази дума. Както описахме по-горе:
///
/// - Позната ли е тази дума? Ако да, направо я връщаме, валидна е.
/// - Пробваме всички възможни други думи на една буква разлика. Познати ли са някои от тези
/// думи? Ако да, връщаме тази, която се среща най-често в корпуса.
/// - Пробваме всички възможни други думи на две букви разлика по същия начин.
/// - В краен случай, връщаме оригиналната дума, не знаем как да я коригираме.
///
/// Очакваме trim + downcase на входа, тоест
/// `spell_checker.correction(" Foo ")` е еквивалентно на
/// `spell_checker.correction("foo")`
///
/// (Бележка: Би имало смисъл това да е единствения публичен метод -- всички по-надолу биха
/// могли да бъдат private API което се използва от този метод, но искаме да ти тестваме в
/// отделен файл, so here we are.)
///
pub fn correction(&self, word: &str) -> String {
let corrections:Vec<String> = self.candidates(clean_line(word).as_str());
let mut corrections_probability: Vec<(String, f64)> = vec![];
for corrected_word in corrections{
corrections_probability.push((corrected_word.clone(), self.probability(corrected_word.as_str())));
}
corrections_probability.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
corrections_probability[corrections_probability.len() - 1].0.clone()
}
/// Каква е вероятността тази дума да се срещне в оригиналния текст? Броя срещания на тази
/// дума, разделен на броя думи в текста.
///
pub fn probability(&self, word: &str) -> f64 {
match self.counter.words.get(word) {
Some(count) => return *count as f64 / self.counter.words.len() as f64,
None => return 0 as f64
}
}
/// Кои думи от този Set са познати (присъстват в подадения корпус)?
///
pub fn known<'a>(&self, words: &'a HashSet<String>) -> Vec<&'a String> {
let mut result: Vec<&'a String> = vec![];
for word in words{
if self.counter.words.contains_key(word){
result.push(word);
}
}
result
}
/// Всички познати кандидати за поправка на тази дума:
///
/// - Ако думата е позната, директно връщаме вектор с нея.
/// - Намираме познатите edits1 на тази дума -- ако има такива, връщаме ги.
/// - Намираме познатите edits2 на тази дума -- ако има такива, връщаме ги.
/// - Иначе, връщаме вектор с думата.
///
pub fn candidates(&self, word: &str) -> Vec<String> {
let mut result:Vec<String> = vec![];
let mut word_only:HashSet<String> = HashSet::new();
word_only.insert(word.to_string());
for candidate in self.known(&word_only){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits1(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
for candidate in self.known(&self.edits2(word)){
result.push(candidate.clone());
}
if result.len() != 0{
return result;
}
result.push(word.to_string());
result
}
/// Всички думи, които са на една промяна разстояние от дадената дума:
///
/// - Една буква изтрита на коя да е позиция
/// - Две букви разменени (една до друга)
/// - Една буква от азбуката замества коя да е буква от думата
/// - Една буква от азбуката добавена в думата на която и да е позиция
///
/// Изхода е HashSet, понеже две различни промени е възможно да продуцират един и същ резултат,
/// а дубликати не ни интересуват.
///
pub fn edits1(&self, word: &str) -> HashSet<String> {
let mut result:HashSet<String> = HashSet::new();
result.extend(removed_letter(word));
result.extend(swapped_letters(word));
result.extend(letter_changed(word, self.alphabet.as_str()));
result.extend(add_letter(word, self.alphabet.as_str()));
result
}
/// Всички думи, които са на две промени разстояние от дадената дума. Вижте инструкциите на
/// edits1 за това какво е "промяна" и направете тези промени по променените веднъж думи.
///
pub fn edits2(&self, word: &str) -> HashSet<String> {
let edit_1: HashSet<String> = self.edits1(word);
let mut result:HashSet<String> = HashSet::new();
for edited in edit_1{
result.extend(removed_letter(edited.as_str()));
result.extend(swapped_letters(edited.as_str()));
result.extend(letter_changed(edited.as_str(), self.alphabet.as_str()));
result.extend(add_letter(edited.as_str(), self.alphabet.as_str()));
}
result
}
}
#[cfg(test)]
mod tests {
use crate::*;
use std::fs;
#[test]
fn test_basic() {
let line = String::from(" Foo Bar ");
assert_eq!("Foo Bar", clean_line(&line));
let mut counter = WordCounter::new();
assert_eq!(counter.words(), WordCounter::from_str("").words());
assert_eq!(counter.get("word"), 0);
assert_eq!(counter.total_count(), 0);
assert_eq!(format!("{}", counter), "WordCounter, total count: 0\n");
counter.add("word");
let spell_checker = SpellChecker::new("foo bar", ALPHABET_EN);
assert_eq!(spell_checker.correction("foo"), "foo");
assert!(spell_checker.probability("foo") > 0.0);
assert_eq!(spell_checker.known(&HashSet::new()).len(), 0);
assert!(spell_checker.candidates("foo").len() > 0);
assert!(spell_checker.edits1("foo").len() > 0);
assert!(spell_checker.edits2("foo").len() > 0);
}
- #[test]
+ //Тези тестове имат нужда от допълнителни файлове
+ /*#[test]
fn test_advanced() {
//Този тест ще използва файла big.txt -> https://norvig.com/big.txt
//Този тест е копиран от https://norvig.com/spell-correct.html
let contents = fs::read_to_string("big.txt")
.expect("Something went wrong reading the file");
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_EN);
assert_eq!(spell_checker.known(&spell_checker.edits1("somthing")).len(), 2);
assert_eq!(spell_checker.known(&spell_checker.edits2("somthing")).len(), 8);
assert_eq!(spell_checker.correction("speling"), "spelling");
assert_eq!(spell_checker.correction("korrectud"), "corrected");
assert_eq!(spell_checker.correction("bycycle"), "bicycle");
assert_eq!(spell_checker.correction("inconvient"), "inconvenient");
assert_eq!(spell_checker.correction("arrainged"), "arranged");
assert_eq!(spell_checker.correction("peotry"), "poetry");
assert_eq!(spell_checker.correction("peotryy"), "poetry");
assert_eq!(spell_checker.correction("word"), "word");
}
#[test]
fn test_bg()
{
//За корпус е използвана следната книга
//Andi_Ueyr_-_Marsianetsyt.txt
let contents = fs::read_to_string("Andi_Ueyr_-_Marsianetsyt.txt")
.expect("Something went wrong reading the file");
let spell_checker = SpellChecker::new(contents.as_str(), ALPHABET_BG);
assert_eq!(spell_checker.correction("грежка"), "грешка");
assert_eq!(spell_checker.correction("търссене"), "търсене");
assert_eq!(spell_checker.correction("тои"), "той");
assert_eq!(spell_checker.correction("въда"), "вода");
assert_eq!(spell_checker.correction("Мерс"), "марс");
assert_eq!(spell_checker.correction(" св "), "се");
assert_eq!(spell_checker.correction("дума"), "дума");
- }
+ }*/
}