Анализ изменений в тексте (MASM)

См. также

David Eppstein. Longest Common Subsequence (источник на английском языке)

Общие подпоследовательности. Дистанция (в том числе перевод работы Дэвида Эпштайна, но с ошибками)

Вариант 3-го практического задания для групп 110, 111 (2006)

Постановка задачи

Реализовать:

алгоритм выявления максимальной общей подпоследовательности двух входных последовательностей (оканчивающихся символом «конца файла» Ctrl+Z) на базе итеративного варианта алгоритма LCS (Longest Common Subsequence).
диалоговый интерфейс пользователя, обеспечивающий ввод двух последовательностей и вывод результатов выявления изменений.

Варианты сложности

длина входных последовательностей ограничена 512 символами (более простой вариант),
входные последовательности представляют собой тексты, поделённые не более чем на 256 строк, длина которых не превышает 128 символов (вариант посложнее).

Краткие теоретические сведения

Итеративный вариант LCS

Для начала необходимо построить таблицу различий. Пример на псевдокоде:

{
  A. B - входные последовательности
  m, n - длина A и B соответственно
  L    - матрица размера m x n
}
 
выделить память для матрицы L;
 
for i := m downto 0 do
  for j := n downto 0 do
  begin
    if ( A[i] == 0 ) or ( B[j] == 0 )
      L[i,j] := 0;
    else if A[i+1] = B[j+1]
      L[i,j] := 1 + L[i+1, j+1];
    else
      L[i,j] := max ( L[i+1, j], L[i, j+1] );
  end;
{
  в L[0,0] будет длина максимальной общей подпоследовательности
}

После построения матрицы L для получения самой общей подпоследовательности достаточно выполнить следующий проход:

S := '';
i := 0;
j := 0;
 
while ( i < m ) and ( j < n ) do
begin
  if A[i] = B[j] then
  begin
    S := S + A[i];
    i := i + 1;
    j := j + 1;
  end
  else if L[i+1,j] >= L[i,j+1]
    i := i + 1;
  else
    j := j + 1;
end

Контрольная сумма

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

Чтобы КС с приемлемой вероятностью идентифицировала строки, необходимо подобрать подходящий алгоритм. Предлагается реализовать алгоритм вычисления циклического избыточного кода CRC-16 (Cyclic Redundancy Code).

Принцип вычисления CRC основан на выполнении деления на некоторый целый делитель длинного целого делимого, в качестве которого выступает исходная последовательность данных. При этом первый символ последовательности выступает в качестве старшего байта «большого целого» и т.д. все остальные байты. Тогда на примере CRC-4 вычисление циклического избыточного кода можно проиллюстрировать схемой «деления» в столбик.

  A    A+1
_ 1111 0000 | 10010  — делитель
  1001 0
  ________
 _ 110 00
   100 10
   ________
  _ 01 100
    00 000
    ________
   _ 1 1000
     1 0010
     _______
       0110 — это и есть CRC-4

Надо заметить, что, во-первых, запоминать частное не нужно, важен только остаток. А во-вторых, количество бит делителя на единицу больше, чем разрядность самого циклического кода, и старший бит делителя всегда установлен. Это требование определяет разрядность вычисляемого избыточного кода, так как при его невыполнении получится меньший диапазон значений «остатков».

Выбор делителя — важная задача, подробно рассмотренная в [2]. Наиболее популярными являются значения:

10001000000100001 — для 16-битного кода (стандарт «X25»),
11000000000000101 — для 16-битного кода,
100000100110000010001110110110111 — для 32-битного кода (стандарт IEEE 802.3 «Ethernet»).

Требования

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

Интерфейс

При реализации варианта а) для отображения различий достаточно вывести две исходные строки выравненные по вхождениям общей подпоследовательности. Например, пусть введены две строки «x := tg(a);» и «y := arcsin(b);». Тогда вывод различий может выглядеть следующим образом:

x := tg....(a);
 ||||      | ||
y := arcsin(b);

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

i := 1;
for j := 1 to 10 do
  i := i * j;
writeln;

// i := 1;
readln (i);
for j := 1 to 10 do
  i := i * j;
writeln (i);

Тогда вывод различий может выглядеть так:

——————————————————————-(1)
001      i := 1;
——————————————————————-(2)
    001  // i := 1;
    002  readln (i);
———————————————————————-
======================================================================
002 003  for j := 1 to 10 do
003 004    i := i * j;
======================================================================
——————————————————————-(1)
004      writeln;
——————————————————————-(2)
    005  writeln (i);
———————————————————————-

Тестирование

При тестировании рекомендуется использовать перенаправление ввода-вывода операционной системы.

Литература:

Кнут Д.Е. Искусство программирования для ЭВМ, т. 2 «Получисленные алгоритмы» — М.: «Мир», 1977.
Tanenbaum, A.S. Computer Networks — Prentice Hall, 1981. ISBN: 0 13 164699 0.