Редакционные расстояния (edit distance) могут помочь, когда нужно формально сравнить слова или предложения и понять, какие из них больше похожи друг на друга. Важно: редакционные расстояния говорят не о смысловой близости слов или предложений, а только о близости их формы.
Как это работает?
Основное понятие при подсчете редакционных расстояний — операция. Операций бывает всего четыре:
- удаление
- вставка
- замена
- перестановка.
Чтобы узнать редакционное расстояние между двумя строками, нужно посчитать минимальное количество операций, которые нужно сделать, чтобы превратить первую строку во вторую.
Каждый раз в операции может участвовать один символ в строке. За одну операцию мы можем только вставить\удалить символ или заменить некоторый один символ на один другой символ. Нельзя, например, удалить сразу две буквы и сказать, что мы произвели только одну операцию (удаление). Операций было две: 1) удаление символа № 1, 2) удаление символа № 2. Такие операции называются посимвольными.
Немного примеров
Если мы хотим превратить «сон» в «слон», нам нужно произвести одну операцию: вставить букву «л» после буквы «с». «Сон» в «сын» тоже превращается за одну операцию: замена буквы «о» на «ы». Для перехода от «сон» к «клон» нужно минимум 2 операции: 1) заменить «с» на «к», 2) вставить «л» после «с». Можно превращать и по-другому, но меньше, чем за два шага не получится.
Количество операций — это и есть редакционное расстояние между двумя строками.
Виды редакционных расстояний
Есть несколько основных редакционных расстояний. Основное отличие между ними — набор операций, который разрешено использовать.
В таблице ниже перечислены наиболее используемые редакционные расстояния и операции, разрешенные для каждого из них.
Расстояние Хэмминга разрешает только замены, так что с помощью него можно сравнивать только строки одинаковой длины: мы не можем удлинить строку с помощью вставки или укоротить ее с помощью удаления.
Расстояние Дамерау—Левенштейна разрешает все четыре операции: замену, вставку, удаление и перестановку соседних символов. Федерик Демерау показал, что эти четыре операции покрывают порядка 80% ошибок при письме.
Что еще можно изменить?
В простом случае мы просто считаем, сколько операций нужно для превращения одной строки в другую, и за каждую операцию, добавляем 1 очко штрафа. Редакционное расстояние в этом случае — сумма штрафных баллов.
Можно усложнить схему и давать разное количество баллов штрафа за разные операции; за операции, сделанные, например, в начале или в конце слова; по-разному штрафовать за разные замены.
Где применяется?
Основные области применения редакционных расстояний — компьютерная лингвистика и биоинформатика.
В компьютерной лингвистике возникает множество задач, где нужно посчитать формальную меру близости между строками: например, для проверки орфографии, или для сравнения, насколько похожи два предложения. Первые системы автоматической проверки орфографии фактически сводились к подсчету редакционного расстояния Левенштейна или Дамерау—Левенштейна с использованием сложной системы штрафов. Система шла от слова к слову и проверяла, есть ли такое слово в словаре, а когда встречала слово, которого нет в словаре, то пыталась заменить его на наиболее близкое по редакционному расстоянию слово из словаря. Сейчас расстояние Левенштейна редко используется как единственный признак близости, но очень часто как один из.
В биоинформатике редакционные расстояния используются для определения похожести друг на друга разных участков ДНК или РНК, которые в таком случае представляются как последовательность, состоящая из A, G, C, U и T — это первые буквы четырех азотистых основания, которые могут входить в состав ДНК или РНК: аденин, гуанин и цитозин, урацил и тимин.
Бывают и неочевидные применения, например, определение, на что больше похожа буква на нечеткой фотографии текста, на «Л» или «П», в таком случае буквы представляют как стоящие друг над другом строки, состоящие из черных и белых пикселей.
