А.В. Дубанов
2
Для решения задачи поиска похожих фрагментов кода наше вни-
мание привлекли
методы парного
выравнивания последовательно-
стей
. Эти методы широко применяются в биоинформатике для анно-
тации белковых и нуклеотидных последовательностей по сходству.
Такая аннотация основана на выявлении сходных (необязательно
идентичных) подпоследовательностей в аннотированной последова-
тельности и в последовательности, охарактеризованной ранее. В био-
информатике такие подпоследовательности называют гомологичными
или консервативными. Применительно к исходному коду будем назы-
вать их похожими или сходными. Весьма привлекательными особен-
ностями алгоритмов локального выравнивания являются возможности
их настройки, статистической оценки уровня значимости обнаружен-
ного сходства, а также наглядного представления результатов вырав-
нивания [3]. Методы локального выравнивания уже успешно приме-
няются на практике для анализа научно-технических текстов [4].
Поэтому мы предложили использовать парное выравнивание для
сравнения исходных кодов.
Целью данной работы были модификация алгоритма выравнива-
ния последовательностей символов для сравнения исходных текстов
программ и демонстрация его способности находить похожие фраг-
менты в исходных текстах программ. В дальнейшем этот алгоритм
предполагается использовать для выявления случаев «списывания»
домашних заданий студентами, поэтому он должен быть нечувстви-
тельным к переименованию идентификаторов (имен процедур и пе-
ременных), задаваемых программистом. В связи с этим в качестве
выравниваемых последовательностей рассматривались последова-
тельности токенов, полученных при лексическом анализе исходных
текстов.
Алгоритм выравнивания последовательностей
. Алгоритм был
получен путем модификации одного из описанных в литературе алго-
ритмов выравнивания последовательностей биополимеров и реализо-
ван на языке Haskell редакции 2010 г. с использованием Haskell
Platform 2013.2.0.0 в операционной системе OpenSUSE 13.1 на персо-
нальном компьютере с процессором Intel Core i5 (2,6 ГГц) и 4 Гбайт
RAM. Разработанная программа включает в себя лексический анализа-
тор, реализацию алгоритма выравнивания и средства вывода результа-
та вычислений в виде HTML-файла, работающие последовательно. Те-
сты были выполнены на примерах фрагментов кода, написанных на
ограниченном подмножестве языка Scheme 5-й редакции (R5RS).
За основу был взят алгоритм парного выравнивания, предназна-
ченный для нахождения непересекающихся участков наибольшего
сходства в двух последовательностях биополимеров, причем необяза-
