Главная » Разборы » Аналог или цифра

Выравнивание журналов по порядку: общая подпоследовательность и общий набор

Запросить

Два журнала могут содержать одинаковые обозначения событий, но перечислять их в разном порядке. Сравнение множеств покажет полное совпадение состава и при этом не объяснит последовательность. Для отдельной учебной задачи возьмём журналы A, B, C, D и B, D, A, C. Буквы здесь — условные уникальные обозначения записей. Это не реальные журналы судна и не доказательство причинного порядка событий; рассмотрим только сохранение порядка в доступных последовательностях.

Совпадение набора и порядка. Первый ряд, Второй ряд, Общие элементы, Общая подпоследовательность.
Концептуальная схема. Набор содержит четыре общих элемента. С сохранением порядка можно выровнять два.

Определить правило совпадения

Общая подпоследовательность получается из каждого журнала удалением некоторых элементов без перестановки оставшихся. Соседство сохранять не обязательно, но относительный порядок выбранных элементов должен совпасть. Это отличается от непрерывного общего фрагмента, где промежуточные пропуски не допускаются.

В нашем примере A, C подходят обоим журналам: в первом A стоит раньше C, во втором тоже. Подходит и B, D. При этом нельзя взять все четыре буквы, потому что их общий порядок в двух исходных записях различается.

Проверить наибольшую длину

Рассмотрим все тройки первого журнала с сохранением порядка: ABC, ABD, ACD и BCD. Ни одна не встречается во втором как подпоследовательность. Для ABC во втором B расположен до A, для ABD также нарушен порядок A и B. Для ACD буква D расположена до A, для BCD — до C.

Значит, общей подпоследовательности длиной три нет. Длина два достижима, например для AC или BD. Следовательно, наибольшая общая длина равна двум. Этот результат можно проверить прямым перебором маленького учебного набора, не полагаясь на совпадение внешнего вида таблиц.

Сопоставить с общим набором

Множество букв в обоих журналах одинаково: A, B, C и D. Его пересечение содержит все четыре элемента. Поэтому вопрос «какие идентификаторы встречаются в обоих?» даёт другой результат, чем вопрос «какую наибольшую последовательность можно сохранить в обоих без перестановок?».

Ни одно сравнение не является универсально лучшим. Для проверки состава подходит одно, для обсуждения порядка — другое. Ошибка возникает, когда результат по набору идентификаторов выдают за подтверждение одинаковой последовательности записей или за полное совпадение двух журналов.

Сохранить несколько допустимых выравниваний

В примере существует более одного ответа наибольшей длины. Выбор AC не делает BD неверным. Если программа обязана возвращать только один вариант, правило выбора нужно описать отдельно. Иначе разные корректные реализации могут показать разные пары, сохраняя одинаковую максимальную длину.

При повторяющихся идентификаторах появляются дополнительные вопросы сопоставления конкретных экземпляров. Само совпадение буквы уже не указывает единственную запись. Для реальной работы понадобятся сведения об идентичности событий, времени и пропусках, которых в нашей упрощённой модели нет.

Ограничить вывод о времени

Порядок строк в выгрузке не обязательно равен физическому порядку возникновения событий. Он может отражать получение, сортировку или другое правило источника. Выравнивание двух доступных последовательностей само по себе не синхронизирует часы и не устанавливает причины перестановки.

Итог учебного разбора содержит одинаковый набор из четырёх обозначений и общую подпоследовательность максимальной длины два. Такое разделение помогает формулировать задачи сравнения судовых журналов точнее: совпадение состава, сохранение порядка и доказательство хронологии требуют разных исходных сведений и не заменяют друг друга одним удобным числом.

Все разборы

Весь каталог Motorola и аналогов — 13 позиций

Возимые и носимые станции, TETRA, PoC и Си-Би — всё, что держим на складе.