Разработка упражнения. Метод "расстояние Левенштейна или Дамерау - Левенштейна" как основа для упражнения - Компьютерная лингвистика в образовательной среде

При проектировании упражнения встал вопрос о его реализации. Было необходимо найти такой метод, который не только соответствовал основным требованиям составления упражнений на заучивание терминологии, но и мог быть использован в коде на языке программирования Python.

Проанализировав работы в сфере обработки естественного языка, был выбран метод "расстояние Левенштейна" (также редакционное расстояние или дистанция редактирования), впервые он был упомянут в 1965 г. советским математиком В. И. Левенштейном. В. И. Левенштейн. "Двоичные коды с исправлением выпадений, вставок и замещений символов" 1965г.

Расстояние Левенштейна находит применение:

    - при исправлении ошибок в слове при вводе текста, в процессе автоматического распознавания письменного текста или речи; - в ходе сравнения текстовых файлов (за единицу в подобном анализе берется строка); - в биоинформатике (сравнение хромосом, генов и белков).

Данное понятие основано на определении "редакционное предписание". Редакционное предписание - последовательность действий, необходимых для получения из первой строки второй кратчайшим способом. Набор действий, допустимый при изменении элементов, имеет следующие обозначения: D (delete) - удаление символа; I (insert) - добавление символа; R (replace) - замена символа; M (match) - совпадение символа. В. М. Черненький, Ю. Е. Гапанюк "Методика идентификации пассажира по установочным данным" 2012г.

Пример редакционного предписания (Таблица 1):

(Таблица 1)

Действие

I

M

I

M

M

R

D

Исходное слово

М

Г

Л

А

Результат

С

М

У

Г

Л

Ы

Й

Сумма всех действий кроме M и будет расстоянием Левенштейна. В данном примере дистанция редактирования равна 4.

Существует масса способов, при которых можно преобразовать одно слово в другое. Если выбран метод "расстояние Левенштейна", необходимо свести действия к минимуму.

В тех случаях, когда поиск того или иного слова производится в тексте, набранном с клавиатуры, вместо расстояния Левенштейна используется усовершенствованное Расстояние Дамерау - Левенштейна.Damrau F. A. "Technique for Computer Detection and Correction of SpellingErrors" 1964.171P.

В своих исследованиях Ф. Дамерау показал, что наиболее часто совершаемая ошибка - транспозиция T(transposition) - перестановка двух соседних символов. При расстоянии Левенштейна количество действий при транспозиции будет равно 2, тогда как при корректировке Дамерау данное действие принимается за единичное расстояние.

Пример (Таблица 2):

(Таблица 2)

Действие (расстояние Дамерау - Левенштейна)

I

T

M

M

R

D

Действие(расстояние Левенштейна)

I

R

R

M

M

R

D

Исходное слово

С

М

У

Г

Л

Ы

Й

Результат

С

У

М

Г

Л

Ы

Й

Основные недостатки данного метода в отношении слов и текстовых полей заключаются в следующем:

    1) достаточно большие расстояния при изменении положения слова (частей слов) в тексте; 2) небольшое расстояние между совершенно разными короткими словами и значительная разница между достаточно длинными, но похожими словами.

Несмотря на представленные недочеты, в качестве упражнения данный алгоритм вполне соответствует нашим требованиям. Дистанция позволит отследить соответствие вставленного в текст термина с его оригиналом и вывести количество ошибок, допущенных при вводе (на сколько символов одно слово отличается от другого).

В настоящее время существует достаточно большое количество примеров реализации данного метода на языке программирования Python. Многие из них требуют подгрузки дополнительных библиотек. Чтобы избежать лишней перегрузки программы, предпочтение было отдано достаточно простому решению: [Приложение 2].

Адаптировав его под полученные данные, становится возможным создание полей ввода для занесения пользователем печатных слов, а на выходе - получение количества ошибок, что и будет дистанцией редактирования.

Выводы по второй главе:

В данной главе отражены основные этапы проектирования и создания упражнения для заучивания политических терминов:

    1) Формирование списка основных политических терминов, разделение их на 4 категории: "Вертикаль власти", "Выборы", "Полномочия власти, "Образ власти". 2) Поиск и разметка слов в статьях корпуса политических статей. Сортировка их в соответствии с группой. 3) Выбор тематики упражнения был сделан в пользу вида "Вставить пропущенное слово", была разработана основная концепция задания. 4) Осуществление проектирования упражнения с использованием метода "Расстояние Левенштейна или дистанция редактирования". В данной части исследования были рассмотрены основные положения данного метода. Среди уже существующих вариантов реализации, был выбран наиболее емкий и соответствующий тематике упражнения вариант.

Похожие статьи




Разработка упражнения. Метод "расстояние Левенштейна или Дамерау - Левенштейна" как основа для упражнения - Компьютерная лингвистика в образовательной среде

Предыдущая | Следующая