Разработка и модификация моделей и алгоритмов поиска данных в INTERNET/INTRANET среде для улучшения качества поиска тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Хорошко, Максим Болеславович

• Хорошко, Максим Болеславович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Хорошко, Максим Болеславович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. АНАЛИЗ ИНТЕРНЕТ ТЕХНОЛОГИЙ И ФОРМАЛИЗАЦИЯ ПРОБЛЕМЫ ИНФОРМАЦИОННОГО ПОИСКА

1.1 Классификация поисковых систем и моделей информационного поиска

1.2 Особенности реализации технологии информационно-поисковой системы

1.3 Анализ существующих постановок и методов решения задачи оптимизации информационного поиска

1.4 Формализация проблемы оптимизации информационного поиска и построение математической модели ИПС

Выводы по главе 1

2. ФОРМИРОВАНИЯ НАБОРА МЕТРИК ЭФФЕКТИВННОСТИ ДЛЯ ОЦЕНКИ СИСТЕМ ИНФОРМАЦИОННОГО ПОИСКА

2.1 Постановка задачи оценки информационно-поисковой системы

2.2 Метрики оценки информационно-поисковых систем

2.3 Экспериментальное исследование предложенной метрики ошибок

2.4 Оценка релевантности и выбор оптимального набора метрик

2.5 Оценка качество системы и её полезность для пользователя

Выводы по главе 2

3. МЕТОДЫ ПОСТРОЕНИЯ ИНДЕКСА ПОИСКОВОЙ СИСТЕМЫ

3.1 Метод инвертированных и сигнатурных файлов

3.2 Суффиксные массивы

3.3 Построение индекса в виде дерева

3.4 Индексные структуры для нечетких сравнений

Хеширование по сигнатуре

3.5 Модификация метода инвертированных файлов

3.6 Экспериментальное исследование методов построения индекса

Выводы по главе 3

4. МОДИФИКАЦИЯ АЛГОРИТМОВ ОПТИМИЗАЦИИ ИНФОРМАЦИОННОГО ПОИСКА И ИХ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

4.1 Описание генетического алгоритма для системы поиска и оценка сложности

4.2 Описание экспериментальных исследований

4.3 Модификация алгоритмов булевого поиска и их экспериментальное исследование

4.4 Модификация модели векторного пространства для ранжирования и экспериментальное исследование алгоритмов

4.5 Модификация вероятностной модели информационного поиска и экспериментальное исследование

4.6 Экспериментальное исследование модификации методов обратной связи по релевантности

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

4.8 Оценка алгоритмов поиска информации Sphinx, Lucene, Xapian

4.9 Улучшенная модель поиска

Выводы по главе 4

5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ИНФОРМАЦИОННОГО ПОИСКА И ИХ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ

5.1 Модель информационно-поисковой системы

5.2 Имитационные модели информационно-поисковой системы

5.3 Проектирование приложения - информационно поисковой системы IRSI

5.4 Программная реализация алгоритмов

Выводы по главе 5

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ В

ПРИЛОЖЕНИЕ Г

Введение диссертации (часть автореферата) на тему «Разработка и модификация моделей и алгоритмов поиска данных в INTERNET/INTRANET среде для улучшения качества поиска»

ВВЕДЕНИЕ

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

В настоящее время работает ряд авторитетных международных конференций, посвященных обсуждению вопросов информационного поиска, например, таких как: WWW (World Wide Web) Conference -специально организованная конференция для решения задач связанных с Интернет; TREC (Text Retrieval Conference) - серия конференций, сконцентрированных на исследовании различных областей информационного поиска и их задач. Она поддерживается National Institute of Standards and Technology (NIST) и Association of Religion Data Archives (ARDA), расположенных в США, начиная с 1992. Целью TREC является поддержка исследований сообщества информационного поиска с помощью предоставления инфраструктуры, необходимой для развития его технологий. Из Российских конференций посвященные вопросам информационного поиска, можно выделить всероссийскую конференцию «Электронные библиотеки» (RCDL).

Также вопросами улучшения качества поиска и внедрением информационно-поисковых систем, занимаются коммерческие организации Яндекс, Галактика-Зум Sphinx, Lucene, Google и др.

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

Существует большой спектр предлагаемых решений: начиная от построения технологии информационного поиска, структур, индексов и до

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

Диссертационная работа выполнена в рамках научного направления ФГБОУ ВПО ЮРГПУ(НПИ) им М.И. Платова «Теория, принципы и технологии построения информационно-вычислительных и измерительных систем», госбюджетной темы 7.05 «Разработка теории, методов оптимизации функциональной и программно-технической платформы корпоративных информационных систем» (Утверждено решениями ученого совета от 25.04.2001г. и 15.05.2003г).

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

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

Для достижения поставленной цели решаются следующие задачи:

1. Теоретический анализ вопросов построения архитектуры и технологий информационно-поисковых систем, ориентированный на повышение эффективности в зависимости от типа запроса пользователя.

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

3. Разработка и исследование модификаций методов построения индекса.

4. Анализ и разработка модификации алгоритмов информационного поиска в части расчета критерия релевантности документа.

5. Разработка имитационной модели информационно-поисковой системы с целью возможной оценки предлагаемых технических решений.

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

Объектом исследования является технология функционирования, методы построения индексов, метрики оценки, модели и алгоритмы информационно-поисковых систем.

Предметом исследования являются массивы данных, обрабатываемый в информационно поисковой системе и математические модели, их описывающие.

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

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

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

1. Новая метрика «Чувствительная метрика ошибок», которая оценивает первые N - документов на соответствие полученной релевантности. Чем выше документ в списке, тем меньше допустима ошибка, т.к. пользователи просматривают документы по порядку.

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

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

4. Модификация алгоритмов поиска информации Sphinx, Lucene, Xapian с помощью генетического алгоритма, позволяющая улучшить характеристики модели корпоративного поиска.

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

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

7. Модификация архитектуры информационно-поисковой системы, позволяющая уменьшить количество операций чтение/запись из хранилища.

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

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

Для практического применения системы в диссертации создан программный продукт (IRSI), позволяющий выполнять поиск в корпоративной информационной среде и нескольким сайтам.

Реализация результатов работы. Разработанные в диссертационной работе теоретические и практические результаты внедрены в ООО «ВелесВент», ОАО «НГЧ».

Разработанный программный продукт имеет свидетельство об официальной регистрации программных систем и баз данных в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ): • программная система IRSI/ Информационно-поисковая система информации в Intranet/Internet среде. Зарегистрировано в Реестре программ для ЭВМ 6.07.2011 г., per. № 2011616861

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

• VII Международной научно-практической конференции «Моделирование, Теория, методы и средства», 2007г. (г. Новочеркасск)

• Научно-технической конференции студентов и аспирантов ЮРГТУ (НПИ) «Студенческая весна 2008» (г. Новочеркасск)

• VIII Межрегиональной научно-практической конференции студентов и аспирантов, 2008 г. (г. Новокузнецк)

• II Российской летней школе по информационному поиску, 2008г. «RuSIR 2008» (г. Таганрог)

• VII, XI Международной научно-практической конференции «Теория, методы, проектирования, программно-техническая платформа корпоративных информационных систем», 2009г, 2013г. (г. Новочеркасск)

• IV Российской летней школе по информационному поиску, 2010г. «RuSIR 2010» (г. Воронеж)

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

Структура диссертационной работы. Диссертация содержит 173 станицы основного текста, 74 рисунка, 22 таблицы и состоит из введения, пяти глав, заключения, списка литературы из 100 наименований и трех приложений объемом 38 страниц.

и

1. АНАЛИЗ ИНТЕРНЕТ ТЕХНОЛОГИЙ И ФОРМАЛИЗАЦИЯ ПРОБЛЕМЫ ИНФОРМАЦИОННОГО ПОИСКА

1.1 Классификация поисковых систем и моделей информационного поиска

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

Информационный поиск — это один из ключевых механизмов доступа пользователей к нужной им информации. Один из первых фундаментальных обзоров задач информационного поиска и информационно-поисковых систем был представлен в работе Рейзенберга, «Information Retrieval» [9], и не смотря на то, что данная работа была опубликована в 1979 году, это до сих пор один из полных и исчерпывающих обзоров по информационному поиску.

Существующие информационные системы, работающие с электронными документами, можно условно разделить на две категории: информационно-поисковые системы (в зарубежной терминологии они фигурирую под термином information retrieval systems), и системы выборки данных [10]. Стоит отметить, что данная классификация условна и в её контексте многие современные информационные системы совмещают в себе свойства как систем выборки данных, так и информационно-поисковых систем. Базовые отличия этих двух систем представлены в таблице 1.1.

Таблица 1.1 Базовые отличия систем выборки данных и ИПС

Наименование Система выборки данных Информационно поисковая система

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

Классификация документов детерминированная вероятностная

Язык запросов искусственный естественный

Критерии выборки документов булева функция релевантности вероятностная функции релевантности

Устойчивость к ошибкам в данных и запросах неустойчивы устойчивы

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

И системы выборки данных, и информационно поисковые системы, работают с некоторой коллекцией документов, которую можно рассматривать как список записей (документов), где каждая запись содержит в себе некоторый набор слов, состоящих из символов алфавита [81]. В реальных информационных системах в исходном множестве документов может содержаться дополнительная информация, описывающая документы, которая так же может использоваться для осуществления поиска.

По данным недавнего исследования (2011г.) международной ассоциации AHM, 78% респондентов считают, что найти корпоративную информацию гораздо сложнее, чем открытую в сети Internet [87]. Объясняется это тем, что на предприятиях имеются порой десятки различных разнородных систем и хранилищ данных (в отличие от Интернета с достаточно однородной Web-средой). Обычно каждое решение имеет свои собственные средства поиска, но они, как правило, функционируют только внутри своей системы. В связи с этим на первое место выходит проблема поиска в корпоративных системах.

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

Обобщенная архитектура корпоративной информационной системы представлена на рис. 1.1.

Корпоративная информационная система, также как и другие информационные системы может основываться на разных типах архитектур:

• файл-серверная;

• клиент-серверная;

• сервис-ориентированная;

• облачная.

Клиенг Клиент

Рис. 1.1. Обобщенная архитектура КИС.

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

1.1.2 Методы информационного поиска. Типы информационного поиска можно разделить на две основные группы: это поиск по сходству, и поиск по ключевым словам (рис. 1.2) [84].

Рис. 1.2 Типы информационного поиска

Релевантный поиск по ключевым словам. В общих чертах задачу релевантного поиска по ключевым словам можно сформулировать в следующем виде: имеется некоторое множество электронных текстовых документов и существует пользователь, который, взаимодействуя с системой формирует поисковые запросы, получая множество удовлетворяющих запросу документов. В этом случае задачей поиска является более полная и точная выборка подмножества документов наиболее релевантных (близких по смыслу) поисковому запросу. Представителями поисковых систем, осуществляющих релевантный поиск, являются системы интернет поиска: Google, Яндекс, AltaVista.

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

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

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

В некоторых системах, для построения семантической сети используются несколько категорий отношения - по типу «вид-род», «общее-частное» и т.д. [18].

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

Модификация булевого поиска. В этом случаи поисковой системой учитываются неточности при задании поисковых запросов или при поиске по сходству электронных документов. С одной стороны поиск по сходству увеличивает объём выборки документов релевантных запросу, однако при этом увеличивается вероятность выборки документов с очень малой степенью релевантности. Меру корреляции между терминами поискового запроса и терминами исходных документов обычно определяют в виде расстояния редактирования [19,20].

1.1.3 Средства повышения производительность, точности и полноты поиска. Повышение производительности поиска связано с такими основными факторами:

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

• Компьютерная мощность - увеличение этого параметра позволяет системе поиска обрабатывать информацию за меньшее время.

• Пропускная способность сети - из-за большой загрузки канала может увеличиться интервал времени от момента запроса пользователя до момента получения им ответа. Чтобы этого не происходило, необходимо своевременно обновлять/изменять архитектуру КИС.

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

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

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

Использование тезауруса в информационно-поисковых системах призвано повысить качество анализа текста и полноту поиска информации. Так, отсутствие полноценного тезауруса русского языка в поисковых машинах не позволяет задействовать все возможности расширения запроса при поиске, уже доступные в ряде англоязычных систем (Excalibur, Oracle interMedia Text) - это расширение слов запроса синонимичными, более общими или более частными, родственными по смыслу понятиями.

1.2 Особенности реализации технологии информационно-поисковой системы

Решающую роль при разработке современных ИПС играют объёмы исходных данных. К системам, работающим с большим объемом информации, таким как Web-поиск, крупные электронные библиотеки

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

В условиях постоянного роста объема информации главная задача поисковых систем - сохранение приемлемых для пользователей скорости и полноты выполнения запросов. Для запросов не очень часто употребляемого слова (менее 5 ООО запросов в месяц) время отклика системы (без учёта времени передачи данных по каналу от поисковой системы к пользовательскому компьютеру) должно исчисляться десятыми долями секунды [27].

На сегодняшний день известны три основных подхода для уменьшения времени отклика:

• оптимизация базовых поисковых алгоритмов и архитектуры поиска;

• регулярное увеличение мощностей вычислительных ресурсов поисковой системы;

• использование архитектурной возможности масштабирования системы (если масштабируемость была заложена при проектировании системы).

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

Увеличение мощностей - это регулярный переход на более мощные процессоры, добавление оперативной памяти, увеличение объёма жёстких

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

Обобщенная архитектура, которая включает основные блоки, присутствующие практически у всех ИПС представлена на рис. 1.3.

1.2.1 Обобщенная технология поиска. Процесс работы поисковой системы включает в себя основные этапы:

• сканирование;

• хранение;

• индексирование;

• поиск;

• ранжирование.

Сеть

Рис. 1.3 Обобщенная технология поисковой системы

Сетевые роботы - это программы, которые, исходя из некоторого начального множества ссылок (URL), рекурсивно сканируют Web-страницы, извлекая из них новые ссылки [12,28]. Как правило, извлеченные ссылки сначала передаются модулю стратегии сканирования, который определяет, какие из них стоит посещать и отдает соответствующие ссылки обратно сетевым роботам. Этот выбор напрямую зависит от направленности поисковой системы: она может быть специализированной (выполняющая поиск только по определенной тематике) или охватывать более широкую область. Также, стратегия сканирования может включать глубину индексирования сайта, т.е. может быть направлена на посещение как можно большего числа сайтов, в то время как другая ПС ориентирована на страницы определенного домена.

Собранные роботами документы складываются в хранилище -специализированную базу данных. Хранилище содержит большое количество объектов данных (Web-страниц). Основные свойства хранилища:

1) масштабируемость;

2) поддержка двух режимов доступа:

• случайного - для того, чтобы быстро найти конкретную страницу по ее идентификатору (например, для создания копии страницы из кэша ПС);

• потокового - для того, чтобы скопировать значительную часть всей коллекции (например, для индексирования или анализа);

3) поддержка обновлений.

Для повышения эффективности поиска используются индексные структуры, за создание которых отвечает модуль индексирования. Кроме текстовых индексов [29], часто строятся и дополнительные индексы, хранящие необходимую информацию для конкретной ПС, которая, как правило, используется для ранжирования результатов поиска. Например, размер Web-страниц, количество используемых графических изображений, рассчитанные метрики.

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

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

1.2.2 Распределенные ПС. Естественной попыткой решить проблему масштабируемости ПС является использование распределенной архитектуры [30, 31]. В рамках такой архитектуры поиск производится по виртуально единому индексу, который физически распределен по ряду серверов. Эффективная система должна выполнять запросы, не производя поиск во всех частях индекса, а стараясь искать только там, где действительно содержится ответ [32]. Возможность оптимального решения зависит от принципов разбиения индекса на части, где храниться информация о документах обновляемых довольно часто, а как следствие, индексы меняются с такой же периодичностью. В распределённой ПС Web пополнение и поддержка разных частей индекса может выполняться разными роботами, и то, насколько они будут эффективны, также зависит от принципов разбиения индекса [12].

Список литературы диссертационного исследования кандидат наук Хорошко, Максим Болеславович, 2014 год

ЛИТЕРАТУРА

1. Pinkerton В. Finding What People Want: Experiences with the WebCrawle I I Proc. of the 2nd World Wide Web conference. 1994.

2. Singhal A., Kaszkiel M. A Case Study in Web Search Using TREC Algorithms // Proc. of the 10th International World Wide Web Conference. Hong Kong, 2001.

3. The Term Vector Database: fast access to indexing terms for Web pages. / R. Stata, K. Bharat, F. Maghoul // Proceedings of WWW9, 2000: сайт-URL: http://www9.org/w9cdrom/159/159.html (дата обращения 25.09.2010).

4. Vakkari P. Cognition and Changes of Search Terms and Tactics During Task Performance: A Longitudinal Study // Proceedings of the RIAO 2000 Conference. Paris, 2000.

5. Dumais S.T. Using Latent Semantic Indexing (LSI) for Information Retrieval, Information Filtering, and Other Things // Talk at Cognitive Technology Workshop. April 4-5, 1997.

6. Gabrielli S., Mizzaro S. Negotiating a Multidimensional Framework for Relevance Space // Proc. of the MIRA'99, 1999.

7. Greisdorf H. Relevance: An Interdisciplinary and Information Science Perspective. Informing Science, N3 (2), 2000.

8. Ярочкин В.И. Информационная безопасность: Учебник. М.: Академический проект; Фонд «Мир», 2003. 640 с.

9. Rijsbergen. С. J. Information Retrieval. University of Glasgow // Dept. of Computer Science, 1979.

10. Адаманский А. Обзор методов и алгоритмов полнотекстового поиска, сайт - URL: www.callisto.nsu.ru/documentation/searchreview.pdf (дата обращения 10.03.2011).

11. Писецкий А.Ф., Пунин Г.В., Лунина Т.Г. Опыт построения и эксплуатации поисковой машины и каталога электронных образовательных ресурсов // Тамбов, б.н., 2011.

12. Некрестьянов И. Тематико-ориентированные методы информационного поиска. СПбГУ // Диссертационная работа, 2000.

13. Лодыженский Г.М. Технология "клиент-сервер" и мониторы транзакций. // Открытые системы, N 3, 1994.

14. Кулёмин М. Облачные вычисления. 2010. Колесов А. Облачные вычисления: что же это такое? сайт - URL: http://www.pcweelc.ruyits/article/detail.php?ID=135408 (дата обращения 25.11.2011).

15. Васильев В.Г. Обработка и классификация документов // Сборник докладок РОМИП, 2009, 141-150 стр.

16. Ермаков А.Е., Плешко В.В. Ассоциативная модель порождения текста в задаче классификации // Информационные технологии, 2000, №12.

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

18. Поспелов А. Д. Ситуационное управление: теория и практика. // М. Наука, 1986. 285 с.

19. Graham A. String Search. // School of Electronic Engineering Science University, 1992.

20. Navarro G. Approximate Text Searching. // Technical Report TR/DCC-98-14, 1998.

21. Шарапов P.B., Шарапова E.B., Саратовцева E.A. Модели информационного поиска // сайт - URL: http://vuz.exponenta.ru/PDF/FOTO/kaz/Articles/sharapovl .pdf (дата обращения 02.15.2009).

22. Когаловский М.Р. Перспективные технологии информационных систем. М.: ДМК Пресс: Компания АйТи, 2003. 288с

23. Чугреев B.JI. Модель структурного представления текстовой информации и метод её тематического анализа на основе частотно-контекстной классификации: дис. канд. техн. наук: 05.13.01 / С.-Петерб. гос. электротехн. ун-т им. В.И. Ульянова (Ленина) «ЛЭТИ». СПб., 2003.

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

25. Андриенко В. Е. Исследование и разработка методов и моделей поиска адекватной информации в полнотекстовых базах данных // Таганрог, Диссертационная работа, 2004.

26. Cisco Visual Networking Index: Forecast and Methodology, 20112016. May 30, 2012, сайт-URL:

http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns70 5/ns827/white_paper_c 11-

481360_ns827_Networking_Solutions_White_Paper.html (дата обращения 20.05.2008).

27. Яндекс. Параллелизм в поисковой архитектуре Яндекс, сайт -URL: http://company.yandex.ru/programs/web_200203.html, html (дата обращения 15.07.2009).

28. Heydon A., Najork М.: A Scalable, Extensible Web Crawler // World Wide Web, 2(4), 1999.

29. Melnik S., Raghavan S., Yang B. Building a distributed full-text index for the web// Proc. of the WWW 10, 2001.

30. Baeza-Yates R. Ribeiro-Neto B. Modern Information Retrieval // ACM Press Series. New York: Addison Wesley, 1999. http://citeseer.ist.psu.edu/

baezayates99modern.html (дата обращения 20.11.2011).

31. Patel A., Petrosjan L., Rosenstiel W. OASIS: Distributed Search System in the Internet // St. Petersburg : St. Petersburg State University Published Press, 1999.

32. Некрестьянов И.С. Маршрутизация запросов в системах распределенного поиска. // Труды второй всероссийской научной конференции 'Электронные библиотеки, 2000.

33. Lawrence S., Giles С. Inquirus, The NECI Meta Search Engine. // Proc. of the WWW7, 1998.

34. Meng W., Yu C., Liu K. Building Efficient and Effective Metasearch Engines. // ACM Computing Surveys, 2002.

35. Zonghuan W., Weiyi M. Towards a highly-scalable and effective metasearch engine. // Proc. of the WWW 10, 2001.

36. Dreilinger D., Howe A. E. Experiences with Selecting Search Engines Using Metasearch. // ACM Transactions on Information Systems, 1997.

37. Meng W., Yu C., Liu K. Naphtali Rishe. Estimating the Usefulness of Search Engines // roc. of the ICDE'99, 1999.

38. Huang L., Hemmje M. ADMIRE: An Adaptive Data Model for Meta Search Engines // Proc. of the WWW9, 2000.

39. Терехов A.A. Разработка методов и инструментальных средств // Диссертация на соискание ученой степени кандидата технических наук, 2010.

40. Седова JI. Т. Расчет эффективности ранжирования информационных порталов методом эталонов от числа учитываемых критериев. // М. : Журнал "Информатизация образования и науки", № 3, 2009.

41. Нестерова А. О. Технологии, модели и алгоритмы поиска в архивах медицинских данных с использованием контекстно-временной онтологии. // Тюмень : Диссертации на соискание ученой степени кандидата наук, 2011.

42. Маннинг, Кристофер Д. Введение в информационный поиск. // М. : Вильяме, 2011.

43. Астрахов, А.В. Технология информационного поиска.// М. 2011.

44. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. // Технологии анализа данных. СПБ. БХВ-Петербург, 2007.

45. Агеев М., Кураленок И., Некрестьянов И. Официальные метрики РОМИП 2010. 2010.

47. Гулин А., Карпович П., Расковалов Д. Яндекс на РОМИП'2009. Оптимизация алгоритмов ранжирования методами машинного обучения. // Российский семинар по Оценке Методов Информационного Поиска. Труды РОМИП, 2009.

48. Patrick P., Vishnu V., A Joint Information Model for n-best Ranking. 1998. сайт - URL: http://aclweb.Org/anthology-new/C/C08/C08-1086.pdf (дата обращения 10.11.2011).

49. Ashwin R. Interest-based information filtering and extraction in natural language // Bellcore Workshop on High-Performance Information Filtering, 1991.

50. Indexing by Latent Semantic Analysis / S. Deerwester [and others] // Journal of the American Society for Information Science. 1990. № 41(6),

51. Luhn H.P. A statistical approach to mechanised encoding and searching of library information. // IBM Journal of Research and Development, 1957.

52. Justin Z. Alistair M. Inverted Files Versus Signature Files for Text Indexing. // ACM Transactions on Database Systems, 1998.

53. Udi M., Gene M. Suffix arrays: A new method for on-line string searches. // University of Arizona, 1991.

54. Burrows M., Wheeler D.J. Block-sorting Lossless Data Compression Algorithm. 1994.

55. Larsson, JesperN. Notes On Suffix Sorting. 1998.

56. Bentley S. Fast Algorithms for Sorting and Searching Strings. // SODA, 1997.

57. Ulckonen E. On-line construction of suffix trees // Algorithmica, 1995.

58. Berman A. P. A New Data Structure For Fast Approximate Matching. // University of Washington, Dept. of Computer Science, 1994.

59. Wu S., Manber U.. GLIMPSE: A Tool to Search Through Entire File. //Winter USENIX Technical Conference, 1994.

60. Сизиков E.B. Структура поискового индекса, основанного на нечетком сравнении терминов // Перспективные информационные технологии и интеллектуальные системы, № 3 (19), 2004.

61. Berman, Andrew P. New Data Structure For Fast Approximate. 1994.

62. Block Addressing Indices for Approximate Text Retrieval. // Journal of the American Society on Information, 2000.

63. Ripley D. B. Pattern Recognition and Neural Networks. // Cambridge University Press, 1996.

64. Croft, Bruce W., Harper J. Using problemastic models of document retrieval witout relevance information . 1979.

65. Greiff, Warren R. A theory of tems weighting based on exploratory data analysis. // ACM Press, 1998.

66. Sparck Jones, Karen, S. Walker. A probalistic model of information retrieval. // IP&M, 2000.

67. Harman, Donna. Relevance feedback revisited. // ACM Press, 1992.

68. Buckley, Chris. The effect of adding relevance information in a relevance feedback environment 11 ACM Press, 1994.

69. Spink, Amanda, Bernard J. Janes. Use of query reformulation and relevance feedback by Excite users. 2000.

70. Ponte, Jay M., Bruce W. A language modeling approach to information retrieval. // ACM Press, 1998.

71 .Lafferty Z. Model-based feedback in the language modeling. // ACM Press, 2001.

72. Лавренко В. Языковые модели релевантности. 2001,

73. Thomas, Cover and. Elements of information Theory. 1991.

74. Kraaij, Spitters. Language models for topic trancking. 2003.

75. Berger, Laffertly. Informaton retrieval as statistical translation. 1999.

76. Хорошко М.Б. Модификация алгоритма булевого поиска / М. Б. Хорошко // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. - 2011 № 3 - С. 14-18

77. Воробьев С.П., Хорошко, М.Б. Модификация модели векторного пространства для ранжирования документов/ Воробьев С.П., Хорошко, М.Б// Электронный журнал «Инженерный вестник Дона», 2012 г. №3, http://www.ivdon.ru/magazine/archive/n3y2012/976

78. Воробьев С.П., Хорошко, М.Б. Модификация схемы ВМ25 с помощью генетического алгоритма / Воробьев С.П., Хорошко, М.Б// Электронный журнал «Инженерный вестник Дона», 2012 г. №4, http://www.ivdon.ru/magazine/archive/n4t 1 у2012/1177

79. Хорошко, М.Б. Обзор математических моделей информационного поиска / М. Б. Хорошко // Компьютерные технологии в науке, производстве, социальных и экономических процессах: материалы VIII междунар. науч - практ. конф., г. Новочеркасск, 16 ноября 2007г. - С. 83-89

80. Хорошко, М.Б. Оценка эффективности поисковых систем / М. Б. Хорошко // VIII Межрегион, науч. - практ. конф. студентов и аспирантов: материалы конф., г. Новокузнецк, 11 апреля 2008 г. - Т. 1 С. 11-12

81. Хорошко, М.Б. Система поиска информации в Интернете / М. Б. Хорошко // Студенческая научная весна - 2008: материалы Межрегион, науч.-техн. конф. студентов, аспирантов и молодых учёных Юж. федер. округа, г. Новочеркасск, 2008 г. - С. 97-99

82. Хорошко, М.Б. Оценка качества поиска / М. Б. Хорошко // Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем: материалы VII Междунар. науч.-практ. конф., г. Новочеркасск, 2009 г. - С. 242-250

83. Хорошко, М.Б. Типы, модели и методы информационного поиска / М. Б. Хорошко // Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем: материалы VII Междунар. науч.-практ. конф., г. Новочеркасск, 2009 г. - С. 251-272

84. Хорошко, М.Б. Алгоритмы, используемые в поисковых системах / М. Б. Хорошко // Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем: материалы VII Междунар. науч.-практ. конф., г. Новочеркасск, 2009 г. - С. 272-284

85. Сычев A.B. Информационно-поисковые системы, 2006 г.

86. Генетические алгоритмы: Учебное пособие / Под ред. В. М. Курейчика. - 2-е изд., доп., Физматлит, 2010г.

87. Как организовать поиск в корпоративных системах, Андрей Колесов PC Week/RE №2 (752) 8 февраля 2011.

88. Козлович А.А., Поиск релеватной информации в среде интернет с использованием многоагентных технологий, Электртонный Журнал, «Перспективные информационные технологии и интеллектуальные системы», №4/2002, Таганрог.

89. Full Text Search Software , сайт - URL: http://fiill-text-search.fmdthebest.com/compare/5-9/, 2012 г. (дата обращения 10.06.2010).

90. Sphinx Search, 2011, сайт - URL: http://sphinxsearch.c0m/inf0/articles/#en (дата обращения 10.06.2010).

91. Xapian - the open source search engine, сайт - URL: http://xapian.org/docs/ (дата обращения 10.06.2010).

92. Buckley С., Voorhees E. Evaluating evaluation measure stability. // In Proc. of the SIGIR'OO, pp. 33-40, 2000.

93. Voorhes E.. The TREC-8 Question Answering Track Report // In Proc. of the TREC-8, 1999.

94. Jarvelin K., Kekalainen, J. Cumulated gain-based evaluation of IR techniques. // ACM Trans. Inf. Syst. 20,4 (Oct. 2002), 422-446.

95. Tie-Yan Liu, Learning to Rank for Information Retrieval. Found. Trends Inf. Retr. 3, 3 (Mar. 2009), 225-331.

96. Chapelle O., Metlzer D., Zhang Y. Expected reciprocal rank for graded relevance. // In Proceeding of the 18th ACM Conference on information and Knowledge Management (Hong Kong, China, November 02 - 06, 2009). CIKM '09. ACM, New York, NY, 621-630.

97. Hearst, Marti A.,and Christian Plaunt. 2006. Clustering versus faceted categories for information exploration // С ACM 49(4):59-61.

98. Joachins, Thosten. 2002. Optimizing search engines using clickthrouh data. // In Proc. KDD.

99. Браславский П.И., Губин М.В., Добров Б.В., Инициативный проект Российского семинара по оценке методов информационного (РОМИП) // доклад на международной конференции «Диалог», 2003г.

100. Себрант А., Третьяков А. "Поисковая реклама как специфический транспорт маркетинговых коммуникаций", 2003г.

Фрагмент исходного кода программного комплекса IRSI

//-................Файл Free.cs

using System;

using System.Collections.Generic; using System.Linq; using System.Text;

namespace Проект {

static class Free {

/***** Количество слов в тесте *****/ public static int Size(string text, string query) {

int count = 0; string[] Words;

Words = text.SplitC 7,V, V,'?','!', '*',')','(');

/***** Удаляем пустые элементы *****/ string!] items = {""};

Words = (from x in Words

where !items.Contains(x) select x).ToArray();

for (int i = 0; i < Words.Length; i++)

if ('Words [i].ToLower() = query. ToLower()) count++; return count;

}

/***** Количество слов в тесте *****/

public static int Length(string text) {

stringf] Words;

Words = text.SplitC V, V, V,'?','!', '*',')', 'С,'-');

/***** Удаляем пустые элементы *****/ string[] items = { "" }; Words = (from x in Words

where ! items. Contains(x) select x).ToArray();

return Words.Length;

}

/***** Разделить запросы на слова *****/

public static string[] Query_word(string[] text)

{

/***** Удаляем пустые элементы *****/ stringf] items ={""};

text = (from x in text

where litems.Contains(x) select x).ToArray(); return text;

j

}

//-.....—......—Файл Func.cs

using System;

using System.Collections.Generic; using System.Linq; using System.Text;

namespace Проект {

class func {

public string i 1; public string i2;

// индекс точки

int otdelenie(string str) {

int index = 0;

for (int i = 0; i < str. Length; i++) {

if(str[i]=V)

{

index = i; break;

}

}

return index;

}

// отделение дробной части от целой

public void tohka(string str)

{

string si = "0"; string s2 = "0";

// получение индекса

int index = otdelenie(str);

if (index !=0) {

sl = str.Remove(index); s2 = str.Remove(0, index + 1);

}

11 = Convert.ToString(int.Parse(sl), 2); if (s2.Contains("E")) s2 = "0";

12 = Convert.ToString(int.Parse(s2), 2);

// сравнение

public void srav(string sl, string s2)

{

int 11 = sl.Length; int 12 = s2. Length;

string s_0 = "";

for (int i = 0; i < Math.Abs(ll - 12); i++) s_0 = s_0.Insert(0, "0");

if (11 >12) {

// добавляем 12 s2 = s2.Insert(0, s_0);

if (11 <12) {

// добавляем 12 sl = sl.lnsert(0, s_0);

11 = sl;

12 = s2;

}

// скрещивание двух чисел

public void cros(string sl, string s2, int flag) {

string tempi ="";

string temp2 = ""; /*

* flag = 1 расческа

* flag = 2 пополам */

for (int i = 0; i < si.Length; i++) {

switch (flag) {

case 1:

// метод расчески

if (i % 2 = 0) {

tempi = tempi.Insert(templ.Length, sl[i].ToString()); temp2 = temp2.Insert(temp2.Length, s2[i].ToString());

}

else {

tempi = tempi.Insert(temp 1.Length, s2[i].ToString()); temp2 = temp2.Insert(temp2.Length, sl[i].ToStringQ);

}

break; case 2:

// метод пополам

if (i > i / 2) {

tempi = tempi.Insert(tempI.Length, sl[i].ToString()); temp2 = temp2.Insert(temp2.Length, s2[i].ToString());

}

else {

tempi = templ.Insert(templ.Length, s2[i].ToString()); temp2 = temp2.Insert(temp2.Length, sl[i].ToString());

}

break;

}

}

11 = tempi;

12 = temp2;

}

}

}

//-----------------Файл Gen-Algor.cs

using System;

using System.Collections.Generiс; using System.Linq; using System.Text;

namespace Проект {

struct Metrik

{

js|c j(e >fc j|e s|e ^Jg^pj^j^jj ^ ^ ^ ^ J

public double r; // полнота public double p; 11 точность public double a; // аккуратность public double eror; // ошибка public double f; // f мера

}

struct Parametr {

/***** Параметры *****/

public double query_wtd; ii вес слова запроса

public double docjwtd; 11 вес слова в документе

}

struct Р_М

{

public Parametr Param; public Metrik Metrik; public double estimate;

class Gen_Algor {

/***** Параметры *****/

int count_PM = 10;// количество PM

int ver = 40; // вероятность мутации

public P_M[] PM; int count = 0;

/****** Скрешивание *****/ float skr_l = 0, skr_2 = 0;

public Gen_Algor()

{

this.PM = new P_M[count_PM];

// случайные числа Random rnd = new Random();

/***** Задаем начальные параметры *****/

this.РМ[0].Param.doc_wtd = 0; this.PM[0].Param.query_wtd = 0;

for (int i = 1; i < count J1 M; i++)

this.PM[i].Param.doc_wtd = rnd.NextDouble(); this.PM[i].Param.query_wtd = rnd.NextDouble();

}

}

/****** Добавление набора ******/

public void Add_PM(double rel_ps, double r, double p, double a, double error,

double f, int i) {

/***** Метрики *****/ this.PM[i].Metrik.a = a; this.PM[i].Metrik.r = r; this.PM[i].Metrik.p = p; this.PM[i].Metrik.eror = error; this.PM[i].Metrik.f = f;

j sjs sfc s|i sjc s|< J у r^ ^ sjt j

this.PM[i].estimate = rel_ps;// Estimate(i);

}

public void Gen() { /***** Сортировка *****/ Sort_PM();

/***** Мутация и скрещивание *****/ Mut_Sel();

/***** Операции мут и скрещив *****/

void Mut_Sel() {

int sk = (int)Math.Round((double)PM.Length / 3, 0);

/***** Скрещивание *****/

for (int j = 0; j < sk; j = j + 2)

{

// расческа

Select((float)PM[j].Param.doc_wtd, (float)PM(j + l].Param.doc_wtd, 1);

ifO'!=0)

PM[j].Param.doc_wtd = skr_l; PM[j + l].Param.doc_wtd = skr_2;

Select((float)PM[j].Param.query_wtd, (float)PM[j + l].Param.query_wtd,

if (j != 0)

PM[j].Param.query_wtd = skr_l;

PM[j + l].Param.query_wtd = skr_2; // пополам параметр 2

>

j^ «и ^{угйция ^ !

for (int j = sk; j < PM.Length; j++) {

Mutation((float)PM[j].Param.doc_wtd, ver); PM[j].Param.doc_wtd = skr_l;

Mutation((float)PM[j].Param.query_wtd, ver); PM[j],Param.query_wtd = skr_l;

}

}

/***** Сортировка результатов *****/ void Sort_PM() {

P_M tpm = new P_M();

for(int i=0; i<PM.Length; i++) for(int j=i+l; j<PM.Length; j++)

if (this.PM[i],estimate < this.PM[j].estimate) {

tpm = PM[i];

PM[i] = PM[j];

PM(j] = tpm;

}

}

/***** Общая оценка *****/ double Estimate(int i) { double estimate = 0; estimate += this.PM[i].Metrik.f; estimate += this.PM[i].Metrik.a; estimate -= this.PM[i].Metrik.eror;

return estimate; }

/***** Скрещивание *****/

void Select(float fl, float f2, int flag) {

func f = new func(); // делая двоичное // первое число string temp = f 1 .ToString(); f.tohka(temp);

string fljl = f.il; string fl_i2 = f.i2;

// второе число temp = f2.ToString(); f.tohka(temp);

string E2J1 = f.il; string f2_i2 = f.i2;

// сравнение целых чисел f.srav(fl_il, f2Jl); fljl = f.il; f2_il = f.i2;

// сравнение дробных чисел f.srav(fl_i2, f2_i2); fl_i2 = f.il; f2_i2 = f.i2;

// скрещивание /*

* flag = 1 расческа

* flag = 2 пополам */

f.cros(fl_il, f2_il, flag); fl_il = f.il; £2J1 = f.i2;

f.cros(fl_i2, f2_i2, flag); fl_i2 = f.il; f2_i2 = f.i2;

// перевод в десятичное

fljl = Convert.ToInt32(f 1J 1, 2).ToString();

fl_i2 = Convert.ToInt32(fl_i2, 2).ToString();

f2_il = Convert.ToInt32(f2_i 1, 2).ToString(); f2_i2 = Convert.ToInt32(f2_i2, 2).ToString();

// соединяем целую и дробную часть

string fl_str = ""; string f2_str = "";

fl_str = fl_str.lnsert(0, fl_il);

fl_str = fl_str.Insert(fl_str.Length,",");

fl_str = fl_str.lnsert(fl_str.Length, fl_i2);

f2_str = f2_str.Insert(0, f2_il);

f2_str = f2_str.Insert(f2_str.Length, ",");

f2_str = f2_str.Insert(f2_str.Length, f2_i2);

// перевод во float skr_l = float.Parse(fl_str); skr_2 = float.Parse(f2_str);

}

j * * * * * МуГсЩИЯ

void Mutation(float fl, int ver) {

Random rnd = new Random();

func f = new func();

// перевод числа

string temp = fl.ToString();

f.tohka(temp);

string fl_il = f.il; string fl_i2 = f.i2; string tempi = "";

// мутация

for (int i = 0; i < flil.Length; i++) {

if (rnd.Next(lOO) < ver)

tempi = templ.Insert(templ.Length, rnd.Next(l).ToStringQ); else

tempi = tempi.Insert(templ.Length, fl_il[i].ToString());

}

fl_il = tempi; tempi =""; // дробной части

for (int i = 0; i < fl_i2.Length; i++) {

if (rnd.Next(lOO) < ver)

tempi = tempi.Insert(temp 1.Length, md.Next(l).ToString()); else

tempi = tempi.Insert(temp 1.Length, fl_i2[i].ToString());

fl_i2 = tempi; // делаем дес

fl_il = Convert.ToInt32(fl_il, 2).ToString(); fl_i2 = Convert.ToInt32(fl_i2, 2).ToString();

11 объединяем string fl_str = "";

flstr - fl_str.lnsert(0, flil);

fl_str = fl_str.Insert(fl_str.Length,",");

fl _str = f 1 _str.Insert(f 1 _str.Length, fl_i2);

skrl = float.Parse(fl_str);

}

}

}

//-—-------------Файл Mod-Lang.cs

using System;

using System.CoIlections.Generic; using System.Linq; using System.Text;

namespace Проект {

class Mod_Language {

public struct Doc_prob { public int id_doc; public string text;

public double retrieval; }

/****** Параметры настройки ******/ double kl ; double dop_k = 1;

public Doc_prob[] DP; // Документы double[] PMC; int count = -1; string[] query; public int id_q;

/***** Инициализация *****/

public Mod_Language() {

DP = new Doc_prob[l];

kl = (double) 0.8; }

/***** Добавляем документы *****/

public void Add_Doc(int id_doc, string text, stringf] query, int id_slovo, double

par_kl)

{

this.query = query; id_q = id_slovo;

count++;

Array.Resize(ref DP, count+1);

/***** Заносим *****/ DP[count].id_doc = id_doc; DP[count].text = text;

if(par_kl != 0) kl = par_kl;

}

/***** Алгоритм *****/

public void Algoritm()

{

PMC = new double[this.query.Length]; int count=0; int L=0;

/***** Установка начальных значений *****/ for (int j = 0; j < this.query.Length; j++)

РМС0] = 1; /****** *****/

for (int i = 0; i < this.DP.Length; i++) {

L = Free.Length(this.DP[i].text);

for (int j = 0; j < this.query.Length; j++) {

count = Free.Size(this.DP[i].text, query[j]);

if (count > 0) {

PMC[j] *= (double)count / L; PMC[j] *= 40;

}

}

}

/***** Вычисляем релеватность *****/

Algoritm_calculate(); /***** Сортировка *****/ Sort();

}

/***** Алгоритм вычисления*****/

void Algoritm_caIculate()

{

double rel = 0; int l_d = 0; int tf = 0;

double MC=1;

for (int j = 0; j < this.query.Length; j++) if(PMC[j]>0) MC*=PMC[j];

for (int i = 0; i < this.DP.Length; i++) {

tf = 0; rel = 1;

/***** Вычисляем длину документа *****/ Id = Free.Length( this.DP[i].text);

for (int j = 0; j < this.query.Length; j++) {

/***** Вычисляем частоту термина в документе *****/ tf = Free.Size(this.DP[i].text, this.query[j]);

/***** Вычисляем релевантность *****/

if (tf > 0)

{

rel *= Retrieval(tf, l_d); rel *= 40;

}

}

if (rel = 1) rel = 0; else

rel = kl * rel + (1 - kl) * (MC+1);

this.DP[i].retrieval = rel;

}

}