Диссертация (1149623), страница 6
Текст из файла (страница 6)
В работе [40] рассматривается задачаинтеллектуального плагиата — перефразирования оригинального содержимого— и предлагается следующая классификация способов перефразирования: использование лексического изменения, изменение в построении предложений иизменения в модальности. Одним из результатов проведённого исследования является специальный корпус перефразирования, который может использоватьсяпри обнаружении содержательного плагиата, когда чужие идеи выражаются«своими словами».В [151] рассматривается задача поиска неточно повторяющихся фрагментовтекста в нескольких больших коллекциях документов, содержащих научные ста-На сервере кеширование, как правило, применяется для предотвращения повторной генерации одних и тех же страниц, на клиенте — для того, чтобы не загружать одни и те же страницымногократно.525тьи, записи в блогах, произвольные веб-страницы (десятки миллионов документов на английском и китайском языках общим объёмом в сотни Гб).
В работепредлагается алгоритм, который, пользуясь N-граммами, находит близкие помере Жаккара [82] предложения в различных документах, а затем решает в отношении найденных предложений задачу выравнивания последовательностей6.Обе операции требуют вычислений значительного объёма. Авторы ставят эксперименты на вычислительном кластере, применяя подход MapReduce [56], и уделяют отдельное внимание производительности предлагаемого решения. Анализируя полученные результаты, авторы делают вывод об эффективности предложенного ими алгоритма.Работа [67] посвящена анализу повторяющихся фрагментов в веб-страницах.В ней показывается, что 40-50% Веб-контента приходится на потенциальныешаблоны, причём, согласно оценкам авторов, эта доля на момент публикацииработы росла со скоростью 6-8% в год.
Авторы предлагают рандомизированныйалгоритм7 выявления текстовых шаблонов в коллекциях веб-страниц и делаютвывод о том, что бо́льшая часть Интернет-трафика приходится на стандартныеданные, а не на уникальное содержимое Веб-страниц. При этом они отмечают,что источником бо́льшей части ссылок между страницами также являются имеющиеся в них повторы.Помимо того, что работы, рассмотренные в данном разделе, интересны с точкизрения поиска повторов в текстовых данных, очевидна общая с многими работами из раздела 1.2 направленность на нахождение повторов в текстовых данных. Основные цели перечисленных в данном разделе работ — оптимизация ра-Задача выравнивания последовательностей (sequence alignment) заключается в нахождениинаибольшей общей подпоследовательности двух или, для, случая множественного выравнивания (Multiple Sequence Alignment), большего количества строк.
Данная задача актуальнадля биоинформатики и информатики [86].6Рандомизированный алгоритм — процедура, в которой один или несколько шагов основанына случайном выборе правила [3, 4].726боты программного обеспечения, повышение сопровождаемости коллекций документов, обнаружение и анализ плагиата.
Кроме того, специфика предметныхобластей информационного поиска и программной инженерии различна: информационный поиск работает с большими (до сотен Гб) коллекциями данных, длячего часто требуется значительные вычислительные ресурсы. При поиске информации приоритетной является не полнота, а скорость работы и правильное ранжирование результатов.Поиск клонов в программном обеспеченииВ большинстве работ по поиску и анализу повторов в документацииПО [76, 89, 110, 111, 145, 150] используются средства поиска повторов в кодеПО (software clone detection tools). Рассмотрим вопрос поиска программных клонов подробнее.Несмотря на богатый набор средств повторного использования, предоставляемый современными языками и системами программирования, проблема нахождения повторов (клонов) в исходных кодах программного обеспечения являетсяактуальной.
В попытках найти её решение многими исследователями создавались средства обнаружения программных клонов, подробный систематизирующий обзор которых доступен в [124].Многие средства поиска повторов в исходных кодах анализируют синтаксические деревья программ. Поскольку синтаксическое дерево программы являетсярезультатом работы синтаксического анализатора, подобные инструменты работают с лишь программами, написанными на конкретных языках программирования, поддерживаемых этими инструментами.
Примерами таких средств являются Deckard [85] и ClemanX [106]. Также предлагают находить программныеклоны при помощи анализа синтаксических деревьев М.Х. Ахин и В.М. Ицыксон [1] и Н.Г. Зельцер [6]. Интересное решение предлагают Б. Бейгель (B. Beigel)и Д. Диль (D. Diehl) [43]. В их работе описывается фреймворк JCCD, предназначенный для написания и настройки поиска клонов при помощи синтаксических27деревьев.
Но грамматику исходного языка при этом может задавать пользователь.С точки зрения данной диссертационной работы интересен поиск повторов втекстах на естественных языках. При помощи анализа синтаксических деревьев,очевидно8, его нельзя реализовать столь же просто, как для исходных кодов ПО.На практике это подтверждается тем, что многие упомянутые средства анализатекстов на естественных языках [32, 75, 105, 137] используют для синтаксического и семантического анализа нейронные сети, а не построенные по формальным грамматикам анализаторы.Тем не менее, поиск повторов в текстах на естественных языках можно осуществлять при помощи универсальных средств поиска программных клонов, таких как Simian [130] и Clone Miner [35].
Универсальные средства поиска клоноврассматривают исходный код программ как обычный «плоский» текст, при этомвыполняя базовый анализ текста с разбиением на токены (слова), но не выполняясинтаксического анализа. В дальнейшем будем понимать под токеном подстроку документа, ограниченную слева и справа неотображаемыми символами(пробелами, переводами строк, табуляцией и т.д.)9.
Так, например, каждая изстрок «FM Registers» и «Primary key» состоит из двух токенов. В отличие от определяющих синтаксис грамматик, лексические правила различных языков программирования часто бывают похожими друг на друга, что позволяет подобныминструментам не зависеть от входного языка. Общие лексические правила просты и у естественных языков: для разбиения текстов на токены достаточно распознавать алфавит языка, пробелы и знаки препинания. Simian пригоден для по-Типичные компьютерные языки относятся к классу контекстно-свободных.
Для этого классасуществуют простые и эффективные средства синтаксического анализа. Но естественныеязыки не являются контекстно-свободными [129], и простых средств однозначного синтаксического анализа для них не создано.8Фактически, речь идёт об отдельных словах текста, поэтому часто вместо термина «токен»будем использовать также термин «слово».928иска повторов в любых текстовых файлах. При анализе исходных текстов программ, написанных на поддерживаемых им языках программирования, инструмент позволяет использовать дополнительные настройки наподобие «распознавать идентификаторы и игнорировать их регистр» и т.д.
Более подробное описание Clone Miner будет приведено ниже.1.4. Средства разметки электронных документовВ этом разделе рассматриваются известные языки и программные средства,предназначенные для разметки текстов. В обзоре будет сделан акцент на возможности повторного использования текстов.В 1964 году Дж. Зальцером (J.
Saltzer) была создана система RUNOFF [34].Язык разметки системы RUNOFF позволял снабжать текст документа простымидирективами форматирования (жирный, подчёркнутый текст и т.д.). СистемаRUNOFF также брала на себя работу по выравниванию текста и генерации колонтитулов. В настоящее время семейство языков разметки ROFF (troff, nroff,groff) [68], основанное на языке RUNOFF и поддерживаемое системой Unix ManPages [103], используется в сообществах Unix и Linux. Система Unix Man Pagesреализует форматирование для вывода на терминал, принтер и для экспорта ввиде Веб-страниц. Система поддерживает концепцию Single Source (единый источник): из одного исходного представления генерируются различные конечныеформаты.
RUNOFF/Unix Man Pages не предоставляет возможностей повторногоиспользования.ШирокоизвестенсозданныйЧ. Гольдфарбом(C. Goldfarb)языкSGML [71, 81]. На базе SGML был создан язык XML, а также языки разработкипромышленной документации — DocBook [147] и DITA [55]. DocBook и DITAподдерживают Single Source: в качестве выходных форматов используются PDF,Eclipse Help, HTML и др. DocBook и DITA поддерживают также смысловую (семантическую) разметку. Технический писатель может оперировать такими понятиями как «раздел второго уровня», «листинг программы», «выделенный текст».Внешний вид документа определяется генератором выходного формата и29настраивается отдельно от самого документа.
Такой подход называетсяWYSIWYM (What You See Is What You Mean), в противоположность подходуWYSIWYG (What You See Is What You Get), предлагаемому текстовыми процессорами офисных пакетов, например, Microsoft Word.DITA предоставляет возможности повторного использования. Для этого описание каждой темы выделяется в отдельный модуль и может быть использованоповторно в различных контекстах с применением условного включения. ВDocBook базовые возможности повторного использования реализованы при помощи механизма XInclude10; дополнительные возможности повторного использования предоставляются сторонними средствами, например, системой DocLine [11].Для оформления научных текстов популярным является язык разметки ТеХ,созданный Д. Кнутом (D.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
