Лабораторная работа №2. Исправление опечаток на основе редакционного расстояния
===============================================================================
.. toctree::
:maxdepth: 1
:titlesonly:
:caption: Full API
lab_2_spellcheck.api.rst
.. important::
Описание лабораторных работ и другие полезные материалы
доступны на
`сайте дисциплины `__
Дано
----
1. Текст первой главы «Мастера и Маргариты» на русском языке
(``assets/Master_and_Margarita_chapter1.txt``)
2. Список стоп-слов (``assets/stop_words.txt``)
3. Предложения со словами с ошибками
(``assets/incorrect_sentence_n.txt``)
В рамках данной лабораторной работы вам предстоит
реализовать и сравнить эффективность нескольких метрик
строкового расстояния, которые являются ключевым
компонентом системы проверки орфографии — `spellcheck`.
Основная задача — найти слово с возможной опечаткой и найти подходящее слово замену.
Близость определяется на основе вычисления «расстояния» между строками.
Вам необходимо реализовать и сравнить следующие алгоритмы:
- расстояние на основе коэффициента сходства Жаккара
- расстояние на основе частотности
- расстояние Левенштейна
- расстояние Джаро-Винклера.
Каждый алгоритм по-разному вычисляет расстояние
между словом-опечаткой и его потенциальной заменой в словаре.
Итогом работы станет сравнение эффективности этих алгоритмов
для задачи поиска кандидатов исправления.
Что надо сделать
----------------
Шаг 0. Начать работу над лабораторной (вместе с преподавателем на практике)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. Создайте форк репозитория.
2. Установите необходимые инструменты для работы.
3. Измените файлы ``main.py`` и ``start.py``.
4. Закоммитьте изменения и создайте Pull request.
.. important:: В файле ``start.py`` вы должны написать код,
вычисляющий и сравнивающий метрики.
Для этого реализуйте функции в модуле ``main.py`` и импортируйте их в
``start.py``. Весь код, выполняющий вычисление и сравнение, должен быть
выполнен в функции ``main`` в файле ``start.py``:
.. code:: py
def main() -> None:
pass
Вызов функции в файле ``start.py``:
.. code:: py
if __name__ == '__main__':
main()
В рамках данной лабораторной работы **нельзя использовать модули
collections, itertools, а также сторонние модули.**
Обратите внимание, что желаемую оценку необходимо указать в файле
``settings.json`` в поле ``target_score``. Возможные значения: 0, 4, 6, 8, 10.
Чем большее значение выставлено, тем больше тестов будет запущено.
.. note:: Если на вход в функции подаются аргументы неправильных типов,
то возвращается значение ``None``.
Шаг 1. Токенизировать текст
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Для токенизации текста Вы можете использовать уже
реализованную в прошлой лабораторной функцию :py:func:`lab_1_keywords_tfidf.main.clean_and_tokenize`.
Шаг 2. Удалить стоп-слова
~~~~~~~~~~~~~~~~~~~~~~~~~
Для удаления стоп-слов Вы можете использовать уже
реализованную в прошлой лабораторной функцию :py:func:`lab_1_keywords_tfidf.main.remove_stop_words`.
Шаг 3. Построить словарь для коллекции документов
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.build_vocabulary`.
Функция принимает на вход список токенов и возвращает словарь, который
содержит каждый уникальный токен и его относительную частоту в переданном списке.
Частота рассчитывается как отношение количества вхождений токена к общему количеству токенов.
Продемонстрируйте полученный словарь в файле ``start.py``.
Шаг 4. Найти слова, отсутствующие в словаре
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.find_out_of_vocab_words`.
Функция принимает на вход список токенов и список слов из словаря корпуса.
Возвращает список токенов, которых нет в словаре корпуса.
Это могут быть как неологизмы или редкие термины, так и слова с опечатками.
Выведите отсутствующие в словаре слова в файле ``start.py``.
Шаг 5. Рассчитать расстояние Жаккара на основе коэффициента сходства
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.calculate_jaccard_distance`.
**Коэффициент сходства Жаккара (Jaccard similarity coefficient)** -
мера сходства между двумя множествами,
определяемая как размер пересечения множеств, делённый на размер их объединения.
Для строк коэффициент Жаккара можно вычислять на основе символов или n-грамм.
В данной работе расчеты производятся на основе отдельных символов (букв).
Формула:
.. math::
J(A, B) = 1 - \frac{|A \cap B|}{|A \cup B|}
где
- :math:`A` и :math:`B` — множества символов строк,
- :math:`|A \cap B|` — размер пересечения множеств :math:`A` и :math:`B`,
- :math:`|A \cup B|` — размер объединения множеств :math:`A` и :math:`B`
Пример: ``calculate_jaccard_distance('молоко', 'малоко')``
- Множества символов: ``{'м', 'о', 'л', 'к'}`` и ``{'м', 'а', 'л', 'о', 'к'}``
- Пересечение: ``{'м', 'о', 'л', 'к'}`` (размер = 4 элемента)
- Объединение: ``{'м', 'а', 'л', 'о', 'к'}`` (размер = 5 элементов)
- Результат: :math:`J = 1 - \frac{4}{5} = 0.2`
В случае подачи на вход пустых строк возвращается значение ``1.0``.
Шаг 6. Рассчитать расстояние между двумя строками
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Функция :py:func:`lab_2_spellcheck.main.calculate_distance` должна реализовываться и дополняться
в ходе выполнения работы и знакомства с новыми алгоритмами.
На вход принимается строка для сравнения, словарь частот и название метода.
Возвращается словарь, где ключи — слова из словаря, а значения — вычисленное расстояние.
Функция считает расстояние между двумя словами в зависимости от выбранного алгоритма:
сходства Жаккара, метода, основанном на подсчете частот, расстояния Левенштейна или сходства Джаро-Винклера.
В функции :py:func:`lab_2_spellcheck.main.calculate_distance`
реализуйте ветку для метода ``"jaccard"``.
1. Функция должна проходить по каждому слову из словаря частот.
2. Для каждого слова вызовите функцию
:py:func:`lab_2_spellcheck.main.calculate_jaccard_distance`
3. Сохраните результат в новый словарь, где:
* ключ — текущее слово из словаря частот;
* значение — вычисленное расстояние Жаккара.
4. Верните этот словарь как результат работы функции.
Пример:
.. code-block:: python
>>> calculate_distance("кот", {"кот": 0.5, "пёс": 0.5}, method="jaccard")
{"кот": 0.0, "пёс": 1.0}
Продемонстрируйте получаемый с помощью метода Жаккара словарь в файле ``start.py``.
Шаг 7. Найти наиболее похожее слово
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. important:: Выполнение Шагов 1-7 соответствует 4 баллам.
Реализуйте функцию :py:func:`lab_2_spellcheck.main.find_correct_word`.
Функция должна реализовываться и дополняться
в ходе выполнения работы и знакомства с новыми алгоритмами.
Функция находит наиболее похожего кандидата для введенного слова с помощью
реализуемых методов.
Для всех методов на основе расстояния выбирается слово с минимальным значением.
.. important::
Если найдено несколько слов с одинаковым значением расстояния,
выбирается слово, которое:
* ближе всех по длине к исходному слову;
* при равенстве длины — идёт раньше других в алфавитном порядке.
Добавьте подсчет расстояния Жаккара в функцию.
Шаг 8. Рассчитать расстояние на основе подсчета частотности
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Даже если два слова сильно похожи по форме (например, по расстоянию Левенштейна),
правильным исправлением с большей вероятностью будет то слово, которое чаще встречается
в языке. Например, для опечатки ``"молако"`` кандидаты ``"молоко"`` и ``"малака"``
равноудалены на один символ, но ``"молоко"`` встречается гораздо чаще — именно его
мы хотим выбрать.
Пусть имеется словарь частот :math:`V`, где каждому слову :math:`w` сопоставлена
его относительная частота :math:`f(w)`.
Для заданного слова с опечаткой :math:`t` определим **расстояние на основе частотности**
для каждого кандидата :math:`c` как:
.. math::
\text{distance_freq}(t, с) =
\begin{cases}
1.0, & \text{если } c \notin V \\
1.0 - f(c), & \text{если } c \in V
\end{cases}
То есть слова, которые встречаются чаще, имеют меньшее расстояние и
считаются более вероятными исправлениями. При выборе кандидата
следует минимизировать это расстояние.
При выполнении шагов 8.1 - 8.4 реализуем все требуемые трансформации
текста для генерации кандидатов.
.. note:: Все трансформации должны возвращать **отсортированный список слов**.
Шаг 8.1. Генерация кандидатов: удаление символов
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.delete_letter`.
Удаление символа — одна из базовых операций для генерации возможных кандидатов.
Формально, если слово имеет длину n, операция удаления создает n кандидатов.
Формула:
.. math::
D(w) = \{ w[:i] + w[i+1:] | i = 0..n-1 \}
Например, для слова ``'кот'`` должны быть получены: ``['ко', 'кт', 'от']``
Функция принимает слово и возвращает список всех возможных слов,
полученных удалением одного символа.
Шаг 8.2. Генерация кандидатов: вставка символов
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.add_letter`.
Вставка символа позволяет учесть ошибки пропуска. Для слова длины n и алфавита A
формально создается n+1 позиция для вставки каждого символа из A.
Формула:
.. math::
I(w) = \{ w[:i] + a + w[i:] | i = 0..n, a ∈ A \}
Пример: для слова ``'кот'`` и алфавита ``['и', 'р']`` результат может быть:
``['икот', 'ркот', 'киот', 'крот', 'коит', 'корт', 'коти', 'котр']``
Функция принимает слово и алфавит, возвращает список всех возможных слов,
полученных вставкой одного символа из алфавита в любую позицию.
Шаг 8.3. Генерация кандидатов: замена символов
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.replace_letter`.
Замена символа моделирует опечатки при нажатии неправильной клавиши.
Для слова длины n и алфавита A.
Формула:
.. math::
R(w) = \{w[:i] + a + w[i+1:] | i = 0..n-1, a ∈ A\}
Пример: для слова ``'море'`` и алфавита ``['а', 'й']`` результат может быть:
``['аоре', 'йоре', 'маре', 'мйре', 'моае', 'мойе', 'мора', 'морй']``
Функция принимает слово и алфавит, возвращает список всех возможных слов,
полученных заменой каждого символа на символы из алфавита.
Шаг 8.4. Генерация кандидатов: перестановка соседних символов
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.swap_adjacent`.
Перестановка соседних символов моделирует опечатки, когда две буквы перепутаны местами.
Формула:
.. math::
S(w) = \{ w[:i] + w[i+1] + w[i] + w[i+2:] | i = 0..n-2 \},
где ``n`` — длина слова.
Например, для слова ``'май'`` результат: ``['амй', 'мйа']``.
Функция принимает слово и возвращает список всех возможных слов,
полученных перестановкой каждой пары соседних символов.
Шаг 9. Сгенерировать кандидатов для исправления
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.generate_candidates`.
Полный набор кандидатов для исправления опечаток строится как объединение всех базовых операций.
Формула:
.. math::
C(w) = D(w) ∪ I(w) ∪ R(w) ∪ S(w)
Функция принимает слово и возвращает список всех возможных кандидатов,
полученных применением четырех базовых операций:
удаление, вставка, замена и перестановка соседних символов.
Используйте функции из предыдущих шагов (8.1-8.4).
Удалите дубликаты из результирующего списка.
Шаг 10. Предложить кандидатов для исправления
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.propose_candidates`.
Функция принимает слово и возвращает кортеж из кандидатов для исправления.
Используйте функцию из предыдущего шага для генерации кандидатов.
Так как порой опечатки накладываются друг на друга, для их исправления
может быть полезно посмотреть на кандидаты, которые имеют несколько
исправлений.
Сгенерируйте кандидаты дважды: сначала для данного слова, а
затем для каждого из полученных кандидатов.
Шаг 11. Рассчитать расстояние на основе подсчета частотности
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. important:: Выполнение Шагов 1-11 соответствует 6 баллам.
Реализуйте функцию :py:func:`lab_2_spellcheck.main.calculate_frequency_distance`.
Функция принимает слово с опечаткой и словарь частот, возвращает словарь с кандидатами и
их расстоянием на основе частотности (формула описана в Шаге 8.).
Добавьте подсчет схожести на основе частотности в функции
:py:func:`lab_2_spellcheck.main.calculate_distance`
и :py:func:`lab_2_spellcheck.main.find_correct_word`.
Продемонстрируйте исправление некорректных слов с помощью алгоритма в файле
``start.py``.
Шаг 12. Реализовать алгоритм Левенштейна
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
**Расстояние Левенштейна** — это метрика, которая измеряет сходство между двумя строками символов,
вычисляя минимальное количество односимвольных элементарных операций таких, как
вставка, удаление и замена, необходимых для преобразования одной строки в другую.
Рассмотрим пример для каждой односимвольной операции.
1. Вставка. Даны два слова ``кот`` и ``скат``. Для того чтобы преобразовать первое слово во второе,
необходимо выполнить две операции вставки: первую, чтобы преобразовать
``кот`` в ``скот``, а вторую, чтобы преобразовать ``скот`` в ``скат``.
Таким образом, расстояние Левенштейна равно 2.
2. Удаление. Даны два слова ``коты`` и ``кот``. Для того чтобы преобразовать первое слово во второе,
необходимо выполнить одну операцию удаления. Таким образом, расстояние Левенштейна равно 1.
3. Замена. Даны два слова ``коты`` и ``косы``. Необходимо выполнить одну операцию замены
``т`` на ``с``. Таким образом, расстояние Левенштейна равно 1.
Таким образом, чем больше расстояние, тем более различны строки. Для двух одинаковых
последовательностей расстояние равно нулю.
На практике минимальное количество элементарных операций для
**расстояния Левенштейна** вычисляется с помощью матрицы, где каждая ячейка хранит
минимальное количество операций для подстрок (префиксов строк).
При выполнении шагов 15.1 - 15.3 изучим и реализуем алгоритм подсчёта расстояния Левенштейна
с помощью матрицы Вагнера-Фишера.
Шаг 12.1. Инициализировать матрицу Левенштейна
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.initialize_levenshtein_matrix`.
Пусть дана пара слов: ``кот`` и ``кто``. Первое слова является некорректным, а второе -
кандидатом для исправления первого.
Функция создает и инициализирует матрицу размером ``n x m``, где
``n`` - значение на единицу больше, чем длина некорректного слова,
``m`` - значение на единицу больше, чем длина слова-кандидата,
для вычисления расстояния Левенштейна.
Первым шагом матрица инициализируется нулевыми значениями и приобретает следующий вид:
+--------+--------+-------+-------+-------+
| | ``""`` | ``к`` | ``т`` | ``о`` |
+--------+--------+-------+-------+-------+
| ``""`` | 0 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
| ``к`` | 0 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
| ``о`` | 0 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
| ``т`` | 0 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
Затем первая строка заполняется числами от 0 до длины слова-кандидата, первый
столбец — от 0 до длины некорректного слова. В данном примере длина и некорректного слова,
и кандидата равна 3, тогда получается матрица вида:
+--------+--------+-------+-------+-------+
| | ``""`` | ``к`` | ``т`` | ``о`` |
+--------+--------+-------+-------+-------+
| ``""`` | 0 | 1 | 2 | 3 |
+--------+--------+-------+-------+-------+
| ``к`` | 1 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
| ``о`` | 2 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
| ``т`` | 3 | 0 | 0 | 0 |
+--------+--------+-------+-------+-------+
Теперь первая строка и первый столбец отражают базовые случаи.
Шаг 12.2. Заполнить матрицу Левенштейна
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.fill_levenshtein_matrix`,
которая заполняет матрицу для вычисления **расстояния Левенштейна**.
Расстояние Левенштейна :math:`lev[i][j]` определяется рекурсивно:
.. math::
\text{lev}[i][j] =
\begin{cases}
j, & \text{если } i = 0 \quad (\text{вставка всех символов строки } b)\\
i, & \text{если } j = 0 \quad (\text{удаление всех символов строки } a)\\
\text{lev}[i-1][j-1], & \text{если } a[i-1] = b[j-1] \quad (\text{cost = 0})\\
\min
\begin{cases}
\text{lev}[i-1][j] + 1, \\
\text{lev}[i][j-1] + 1, \\
\text{lev}[i-1][j-1] + cost
\end{cases} & \text{иначе cost = 1}
\end{cases}
где:
- :math:`\text{lev}[i][j]` - расстояние Левенштейна между префиксами длины ``i`` и ``j``, то есть
минимальное число операций (вставка, удаление, замена), чтобы превратить
первые ``i`` символов строки ``a`` в первые ``j`` символов ``b``.
- :math:`\text{lev}[i-1][j]` + 1 — удаление символа
- :math:`\text{lev}[i][j-1]` + 1 — вставка символа
- :math:`\text{lev}[i-1][j-1]` + 1 — замена символа
В таком случае заполнение матрицы по строкам для слов *кот* и *кто* будет проходить
следующим образом:
1. На первой итерации сравниваем первые символы в каждой строке, то есть ``к`` и ``к``.
Символы равны, значит стоимость замены одного символа другим (``cost``) равна 0.
2. Далее вычисляем минимумы при ``i=1`` и ``j=1``:
Удаление: :math:`lev([0][1]) + 1 = 1 + 1 = 2`
Вставка: :math:`lev([1][0]) + 1 = 1 + 1 = 2`
Замена: :math:`lev([0][0]) + cost = 0 + 0`
3. Минимальное значение равно 0, значит :math:`lev[1][1] = 0`
4. Повторяем шаги 1-3 для всех ``j`` в строке ``i``, а затем и для всех строк ``i``.
В результате итеративного заполнения получается следующая матрица:
+--------+--------+-------+-------+-------+
| | ``""`` | ``к`` | ``т`` | ``о`` |
+--------+--------+-------+-------+-------+
| ``""`` | 0 | 1 | 2 | 3 |
+--------+--------+-------+-------+-------+
| ``к`` | 1 | 0 | 1 | 2 |
+--------+--------+-------+-------+-------+
| ``о`` | 2 | 1 | 1 | 1 |
+--------+--------+-------+-------+-------+
| ``т`` | 3 | 2 | 1 | 2 |
+--------+--------+-------+-------+-------+
Шаг 12.3. Рассчитать расстояние Левенштейна
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.calculate_levenshtein_distance`.
Функция возвращает итоговое значение расстояния Левенштейна между двумя строками,
используя заполненную матрицу. Значение, хранящееся в правом нижнем углу матрицы, отвечает
за расстояние Левенштейна.
В примере со словами ``кот`` и ``кто`` расстояние Левенштейна равно 2 и соответствует
двум операциям: замене ``о`` на ``т``, замене ``т`` на ``о``.
.. note:: Необходимо добавить поддержку подсчёта расстояния Левенштейна в функцию
:py:func:`lab_2_spellcheck.main.calculate_distance`. Для этого найдите
расстояние между каждым словом-кандидатом из словаря с некорректным словом.
Шаг 13. Найти наиболее похожее слово
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. important:: Выполнение Шагов 1-13 соответствует 8 баллам.
Дополните реализацию функции :py:func:`lab_2_spellcheck.main.find_correct_word`
расстоянием Левенштейна. Для данного алгоритма выбирается слово с минимальным
расстоянием.
Продемонстрируйте исправление некорректных слов с помощью расстояния Левенштейна
в файле ``start.py``.
Шаг 14. Реализовать алгоритм Джаро-Винклера
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Расстояние Джаро-Винклера — это метрика сходства строк, которая
основана на метрике Джаро, учитывающей количество совпадающих
символов и перестановок между ними.
Расстояние Джаро-Винклера добавляет к расстоянию Джаро поправку: если
строки совпадают в начале (имеют общий префикс), то итоговое сходство
увеличивается. Такая модификация полезна, поскольку в реальных
данных совпадение начальных символов часто более значимо (например,
в именах, фамилиях или названиях).
Шаг 15. Определить совпадающие символы
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.get_matches`.
Функция находит количество совпадающих символов между двумя строками
в пределах заданного расстояния.
Каждый символ из первой строки может быть сопоставлен с символом из второй строки,
если они совпадают и находятся в радиусе ``match_distance``.
Чем больше расстояние, тем больше перестановок
и вставок алгоритм может учесть при сопоставлении символов.
Например, слова *кот* и *кто* при заданном расстоянии совпадающих символов 1 будут
считаться идеальными кандидатами друг для друга и совпадут во всех позициях, так как
окно поиска, равное 1, позволяет искать символы не только на том же месте, но и на соседних
позициях. Алгоритм идёт последовательно: сначала ``к`` совпало по индексу 0;
затем ``о`` не совпало в центре, но совпало справа; затем ``т`` совпало слева.
В итоге каждый символ нашёл себе пару.
При расстоянии 0 совпадающим будет один символ *к*
(поиск строгого позиционного совпадения).
Шаг 16. Подсчитать количество транспозиций
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.count_transpositions`.
Функция подсчитывает количество транспозиций среди совпадающих символов.
Транспозиция — это случай, когда совпадающие символы находятся на разных позициях в двух строках.
Эта метрика используется в алгоритмах типа Джаро-Винклера, который будет рассмотрен далее,
для учета перестановок символов при сравнении строк.
Вновь обратимся к примеру со словами ``кот`` и ``кто``.
На предыдущем шаге было определено, что все символы считаются совпавшими.
Теперь важно посчитать количество транспозиций.
И в слове ``кот``, и в слове ``кто``, первая буква ``к``, значит количество транспозиций
не увеличивается.
Вторые и третьи символы не совпадают, поэтому считаем, что количество транспозиций равно 2.
Однако транспозиция — это пара символов, поменявшихся местами, поэтому итоговое число
делится пополам. Следовательно, количество транспозиций необходимых для того, чтобы
получить из слова ``кот`` слово ``кто`` равно 1.
+----------+-----------+-----------+-----------+
| Позиция | Токен | Кандидат | Результат |
+==========+===========+===========+===========+
| 0 | ``к`` | ``к`` | ``+`` |
+----------+-----------+-----------+-----------+
| 1 | ``о`` | ``т`` | ``-`` |
+----------+-----------+-----------+-----------+
| 2 | ``т`` | ``о`` | ``-`` |
+----------+-----------+-----------+-----------+
Шаг 17. Рассчитать расстояние Джаро
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.calculate_jaro_distance`.
**Расстояние Джаро** — это мера различия между двумя строками, основанная на сходстве Джаро,
которая учитывает как количество общих символов, так и их порядок.
Если :math:`J_sim(s_1, s_2)` — стандартное сходство Джаро между строками :math:`s_1` и :math:`s_2`,
тогда **расстояние Джаро** определяется как:
.. math::
J_\text{d}(s_1, s_2) = 1 - J_\text{sim}(s_1, s_2)
Стандартное сходство Джаро вычисляется по формуле:
.. math::
J_\text{sim}(s_1, s_2) = \frac{1}{3} \left( \frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m} \right)
где:
- :math:`m` — количество совпадающих символов
- :math:`t` — количество транспозиций
- :math:`|s_1|, |s_2|` — длины строк
Если совпадающих символов нет (:math:`m = 0`), сходство равно 0, а расстояние — 1.
Пример:
``calculate_jaro_distance('кофа', 'кофе') -> 0.167``
То есть чем ближе строки друг к другу, тем меньше расстояние.
Шаг 18. Реализовать поправку Винклера
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.winkler_adjustment`.
Поправка Винклера усиливает влияние совпадений в начале строк (общий префикс).
Формула поправки:
.. math::
adjustment = l \times p \times (1 - J)
где:
- :math:`l` — длина общего префикса (максимум 4 символа)
- :math:`p` — коэффициент масштабирования (обычно 0.1)
- :math:`J` — значение сходства Джаро
Пример расчёта расстояния:
``winkler_adjustment('привет', 'превед', 0.694)``
.. math::
winkler = 2 \times 0.1 \times (1 - 0.694) = 0.0611
Шаг 19. Рассчитать расстояние Джаро–Винклера
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Реализуйте функцию :py:func:`lab_2_spellcheck.main.calculate_jaro_winkler_distance`.
**Расстояние Джаро–Винклера** объединяет расстояние Джаро с поправкой Винклера.
Оно вычисляется через сходство Джаро-Винклера по формуле:
.. math::
JW_\text{d} = 1 - JW_\text{sim}
где сходство Джаро-Винклера это:
.. math::
JW_\text{sim} = J_\text{sim} + adjustment
где :math:`J_\text{sim}` — сходство Джаро, :math:`adjustment` — поправка Винклера.
Таким образом, расстояние Джаро-Винклера имеет вид:
.. math::
JW_\text{d} = J_\text{d} - adjustment
где :math:`J_\text{d}` — расстояние Джаро, :math:`adjustment` — поправка Винклера.
Данный алгоритм даёт меньшее расстояние для нормального слова *привет* и
большее для некорректного слова *превед*, что соответствует принципу минимизации
расстояния.
.. note:: Необходимо добавить поддержку подсчёта расстояния Джаро-Винклера в функцию
:py:func:`lab_2_spellcheck.main.calculate_distance`. Для этого найдите
расстояние между каждым словом-кандидатом из словаря с некорректным словом.
Шаг 20. Найти наиболее похожее слово
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. important:: Выполнение Шагов 1-20 соответствует 10 баллам.
Дополните реализацию функции :py:func:`lab_2_spellcheck.main.find_correct_word`
расстоянием Джаро-Винклера. Для данного алгоритма выбирается слово с минимальным
расстоянием.
Продемонстрируйте исправление некорректных слов с помощью алгоритма в файле
``start.py``.
Полезные ссылки
---------------
- `Коэффициент сходства Жаккара `_
- `Алгоритм Левенштейна `_
- `Обо всех алгоритмах `_