Эффективный алгоритм сравнения документов в формате ${\mathrm{\LaTeX}}$

Рассматривается задача построения различий, возникающих при редактировании документов в формате ${\mathrm{\LaTeX}}$. Каждый документ представляется в виде синтаксического дерева, узлы которого называются токенами. Строится минимально возможное текстовое представление документа, не меняющее синтаксическое дерево. Весь текст разбивается на фрагменты, границы которых соответствуют токенам. С помощью алгоритма Хиршберга строится отображение последовательности текстовых фрагментов изначального документа в аналогичную последовательность отредактированного документа, соответствующее минимальному редактирующему расстоянию. Строится отображение символов текстов, соответствующее отображению последовательностей текстовых фрагментов. В синтаксических деревьях выделяются токены такие, что символы соответствующих фрагментов текста при отображении либо все не меняются, либо все удаляются, либо все добавляются. Для деревьев, образованных остальными токенами, строится отображение с помощью алгоритма Zhang–Shasha.

Ключевые слова: автоматизация, анализ текста, лексема, машинное обучение, метрика, редактирующее расстояние, синтаксическое дерево, токен, ${\mathrm{\LaTeX}}$
Цитата: Чувилин К.В. Эффективный алгоритм сравнения документов в формате ${\mathrm{\LaTeX}}$ // Компьютерные исследования и моделирование, 2015, т. 7, № 2, с. 329-345
Citation in English: Chuvilin K.V. An efficient algorithm for ${\mathrm{\LaTeX}}$ documents comparing // Computer Research and Modeling, 2015, vol. 7, no. 2, pp. 329-345
Creative Commons License
Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в Перечень российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук ВАК, группы специальностей: 01.01.00, 01.02.00.
 

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал индексируется в Scopus