Теоретико-множественная модель представления объектов

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

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

Модели  с учетом связей между документами

Используются  следующие гипотезы:

     Если  элемент А ссылается на элемент Б, то автор элемента А рекомендует документ Б. Таким образом наличие и количество ссылок на документ повышает его значимость.

     Если  документы А и Б связаны гиперссылками, то это повышает вероятность того, что они связаны тематически, в сравнении с тем случаем, когда ссылок между ними нет.

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

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

     Методы  абстрагирования 

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

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

Существенным  шагом в развитии теории и практики информационного поиска явилась  линейная алгебраическая модель, предложенная профессором В.Н. Решетниковым в 1979 г. и послужившая удобным инструментом для исследования различных задач анализа и обработки информации [1]. В этой модели поисковые образы документов и запросов представляются элементами конечномерного линейного пространства, а организация поиска данных сводится к поиску решения системы линейных алгебраических уравнений в этом пространстве. Рассматриваемый подход, как и большинство моделей поиска, отражает в большей степени попытку связать между собой представленные в хранилищах данных документы и информационные запросы путем введения мер близости между ними. Характер этой связи описывается таким понятием, как релевантность, которое в алгебраической модели интерпретируется множеством решений поискового уравнения на конечном множестве конечномерного векторного пространства. Поисковое уравнение при этом определяется запросом.

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

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

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

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

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

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

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

Задача информационного поиска в АИПС

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

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

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

Задачи обработки  изображений

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

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

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

Список литературы

1. Решетников В.Н. Алгебраическая теория информационного поиска. // Программирование. – 1979. – № 3. – C. 78–83.

2. Решетников В.Н. Информационный поиск и Z-структура. // Математические вопросы задач оптимизации и управления. – Изд-во МГУ, 1981.

3. Решетников В.Н., Сотников А.Н. Алгоритмы отсечения для построения псевдорелевантных множеств. // Программное обеспечение вычислительных комплексов. – Изд-во МГУ. – 1985. – С. 60–64.

4. Прохоров А.Ю., Сотников А.Н. Поиск во временном ряде фрагментов, «похожих» на заданный шаблон. // Программные продукты и системы. – № 3. – 2003.

5. Bereznev V., Sotnikov A., Cherednitchenko I. The system for hand-written and textual symbols identification. // Pattern recognition and Image analysis, № 4, 1995.

6. Сотников А.Н., Чередниченко И.Н. Построение автоадаптивного фонта в документах электронных библиотек. // Программные продукты и системы. – 2008. – № 2. – С. 16–19.