Google
 
Главная2-й курс3-й курс4-й курс5-й курсСпецкурсыСсылкиКарта(версия для печати)

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

См. также
David Eppstein. Longest Common Subsequence (источник на английском языке) Общие подпоследовательности. Дистанция (в том числе перевод работы Дэвида Эпштайна, но с ошибками)

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

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

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

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

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

Итеративный вариант 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]. Наиболее популярными являются значения:

Требования

Интерфейс

При реализации варианта а) для отображения различий достаточно вывести две исходные строки выравненные по вхождениям общей подпоследовательности. Например, пусть введены две строки «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);
———————————————————————-

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

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

Литература: