- Заполняется
- Читается
- Ответ
Расстояние редактирования (расстояние Левенштейна)
Сколько изменений по одной букве превращают kitten в sitting? Три: заменить k на s, заменить e на i и добавить g. Это число — расстояние редактирования. По нему программы проверки орфографии упорядочивают подсказки, а биологи сравнивают гены. Введите два слова и посмотрите, как таблица его находит. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Введите два слова: первое идет сверху вниз по левому краю таблицы, второе — вдоль верхнего края. В каждой клетке записано наименьшее число правок, превращающих буквы до ее строки в буквы до ее столбца. В конце правки считываются в обратном порядке, начиная с правой нижней клетки. Кнопка Новый пример выбирает другую пару слов. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Введите два слова: первое идет сверху вниз по левому краю таблицы, второе — вдоль верхнего края.
- Нажмите Пуск или используйте Шаг и Назад, чтобы двигаться по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
- Смотрите, как каждая клетка выбирает самого дешевого из трех соседей, а затем как правки считываются в обратном порядке оранжевым цветом.
Как работает таблица
В клетке записано наименьшее число правок, превращающих буквы первого слова до ее строки в буквы второго слова до ее столбца. Первая строка считает вставки, строя второе слово с нуля, а первый столбец считает удаления. Если две буквы клетки совпадают, она копирует клетку сверху слева: правка не нужна. Иначе она на единицу больше наименьшего из трех соседей: сверху слева для замены, сверху для удаления и слева для вставки.
Как считать правки в обратном порядке
Правая нижняя клетка — это расстояние редактирования. Начиная с нее, приложение находит, от какого соседа пришло значение клетки, и переходит к нему: по диагонали для сохраненной или замененной буквы, вверх для удаленной, влево для вставленной. Если читать от левого верхнего угла, эти шаги дают кратчайший список правок, показанный под таблицей: обычная буква сохранена, k→s — замена, −e — удаление, +g — вставка.
Часто задаваемые вопросы
Что такое расстояние Левенштейна?
Другое название этого расстояния редактирования: наименьшее число вставок, удалений и замен одной буквы, превращающих одну строку в другую. Оно названо в честь Владимира Левенштейна, который описал его в 1965 году.
Чему равно расстояние редактирования между kitten и sitting?
3: заменить k на s, заменить e на i и вставить g в конце. Таблица показывает, что более короткого списка правок не существует.
Насколько быстр алгоритм расстояния редактирования?
Для слов длиной m и n в таблице (m + 1)·(n + 1) клеток, и каждая заполняется за один шаг, поэтому нужно время O(m·n). Если нужно только само расстояние, достаточно двух строк таблицы.
Какие еще бывают расстояния редактирования?
Расстояние Дамерау — Левенштейна также считает одной правкой перестановку двух соседних букв, что хорошо подходит для опечаток. Расстояние Хэмминга допускает только замены и работает для строк одинаковой длины. Расстояние LCS допускает только вставки и удаления.
Отправляются ли куда-нибудь данные?
Нет. Все вычисляется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор