Расстояние Левенштейна

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

Например, чтобы превратить слово «строка» в слово «собака» надо «т» заменить на «о», «р» на «б» и «о» на «а», вставок и удалений не требуется — таким образом расстояние Левенштейна между этими двумя словами равно 3.

Расстояние Левенштейна и его обобщения активно применяется:

• для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированого текста или речи).
• для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
• в биоинформатике для сравнения генов, хромосом и белков.

Более подробно можно почитать в Википедии.

Расстояние Левенштейна

Исходная строка

Целевая строка

Рассчитать

Расстояние Левенштейна

 

 Ссылка  Сохранить  Виджет