В ходе работы в последнее время нам все чаще приходится сталкиваться с книгами в электронном формате, материалами на веб-сайтах, промышленной документацией для программных продуктов, и многими другими электронными источниками информации. В частности, сложное программное обеспечение обычно сопровождается большим количеством подробной документации, которая содержит много сложно-структурированной информации.
Одной из важных особенностей электронной документации является наличие повторяющихся фрагментов текста, что значительно усложняет написание документа, так как в случае отсутствия дополнительных инструментов процесс его разработки и сопровождения может оказаться весьма трудоёмким и отнять немало времени. Также, если не
отслеживать наличие повторов в тексте, становится вероятным понижение качества документа. Поэтому важной задачей становится упрощение и частичная автоматизация процесса поиска и рефакторинга таких повторов. Для её выполнения существуют такие решения, как DocLine[1][2][3] — проект, целью которого является создание инструмента для разработки и сопровождения электронной документации со значительными повторами в тексте. DocLine работает с достаточно популярным форматом DocBook[4] и его расширением DRL[5] и предоставляет возможности для нахождения имеющихся в тексте повторов и удобной работы с ними.
В большинстве случаев существенное количество повторов не являются дословными. Существующий и реализованный в DocLine на данный момент алгоритм[6] позволяет искать в тексте точные и вариативные повторы с одним фрагментом текста в середине. Алгоритм комбинирует находящиеся рядом точно повторяющиеся фрагменты текста. Последние ищутся при помощи реализованного с использованием инструмента Clone Miner[7][8] алгоритма на основе суффиксных
массивов[9]. Clone Miner предназначен, в первую очередь, для поиска повторов в исходных тестах программ. Изменения при копировании текста программ обычно представлены небольшим количеством достаточно крупных локализованных правок. Для текстов на естественных языках характерны как содержательные, так и стилистические правки после копирования, которые приводят к большому количеству мелких изменений. В случае текстов, таким образом, мы сталкиваемся со следующими ограничениями подхода[10]: возможен поиск нечётких клонов только с одной вариативной частью, рассматриваются кандидаты клонов только с промежутком в середине клона (не в начале или конце).
Соответственно, возникает необходимость в функциональности, позволяющей быстро находить значительные нечёткие повторы в тексте, и которая не имела бы описанных выше ограничений.
Так как работа направлена на нахождение нечётких повторов в тексте документации, естественно при создании алгоритма было использовать существующие методы для нечёткого поиска. В ходе дипломной работы был использован и модифицирован для нечёткого сравнения алгоритм Рабина-Карпа[11] с использованием хеширования по сигнатуре[12][13] для быстрого сравнения фрагментов текста, а так же улучшенный алгоритм вычисления редакционного расстояния[14] между двумя фрагментами текста.
В рамках данной работы были достигнуты следующие результаты:
1. Изучены средства нечёткого поиска и сопоставления текстов, научные работы и алгоритмы в области нечёткого поиска.
2. Предложен новый алгоритм с использованием модификаций алгоритма Рабина-Карпа, хеширования по сигнатуре и алгоритма вычисления редакционного расстояния. Алгоритм реализован.
3. Проведены эксперименты и тестирование алгоритма
