- Заполняется
- Читается
- Ответ
Наибольшая общая подпоследовательность (LCS)
Какие буквы есть в обоих словах, причем в том же порядке? На этот вопрос отвечает наибольшая общая подпоследовательность, и на ней построены инструменты diff, проверка орфографии и сравнение ДНК. Введите два слова, посмотрите, как заполняется таблица из их букв, а затем проследите ответ обратно от угла. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Введите два слова: первое идет сверху вниз вдоль левого края таблицы, второе — вдоль верхнего. В каждой клетке записана длина наибольшей общей подпоследовательности букв до ее строки и столбца. В конце буквы считываются обратным ходом от правой нижней клетки. Кнопка Новый пример выбирает другую пару слов. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Введите два слова: первое идет сверху вниз вдоль левого края таблицы, второе — вдоль верхнего.
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
- Посмотрите, как каждая клетка сравнивает свои две буквы, а затем пройдите по оранжевому пути обратно от угла, чтобы прочитать ответ.
Как устроена таблица
В клетке записана длина наибольшей общей подпоследовательности букв первого слова до ее строки и букв второго слова до ее столбца. Строка и столбец, отмеченные –, обозначают пустое слово, поэтому в них 0. Если две буквы клетки равны, клетка на единицу больше клетки слева сверху. Если они различаются, одна из двух букв не входит в ответ, поэтому клетка берет большее из значений клетки сверху и клетки слева.
Как прочитать буквы
Правая нижняя клетка — это длина ответа. Чтобы найти сами буквы, начните с нее: там, где две буквы совпадают, эта буква входит в подпоследовательность, и нужно перейти влево вверх; иначе нужно перейти к большей из клеток сверху и слева. Буквы, собранные по пути и прочитанные в обратном порядке, образуют наибольшую общую подпоследовательность. Могут быть и другие той же длины; обратный ход находит одну из них.
Часто задаваемые вопросы
Чем подпоследовательность отличается от подстроки?
Подстрока — это буквы, стоящие подряд, как ACE в RACER. Подпоследовательность сохраняет порядок, но может пропускать буквы, поэтому ACE — еще и подпоследовательность ABCDE. Наибольшая общая подстрока — другая задача с похожей таблицей.
Насколько быстр алгоритм LCS?
Для слов длиной m и n в таблице m·n клеток, и каждая заполняется за один шаг, поэтому объем работы — O(m·n). Для двух текстов по 10 000 строк это 100 миллионов клеток, поэтому инструменты diff используют более хитрые методы, основанные на той же идее.
Единственна ли наибольшая общая подпоследовательность?
Нет. У ABCBDAB и BDCABA три разные общие подпоследовательности длины 4: BCBA, BCAB и BDAB. Таблица дает длину, а обратный ход выбирает одну из них.
Показывает ли LCS, насколько похожи два слова?
Отчасти. Два слова длиной m и n с наибольшей общей подпоследовательностью длины k можно превратить одно в другое, удалив m − k букв и вставив n − k. Редакционное расстояние, которое разрешает еще и замену буквы, часто оказывается лучшей мерой.
Отправляется ли что-нибудь куда-либо?
Нет. Все вычисляется в вашем браузере, а последние настройки остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор