Статья Автор: Лебедев Дмитрий

TUZ_4-10 Автокорректор слов

TUZ_4-10 Автокорректор слов

TUZ_4-10 Автокорректор слов
4.10. Автокорректор слов
Существует несколько методов автоматического исправления орфографических ошибок в словах.
Один из наиболее распространенных основан на вычислении расстояния между словами.
Этот метод предполагает замену букв в слове ближайшими на клавиатуре.
Например, если предполагаемое слово «car», а входное слово «csr», то букву «s»,
следует заменить буквой «a», которая находится рядом с «s» на клавиатуре, поэтому «csr» → «car».
Эта задача требует вычисления всех расстояний между ключевыми словами в списке и 
данным словом с последующей заменой входного слова словом из списка, имеющим минимальное расстояние до заданного.
Ваша задача: написать функцию, которая принимает проверяемое слово word и список слов words
и возвращает слово w из списка words, имеющее минимальное расстояние от заданного.
В табл. 4.10 показаны ожидаемые результаты для некоторых входных данных.  
Таблица 4.10. Некоторые ожидаемые результаты для задачи автокоррекции слов
Words, word Ожидаемый результат
pycorn, pipline, python, ceo, we
pohytn		 python
camerier, academic, company, creamier
ceamierr		 creamier

При вычислении расстояние между буквами на клавиатуре QWERTY все буквы разбиваются на три ряда:
  • 1-й (top) = "qwertyuiop"
  • 2-й (mid) = "asdfghjkl"
  • 3-й (bot) = "zxcvbnm"
Расстояние между буквами вычисляется как квадрат суммы двух расстояний:
dist( i, j ) = ( | rj - ri| +| cj-ci |)2, где rj,ri - индексы букв в рядах клавиатуру, а cj,ci - номера рядов.
Например:
 dist(a,s)=(|2-1|+|2-2|)2 = 1 (буквы находятся во одном ряду на соседних позициях)
 dist(a,b)=(|5-1|+|3-2|)2 = 25 (буквы находятся в соседних рядах и на разных позициях)
 dist(a,z)=(|1-1|+|3-2|)2 = 1 (буквы находятся в разных рядах, но на одинаковых позициях)
 

Алгоритм
Пусть даны строка word и список слов words.
Для каждого слова w в words алгоритм проверяет, имеют ли w и word одинаковую длину.
Если это так, то алгоритм вычисляет расстояние на клавиатуре QWERTY для каждой пары символов в w и word,
сохраняет расстояния в массив storage и вычисляет сумму расстояний.
Эта сумма присваивается слову w.
Процесс повторяется для всех слов в words.
Наконец, алгоритм возвращает слово из words, которое имеет минимальное расстояние до данного слова word.
Если таких слов несколько, то возвращается слово с минимальным индексом


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать