Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет

Крутояров, Дмитрий Владимирович

Автоматизация и управление технологическими процессами и производствами (по отраслям)

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет

кандидата технических наук: Крутояров, Дмитрий Владимирович
город: Москва
год: 2006
специальность ВАК РФ: 05.13.06

Диссертация по информатике, вычислительной технике и управлению на тему «Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет»

Автореферат диссертации по теме "Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет"

На правах рукописи

КРУТОЯРОВ ДМИТРИЙ ВЛАДИМИРОВИЧ

1 ' ■

' ? .«■"

АВТОМАТИЗИРОВАННАЯ СИСТЕМА ПОИСКА ЗАИМСТВОВАНИЙ В ЭЛЕКТРОННЫХ ИЗДАНИЯХ, ОПУБЛИКОВАННЫХ В СЕТИ ИНТЕРНЕТ

Специальность 05.13.06 — Автоматизация и управление технологическими процессами и производствами (полиграфическое производство)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2006

Работа выполнена на кафедре информационных технологий в Московском государственном университете печати

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Гасов Владимир Михайлович

доктор технических наук, профессор Назаров Александр Викторович

кандидат технических наук, доцент Куликов Вячеслав Васильевич Издательство «ТЕРРА»

Защита диссертации состоится 20 декабря 2006 г. в ^ час. мин. на заседании диссертационного совета К 212.147.02 при Московском государственном университете печати (МГУП) по адресу: 127550, Москва, ул. Прянишникова, д. 2а.

С диссертацией можно ознакомиться в библиотеке МГУП.

Автореферат разослан «>1 » ноября 2006 г.

Ученый секретарь диссертационного совета д.т.н., профессор

/у,. Аи«л~

В.Н. Агеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы обусловлена проблемой нарушения авторских прав в электронных изданиях (ЭИ), опубликованных в сети Интернет. С каждым годом все больше изданий переводится в электронную форму. Одни из них публикуются на компакт-дисках, другие — в глобальной сети Интернет. При этом практически любое электронное издание, в том числе и опубликованное в сети Интернет, является объектом авторского права. В настоящее время, многие ошибочно считают, что материалы, опубликованные в глобальной сети Интернет можно копировать, не заботясь об исключительных правах автора. Статья 9 закона об «Авторском праве и смежных правах» гласит: «Для возникновения и осуществления авторского права не требуется регистрации произведения, иного специального оформления произведения или соблюдения каких-либо формальностей».

Проблема незаконного заимствования текстовых материалов затрагивает и систему высшего образования. В глобальной сети Интернет опубликованы, в некоторых случаях незаконно, многие электронные издания. В силу незнания действующего законодательства в области авторского права, многие пользователи сети, в том числе и студенты, считают возможным копировать фрагменты опубликованных в сети Интернет электронных изданий, с последующим присвоением авторства. По данным, опубликованным Education Week (http://www.plagiarism.org/plagiarism_stats.html), основанным на национальном исследовании (USA) следует, что 54% студентов незаконно используют в своих работах материалы, опубликованные в сети Интернет. Стоит также отметить, что 47% учащихся считают, что их преподаватели часто игнорируют случаи плагиата в сдаваемых работах.

В настоящее время в мире существует значительное количество систем, позволяющих осуществлять поиск заимствований (обзор систем представлен в четвёртом разделе первой главы диссертационной работы), однако в России разработки в данном направлении ведутся не так давно. Система анализа текстов на наличие заимствований Antiplagiat.ru весной 2005 года впервые в России предложила набор услуг, в совокупности реализующих технологию проверки документов на наличие заимствований из общедоступных сетевых источников1. Основным недостатком существующей системы является огра-

1 http://www.antiplagiat.ni/

ниченность области поиска документов с заимствованиями, которая включает в себя лишь документы, ранее загруженные из сети Интернет, прошедшие процедуру фильтрации и занесённые в системную базу данных2.

Актуальность исследования заключается в необходимости создания методов и автоматизированного инструментария, позволяющих осуществлять эффективный и адекватный поиск ЭИ, опубликованных в сети Интернет, содержащих заимствования.

Предмет и объект исследования. Объектом исследования являются системы, позволяющие производить поиск заимствований в текстовом материале, опубликованном в глобальной сети Интернет. Предметом исследования и разработки являются методы и алгоритмы, позволяющие осуществлять поиск заимствований в текстовом материале, а также алгоритмическое обеспечение систем поиска заимствований в текстовой информации, опубликованной в глобальной сети Интернет.

Цель и задачи исследования. Целью диссертационной работы является разработка методов, алгоритмов и создание автоматизированной системы (АС), позволяющих производить поиск заимствований в текстовой информации, опубликованной в глобальной сети Интернет. Для достижения цели были решены следующие задачи:

• обзор программных систем, позволяющих производить поиск заимствований в сети Интернет;

• анализ методов и способов, позволяющих защищать электронные документы от несанкционированного копирования;

• разработка методов и алгоритмов, позволяющих осуществлять поиск заимствований в ЭИ, опубликованных в сети Интернет;

• разработка метода поиска электронных документов, опубликованных в сети Интернет, потенциально похожих на исходный документ;

• исследование частоты использования словосочетаний и устойчивых выражений в электронных документах, связанных с полиграфией и издательским делом;

• программная реализация разработанных и предложенных методов и алгоритмов поиска заимствований в ЭИ, опубликованных в сети Интернет;

1 http://www.aDtiplagiat.ru/show.php7docstechnology

• исследование скорости и эффективности разработанных методов поиска заимствований.

Методы исследования. В представленной работе были использованы: теория множеств, теория фильтров, теоретико-вероятностные методы и методы концептуального анализа3, а также внелингвистический контент-анализ в сочетании с элементами нечёткого сравнения, лексического и синтаксического анализа.

При создании программного комплекса, а также при исследовании алгоритмов сравнения текстовой информации применялись методы объектно-ориентированного программирования (ООП), объектно-компонентного программирования (ОКП), динамического программирования, структурного и модульного программирования, теория баз данных.

Оценка теоретической значимости результатов работы. Полученные методы и алгоритмы являются теоретической основой для создания автоматизированной системы поиска заимствований в электронных изданиях, опубликованных в глобальной сети Интернет. Предложенные методы позволяют производить сравнение текстового материала, опираясь сразу на два ортогональных метода (внелингвистический и лингвистический). Комбинация внелингвистического контент-анализа в сочетании с элементами лексического и синтаксического анализа позволяет по-новому подойти к проблеме сравнения текстовых фрагментов для выявления заимствований.

Практическая значимость работы. Практическая ценность диссертационной работы заключается в разработанных методах, которые прошли в ходе тестовых испытаний исследование на скорость и эффективность. Разработанные методы решения задачи поиска заимствований позволяют значительно сократить время, затрачиваемое на ручной анализ документов в сети Интернет для определения текстовых документов с заимствованиями.

Программный комплекс «\VebCompare», разработанный с использованием результатов представленной диссертационной работы, позволяет производить поиск электронных изданий опубликованных в сети Интернет, содержащих заимствования. Тестирование АС показало высокую эффективность разработанного в рамках диссертационного проектирования метода поиска заимствований, о чём свидетельствуют данные, представленные в

3 Апресян Ю.Д. Избранные труды, т. I. Лексическая семантика: 2-е изд., испр. и доп. - М.: Школа «Языки

русской культуры», Издательская фирма «Восточная литература» РАН, 1995. - 472 с.

четвёртой главе и приложениях. Также определён размер документов (от 3-5 до 30 Кб), для которых использование разработанного программного комплекса является наиболее эффективным. В среднем, для документов с оговоренным ранее размером, при использовании разработанного двухуровневого метода время сравнения снижается на 30-70% по сравнению с обычным одноуровневым сравнением.

Разработанный программный комплекс «WebCompare» зарегистрирован в Международном Центре сертификации результатов интеллектуальной деятельности (получен сертификат регистрации объекта интеллектуальной собственности SRI № RU02R1RU20060049 от 25.09.2006).

Достоверность полученных результатов и выводов. Достоверность полученных результатов подтверждается использованием проверенных математических методов. Реализованная в рамках диссертационной работы программная система показала на практике эффективность предложенных методов и алгоритмов для поиска заимствований в ЭИ, опубликованных в сети Интернет. Достоверность и эффективность подтверждена представленными актами о внедрении.

Научная новизна и значимость работы. В диссертационной работе решена научно-практическая задача автоматизации поиска заимствований в ЭИ, опубликованных в сети Интернет. Разработаны и программно реализованы методы и алгоритмы, позволяющие производить поиск заимствований в текстовом материале, опубликованном в глобальной сети Интернет. Получены новые научные результаты:

• разработан двухуровневый метод поиска заимствований в электронных изданиях, опубликованных в сети Интернет, позволяющий сократить время сравнения документов, содержащих от 5 до 30 Кб текстовой информации, в среднем на 50%;

• разработан метод поиска электронных документов, опубликованных в сети Интернет, потенциально похожих на исходный документ;

• разработан алгоритм поиска в верхней треугольной матрице последовательностей, параллельных главной диагонали, максимально покрывающих ось абсцисс не перекрывающимися проекциями, позволяющий формировать последовательности слов для двухуровневого метода поиска заимствований;

• разработана архитектура и программно реализована автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет, а также расположенных на локальных носителях информации.

Основные положения, выносимые на защиту:

• метод поиска заимствований в ЭИ, опубликованных в сети Интернет;

• метод поиска электронных документов, опубликованных в сети Интернет, потенциально похожих на исходный;

• автоматизированная система поиска заимствований в ЭИ, опубликованных в сети Интернет «\VebCompare»;

• оценка скорости работы и эффективности программно реализованной автоматизированной системы поиска заимствований.

Апробация результатов работы. Основные положения диссертационной работы и результаты исследований были представлены на конференциях и заседаниях:

• 58-я и 59-я научно-техническая конференция Московского государственного университета печати;

• конференция студентов и аспирантов МГУП;

• научно-техническое совещание ООО «Директмедиа Паблишинг»;

• заседания кафедры «Информационные технологии» МГУП. Внедрение автоматизированной системы. Разработанный программный комплекс был внедрён в одном из крупнейших издательств на территории РФ, специализирующихся на выпуске электронных изданий: ДиректМе-диа Паблишинг. Автоматизированная система также прошла внедрение на кафедре «Информационные технологии» в Московском государственном университете печати.

Публикации. Основные результаты диссертационной работы были представлены в 7 работах, опубликованных в журналах, сборниках и вузовских изданиях Российской Федерации. Получен сертификат регистрации объекта интеллектуальной собственности в Международном Центре сертификации результатов интеллектуальной деятельности.

Структура и объём диссертации. Диссертационная работа состоит из введения, 4 глав, заключения, библиографического списка, 9 приложений.

Диссертация изложена на 187 страницах, содержит 26 рисунков, 5 таблиц,'библиографический список включает 131 наименование, 9 приложений.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулированы цели и задачи диссертационной работы, представлены положения, выносимые на защиту, отмечена научная новизна и практическая значимость, приводится краткое содержание глав диссертации.

В первой главе рассматриваются вопросы анализа предметной области и постановка задачи диссертационной работы. В первом разделе представлено краткое описание истоков авторского права, а также рассмотрены вопросы ответственности за нарушение авторских прав. Во втором разделе отмечено, что авторское право на произведение науки, литературы и искусства возникает в силу факта его создания. Для возникновения и осуществления авторского права не требуется регистрации произведения, иного специального оформления произведения или соблюдения каких-либо формальностей, о чём многие пользователи сети Интернет даже не подозревают, ошибочно считая, что на все материалы, опубликованные в сети Интернет, не распространяется закон об авторском праве и смежных правах. Проведено разделение нарушения авторских прав в глобальной сети Интернет на две категории:

• нарушение личных неимущественных прав - присвоение авторства на размещенные в Интернете произведения, то есть плагиат;

• нарушение имущественных прав - размещение произведений в сети и предоставление к ним доступа без разрешения правообладателя. Рассмотрены вопросы и представлены статистические данные по нарушениям авторских прав и незаконному заимствованию материалов в зарубежных учебных заведениях. Так более 75% студентов в Северной Америке признаются в плагиате. При этом, согласно исследованиям US News and World Report, 90% студентов полагают, что плагиаторов либо никогда не уличают в этом, либо не наказывают соответственно проступку. Также отмечается, что во многих университетах Мира, при неоднократном обнаружении значительного плагиата в работе учащегося, устав учебного заведения позволяет дисциплинарной комиссии осуществить процедуру отчисления без пра-

ва восстановления. Здесь же описаны действия, направленные на пресечение нарушения авторских прав.

Четвёртый раздел посвящен обзору систем и сервисов поиска плагиата и заимствований. В обзоре представлены такие системы, как: Essay Verification Engine (EVE2), PowerResearcher, WCopyfind, Turnltln (Plagiarism.org), JISC Plagiarism Detection Service, Glatt Plagiarism Services, MyDropBox Suite, Placens.com, Copyscape, Urkund, Scriptum, Antiplagiat.ru. В данном разделе представлена информация также и о системах поиска плагиата в исходных текстах программ: JPlag (Detecting Software Plagiarism), Moss (Measure Of Software Similarity), SID (Software Integrity Detection).

В пятом разделе дано определение термина «электронное издание», основанное на ГОСТ 7.83-2001 и диссертационной работе Чикунова Ивана Михайловича. Рассмотрены виды текстовой информации. Описаны способы защиты электронных изданий, опубликованных в сети Интернет.

Шестой раздел посвящён автоматизации обработки текстовой информации, в нём же проведено описание задач, решаемых системами автоматизированной обработки текстовой информации. На основе проведённого анализа была сформулирована постановка задачи диссертационной работы, представленная в седьмом разделе первой главы.

Вторая глава посвящена рассмотрению методов и алгоритмов анализа, представления и сравнения текстовой информации. В первом разделе рассмотрены методы и способы анализа и представления текстовой информации, в том числе используемые в информационно-поисковых системах (ИПС): Дескрипторный метод, Дублинское Ядро, Векторная модель, Метод А.Т. Фоменко, Семантические сети, Статистические методы, Латентно-семантический анализ, Нейронные сети, Контент-анализ.

Проведён обзор основных уровней лингвистической обработки текстовой информации в системах автоматизированной обработки текстов (АОТ): морфологический, синтаксический, семантический. Основная задача морфологического анализа в системах АОТ заключается в получении основ слов, по их словоформам. Большинство таких систем работает с использованием специального морфологического словаря, однако существуют методы, позволяющие проводить морфологический анализ практически без использования словарей. Как правило, синтаксис разделяют на два уровня:

• учение о словосочетаниях — выделяются типы синтаксических отношений между словами и разновидности подчинительных словосочетаний;

• учение о предложениях - излагаются принципы и законы построения простых и сложных предложений.

В последнее время, к проблеме машинного синтаксического анализа существует два основных подхода:

• формально-грамматический - направлен на генерацию систем правил, для последующего принятия решения в пользу определённой синтаксической конструкции;

• вероятностно-статистический — ориентирован на сбор статистических данных о встречаемости синтаксических конструкций в похожем контексте, на основе которых принимается решение о выборе синтаксической структуры.

На семантическом уровне одной из главных задач является снятие лексической и структурной неоднозначности. Одна и та же мысль может быть выражена в текстах разными словами и с использованием разных синтаксических конструкций. При этом задачей семантического анализа является определение семантической тождественности анализируемого текстового материала.

Четвёртый раздел второй главы посвящен анализу возможности использования кластерного анализа, представляющего собой совокупность математических методов, предназначенных для формирования относительно «отдалённых» друг от друга групп «близких» между собой объектов по информации о расстояниях или связях (мерах близости) между ними. В пятом разделе проведена оценка целесообразности использования графовой модели. Шестой раздел посвящён исследованию возможности использования авторского инварианта в контексте решаемой диссертационной работы. В седьмом разделе представлены материалы относительно стеганографии и цифровых водяных знаков, внедряемых в графические, аудио, видео и текстовые документы. Восьмой раздел посвящён применению теории нечётких множеств для решения задачи сравнения текстового материала.

Разделы с девятого по тринадцатый содержат информацию об алгоритмах сравнения текстовой информации. Девятый раздел посвящён алгоритмам

поиска точно совпадения: алгоритм Боуера-Мура (Воуег-Мооге), алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt). Десятый - алгоритмам поиска общих подпоследовательностей: алгоритм Мазека (Masek) и Патерсона (Paterson), алгоритм Укконена (Ukkonen), алгоритм Хиршберга (Hirschberg), алгоритм Ханта(НиШ) и Шиманского (Szymanski). Одиннадцатый раздел посвящен методам поиска максимальной повторяющейся подстроки. А также задаче нахождения самой длинной подстроки - Longest Repeated Substring (LRS) встречающейся более одного раза в исходной строке. В двенадцатом разделе рассмотрены такие алгоритмы вычисления расстояния между строками, как: расстояние Хемминга (Hamming), расстояние Левенштейна (Levenstein), расстояние редактирования. Тринадцатый раздел посвящён алгоритмам нечёткого поиска: k-несовпадений и к-различий Ландау-Вишкина (Landau-Vishkin).

В четырнадцатом разделе проводится обоснование выбора метода анализа текстовой информации, используемого для решения поставленной диссертационной задачи.

Основой в разрабатываемых методах является внелингвистический контент-анализ в сочетании с элементами нечёткого сравнения, лексического и синтаксического анализа. Таким образом, разработанные методы позволяют производить сравнение текстового материала, опираясь сразу на два ортогональных метода (внелингвистический и лингвистический).

Третья глава полностью посвящена разработке и математическому описанию методов, позволяющих осуществлять поиск заимствований в электронных изданиях, опубликованных в сети Интернет. Рассмотрены возможности введения в алгоритм сравнения, весовых функций, позволяющих учитывать значимость совпавших элементов для сравниваемого текста, а также длины блоков совпадения. Кроме того, рассмотрена задача выбора таких текстов из Г=Г„Гг.....Г,, которые максимально покрывают х,, при этом, не пересекаясь между собой.

В первом разделе разработан метод поиска электронных документов, опубликованных в сети Интернет, потенциально похожих на исходный документ. Под похожестью текстовых документов подразумевается наличие в текстах одинаковых фрагментов. При этом фрагментом может считаться подпоследовательность, состоящая из более чем одного слова или предложе-

ния, не обязательно идущих в том же порядке, что и в исходном документе. Текст и документ в настоящей работе считаются равнозначными терминами, обозначающими текстовый документ. При этом такая информация как цвет, шрифт, начертание, кегль, интерлиньяж, выравнивание и прочее не влияет на сравнение документов.

В общем случае, для электронного издания Н = Н,,Н2,...,Н, основываясь на исходном тексте Н, должны быть сформированы поисковые запросы. После выполнения запросов поисковая система возвращает список URL адресов на документы, потенциально похожие на исходный документ. Автоматизированная система загружает из глобальной сети документы, ссылки на которые были получены от поисковой системы. После чего производится сравнение загруженных документов Г = Г,, Г2.....Г, с исходным текстом Н,.

Ниже представлено краткое описание алгоритма формирования поисковых запросов на основе исходного текста. Текстом * будем называть упорядоченный конечный набор слов: * = .....-О. Обозначим исходный текст

как х и составим на его основе симметричную матрицу А = (аи) с размерностью п-п, где п — количество слов в тексте х. Элементами составляемой матрицы могут являться О и 1 по следующему правилу:

{О, если х, * хj 1, если j:, = Xj

Необходимо найти все последовательности из единиц, располагающиеся над главной диагональю матрицы, при этом параллельные главной диагонали. Учитываем, что /3+1 - определяет длину последовательности, а а — определяет сдвиг найденной последовательности относительно главной диагонали. При а < О последовательность расположена над главной диагональю матрицы А = (a:J), а так как анализируемая матрица симметрична относительно главной диагонали, то воспользуемся возможностью сократить объём вычислений, исключив из рассмотрения случай при в>0. Необходимо найти все последовательности в матрице Л = (а,;) такие, что:

Таким образом, необходимо найти такие i, при которых для описанной последовательности выполняется равенство:

Обозначим найденные последовательности слов как yp = yp(a,ß,i) р = 1,2,...,/'. Следует отметить, что при таком поиске последовательностей, значение Р значительно превосходит реальное количество повторяющихся последовательностей. Проанализировав количественное несоответствие получаемого числа последовательностей, мы сделали вывод о том, что получаемые данные увеличиваются в соответствии с правилом треугольных чисел

(1, 3, 6, 10, 15, 21...) и вычисляются по формуле: t(n) = . Однако при

включении в текст частично перекрывающихся последовательностей или входящих в состав других последовательностей, что свойственно текстам на естественном языке, возникает ситуация, при которой получаемые по описанному алгоритму результаты не соответствуют треугольным числам. Для решения задачи был разработан алгоритм поиска в верхней треугольной матрице последовательностей, параллельных главной диагонали, максимально покрывающих ось абсцисс не перекрывающимися проекциями. Блок-схема предложенного алгоритма представлена в диссертационной работе в приложении 3.

Обозначим через У = у,, у2.....ур список найденных последовательностей,

отсортированных по частоте вхождения в текст х. Как отмечено в диссертационной работе, значимость выражений, часто употребляемых во всех текстах данного направления меньше чем значимость выражений, редко употребляемых в текстах данного направления, но часто употребляемых в анализируемом тексте. Таким образом, необходимо удалить из списка Y = у,,у2,~,уР такие последовательности, которые являются часто употребляемыми и распространёнными. Описанная задача решается с использованием базы данных (БД), сформированной на основе корпуса текстов Ф = je,tjc2,...,xt из одной тематической области. Далее полученные последовательности из ¥ используются для формирования запросов в поисковую систему. Всё множество документов, загруженных по URL адресам, полученным от поисковой системы, обозначим через Г = r,,r2,...,ri,.

Второй раздел посвящён разработке метода сравнения текстовых документов, а также вопросам уменьшения размерности текстового материала для увеличения скорости сравнения текстов.

Для решения задачи поиска одинаковых подпоследовательностей в 2-х текстах используется следующий алгоритм:

- исходный текстовый документ. х2 - сравниваемый с исходным текстовый документ х2е Г х2 = Г,, 1 = 1,2...,у. Л - список индексов элементов из х2, уже проверенных и считающихся совпавшими с некоторыми элементами из л,. М - список индексов элементов из х,, совпавших с элементами из х2. Л - количество совпавших элементов из х, и х2.

Шаг 1: Сравниваем х,1' с дг,(2). Если х'1' = х,(2>, то Л, = 1, Л/, = 1, Л = 1 и переходим к шагу 2, иначе сравниваем с х[2' и так далее до х™ пока в тексте хг не будет найден элемент равный х,т. Обозначим позицию найденного элемента в тексте х2 за к,. При условии начала индексации с единицы получаем, что в случае, если элемент х{" не был найден в х2, к,=0.

Шаг 2: Сравниваем с х^. Если х<" = х™,, (£, + 1)е Л, Ц-, +1)<п2, то Л = Л + 1, Лд = +1, М1=2 и переходим к следующему шагу, иначе сравниваем х'" с х™, при условии (£,-1)е Л (*,-1)>1, потом при отсутствии совпадения сравниваем х2> с х"1г (к, А (к1 + 2)< «2 и так далее, при этом условием завершения проверки на втором шаге будет являться то, что не осталось элементов в хг не проверенных на этом шаге, за исключением содержащихся в списке Л. Индекс позиции найденного элемента в тексте х2 обозначим как кг, при этом если элемент х"> не был найден в хг, то к2 = к,.

Шаг /.• Сравниваем х,а> с . Если х'" = (км +1)е Л, + 1)< п2, то Л = Л + 1, Ал -к,_, +1, Мд = I и переходим к шагу / + 1, иначе сравниваем х,(" с

ПРИ условии (£,_, - 1)й А -1) > 1, потом при отсутствии совпадения сравниваем х,(|) с (*,_, +2)е Л + 2)<л2 и так далее пока в х2 не встретится элемент равный х'". Индекс позиции найденного элемента в х2 обозначим как к,, при этом если элемент х'0 не был найден в х2 на шаге г, то к1 = .

Работа алгоритма сравнения двух текстов х, и хг проиллюстрирована на рисунке 1.

• со

• ш

Рис. 1. Иллюстрация работы алгоритма сравнения Зс, с хг Во втором разделе рассмотрены также методы уменьшения размерности документа, при этом показана неэффективность использования рассмотренных методов в контексте решения поставленной задачи.

Третий раздел посвящен разработке и математическому описанию метода уменьшения размерности сравниваемых текстовых документов.

Разработанный метод базируется на использовании информации о местоположении словосочетаний, часто встречающихся в исходном для сравнения текстовом документе, при этом относительно редко употребляемых в текстах рассматриваемой области.

I, е Н - исходный текстовый документ. хг а г - сравниваемый с исходным текстовый документ. $ - последовательность слов, найденная в верхней треугольной матрице А = (аи). 5 - множество последовательностей 1 в сформированной на основе корпуса текстов Ф = .....х> БД, содержащей последовательности слов и выражения, которые являются часто употребляемыми и распространёнными в рассматриваемой тематической области. 5, - множество последовательностей у™ р = 1...Р1 из лг,. Ыу,„ - количество появлений последовательности у'" в х.. N ,„ - количество появлений последовательности у1''1 в 5. Выберем такую последовательность у"! из 5,, что = МЛХ{Й).

Следует отметить, что в зависимости от размера исходного документа , вы-

бирается количество последовательностей, для которых осуществляется поиск окрестностей.

После определения места вхождения последовательности у'\' в х,, как:

(*„♦...........(jr»»(1)»>-.;c4rot>) ' формируются «правая» и «левая» окрест____у_У V

Першая последовательность Последняя последовательность

ности для у"!. т - длина окрестности, к ,„ - длина последовательности >. Таким образом, хщ „^.....дс - «левая» окрестность для в xt, обозначаемая как ujn =и?'(г,т). А дг 4 „1+„ - «правая» окрестность для у<4 в г,,

обозначаемая как =и'"(.у,т). Таким образом, общее количество окрестностей в л, для у'1.' составляет 2 • Ny<„.

Осуществив поиск последовательности у''} в х2, получаем «левую» окрестность x4f_mtl.....хч>, обозначаемую как и"' "О и «правую» окрестность j (11.„., обозначаемую как и'г2) = и'г2)(у,т). Из полученных окрестностей формируется 2 множества: Z, - для yjV в X, и Z2 - для уЧ? в х2.

Множество объединённых окрестностей для исходного текста: Z, = Z,">,Z21).....Z™n Zjl) = u("i(l,m)i*Jum,(l,m) Z^ = «<",(#,„,m)Uum,(Nr,„«)

Множество объединённых окрестностей для документа, сравниваемого с исходным текстом:

Z,=ZI<2,,Z<2\...,Z£> Z,ra=«|2|,(l,m)UU<2V(l,m) Z<?> =umi(N m,m)<Jumr(N ,„,m)

P 9

Сравнение элементов из Z, и Z2 осуществляется в соответствии с ранее описанным алгоритмом сравнения текстовой информации. В качестве сравниваемых элементов выступают объединённые окрестности длиной 2-т, полученные для последовательности у'^! в J, и jf2. При сравнении элементов

г'/' с Z™ используются весовые функции, позволяющие увеличить значимость совпадения редко употребляемых слов по отношению к распространённым и часто употребляемым словам. Также используется весовая функция, учитывающая длину совпавшего фрагмента. Введение весовой функции основано на предположении, что в контексте задачи поиска заимствований.

значимость совпадения фрагмента, содержащего X элементов, выше, чем значимость совпадения двух не смежных фрагментов, общей длиной X элементов.

С использованием разработанного метода формирования объединённых результатов сравнения текстовых документов решена задача выбора таких текстов из Г = Г„Г3,...,Г., которые максимально покрывают I,, при этом

не пересекаясь между собой. Разработанный метод основан на модифицированной в соответствии со спецификой предметной области задаче о наименьшем разбиении. При этом основной задачей является получение информации о совпадении блоков текстовой информации при сравнении исходного документа с несколькими загруженными. Получение объединённых результатов может быть полезным и целесообразным при необходимости найти в глобальной сети Интернет документы, содержащие фрагменты исходного документа, размещённые в разных файлах. То есть при получении обычных результатов сравнения может оказаться, что каждый из сравниваемых файлов содержит незначительную часть исходного, однако при этом в целом сравниваемые документы могут содержать весь исходный документ по частям.

Четвёртая глава посвящена разработке и программной реализации автоматизированной системы поиска заимствований в электронных изданиях, опубликованных в сети Интернет. В главе представлены также данные о скорости сравнения и эффективности разработанной системы.

Первые разделы посвящены обоснованию выбора используемой поисковой системы, поддерживаемых форматов текстовых документов, используемой СУБД, инструментального средства разработки АС. Рассмотрены вопросы, посвященные созданию БД, содержащей словосочетания и часто употребляемые выражения в корпусе текстов Ф = . Следует отме-

тить, что корпус текстов Ф = *,,3с2,.содержал более 13 тыс. электронных документов, суммарный объём составлял свыше 100 мегабайт текста.

Шестой раздел посвящён разработке архитектуры АС.

МЗН МВП мпнс СПТДИ

минсд

МВЕД

БД _ МВЕД

Интернет

. мптд

мзпгщ

1Г

МФСП мво

1 1

мсс мфрс

Рис. 2. Архитектура разработанной автоматизированной системы

МЗН — модуль загрузки настроек системы WebCompare МИНСД — модуль изменения настроек сравнения документов МВП — модуль взаимодействия с пользователем МПНС - модуль подготовки к новому сравнению К DOC - конвертер, преобразующий документы в форматах rtf и doc СПТДИ — система получения текстовых данных из исходного документа МПТД - модуль подготовки текстовых данных МВЗ - модуль ввода пользователем поисковых запросов МАФПЗ — модуль автоматического формирования поисковых запросов МФЗЗ — модуль формирования поисковых запросов из предполагаемого заголовка документа

СППП - система поиска повторяющихся последовательностей МФСП — модуль формирования списка последовательностей МВБД - модуль взаимодействия с базой данных МФПЗ - модуль формирования поисковых запросов

МПСОИ - модуль построения списка окрестностей для исходного документа СВПМ - система взаимодействия с поисковой машиной МЗППД — модуль загрузки потенциально похожих документов

СПТДС - система получения текстовых данных из сравниваемого документа МПСОС - модуль построения списка окрестностей для сравниваемого документа

ССО - система сравнения окрестностей

ССТД - система сравнения текстовых документов

МФСП - модуль формирования списков предложений

МСС - модуль сравнения списков

МВО - модуль визуального отображения

МФРС - модуль формирования результатов сравнения

МФОРС - модуль формирования объединённых результатов сравнения

СФО - система формирования отчётов

Разделы с седьмого по десятый посвящены описанию программной реализации, основных модулей, механизма взаимодействия модулей, а также функциональных возможностей разработанной АС. На рисунках 3 и 4 представлена блок-схема алгоритма работы автоматизированной системы. Разработанный программный комплекс позволяет:

• осуществлять поиск заимствований в электронных изданиях, расположенных на локальном диске или опубликованных в сети Интернет;

• настраивать параметры поиска и сравнения текстовых документов (в том числе: количество, размер и язык загружаемых документов, единица сравнения документов, мера нечёткости сравниваемых элементов, количество запросов в поисковую систему);

• просматривать результаты сравнения электронных документов, при этом совпавшие фрагменты оформляются в виде гиперссылок, что позволяет пользователю перейти к заимствованному фрагменту в сравниваемом с исходным документе;

• сохранять результаты поиска и сравнения электронных документов.

Формирование объединённым результатов сравнения текстовых документов

Да Загрузка документа из интернета по текущему URL- Получение текстовых данных из

загруженного

документа

Формирование списка

окрестностей для

загруженного

документа

' Формирование HTML документов для

просмотра сравниваемых документов

—HZ

Формирование списков

предложений для текущего документа из ЭИ * загруженного документа

Вывел ма дисплей информации о результатах сравнения списков

^^ Конец j^h»—

Рис. 3. Блок-схема алгоритма работы АС (часть 1)

Рис. 4. Блок-схема алгоритма работы АС (часть 2)

В одиннадцатом разделе рассматриваются вопросы планирования эксперимента. Представлена структурная схема процесса тестирования, а также конфигурация ПК, на которых осуществлялось тестирование разработанного

программного комплекса. В двенадцатом разделе проведено описание тестовых наборов. В экспериментальных исследованиях использовались текстовые документы из корпуса текстов Ф, содержащего свыше 13 тысяч документов со средним объёмом 7,5 килобайт. Документы распределялись по тестовым наборам в соответствии с размерами файлов: от О до 2 Кб, от 3 до 5 Кб, от 6 до 10 Кб, от 11 до 30 Кб, от 31 до 50 Кб, от 51 до 100 Кб. Разделение всех документов подлежащих анализу на 6 тестовых наборов позволило экспериментально определить целесообразность применения разработанной АС для текстовых документов определённого объёма.

В тринадцатом разделе приводятся результаты экспериментальных исследований скорости и эффективности разработанной и программно реализованной автоматизированной системы.

Проведение экспериментальных исследований оценки скорости работы разработанного двухуровневого метода показало уменьшение времени сравнения от 39,8% до 60,7% в зависимости от размера сравниваемых документов.

Тестирование скорости работы двухуровневого метода показало, что для документов с объёмом текста менее 30 килобайт среднее время сравнения документов в 2,5 раза меньше, чем при использовании одноуровневого метода. На рисунке 5 представлены данные о среднем времени тысячи сравнений текстовых документов. При этом оценивалось полное время работы системы с учётом времени считывания локального документа, поиска последовательностей, формирования и сравнения окрестностей, сохранения результатов сравнения.

КБ

} Один уровень сравнения —- —Два уровня сравнения |

Рис. 5. Зависимость времени сравнения от размера сравниваемых документов.

Представленные на рисунке 5 данные показывают целесообразность использования разработанного двухуровневого метода для документов с объёмом текстового материала менее 30 килобайт.

Эффективность разработанного двухуровневого метода сравнения документов оценивалась по отношению к методу, использующему одноуровневую архитектуру сравнения текстовых документов.

КБ

| Ошибка I рода ■*—" — Ошибка II рода |

Рис. 6. Зависимость процента ошибок I и II рода от размера сравниваемых текстовых документов.

На рисунке 6 представлены данные о количестве ошибок I и II рода, допускаемых автоматизированной системой при использовании разработанного двухуровневого метода. За ошибку I рода принимается неоправданное отклонение документа при использовании двухуровневого метода сравнения. Ошибка П рода - направление документов на второй уровень сравнения, при условии, что документ не содержит значительных заимствований с исходным документом. Несмотря на достаточно большое количество допускаемых системой ошибок II рода, можно говорить об их незначительном влиянии на качество работы системы. Данное утверждение основано на том факте, что при совершении системой ошибки II рода производится сравнение текстовых документов, не имеющих заимствования, на втором уровне. При этом автоматизированная система покажет реальное количество заимствований, потратив некоторое время на проведение сравнения на втором уровне. В связи с чём, значительно большее значение имеют ошибки I рода, при которых документы, имеющие заимствования, признаются не содержащими заимствования на

первом уровне сравнения, и, таким образом, исключаются из списка документов, сравниваемых на втором уровне.

Данные, представленные на рисунке 6, свидетельствуют о неэффективности применения разработанного метода для документов, содержащих менее 5 килобайт текстовой информации. Таким образом, обобщая данные экспериментальных исследований, можно говорить об эффективности и целесообразности разработанного двухуровневого метода для документов, содержащих от 5 до 30 килобайт текстового материала.

Заключение содержит основные выводы и результаты, полученные в ходе диссертационного исследования, разработки, реализации и тестирования программной автоматизированной системы.

В приложения вынесены материалы, не вошедшие в основную часть диссертационной работы, в том числе 11 листов блок-схем, экранные формы разработанной АС и 15 графиков, содержащих информацию, полученную при экспериментальных исследованиях.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

1. Проанализированы методы представления и сравнения текстовой информации, применимые для решения задачи диссертационной работы. Рассмотрена эффективность и адекватность применения рассмотренных методов для решения поставленных задач. Исследованы возможности применения кластерного анализа, графовой модели, авторского инварианта, стеганографии, теории нечётких множеств.

2. Разработан двухуровневый метод поиска заимствований в электронных изданиях, опубликованных в сети Интернет, позволяющий сократить время сравнения документов, содержащих от 5 до 30 Кб текстовой информации, в среднем на 50%. Показана возможность введения в алгоритм сравнения, весовых функций, позволяющих повысить эффективность разработанного метода.

3. Разработан метод уменьшения размерности текстового документа, позволяющий снизить затраты времени сравнения на 39,8% - 60,7%, в зависимости от размера сравниваемых документов. При этом количество ошибок, возникающих при использовании данного метода, ниже, чем в проанализированных методах.

4. Разработан алгоритм поиска в верхней треугольной матрице последовательностей, параллельных главной диагонали, максимально покрывающих ось абсцисс не перекрывающимися проекциями, позволяющий формировать последовательности слов для двухуровневого метода поиска заимствований.

5. Разработан алгоритм формирования объединённых результатов сравнения текстовых документов, позволяющий определять итоговую оценку объёма заимствования при разбиении исходного текстового материала на незначительные фрагменты в разных текстовых документах, опубликованных в сети Интернет.

6. Разработана и программно реализована автоматизированная система поиска заимствований в электронных изданиях, позволяющая осуществлять поиск плагиата в электронных документах, опубликованных в сети Интернет, а также расположенных на локальных носителях информации, в отличие от крупнейшей отечественной системы, ориентированной на поиск заимствований лишь в тех документах, которые были добавлены в системную базу данных.

7. Проведены экспериментальные исследования, позволяющие оценить эффективность и адекватность предложенных и разработанных методов, направленных на выявление заимствований в электронных изданиях, опубликованных в сети Интернет. На основе проведённых исследования определен размер текстовых документов, при котором наиболее эффективно и целесообразно использование разработанного метода поиска заимствований.

8. Проведена апробация работы и внедрение разработанной в рамках диссертации автоматизированной системы, показавшие эффективность метода поиска и обнаружения заимствований.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Федоренко Д.В. Автоматизированная система сравнения электронных изданий, опубликованных в сети Internet/Intranet // Вестник МГУП. - 2004 №5. - С.74-78 (0,12 п.л.)

2. Федоренко Д.В. Исследование эффективности использования баз данных по сравнению с файловой системой для хранения текстовой информации // Вестник МГУП. - 2005 №5. - С. 19-35 (0,63 п.л.)

3. Федоренко Д.В. Актуальность выявления нарушений авторских прав // Вестник МГУП. - 2005 №5. - С.36-47 (0,58 п.л.)

4. Крутояров Д.В. Автоматизированная система сравнения электронных изданий, опубликованных в сети Internet/Intranet // Вестник МГУП. - 2005 №11 (дополнительный). - С.84-87 (0,13 пл.)

5. Крутояров Д.В. О выборе метода анализа текстовой информации // Проблемы полиграфии и издательского дела. - 2006 №3. - С. 175178 (0,14 п.л.)

6. Крутояров Д.В. Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет «Web-Compare» // Сертификат регистрации объекта интеллектуальной собственности SRI № RU02R1RU20060049 от 25.09.2006 выдан Международным Центром сертификации результатов интеллектуальной деятельности.

7. Крутояров Д.В., Гасов В.М. Метод сравнения текстовых документов, позволяющий выявлять совпадающие фрагменты // Проблемы полиграфии и издательского дела. - 2006 №4 - С. 92-104. (0,4 п.л. / 0,2 п.л.)

Подписано в печать 08.11.0бг. Формат 60x84/16. Печ.л. 1.5. Тираж 100 экз. Заказ №418/317 Отпечатано в РИО Московского государственного университета печати 127550, Москва, ул. Прянишникова,2а

Оглавление автор диссертации — кандидата технических наук Крутояров, Дмитрий Владимирович

ВВЕДЕНИЕ.

1. Анализ предметной области и постановка задачи.

1.1. Истоки авторского права и ответственности за его нарушение.

1.2. Виды нарушения авторских прав.

1.3. Проблема нарушения авторских прав.

1.4. Обзор систем и сервисов поиска плагиата.

1.5. Способы защиты электронных изданий от плагиата в Интернете.

1.6. Автоматизация обработки текстовой информации.

1.7. Постановка задачи.

1.8. Выводы.

2. Методы и алгоритмы анализа, представления и сравнения текстовой информации.

2.1. Методы анализа текстовой информации.

2.2. Методы защиты от копирования текстовой информации в Интернете.

2.3. Обзор уровней лингвистической обработки текстовой информации.

2.4. Определение возможности использования кластерного анализа.

2.5. Оценка целесообразности использования графовой модели.

2.6. Исследование возможности использования авторского инварианта.

2.7. Возможность применения стеганографии.

2.8. Теория нечётких множеств.

2.9. Алгоритмы поиска точного совпадения.

2.10. Алгоритмы поиска общих подпоследовательностей.

2.11. Методы поиска максимальной повторяющиеся подстроки.

2.12. Алгоритмы вычисления расстояния между строками.

2.13. Алгоритмы нечёткого поиска.

2.14. Обоснование выбора метода анализа текстовой информации.

2.15. Выводы.

3. Разработка метода поиска текстовых документов с заимствованиями в глобальной сети Интернет.

3.1. Метод получения потенциально похожих документов.

3.2. Метод сравнения текстовых документов.

3.3. Метод уменьшения размерности сравниваемых текстов.

3.4. Алгоритм формирования результатов сравнения документов.

3.5. Выводы.

4. Программная реализация автоматизированной системы поиска заимствований в электронных изданиях, опубликованных в сети Интернет «WebCompare».

4.1. Обоснование выбора используемой поисковой системы.

4.2. Обоснование выбора поддерживаемых AC WebCompare форматов документов.

4.3. Обоснование выбора используемой СУБД.

4.4. Обоснование выбора инструментального средства разработки АС.

4.5. Создание базы данных.

4.6. Архитектура программного комплекса.

4.7. Краткое описание программной реализации.

4.8. Краткое описание основных модулей АС.

4.9. Функциональные возможности программного комплекса.".

4.10. Механизм взаимодействия модулей. Алгоритм работы АС.

4.11. Планирование эксперимента.

4.12. Описание тестовых наборов.

4.13. Результаты экспериментальных исследований.

4.14. Выводы.

Введение 2006 год, диссертация по информатике, вычислительной технике и управлению, Крутояров, Дмитрий Владимирович

Актуальность темы исследования. Проблемой исследования текстовых произведений занимаются многие века, но лишь в 1851 году английский логик Август де Морган впервые предложил использовать математический аппарат для решения задачи установления авторства. Тем самым Морган породил непрерывающуюся дискуссию о применимости математических методов для задач анализа текстовой информации [104].

Актуальность автоматизации поиска заимствований в электронных изданиях обусловлена проблемой нарушения авторских прав. В настоящее время нелегальное распространение произведений, являющихся объектом авторского права - явление обыденное. Однако Интернет позволил максимально упростить саму процедуру нарушения до буквально двух-трех нажатий клавиш. Одни и те же материалы многократно копируются на разных сайтах, что невозможно без нарушения норм авторского права. Кроме того, проблема незаконного заимствования текстовых материалов затрагивает и систему высшего образования. Благодаря тому, что в глобальной сети Интернет опубликованы, в некоторых случаях незаконно, многие электронные издания, а также в силу незнания действующего законодательства в области авторского права, многие считают возможным копировать фрагменты опубликованных в сети Интернет электронных изданий, с последующим присвоением авторства. По данным, опубликованным Education Week (http://www.plagiarism.org/plagiarismstats.html), основанным на национальном исследовании (USA) следует, что 54% студентов незаконно используют в своих работах материалы, опубликованные в сети Интернет. Стоит также отметить, что 47% студентов считают, что их преподаватели часто игнорируют случаи плагиата в студенческих работах. Центр Академической Честности (The Center for Academic Integrity) обнаружил, что 80% студентов признаются в плагиате, совершённом хотя бы однажды.

С каждым годом все больше изданий переводится в электронную форму [87]. Одни из них публикуются на компакт дисках, другие - в глобальной сети Интернет. При этом практически любое электронное издание, в том числе и опубликованное в сети Интернет, является объектом авторского права.

В настоящее время, многие ошибочно считают, что материалы, опубликованные в глобальной сети Интернет можно копировать, не заботясь об исключительных правах автора. Статья 9 закона об «Авторском праве и смежных правах» гласит: «Для возникновения и осуществления авторского права не требуется регистрации произведения, иного специального оформления произведения или соблюдения каких-либо формальностей».

Предмет и объект исследования. Объектом исследования являются системы, позволяющие производить поиск заимствований в текстовом материале, опубликованном в глобальной сети Интернет. Предметом исследования и разработки является множество методов и алгоритмов, позволяющих осуществлять поиск заимствований в текстовом материале, а также алгоритмическое обеспечение систем поиска заимствований в текстовой информации, опубликованной в глобальной сети Интернет.

Цель и задачи исследования. Целью диссертационной работы является создание автоматизированной системы, а также разработка методов и алгоритмов, позволяющих производить поиск заимствований в текстовой информации, опубликованной в глобальной сети Интернет. Для достижения цели были решены следующие задачи:

1 http://www.antiplagiat.ru/

2 http://www.antiplagiat.ru/show.php?doc=technology

• обзор программных систем, позволяющих производить поиск заимствований в сети Интернет;

• исследование скорости и эффективности разработанных методов поиска заимствований.

Методы исследования. В представленной работе были использованы: теория множеств, теория фильтров, теоретико-вероятностные методы и методы концептуального анализа [3], а также внелингвистический контент-анализ в сочетании с элементами нечёткого сравнения, лексического и синтаксического анализа.

Практическая значимость работы. Практическая ценность диссертационной работы заключается в разработанных методах, которые прошли, в ходе тестовых испытаний, исследование на скорость и эффективность. Разработанные методы решения задачи поиска заимствований позволяют значительно сократить время, затрачиваемое на ручной анализ документов в сети Интернет, для определения текстовых документов с заимствованиями. Программный комплекс «WebCompare», разработанный с использованием результатов представленной диссертационной работы, позволяет производить поиск электронных изданий, опубликованных в сети Интернет, содержащих заимствования. Тестирование АС показало высокую эффективность разработанного в рамках диссертационного проектирования метода поиска заимствований, о чём свидетельствуют данные, представленные в четвёртой главе и приложениях. Также определён размер документов (от 3-5 до 30 Кб), для которых использование разработанного программного комплекса является наиболее эффективным. В среднем, для документов с оговоренным ранее размером при использовании разработанного двухуровневого метода время сравнения снижается на 30-70% по сравнению с обычным одноуровневым сравнением.

• разработан алгоритм поиска в верхней треугольной матрице последовательностей, параллельных главной диагонали, максимально покрывающих ось абсцисс, не перекрывающимися проекциями, позволяющий формировать последовательности слов для двухуровневого метода поиска заимствований;

• разработана архитектура и программно реализована автоматизированная система поиска заимствований в электронных изданиях, позволяющая осуществлять поиск плагиата в электронных документах, опубликованных в сети Интернет, а также расположенных на локальных носителях информации.

Основные положения, выносимые на защиту:

• метод поиска заимствований в ЭИ, опубликованных в сети Интернет;

• метод поиска электронных документов, опубликованных в сети Интернет, потенциально похожих на исходный;

• автоматизированная система поиска заимствований в ЭИ, опубликованных в сети Интернет «WebCompare»;

• 58-я и 59-я научно-техническая конференция Московского государственного университета печати;

• конференция студентов и аспирантов МГУП;

• заседания кафедры «Информационные технологии» МГУП.

Внедрение автоматизированной системы. Разработанный программный комплекс был внедрён в одном из крупнейших издательств на территории РФ, специализирующемся на выпуске электронных изданий: Директме-диа Паблишинг. Автоматизированная система также прошла внедрение на кафедре «Информационные технологии», в Московском государственном университете печати.

Заключение диссертация на тему "Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет"

4.14. Выводы

1. Обоснован выбор используемой поисковой системы в разработанной АС, а также выбор поддерживаемых программным комплексом WebCompare форматов документов.

2. Разработана и программно реализована автоматизированная система поиска заимствований в электронных изданиях, позволяющая осуществлять поиск плагиата в электронных документах, опубликованных в сети Интернет, а также расположенных на локальных носителях информации. При проектировании АС были использованы разработанные и представленные в диссертационной работе методы и алгоритмы, позволяющие проводить анализ и сравнение текстовой информации.

3. Разработана и описана архитектура, а также основные компоненты и модули разработанного программного комплекса WebCompare.

4. Создана база данных, содержащая наиболее часто употребляемые словосочетания и выражения в корпусе текстов Ф = х1,х2,.,х^, позволившая осуществлять фильтрацию последовательностей в разработанном методе двухуровневого сравнения текстовых документов.

5. Проведены экспериментальные исследования, показавшие увеличение скорости сравнения текстовых документов размером от 5 до 30 КБ в среднем на 50%. Результаты экспериментов представлены в данной работе, а также в приложениях.

6. Данные, полученные в ходе экспериментальных исследований, позволяют оценить эффективность и адекватность предложенных и разработанных методов, направленных на поиск и выявление заимствований в электронных изданиях, опубликованных в сети Интернет. Также определен размер текстовых документов, при котором наиболее эффективно и целесообразно использование разработанных методов.

7. Проведена апробация работы и внедрение разработанной системы, показавшие эффективность метода поиска и обнаружения заимствований, разработанной в рамках диссертационной работы, автоматизированной системой WebCompare.

ЗАКЛЮЧЕНИЕ

1. Проведено исследование истоков авторского права, а также ответственности за незаконное присвоение авторства. Представлена информация о действующем законодательстве в области авторского права, подтверждающая наличие правовой основы для разрешения вопросов, связанных с незаконным присвоением авторских прав. Также проведена классификация видов нарушения авторских прав.

2. Проведён обзор, существующих на момент написания диссертационной работы программных систем и сервисов поиска заимствований и плагиата. Представлен обзор систем, позволяющих выявлять заимствования и плагиат в исходных текстах программных продуктов.

3. Проанализированы методы представления и сравнения текстовой информации, применимые для решения задачи диссертационной работы. Рассмотрена эффективность и адекватность применения рассмотренных методов для решения поставленных задач. Исследована возможность применения кластерного анализа, графовой модели, авторского инварианта, стеганографии, теории нечётких множеств.

4. Рассмотрены методы и алгоритмы поиска максимальной повторяющейся подстроки, а также поиска общих подпоследовательностей. Проведён обзор уровней лингвистической обработки текстовой информации, в частности, морфологический, синтаксический и семантический уровни. Проведено обоснование выбора метода анализа текстовой информации.

5. Разработан двухуровневый метод поиска заимствований в электронных изданиях, опубликованных в сети Интернет, позволяющий сократить время сравнения документов, содержащих от 5 до 30 Кб текстовой информации, в среднем на 50%. Рассмотрена возможность введения в алгоритм сравнения, весовых функций, позволяющих повысить эффективность разработанного метода.

6. Разработан метод уменьшения размерности текстового документа, являющийся основой в двухуровневом методе сравнения текстовой информации.

7. Разработан алгоритм поиска в верхней треугольной матрице последовательностей, параллельных главной диагонали, максимально покрывающих ось абсцисс не перекрывающимися проекциями, позволяющий формировать последовательности слов для двухуровневого метода поиска заимствований.

8. Разработан алгоритм формирования объединённых результатов сравнения текстовых документов, позволяющий определять итоговую оценку объёма заимствования при разбиении исходного текстового материала на незначительные фрагменты в разных текстовых документах, опубликованных в сети Интернет.

9. Разработана и программно реализована автоматизированная система поиска заимствований в электронных изданиях, позволяющая осуществлять поиск плагиата в электронных документах, опубликованных в сети Интернет, а также расположенных на локальных носителях информации, в отличие от крупнейшей отечественной системы, ориентированной на поиск заимствований лишь в тех документах, которые были добавлены в системную базу данных.

10. Проведены экспериментальные исследования, результаты которых представлены в данной работе, а также в приложениях. Данные, полученные в ходе экспериментальных исследований, позволяют оценить эффективность и адекватность предложенных и разработанных методов, направленных на выявление заимствований в электронных изданиях, опубликованных в сети Интернет. На основе проведённых исследований определен размер текстовых документов, при котором наиболее эффективно и целесообразно использование разработанного метода поиска заимствований.

11. Проведена апробация работы и внедрение разработанной системы, показавшие эффективность метода поиска и обнаружения заимствований, разработанной в рамках диссертационной работы, автоматизированной системой WebCompare.

Библиография Крутояров, Дмитрий Владимирович, диссертация по теме Автоматизация и управление технологическими процессами и производствами (по отраслям)

1. Алтунин А.Е., Востров Н.Н. Оптимизация многоуровневых иерархических систем на основе теории размытых множеств и методов самоорганизации. В сб.: "Проблемы нефти и газа Тюмени". Тюмень. Вып. 42,1979.

2. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях: Монография. Тюмень: Издательство Тюменского государственного университета, 2000. 352 с.

3. Апресян Ю.Д. Избранные труды, т. I. Лексическая семантика: 2-е изд., испр. и доп. М.: Школа «Языки русской культуры», Издательская фирма «Восточная литература» РАН, 1995. - 472 с.

4. Ашманов И.С., Руссова Н.В. Поисковые системы общие понятия и национальные особенности. - М.: ООО «ФИМА», 1997. - 24с.

5. Баксалова A.M. Уголовно-процессуальная функция обвинения, осуществляемая прокурором, и её реализация на судебном следствии. Диссертационная работа к.ю.н.: 12.00.09 Томск, 2002. - 209 с.

6. Батыршин И.З. Основные операции нечёткой логики и их обобщения. Казань: Отечество, 2001. - 102 с.

7. Бах А.О. Разработка эффективных алгоритмов поиска слов в текстах для построения методов сжатия данных. Диссертационная работа к.т.н.:05.13.13, Новосибирск 2002. - 214 с.

8. Белогаиов Г.Г., Богатырев В.И. Автоматизированные информационные системы. М.: Советское радио, 1973. - 325 с.

9. Беляева JI.H. Лингвистические автоматы в современных информационных технологиях: Монография. СПб.: Изд-во РГПУ им. А.И. Герцена, 2001.-130 с.

10. Бойцов Л.М. Синтез системы автоматической коррекции, индексации и поиска текстовой информации. Диссертационная работа к.т.н.: 05.13.01 Москва, 2003.

11. Будилов В. А. Основы программирования для Интернета. СПб.: БХВ - Петербург, 2003. - 736 е.: ил.

12. Бутузова О., Ильюшина Е.А., Петрова М., Прохоров А.В., Сиротки-на Ю.К построению авторского инварианта. Труды и материалы

13. Международного конгресса «Русский язык: исторические судьбы и современность» (13-16 марта 2001 года). Москва: МГУ, 2001.

14. В.Я. Пивкин, Е.П. Бакулин, Д.И. Кореньков под редакцией Ю.Н. Золотухина Нечеткие множества в системах управления. Электронный ресурс. Электрон. дан. - Режим доступа: http://idisys.iae.nsk.su/fuzzybook/content.html

15. Варфоломеев А.Г. Аннотация проектного предложения СевероЕвропейского открытого университета. Электронный ресурс. -Электрон. дан. 2003. - Режим доступа: http://neou.karelia.ru/site/Activity/Projects/proposals/PROPOSAL7/brie f7/

16. Виноградов В.В. Проблемы авторства и теории стилей. М., 1961. -263 с.

17. Вудс В.А. Сетевые грамматики для анализа естественных языков // Кибернетический сборник. Н.С. М.: Мир, 1978. - Вып. 13.

18. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб.: Питер, 2001. - 384 с.

19. Гасов В.М., Крутояров Д.В. Метод сравнения текстовых документов, позволяющий выявлять совпадающие фрагменты // Проблемы полиграфии и издательского дела. 2006 №4 - с. 92-104.

20. Гасов В.М., Цыганенко A.M. Методы и средства подготовки электронных изданий: Учеб. Пособие / В.М. Гасов, A.M. Цыганенко; Моск. гос. ун-т печати. М.: МГУП, 2001. - 735с.: ил.

21. Генне О.В. Основные положения стеганографии // Защита информации. Конфидент. -2000. №3.

22. Гитман М.Б. Введение в теорию нечётких множеств и интервальную математику: Учебное пособие /4.1. Применение лингвистической переменной в системах принятия решений. Перм. гос. техн. ун-т. Пермь, 1998.-45с.

23. ГОСТ 7.83 2001. Электронные издания. Основные виды и выходные сведения: Межгосударственный стандарт.

24. Дембинская Н. Британцы признали Google лучшим Интернет-брендом. Электронный ресурс. Электрон, дан. - 2006- Режим доступа: http://net.compulenta.ru/258364/

25. Дубинский А.Г. Некоторые вопросы применения векторной модели представления документов в информационном поиске // Управляющие системы и машины. 2001. - №4. - с. 77-83.

26. Дубинский А.Г. Проблема автоматизации поиска информации в глобальной сети // Проблемы автоматизации информационных технологий. Днепропетровск, 1999. - С. 40-48.

27. Дюран Б., Одел П. Кластерный анализ. М.: Статистика, 1977. - 128 с.

28. Ермаков А.Е. Неполный синтаксический анализ текста в информационно-поисковых системах // Компьютерная лингвистика и интеллектуальные технологии: Труды международного семинара Диа-лог'2002. В двух томах. Т.2. «Прикладные проблемы». М. 2002.

29. Ермаков А.Е. Проблемы полнотекстового поиска и их решение. // Мир ПК., №5,2001.

30. Ермаков С.В. Судебное следствие по делам о нарушении авторских и смежных прав. Диссертационная работа к.ю.н.: 12.00.09 Владимир, 2004. - 207 с.

31. Журавлёв А.П. Опыт вероятностно-статистического изучения стилевых различий // Язык и общество. Саратов, 1967.

32. Заболеева-Зотова А.В. Естественный язык в автоматизированных системах. Семантический анализ текстов: Монография / ВолгГТУ. -Волгоград, 2002. 228 с.

33. Закон об авторском праве и смежных правах (Закон РФ от 9 июля 1993 г. N 5351-1; с изменениями, внесенными Федеральным законом от 19 июля 1995 г. N 110-ФЗ, Федеральным законом от 20.07.2004 N 72-ФЗ)

34. Кнут, Дональд, Эрвин Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 702 е.: ил.

35. Кнут, Дональд, Эрвин Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2003. - 832 е.: ил.

36. Красилов А.А Информатика в семи томах. Том 4. Представление знаний (структуры данных) // Интеллсист. Интеллектуальные системы общего назначения. Москва, 2003.

37. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир. 1978.432 с.

38. Крутояров Д.В. Автоматизированная система сравнения электронных изданий, опубликованных в сети Internet/Intranet // Вестник МГУП. 2005 №11 (дополнительный). - с.84-87

39. Крутояров Д.В. О выборе метода анализа текстовой информации // Проблемы полиграфии и издательского дела. 2006 №3. - с. 175178

40. Кузнецов П.Б., Оленикова Ю.К. Основы нечёткой математики (теория нечётких множеств): Учебное пособие / Под ред. д-ра техн. наук, проф. Д.О. Бытева Ярославль: Издательство ЯГТУ, 2003. - 154 с.

41. Левенштейн В.И., Двоичные коды с исправлением выпадений, вставок и замещений символов, Докл. АН СССР, 163,4,1965.

42. Левнер Е.В., Птускин А.С., Фридман А.А. Размытые множества и их применение. -М.: ЦЭМИ РАН, 1998. 108 с.

43. Леонтьев К.Б. Проблемы развития авторского права в современных технологических условиях. Диссертационная работа к.ю.н.: 12.00.03 -М., 2003. -207 с.

44. Лихачёв Д.С. Вопросы атрибуции произведений древнерусской литературы // Труды отдела древнерусской литературы. АН СССР. Институт русской литературы (Пушкинский дом). Т. 17. М. Л., 1961.

45. Максимова Л.Г. Авторское право: Учебное пособие. М.: Гардари-ки, 2005.-383 с.

46. Мальцева Г.Ф. Некоторые количественные приёмы описания индивидуального авторского стиля // Статистика текста. Т.1, Минск, 1969.

47. Марков А.А. Об одном применении статистического метода // Изв. Имп.акад.наук, Сер. 6. 1916. №4

48. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 3 Коо -Од М.: «Советская энциклопедия», 1982. - 1184 стб., ил.

49. Меньков А.В. Теоретические основы автоматизированного управления: Учебное пособие. М.: МГУП, 2002. - 176 с.

50. Мистрик И. Математико-статистические методы в стилистике II Вопросы языкознания. 1967, №3

51. Монсик В.Б., Скрынников А.А. Теория вероятностей и математическая статистика. Статистическая проверка гипотез: Тексты лекций. -М.: МГТУ ГА, 2005. 64 с.

52. Морозов Н.А. Лингвистические спектры: средство для отличения плагиатов от истинных произведений того или иного известного автора. Стилеметрический этюд // Известия отд. Русского языка и словесности Имп.акад.наук. 1915. Т.20, Кн. 4.

53. Москин Н.Д., Варфоломеев А.Г. О применении компьютерных технологий в исследовании фольклорных песен. // Материалы IV научной конференции «Рябининские чтения-2003» Сборник научных докладов. Петрозаводск, 2003.

54. Мэгдайниер С. Защита интеллектуальной собственности на документы в системе WWW. Электронный ресурс. Электрон, дан. -Режим доступа: http://capri.ustu.ru/

55. На электронных документах появятся "водяные знаки" Электронный ресурс. Электрон, дан. - 2001. - Режим доступа: www.cnews.ru

56. Негуляев Е.А. "Невидимый" веб и некоторые вопросы доступности научной информации. VIII Международная конференция по электронным публикациям "EL-Pub2003" Новосибирск: Академгородок, 2003.

57. Новиков Ф.А. Дискретная математика для программистов СПб.: Питер, 2001.-304 с.

58. Новый алгоритм ранжирования. Интернет. Электронный ресурс. -Электрон. дан. 2004. - Режим доступа: http://company.yandex.ru/news/2004/0326/

59. Норвич A.M., Турксен И.Б. Фундаментальное измерение нечеткости. В сб.: Нечеткие множества и теория возможностей. М.: Радио и связь, 1986

60. Олифер В.Г., Олифер Н.А Компьютерные сети. Принципы, технологии, протоколы / В.Г. Олифер, Н.А. Олифер СПб.: Питер, 2001 -672с.: ил.

61. Операционные системы, поддерживающие MySQL. Электронный ресурс. Электрон. дан. - Режим доступа: http://dev.mysql.com/doc/mysql/en/which-os.html

62. Орловский С.А. Проблемы принятия решений при нечёткой исходной информации. М.: Наука, 1981.

63. Пивкин В.Я., Бакулин Е.П., Кореньков Д.И. Нечеткие множества в системах управления. 1995.

64. Погуляев В.В. Правонарушения в сети Интернет: взгляд на проблему сбора доказательств. Электронный ресурс. Электрон, дан. -Режим доступа: http://www.juragent.ru

65. Погуляев В.В., Тулубьева И.Ю. Нарушение авторских прав в сети Интернет. Электронный ресурс. Электрон, дан. - Режим доступа: http://www.juragent.ru

66. Подольский С. В., Скиба С. А., Кожедуб О. А. Разработка Интернет -приложений в Delphi. СПБ.: БХВ - Петербург, 2002. - 432 е.: ил.

67. Производительность СУБД MySQL. Электронный ресурс. Электрон. дан. - Режим доступа: http://www.mysql.com/benchmark.html

68. Севбо И.П. Графические представления синтаксических структур и стилистическая диагностика. Киев: Наук, думка, 1981. 192 с.

69. Севбо И.П., Алёшкина С.М. Исследование зависимости между длиной фразы и количеством уровней в графе // Структурная и математическая лингвистика. Вып. 2. Киев. 1974.

70. Севбо И.П., Петунин Ю.И., Галюта Е.Д. Эксперимент по распознаванию автора, основанный на предварительном статистическом исследовании синтаксических структур //Структурная и математическая лингвистика. Вып. 5. Киев. 1977.

71. Семенова С.Ю. Поиск параметрической информации в тексте: алгоритмический и лексикографический аспекты // Труды Международного семинара Диалог'9б по компьютерной лингвистике и приложениям. М„ 1996. - С. 227-230.

72. Серго А.Г. Некоторые вопросы защиты авторского права в Интернете. Электронный ресурс. Электрон, дан. - Режим доступа: http://www.russianlaw.net/law/doc/al35.htm

73. Серго А.Г., Пущин B.C. Основы права интеллектуальной собственности. Курс лекций. Учебное пособие. М.: Интернет-университет информационных технологий, 2005. - 344 с.

74. Сидоров Ю.В. Математическая и информационная поддержка методов обработки текстов на основе формально-грамматических параметров. Диссертационная работа к.т.н.: 05.13.18 Петрозаводск -2002. -127 с.

75. Степанов А.В. Эвристика стиля атрибуция авторства // Литературная учёба. 1998. №2.

76. Сэлтон Г. Автоматическая обработка, хранение и поиск информации: Пер. с англ. / Под ред. А.И. Китова. М.: Советское радио, 1973.-560 с.

77. Тейксейра С., Кавье П. Delphi 5. Руководство разработчика, том 1. Основные методы и технологии программирования: Пер. с англ. -М.: Издательский дом «Вильяме», 2001. 832 е.: ил.

78. Терлецкий В.В. Охрана авторских и смежных прав при использовании охраняемых объектов в цифровых сетях и продуктах мультимедиа. Диссертационная работа к.ю.н.: 12.00.03 М., 2003. - 159 с.

79. Тригуб Н.А. Система обработки неструктурированной текстовой информации на основе объектного подхода для повышения эффективности информационного поиска. Диссертационная работа к.т.н.: 05.13.01 Москва, 2004. - 189 с.

80. Труды по интеллектуальной собственности Том VI. Под редакцией М.А. Федотова-М., 2003.

81. Украинские вузы не спешат внедрять программу по обнаружению плагиата в работах студентов. Электронный ресурс. Электрон.дан. 2005- Режим доступа:http://www.podrobnosti.ua/ptheme/internet/2005/10/26/255838.html

82. Ухоботов В.И. Введение в теорию нечётких множеств и её приложения. Челябинск: Фотохудожник, 2005. - 133 с.

83. Фаронов В.В. Delphi 5 Руководство программиста. М.: «Нолидж», 2001.-880 е.: ил.

84. Федоренко Д.В. Автоматизированная система сравнения электронных изданий, опубликованных в сети Internet/Intranet // Вестник МГУП. 2004 №5. - с.74-78

85. Федоренко Д.В. Актуальность выявления нарушений авторских прав // Вестник МГУП. 2005 №5. - с.36-47

86. Федоренко Д.В. Исследование эффективности использования баз данных по сравнению с файловой системой для хранения текстовой информации // Вестник МГУП. 2005 №5. - с. 19-35

87. Фоменко В.П., Фоменко Т.Г. Авторский инвариант русских литературных текстов. Приложение: кто был автором "тихого дона"? Электронный ресурс. Электрон, дан- Режим доступа: http://www.newchrono.ru/framel/Methods/html/278.htm

88. Частичный список клиентов MySQL. Электронный ресурс. Электрон. дан. - Режим доступа: http://www.mysql.com/company/

89. Чигарин Т.Г. Авторские права и Интернет. Электронный ресурс. -Электрон. дан. 2004. - Режим доступа: http://www.allpravo.ru/librarv/docl972p0/instruml983/iteml984.html

90. Чикунов И.М. Электронное издание древних рукописей и первопечатных книг. Диссертационная работа к.т.н: 05.13.06 Москва, 2003.- 153 с.

91. Чугреев B.JI. Модель структурного представления текстовой информации и метод её тематического анализа на основе частотно-контекстной классификации. Диссертационная работа к.т.н.: 05.13.01 СП-б-2003. 185 с.

92. Чураков А.Н. Информационное общество и эмпирическая социология. // Социологические исследования. №1. 1998 с. 35-44.

93. Arimura Н., Wataki A., Fujino К., Arikawa S. A Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases. // Algorithmic Learning Theory, 9th International Conference, ALT '98, Otzenhausen, Germany, 1998.

94. Baker B.S. A program for identifying duplicated code. Proceedings of the 24th Symposium on the Interface: Computer Science and Statistics, College Station, Texas, 1992.

95. Boyer R.S. Moore J.S. A Fast String Searching Algorithm // Commun. ACM.- 1977.-Vol. 20, №10.

96. Burrows J.F. Not Unless You Ask Nicely: The Interpretative Nexus Between Analysis and Information // Literary and Linguistic Computing, Oxford University Press. 1992. Vol. 7.

97. Colussi L. Correctness and Efficiency of the Pattern Matching Algorithms // Information and Computation. 1991. Vol. 95, №2.

98. Colussi L. Fastest Pattern Matching in Strings // J. of algorithms. 1994. -Vol. 16, №2.

99. Crochemore M. String-Matching on Ordered Alphabets // Theoretical Computer Science. 1992. - Vol. 92, №1.

100. Crochemore M., Czumaj A., Gasieniec L., Jarominek S., Lecroq Т., Plandowski W., Rytter W. Speeding up Two String Matching Algorithms // Algoritmica. 1994. - Vol. 12, №4/5

101. Finkelstein L., Gabrilovich E., Matias Y., Rivlin E., Solan Z., Wolfman G., Ruppin E. Placing search in context: the concept revisited. In Proc. of the WWW10,2001. p. 406-414

102. Foltz P.W. Using latent semantic indexing for information filtering. In ACM Conference on Office Information Systems (COIS), 1990, p. 4047.

103. Garfield E. From citation amnesia to bibliographic plagiarism. // Current Contents. 1980. No. 23.

104. Greenacre P. Note on plagiarism: The Henley-Stevenson quarrel. // Journal of American Psychoanalysis Association.1978. No. 26.

105. Hendry D.G., Harper D.J. An informal information-seeking environment. // J. of the American Society for Information Science, 48(11): 1036 -1048,1997.

106. Hirschberg D.S. A linear space algorithm for computing maximal common subsequences. // Communications of the ACM, Vol. 18, No. 6, 1975.

107. Holmes D.I. The Evolution of Stylometry in Humanities Scholarship // Literary and Linguistic Computing, Oxford University Press. 1998. Vol. 13, No. 3.

108. Horspool R.N. Practical Fast Searching in Strings // Software Practice & Experience. - 1980. Vol. 10, №6.

109. Hunt J.W., Szymanski T.G. A fast algorithm for computing longest common subsequences. // Communications of the ACM, Vol. 20, No. 5, 1977.

110. Knuth D.E., Morris J.H., Pratt V.R. Fast Pattern Matching in Strings // SIAM J. on Computing. 1977. - Vol. 6, №1.

111. Kolich A.M. Plagiarism: the worm of reason. // College English. 1983. No. 45.-p. 141-148.

112. Kurtz S. Fundamental algorithms for a declarative pattern matching system. Bielefend- 1995.

113. Landau G.M., Vishkin U. Fast parallel and serial approximate string matching. //Journal of Algorithms, Vol. 10, 1989.

114. Landauer Т.К., Foltz P.W., Laham D. Introduction to Latent Semantic Analysis. // Discourse Processes, Vol.25, 1998, p. 259-284.

115. Mallon T. Stolen words Forays into the origins a. ravages of plagiarism. -New York: Penguin books, 1991. 300 p.

116. Masek W.J., Paterson M.S. A faster algorithm for computing string-edit distances.// Journal of Computer and Systems Sciences, Vol. 20, No. 1, 1980.

117. Masek W.J., Paterson M.S. How to compute string-edit distances quickly, in Sankofi D., Kruskall J.B. (eds.) Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, Chapter 14, Addison-Wesley, Reading MA, 1983.

118. McCreight E.M. A space-economical suffix tree construction algorithm.// Journal of the ACM, Vol. 23, No. 2, 1976.

119. Myers E.W. An overview of sequence comparison algorithms in molecular biology/ Technical report TR 91-29, University of Arizona, Tucson, Department of Computer Science, 1991.

120. Ponte J., Croft W.B. A language modeling approach to information retrieval.//SIGIR, 1998.

121. Sunday D.M. A very fast substring search algorithm // Communications of the ACM. 1990. - Vol. 33, №8.

122. Ukkonen E. Algorithms for approximate string matching. // Information and Control. 1985.

123. Ukkonen E. Finding approximate patterns in strings, О (k*n) time. // Journal of Algorithms 1985.

124. Wagner R.A., Fisher M.J. The String to String Correction Problem // Journal of ACM, 21(1), 1974.

125. Yager R.R. Fuzzy sets, probilities and decision. //J. of Cybern. N 10, 1980.

126. Zobel J., Moffat A. Exploring the similarity space // SIGIR Forum, 1998.

127. Вывод на дисплей информации о результатах сравнения списков1. Начало

128. Цикл по всем элементам из списка №11. С1

129. Цикл по всем элементам из списка №2 начиная с позиции прошлого совпадения +11. Нет

130. Цикл по всем элементам из списка №2 начиная с позиции прошлого сравнения в этом цикле -11. Конецj

131. Рис. 7. Блок-схсма алгоритма сравнения списков элементов.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00