Сравнение исходных текстов программ путем выравнивания…
11
на языке Scheme. Несмотря на то что в различных текстах сходные не-
большие фрагменты следуют в разном порядке, при одноцветной раз-
метке они воспринимаются как один большой общий фрагмент. Таким
образом, этот листинг можно рассматривать как пример ложно положи-
тельного результата обнаружения сходства. Пример показывает, что це-
лесообразно классифицировать и сравнивать различные ключевые сло-
ва как разные токены. Кроме того, в таких случаях существенную
помощь при визуальной оценке результата сравнения может оказать ко-
дирование непрерывных подпоследовательностей цветом.
Исходя из изложенного, можно сделать вывод о том, что алгоритм
в большей степени пригоден для сравнения двух исходных текстов с
уже обнаруженным сходством, чем для поиска похожих программ в
некоторой выборке.
Заключение.
В ходе работы был предложен алгоритм сравнения
исходных текстов программ путем выравнивания последовательностей
токенов и на ряде примеров показана его работоспособность. Допол-
нительно в статье приведено описание алгоритма в виде набора рекур-
сивных формул. Представление в виде таких формул правил заполне-
ния таблицы традиционно используется для описания алгоритмов
выравнивания последовательностей, основанных на динамическом
программировании. В данной статье в виде формул представлены
также правила поиска пути по этой таблице. Последнее удобно ис-
пользовать для реализации алгоритма в рамках парадигмы функцио-
нального программирования.
Вместе с тем указанный алгоритм вряд ли готов к немедленному
практическому применению. Так, для поиска не полной идентичности,
а именно сходства кодов целесообразно применить матрицы замен,
аналогичные используемым в биоинформатике при выравнивании по-
следовательностей белков. Для каждого языка программирования, ве-
роятно, потребуется разработать свою специфичную матрицу замен.
Возможно, сравнению также должны подлежать значения констант.
Параметры алгоритма (функция оценки сходства, штраф за делецию и
само разрешение делеций, пороговое значение сходства) должны быть
адаптированы к этим матрицам.
Остаются открытыми вопросы о пригодности данного алгоритма
для поиска похожих программ в некоторой выборке и о статистической
оценке значимости сходства, хотя потенциально эта возможность суще-
ствует, так как в биоинформатике такая оценка успешно применяется.
Далее, потребуется количественно охарактеризовать предложенный ме-
тод как бинарный классификатор (например, его способность отличать
«списанное» решение от самостоятельного) для исходных кодов раз-
личной длины и для различных языков программирования.
