Расстояние Левенштейна
Вычислите расстояние редактирования между двумя строками онлайн. Калькулятор показывает минимальное количество операций вставки, удаления и замены, а также матрицу расстояний.
Как пользоваться: Расстояние Левенштейна
- Введите первую строку в поле «Первая строка».
- Введите вторую строку в поле «Вторая строка».
- Нажмите «Рассчитать» — отобразится расстояние, процент сходства и список операций.
- Изучите матрицу расстояний, чтобы понять оптимальный путь преобразования.
Таблица значений
| Из | В |
|---|---|
| kitten → sitting | 3 |
| sunday → saturday | 3 |
| abc → abc | 0 |
| cat → car | 1 |
Примеры использования
- •Нечёткий поиск и автокоррекция в текстовых редакторах и поисковых системах.
- •Сравнение версий строк кода при рефакторинге и проверке изменений.
- •Анализ сходства ДНК-последовательностей в биоинформатике.
- •Обнаружение опечаток и близких совпадений в базах данных.
Формула
Расстояние Левенштейна — минимальное число операций (вставка, удаление, замена символа), необходимых для преобразования одной строки в другую. Вычисляется методом динамического программирования: D(i,j) = min(D(i-1,j)+1, D(i,j-1)+1, D(i-1,j-1)+[s1[i]≠s2[j]]).
Часто задаваемые вопросы
Что такое расстояние Левенштейна?
Расстояние Левенштейна (редакционное расстояние) — мера различия двух строк, равная минимальному числу односимвольных операций (вставка, удаление, замена), нужных для преобразования одной строки в другую.
Как рассчитывается процент сходства?
Сходство вычисляется по формуле: (1 − расстояние / максимальная длина строки) × 100%. Например, если расстояние равно 2, а длиннейшая строка имеет 10 символов, сходство составит 80%.
Где применяется расстояние Левенштейна?
Алгоритм применяется в системах проверки орфографии, поисковых движках (нечёткий поиск), биоинформатике (сравнение последовательностей ДНК), системах автокоррекции и обнаружении плагиата.