Редакционное расстояние: что это и где используется
#knowhow #glossary
Чаще всего редакционное расстояние (edit distance) применяется в компьютерной лингвистике и биоинформатике. В этих областях нередко возникают задачи, когда надо понять, насколько две строки формально близки. То есть редакционные расстояния говорят не о смысловой близости слов или предложений, а только о близости их формы.
Как вычислить редакционное расстояние
Чтобы узнать редакционное расстояние между двумя строками, нужно посчитать минимальное количество посимвольных операций, которые нужно сделать, чтобы превратить первую строку во вторую. Таких операций всего четыре:
• удаление
• вставка
• замена
• перестановка соседних символов.
В операции может участвовать только один символ в строке. Количество операций — это и есть редакционное расстояние между двумя строками. Простейший пример: чтобы превратить «сон» в «слон», нужно произвести одну операцию: вставить букву «л» после «с».
Виды редакционных расстояний
Есть несколько основных редакционных расстояний. Основное отличие между ними — набор операций, который разрешено использовать. Расстояние Хэмминга разрешает только замены. Расстояние Джаро-Винклера — только перестановки.
Одно из самых известных редакционных расстояний — расстояние Левенштейна, которое разрешает все операции, кроме перестановки.
Попробуем посчитать расстояние Левенштейна между словами «карета» и «ракета». Чтобы превратить карету в ракету, нужно:
1) поменять первую букву — «к» на «р», после этой операции штраф равен 1, и у нас есть слово «какета»
2) поменять третью букву — «р» на «к», после этой операции штраф равен 2, и мы получили нужное слово «ракета».
Расстояние Левенштейна между словами «карета» и «ракета» равно двум.
А расстояние Дамерау-Левенштейна разрешает все четыре операции: замену, вставку, удаление и перестановку соседних символов.
Иногда измеряют пословное расстояние Левенштейна — при таком подходе за единицу принимается не один символ, а одно слово. Тогда между предложениями «Я люблю лингвистику» и «Я люблю компьютерную лингвистику» расстояние будет равно 1, а не 14, как было бы в случае посимвольных операций.
Мы также можем давать разный штраф за разные операции. Например, решить, что мы очень не любим замены символов и давать за них не 1, а 2 балла. В этом случае говорят, что операции имеют разный вес, и называют полученный результат взвешенным расстоянием Левенштейна.
Где применяют редакционное расстояние
В компьютерной лингвистике возникает множество задач, где нужно посчитать формальную меру близости между строками: например, для проверки орфографии, или для сравнения, насколько похожи два предложения. Первые системы автоматической проверки орфографии фактически сводились к подсчету редакционного расстояния Левенштейна или Дамерау-Левенштейна с использованием сложной системы штрафов. Система шла от слова к слову и проверяла, есть ли такое слово в словаре, а когда встречала слово, которого нет в словаре, то пыталась заменить его на наиболее близкое по редакционному расстоянию слово из словаря. Сейчас расстояние Левенштейна редко используется как единственный признак близости, но очень часто как один из.
В биоинформатике редакционные расстояния используются для определения похожести друг на друга разных участков ДНК или РНК, которые в таком случае представляются как последовательность, состоящая из A, G, C, U и T — это первые буквы четырех азотистых основания, которые могут входить в состав ДНК или РНК: аденин, гуанин и цитозин, урацил и тимин.
Бывают и неочевидные применения, например, определение, на что больше похожа буква на нечеткой фотографии текста, на «Л» или «П». В таком случае буквы представляют как стоящие друг над другом строки, состоящие из черных и белых пикселей.
https://sysblok.ru/knowhow/chto-takoe-redakcionnoe-rasstojanie/
https://sysblok.ru/glossary/rasstojanie-levenshtejna/
Ася Ройтберг
#knowhow #glossary
Чаще всего редакционное расстояние (edit distance) применяется в компьютерной лингвистике и биоинформатике. В этих областях нередко возникают задачи, когда надо понять, насколько две строки формально близки. То есть редакционные расстояния говорят не о смысловой близости слов или предложений, а только о близости их формы.
Как вычислить редакционное расстояние
Чтобы узнать редакционное расстояние между двумя строками, нужно посчитать минимальное количество посимвольных операций, которые нужно сделать, чтобы превратить первую строку во вторую. Таких операций всего четыре:
• удаление
• вставка
• замена
• перестановка соседних символов.
В операции может участвовать только один символ в строке. Количество операций — это и есть редакционное расстояние между двумя строками. Простейший пример: чтобы превратить «сон» в «слон», нужно произвести одну операцию: вставить букву «л» после «с».
Виды редакционных расстояний
Есть несколько основных редакционных расстояний. Основное отличие между ними — набор операций, который разрешено использовать. Расстояние Хэмминга разрешает только замены. Расстояние Джаро-Винклера — только перестановки.
Одно из самых известных редакционных расстояний — расстояние Левенштейна, которое разрешает все операции, кроме перестановки.
Попробуем посчитать расстояние Левенштейна между словами «карета» и «ракета». Чтобы превратить карету в ракету, нужно:
1) поменять первую букву — «к» на «р», после этой операции штраф равен 1, и у нас есть слово «какета»
2) поменять третью букву — «р» на «к», после этой операции штраф равен 2, и мы получили нужное слово «ракета».
Расстояние Левенштейна между словами «карета» и «ракета» равно двум.
А расстояние Дамерау-Левенштейна разрешает все четыре операции: замену, вставку, удаление и перестановку соседних символов.
Иногда измеряют пословное расстояние Левенштейна — при таком подходе за единицу принимается не один символ, а одно слово. Тогда между предложениями «Я люблю лингвистику» и «Я люблю компьютерную лингвистику» расстояние будет равно 1, а не 14, как было бы в случае посимвольных операций.
Мы также можем давать разный штраф за разные операции. Например, решить, что мы очень не любим замены символов и давать за них не 1, а 2 балла. В этом случае говорят, что операции имеют разный вес, и называют полученный результат взвешенным расстоянием Левенштейна.
Где применяют редакционное расстояние
В компьютерной лингвистике возникает множество задач, где нужно посчитать формальную меру близости между строками: например, для проверки орфографии, или для сравнения, насколько похожи два предложения. Первые системы автоматической проверки орфографии фактически сводились к подсчету редакционного расстояния Левенштейна или Дамерау-Левенштейна с использованием сложной системы штрафов. Система шла от слова к слову и проверяла, есть ли такое слово в словаре, а когда встречала слово, которого нет в словаре, то пыталась заменить его на наиболее близкое по редакционному расстоянию слово из словаря. Сейчас расстояние Левенштейна редко используется как единственный признак близости, но очень часто как один из.
В биоинформатике редакционные расстояния используются для определения похожести друг на друга разных участков ДНК или РНК, которые в таком случае представляются как последовательность, состоящая из A, G, C, U и T — это первые буквы четырех азотистых основания, которые могут входить в состав ДНК или РНК: аденин, гуанин и цитозин, урацил и тимин.
Бывают и неочевидные применения, например, определение, на что больше похожа буква на нечеткой фотографии текста, на «Л» или «П». В таком случае буквы представляют как стоящие друг над другом строки, состоящие из черных и белых пикселей.
https://sysblok.ru/knowhow/chto-takoe-redakcionnoe-rasstojanie/
https://sysblok.ru/glossary/rasstojanie-levenshtejna/
Ася Ройтберг