Различение множества текстов друг от друга для получения шаблона и данных (поиск общих подпоследовательностей)

Question

Предположим, есть много текстов, о которых известно, что они сделаны из одного шаблона (например, много HTML-страниц, отрисованных из шаблона, подкрепленного данными из какой-либо базы данных). Очень простой пример:

id:937 name=alice;
id:28 name=bob;
id:925931 name=charlie;

Учитывая только эти 3 текста, я хотел бы получить оригинальный шаблон, который выглядит следующим образом:

"id:" + $1 + " name=" + $2 + ";"

и 3 набора строк, которые были использованы с этим шаблоном:

• $ 1 = 937, $ 2 = alice
• $ 1 = 28, $ 2 = bob
• $ 1 = 925931, $ 3 = charlie

Другими словами, "шаблон" - это список общих подпоследовательностей, встречающихся во всех заданных текстах всегда в определенном порядке, а все остальное, кроме этих подпоследовательностей, следует считать "данными".

Я предполагаю, что общий алгоритм был бы очень похож на любой алгоритм LCS (самая длинная общая подпоследовательность), хотя и с другим кодом возврата, который каким-то образом разделял бы "шаблон" (символы, общие для всех заданных текстов) и "строки данных" (разные символы).

Бонусный вопрос: есть ли готовые решения для этого?

Answer 1

Я согласен с комментариями по поводу того, что вопрос плохо определен. Вероятно, формат гораздо более конкретен, чем указывает ваш общий вопрос.

Сказав это, что-то вроде RecordBreaker может помочь. Вы также можете использовать Google для ознакомления, если найдете какие-то полезные ссылки.

Answer 2

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

                   id:   937 name=alice  ;
                   id: 28    name=bob    ;
                   id:925931 name=charlie;
Inferred template: XXX      XXXXXX       X

Большинство инструментов, о которых я знаю для выравнивания нескольких последовательностей, требуют меньших алфавитов - ДНК или белка - но, надеюсь, вы найдете инструмент, который работает с алфавитом, который вы используете (который, по-видимому, по крайней мере, является всеми печатными символами ASCII). В худшем случае вы, конечно, можете реализовать DP самостоятельно: чтобы выровнять 2 последовательности (строки) глобально, вы используете алгоритм Нидлмана-Вунша, в то время как для более чем двух последовательностей существует несколько подходов, наиболее распространенным из которых является сумма пар скоринг. Точный алгоритм для k > 2 последовательностей, к сожалению, требует экспоненциального времени в k, но эвристика, используемая в инструментах биоинформатики, таких как MUSCLE, намного быстрее и производит выравнивания, которые очень хороши. Если их убедить работать с алфавитом, который вы используете, они будут естественным выбором.