Разработка и программная реализация анализа подобия текстов

Введение 5
1 Цели, задачи и алгоритмы сравнения текстов 7
1.1 Цели, задачи и методы сравнения текстов 7
1.2 Обзор и анализ алгоритмов сравнения текстов 12
2 Обзор программных средств 27
2.1 Среда разработки и язык программирования 27
2.3 Классы 33
2.4 Пространство имен System.IO 38
3 Программная реализация анализа подобия текстов 44
3.1 Постановка задачи на дипломное проектирование 44
3.2 Обобщенный алгоритм программы 44
3.3 Векторы сравниваемых текстов 45
3.4 Пользовательские классы и массивы 48
3.5 Выбор текстов, подсчет частот и TF-мер 49
3.6 Создание единого массива терминов, частот и мер двух текстов 51
3.7 Вычисление меры сходства текстов 52
3.8 Тестирование и отладка программы 55
4 Информационная безопасность 59


4.1 Законодательство в сфере информационной безопасности 59
4.2 Оценка рисков информационной системы предприятия 64
4.3 Анализ рисков и уязвомостей системы 66
4.4 Разработка мер безопасности и оценка рисков после их внедрения 69
5 Экономическая часть 72
5.1 Расход трудоемкости разработки программного продукта 72
5.2 Расход на оплату труда разработчика программы 74
5.3 Общие затраты на создание программного продукта 75
5.4 Целесообразность создания продукта 75
Выводы и рекомендации 77
Библиографический список 78
Приложение А. 81

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

1.2 Обзор и анализ алгоритмов сравнения текстов
Алгоритмов сравнения текстов существует огромное количество, многие из них достаточно эффективны в своем диапазоне решаемых задач. Правильное применение нужно алгоритма зависит от конкретной задачи, стоящей перед исполнителем. На самом деле, именно характер данных, их объём и другие особенности предметной области диктуют алгоритм обработки.
1.2.1 Алгоритм шинглов
Алгоритм шинглов (шингл (shingles) с английского это черепичка, чешуйка) предназначен для нечеткого поиска дубликатов текста. Слово «нечеткий» означает, что вхождения дублей ищется не точно, а размыто. К примеру, возможен дубликат не только строки, но и отдельных словосочетаний. В основном модификация алгоритма шинглов используется поисковыми системами для борьбы с поисковым спамом.
Это позволяет из поисковой выдачи исключать тексты похожие друг на друга или полностью идентичные. Однако остается проблема первоисточника, т.е.
...

2.1 Среда разработки и язык программирования
Для реализации проекта выбран язык С# и среда разработки VisualStudio.NET 2010.
С# это объектно-ориентированный язык программирования, который как все объектно-ориентированные языки, имеет три характерных черты: инкапсуляцию, полиморфизм и наследование.
Инкапсуляция – это механизм программирования, который связывает код (действия) и данные, которыми он манипулирует, и при этом предохраняет их от вмешательства извне и неправильного использования. В объектно-ориентированном языке код и данные можно связать таким образом, что будет создан автономный черный ящик. Внутри этого ящика находятся все необходимые данные и код. При таком связывании кода и данных создается объект. Другими словами, объект – это элемент, который поддерживает инкапсуляцию [16].
Основной единицей инкапсуляции в С# является класс. Класс определяет форму объекта. Он задает как данные, так и код, который будет оперировать этими данными.
...

2.4 Пространство имен System.IO
В С# определены как байтовые, так и символьные классы потоков. Однако символьные классы потоков в действительности представляют собой оболочки, которые преобразуют базовый байтовый поток в символьный, причем любое преобразование выполняется автоматически. Таким образом, символьные потоки построены на основе байтовых, несмотря на то, что они логически отделены друг от друга.
Сопрограммы выполняют операции ввода-вывода посредством потоков. Поток (stream) – это абстракция, которая либо синтезирует информацию, либо потребляет ее. Поток связывается с физическим устройством с помощью С#-системы ввода-вывода. Характер поведения всех потоков одинаков, несмотря на различные физические устройства, с которыми они связываются. Следовательно, классы и методы ввода-вывода можно применить ко многим типам устройств. Например, методы, используемые для записи данных на консольное устройство, также можно использовать для записи в дисковый файл.
...

3.2 Обобщенный алгоритм программы
Сначала разработан общий алгоритм программы анализа подобия текстов.
Словесное описание обобщенного алгоритма:
1. Обработка текстовых файлов.
1) Загрузка и обработка файла. Разделение текста на слова, сохранение в виде массива.
2) Подсчет частот слов в цикле.
3) На основании полученных частот расчет относительных частот TF1.
4) Повтор п.1-3 для второго текста.
2. Построение общего списка слов сравниваемых текстов – векторов текстов.
1) Создание списка с четырьмя полями (слово, частота, TF1 и TF2).
2) Заполнение списка словами и TF1 первого текста.
3) Поиск в первом массиве слов второго текста, и добавление в список TF2
4) Добавление в список слов второго текста, не найденных в первом тексте, причем тогда TF1=0.
3. Подсчет значения косинуса между векторами текстов (мера сходства).
4. Вывод результатов на экран.
Обобщенный алгоритм представлен на рис. 3.1.
...

3.4 Пользовательские классы и массивы
Для удобства создан пользовательский класс Termin с четырьмя полями: слово, частота, TF1 и TF2. Пользовательский класс прописан с обобщенным методом сравнения IComparable, для возможности сравнивать объекты пользовательских классов.
class Termin : IComparable

{
public string slovo;
public int chastota;
public double TF1;
public double TF2;


int IComparable.Compare To(object obj)
{
Termin Compare Obj = obj as Termin;
if (Compare Obj == null) throw new ArgumentException("Можно сравнивать только элементы одного типа.");
return slovo.Compare To(Compare Obj.
...

3.5 Выбор текстов, подсчет частот и TF-мер
Пользователь выбирает файлы с текстами для сравнения в окне консоли – нужно только ввести по приведенному образцу путь к файлу. Способ уже был описан в 2.4.
Рисунок 3.4 – Выбор текстов для сравнения

Если файл хранится в папке Debug, можно просто указать его имя, а если нет –ввести путь (рис.3.4).
Текст должен быть в кодировке UTF-8 тип файла txt.
Вначале загруженный в переменную текстовый файл разбивается на слова оператором Split с помощью массива типа char separator, в котором перечислены все разделители: точка, запятая, пробел и т.д.:
string[] word1;
word1 = stroka.Split(separator);

Самым важным было связать слово и подсчитанное количество его повторов, для этого были созданы временные массивы временные массивы word1 и kolvo, в которые записывалось, соответственно слово и его частота, и в массиве же они записывались в поля массива ArrayList slova1.
...

3.6 Создание единого массива терминов, частот и мер двух текстов
Как уже говорилось выше, вначале находятся общие слова двух текстов. Для этого в цикле foreach, который позволяет обращаться к каждому элементу коллекции, и к полям этого объекта, без индекса, сравниваются элементы по полю slovo.
Если объекты эквивалентны, то в массиве slova1 заполняется поле TF2, обозначающее TF-меру терминов второго текста.
foreach (Termin t in slova1)
{
foreach (Termin o in slova2)
{
if (t.slovo.Contains(o.slovo) == true&&t.slovo.Equals(o.slovo))

t.TF2 = o.TF2;
o.slovo = "LLLLLLLLLLLLLLL"; o.TF1 = 0; o.TF2 = 0; o.chastota = 0;
}

}
}
Как видно, здесь можно обойтись простым методом Equals, а соответствующий объект в массиве slova1 забивается и впоследствии удаляется.
...

3.7 Вычисление меры сходства текстов
Как уже говорилось, мерой схожести является косинус между векторами документов и оценивается по формулам (1.2) и (1.3). Теперь, когда получены векторы текстов, можно рассчитать и угол между ними.
Косинус определяет, насколько сонаправлены друг другу вектора. Если он равен 0, то данные вектора лежат под углом 900, то есть перпендикулярны. То есть их тематика совершенно различна. Поскольку косинус 0 равен единице (вектора однонаправлены), то очевидно, что чем больше значение косинуса – тем меньше угол между векторами, тем ближе их направление, тем больше степень соответствия.
Сначала вычисляется мера сходства на основании TF-мер.
Вычисление проводится в цикле foreach, который позволяет проходить каждый элемент массива. В принципе, цикл foreach не лучший выбор, отмечается [22], что он более медленный и иногда работает с погрешностями, однако он необходим тогда, когда нужен полный доступ к полям объекта пользовательского класса.
...

3.8 Тестирование и отладка программы
Вначале, в процессе написания и отладки, чтобы видеть оба текста, и легко отслеживать ошибки, использовались небольшие – в 2-3 предложения, тексты. Особого смысла в них не было, но проверялась корректность работы программы, сделанных вычислений, построения общего массива слов и TF-мер.
Вначале проверялась правильность подсчета абсолютных частот, так как именно на них строится весь расчет: вычисление TF-мер, векторов и меры сходства (рис.3.5). Там же тестируется правильность сравнения объектов.

Рисунок 3.5 – Проверка правильности подсчета частот
Пример отладки программы в процессе работы приведен на рис.3.6. На нем видно выведенный массив слов двух текстов, а также значение абсолютных и относительных частот (TF-мер).
Ниже приведен рассчитанный косинус – мера схожести текстов, и критерии оценки данного показателя.
...

4.1 Законодательство в сфере информационной безопасности
Главным законом в сфере информационной безопасности РФ является Федеральный закон от 27 июля 2006 г. N 149-ФЗ «Об информации, информационных технологиях и о защите информации» (с изменениями и дополнениями) [24].
Законодательство Российской Федерации об информации, информационных технологиях и о защите информации основывается на Конституции Российской Федерации, международных договорах Российской Федерации и состоит из настоящего Федерального закона и других регулирующих отношения по использованию информации федеральных законов.
Правовое регулирование отношений, связанных с организацией и деятельностью средств массовой информации, осуществляется в соответствии с законодательством Российской Федерации о средствах массовой информации. Порядок хранения и использования включенной в состав архивных фондов документированной информации устанавливается законодательством об архивном деле в Российской Федерации [25].
...

4.2 Оценка рисков информационной системы предприятия
В данном разделе рассмотрим структуру информационной системы организации, которая имеет локальную сеть и выход в интернет, а также связь с компьютерами, на которых установлены программы складского учета и учета продаж (касса).
При анализе используется система КОНДОР ООО «Диджитал Секьюрити». Для оценки рисков и общей политики безопасности организации, нужно ответить на вопросы по организации политики безопасности и контроля доступа (рис.4.1).
Рисунок 4.1 – Оболочка программы КОНДОР
На основе проведенного анализа система составляет отчет с оценкой рисков и невыполненных требований. Полученные сводные данные по системе приведены в таблице 4.1.
Таблица 4.1 – Сводные данные по системе
Показатель
Значение
Всего требований
206
Выполнено
54
Не выполнено
152
Уровень риска, %
70,30%
Соотношение рисков приведено по разделам (организационные меры и контроль доступа) и показаны на рис. 4.2.
Рисунок 4.2 – Невыполненные требования и риск

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

4.4 Разработка мер безопасности и оценка рисков после их внедрения
На основании выделенных недостатков определены следующие меры по повышению безопасности:
1) Изменение правил доступа на рекомендованные системой анализа;
2) Отмена групповых идентификаторов с заменой их на индивидуальные. Изменение процедуры назначения паролей и требований к ним;
3) Введение единого надежного уникального пароля пользователя для всех сервисов;
4) Криптографическая защита паролей, повышение безопасности их хранения;
5) Изменение процедуры регистрации событий в соответствии с рекомендованными системой КОНДОР параметрами;
6) Изменение доступа к работе с системными утилитами;
7) Для предотвращения неавторизованного доступа к ресурсам решено применять такое средство защиты операционной системы, как экранирование. Также используются средства контроля маршрутизации.
...

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

Трудоемкость разработки программного продукта определяется [30]:
ТПР = ТО +ТИ + ТА + ТБС + ТН + ТОТ + ТД (1)
Затраты можно вычислить через условное число операторов в программе (Q). Число операторов в отлаженной программе на языке С# составляет 3200.

Расчет затрат труда на подготовку описания.
Так как подготовка описания задачи не проводилась, примем ТО =0. Далее оцениваются затраты труда на изучение описания задачи, они определяются:
ТИ = , (2)
где В – коэффициент увеличения затрат труда вследствие недостаточного описания задачи, уточнений и недоработок, В= 1,2…5;
К – коэффициент квалификации разработчика.
Данный показатель, как и ряд остальных, рассчитывается с учетом квалификации программиста.
Задача была поставлена ясно, но при реализации пришлось изучать дополнительные материалы о языке С#.
...

5.2 Расход на оплату труда разработчика программы
Расходы на оплату труда разработчика программы определяются как произведение трудоемкости создания программного продукта на среднюю часовую оплату программиста (с учетом премий, доплат и отчислений на страховые взносы):
Зр = (11)

Расчет средней зарплаты программиста.
Средняя часовая зарплата программиста определяется исходя из величины его месячного оклада (О), продолжительности рабочей смены и фонда рабочего времени планируемого года. Ставка программиста составляет 15000 рублей, продолжительность рабочего дня – 8 часов, среднемесячное число рабочих дней составит 18 дней.
Таким образом, средняя часовая зарплата составит:
Зсрч = 15000/(18∙8) = 104,1 руб.
Расход на оплату труда разработчика программы.
Расходы на оплату труда разработчика программы определяются
по формуле (11):
Зр = 104,1 412,6 = 42951,7 руб.
и составит 42951,7 руб.

5.3 Общие затраты на создание программного продукта
Общие затраты Спр складываются из заработной платы программиста-разработчика (42951,7 руб.) и затрат на оплату машинного времени.
Рассчитаем оплату машинного времени. Затраты на оплату машинного времени при отладке программы определяются умножением фактического времени отладки программы на цену машино-часа арендного времени:
ЗОТЛ = СМЧ ∙ ТОТЛ (12)
Расчет фактического времени отладки:
ТОТЛф = ТН + tДО + ТОТ, (13)
ТОТЛф = 57,14 + 17,64 + 120 ≈ 194,78 час.

Цена машино-часа принимается 17,4, так как стоимость аренды компьютера составляет 15-20 рублей за час .
Затраты на оплату машинного времени:
ЗОТЛ = 17,4 ∙104,1 = 3405,1 руб.

Теперь подсчитаем общие затраты Спр на создание продукта:
Спр = 3405,1 + 42951,7 = 46356,8 ≈ 46356 руб.
Итого, общие затраты на создание программы для обработки текстов составят 46356 рублей, основные затраты составляет заработная плата программиста.

Библиографический список
1. Мешкова Е.В. Анализ современных методов обработки текстовой информации для автоматической классификации документов / Информационные системы и технологии. Теория и практика: cб. науч. тр. / редкол.: А.Н. Береза [и др.]. – Шахты: ГОУ ВПО «ЮРГУЭС», 2009. – 210 с.
2. Лексин В. Рекомендательная система: полезные задачи текстмайнинга [Электронный ресурс]: Хабрахабр.  Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
3. Лексин В. Рекомендательная система: введение в проблему холодного старта [Электронный ресурс]: Хабрахабр.  Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
4. Лексин В. Рекомендательная система: полезные задачи текстмайнинга. Поиск дубликатов и плагиата среди веб-страниц [Электронный ресурс]: Хабрахабр.  Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
5. Иванов Р. Алгоритм Шинглов. Поиск дубликатов текста [Электронный ресурс]: ОрионXL, 15.01.2010. URL: http://www.orionXL.ru.
6.
...

Были использованы материалы статей по методам обработки и сравнения текстов, а также собственные методические материалы по данной теме. Также использовались книги по программированию на языке С#. Различные определения взяты из Википедии.

Библиографический список
1. Мешкова Е.В. Анализ современных методов обработки текстовой ин-формации для автоматической классификации документов / Информационные системы и технологии. Теория и практика: cб. науч. тр. / редкол.: А.Н. Береза [и др.]. – Шахты: ГОУ ВПО «ЮРГУЭС», 2009. – 210 с.
2. Лексин В. Рекомендательная система: полезные задачи текстмайнинга [Электронный ресурс]: Хабрахабр. Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
3. Лексин В. Рекомендательная система: введение в проблему холодного старта [Электронный ресурс]: Хабрахабр. Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
7. Родненко В. Python: Алгоритм Шинглов – поиск нечетких дубликатов текста [Электронный ресурс]:Code is art, 19.01.2009. URL: http://www.codeisart.ru/
8. Fetterly et al. A Large-Scale Study of the Evolution of Web Pages, Addison-
Wesley, Massachusetts, 2003.
9. Лексин В. Поиск нечетких дубликатов. Алгоритм шинглов для веб-документов. [Электронный ресурс]: Хабрахабр. Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
10. Мешкова Е.В. Методические указания по выполнению курсовой работы по дисциплине «Методы и средства обработки информации в глобальных компьютерных сетях» [Электронная версия], ВИС ЮРГУЭС,2011
11. Попов А. Поиск в Интернете, внутри и снаружи [Электронный ресурс]: Корабли в бутылках, 2005. URL: http://www.shipbottle.ru
12. Латентное размещение Дирихле (LDA) [Электронный ресурс]: Википедия, 2011. URL: wikihttp://ru.wikipedia.org/wiki
13. Лексин В. Холодный старт для веб-страниц [Электронный ресурс]: Хабрахабр. Блог компании Surfingbird, 2013. URL: http://www.habrahabr.ru.
14. Латентно-семантический анализ (ЛСА) [Электронный ресурс]: Вики-педия, 2011. URL: wikihttp://ru.wikipedia.org/wiki
15. Readings in Latent Semantic Analysis for Cognitive Science and Education [Электронный ресурс]: Сборник статей и публикаций по ЛСА, 2012. URL: http://www.timc.imag.fr/Benoit.Lemaire/lsa.html
16. Шилдгт Г. Полное руководство по С# - 2-e изд., М.:Вильямс, 2010, -1024 с.
17. Флёнов М.Е. Библия С# - 2-е изд., перераб.и доп. – СПб.,БХВ-Петербург, 2011. – 560 с.
18. К.Уотсон, К. Нейгел, Я. Хю Педерсен, Д. Д. Рид, М. Скиннер, Э. Уайт. Visual C# 2008: базовый курс: изд-во "Диалектика", 2009.
19. Эндрю Троелсен. Язык программирования C# 2010 и платформа .NET 4 – 2011.