Сравнение исходных текстов программ путем выравнивания…
7
гие неравноценны,
s
(
a
i
,
b
j
) находят в матрице замен (таблицы цены за-
мены одного символа алфавита на другой символ), а значение (иногда
и способ вычисления)
g
подбирается для конкретных матрицы замен,
алгоритма выравнивания и задач исследования.
Во всех примерах, рассмотренных в данной статье, было принято
( , )
i
j
s a b
= 1 при
i
j
a b
и
( , )
i
j
s a b
= –1 в противном случае,
g
= 2 и
t
= 0.
Такие значения
( , )
i
j
s a b
и
g
выбраны исходя из результатов предвари-
тельных тестов предложенного алгоритма. Эти тесты показали прием-
лемые результаты выравнивания коротких последовательностей сим-
волов. При таких параметрах алгоритм настроен на поиск
непересекающихся идентичных подпоследовательностей в последова-
тельностях
A
и
B
. Кроме того, такие значения позволяют легко интер-
претировать результат сравнения: при запрете на делеции в участках
локального сходства значение в ячейке таблицы в нижнем правом
конце непрерывной диагонали из нескольких ячеек будет равно коли-
честву символов, совпадающих в обеих последовательностях. Значе-
ние
max
s
при этом будет соответствовать количеству символов в
наибольшей непрерывной общей подпоследовательности последова-
тельностей
A
и
B
. Значение
t
= 0 в данной работе было выбрано так,
чтобы оно не оказывало влияния на получаемый результат. Выбор
значения
t
для практических целей нуждается в дополнительном ис-
следовании и обсуждении.
Следует отметить, что выравнивание по данному алгоритму как
операция над последовательностями является некоммутативной. Так,
при выравнивании
A
к
B
и
В
к
А
в общем случае будут получаться раз-
личные таблицы, которые, соответственно, могут давать различные
выравнивания, по крайней мере, при слабом сходстве. Эта особенность
имеет место при использовании парного выравнивания в биоинформа-
тике. Возможно, эту особенность будет необходимо учитывать и при
сравнении исходных текстов программ с помощью выравнивания.
В настоящей работе при сравнении исходных текстов программ по-
следовательностями символов являлись последовательности токенов,
полученные при лексическом анализе. Токены считались одинаковыми,
если совпадали их лексические домены. Таким образом, алфавитом яв-
лялось множество лексических доменов языка, распознаваемых лекси-
ческим анализатором. Благодаря этому методика сравнения оказывалась
нечувствительной к замене идентификаторов.
Лексический анализатор распознавал следующие лексические до-
мены подмножества языка Scheme 5-й редакции: идентификаторы,
ключевые слова (else, =>, define, unquote, unquote-splicing, quote,
lambda, if, set!, begin, cond, and, or, case, let, let*, letrec, do, delay,
