Заполнено ячеек
Совпадающие пары
Наибольшая пока

  • Заполняется
  • Читается
  • Ответ

Подробнее о наибольшей общей подпоследовательности

Наибольшая общая подпоследовательность (LCS)

Какие буквы есть в обоих словах, причем в том же порядке? На этот вопрос отвечает наибольшая общая подпоследовательность, и на ней построены инструменты diff, проверка орфографии и сравнение ДНК. Введите два слова, посмотрите, как заполняется таблица из их букв, а затем проследите ответ обратно от угла. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Введите два слова: первое идет сверху вниз вдоль левого края таблицы, второе — вдоль верхнего. В каждой клетке записана длина наибольшей общей подпоследовательности букв до ее строки и столбца. В конце буквы считываются обратным ходом от правой нижней клетки. Кнопка Новый пример выбирает другую пару слов. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Введите два слова: первое идет сверху вниз вдоль левого края таблицы, второе — вдоль верхнего.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
  3. Посмотрите, как каждая клетка сравнивает свои две буквы, а затем пройдите по оранжевому пути обратно от угла, чтобы прочитать ответ.

Как устроена таблица

В клетке записана длина наибольшей общей подпоследовательности букв первого слова до ее строки и букв второго слова до ее столбца. Строка и столбец, отмеченные –, обозначают пустое слово, поэтому в них 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 в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор