Rus  Eng 
   
Программы О компании Поддержка  
   
 
  Главная страница / О компании / Наши публикации
Университетам и школам
 
Библиотекам
 
Наши партнeры
 
Наши публикации
Автоматизация процесса создания цифровых архивов научно-технической документации
Роль новых технологий поиска информации в образовании
Компьютерная программа "Антиплагиатор"
Проект разработки метода корреляционной индексации текстовой и графической информации.
Технология хранения и обработки электронных документов с элементами интеллектуального поиска
Полнотекстовая технология поиска документов “Незабудка”
Поиск и анализ графической информации. Идентификации личности по изображению лица
Создание электронных образовательных ресурсов в условиях традиционной отраслевой библиотеки
Электронный тренажёр для обучения физике
Программный комплекс по созданию архивов научно-технической документации с возможностью размещения на съемных носителях и в Интернете
Поиск и анализ похожих документов в информационно-поисковой системе, базирующийся на методе корреляционной полнотекстовой индексации
Использование программы ССТ PUBLISHER для создания электронного архива Соровского образовательного журнала
Роль новых технологий поиска информации в образовании
Динамический метод фильтрации интернет сайтов с агрессивным содержанием.
Системы обнаружения, сопровождения и кластеризации объектов на основе нейроноподобного кодирования
Технология хранения и обработки электронных документов с элементами интеллектуального поиска:

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

 

Ю.Д. Калафати, К.В. Моисеев С.О. Старков, С.В. Шушкова

 

                Введение. Использование динамических систем  для записи и обработки информации впервые было предложено в [1]. Основная идея  заключалась в том, что заданному набору  информационных блоков  ставится в соответствие набор предельных циклов дискретной динамической системы:  одномерного  [2-4]  или многомерного [5] точечных отображений. Под информационным блоком подразумевается конечная последовательность символов некоторого алфавита и каждому символу ставится в соответствие значение переменной динамической системы. Предлагаемый подход был реализован для записи текстовой и графической информации с помощью кусочно-линейных отображений и продемонстрирована принципиальная возможность ассоциативного поиска информации по ее  фрагментам. Свое развитие исследования получили в [6], где для оптимизации  поиска вместо значений динамической переменной было предложено использовать целочисленный индекс. Несмотря на то, что принципы представления информации с помощью целочисленных индексных циклов достаточно хорошо известны и успешно применяются  для хранения информации в разнообразных БД, построение электронных архивов, обладающих возможностями интеллектуального поиска, в том числе ассоциативного поиска, точного поиска, поиска похожего для запросов на естественном языке представляют самостоятельный интерес и требуют развития.

                 Рассмотрим некоторые ключевые моменты развиваемой технологии.

Алгоритм индексации. Предположим, на индексацию передана первая страница, представленная следующей строкой текста:

a b с a с a d a b a с a b с                                          (1)

В качестве первого шага к исходному алфавиту добавляется символ – признак начала страницы. Этот символ будет иметь номер 256. Преобразуем исходный текст в циклическую последовательность символов и добавляем символ 256 в конец последовательности символов. Для того, чтобы избавиться от избыточной информации в исходной последовательности  вводится понятие расширенного алфавита. Каждый элемент расширенного алфавита создается на основе двух уже существующих символов. Например, если необходимо избавиться от повторяющейся последовательности символов a b c то вводится новый символ 257 = ‘a’ + ‘b’ и 258 = 257 + ‘c’ и с его помощью осуществляется замена в исходном тексте последовательность a b c символом 258. Проиндексируем текст (1) на основе изложенной выше идеи. Пытаемся искать в исходном тексте повторяющиеся пары символов. Берем пару символов из приведенного выше примера – пару a b.Так как данная пара символов повторяется в тексте больше одного раза, добавляем эту пару в расширенный алфавит:

Символ 257 = ‘a’ + ‘b’

Преобразуем исходную последовательность символов, заменив пару символов a b новым символом с индексом 257. Получаем:

257 с a с a d 257 a с 257 с 256                                           (2)

                Далее пытаемся искать повторение других пар и при нахождении повторения создаем новые символы. На основе этой последовательности, создаем массив описания страницы, каждый элемент которого состоит из трех символов: an, an+1, an+2. И упорядочиваем полученный массив по паре (an, an+1). Необходимым условием для работоспособности системы является уникальность пары (an, an+1)в созданном массиве. При добавлении следующей страницы необходимо выполнить следующие действия:

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

Расширенный алфавит представлен в виде двумерного массива целых чисел. Индекс массива – номер символа расширенного алфавита. Первый элемент массива имеет индекс 257. Каждая пара чисел, хранящаяся в элементе массива – это составные части соответствующего символа алфавита. Упорядоченный массив описания страниц – массив, состоящий из элементов (an, an+1, an+2). Этот массив упорядочен по паре (an, an+1) и эта пара является уникальной в рамках всего проиндексированного множества текстов. Точки входа на проиндексированные страницы. Любая пара символов из представления каждой страницы сохраняются в виде двумерного массива целых чисел. Индекс массива – номер проиндексированной страницы, а содержимое элемента массива – необходимая и достаточная информация для запуска процедуры извлечения текста соответствующей страницы

Извлечение текста со страницы.  Для извлечения текста страницы из построенного индекса достаточно иметь информацию о любой паре символов расширенного алфавита(an0, an0+1), содержащейся на странице. Принимаем во внимание то, что массив описания страниц упорядочен по первой паре (an, an+1) и выполнено необходимое условие – уникальность этой пары по всему массиву проиндексированной информации.  При помощи процедуры бинарного поиска ищем пару (an0, an0+1) в массиве описания страниц. Из найденного элемента массива извлекаем элемент an0+2. Далее ищем в массиве описания страниц пару (an0+1, an0+2). Из найденного элемента массива извлекаем элемент an0+3. И т.д. Повторяем эту операцию до тех пор, пока после поиска пары (ai, ai+1)и извлечения элемента ai+2 не будет верным равенство: ai+1 = an0 и ai+2 = an0+1

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

Описание базового алгоритма поиска. Для демонстрации принципиальной возможности поиска информации при данном способе индексации информации был предложен следующий механизм. На вход процедуре поиска в качестве поискового запроса подеется предложение или даже абзац текста. Поисковый запрос кодируется при помощи имеющегося расширенного алфавита. Предположим, что поисковый запрос преобразовался в последовательность a1, a2, a3, a4, a5, a6, a7, a8 элементов расширенного алфавита. Берем первую пару поискового запроса (a1, a2) и ищем ее в упорядоченном массиве описаний страниц. Если такая пара символов не найдена, то переходим к паре символов (a2, a3) и т.д. В случае успешного поиска, например, пары (a2, a3) получаем (a2, a3, ax) элемент массива описания страниц. Сравниваем элемент a4 с элементом ax. В случае если эти элементы совпадают, находим (a3, a4, ay) элемент массива описания страниц. Если элементы a5 и ay совпадают, считаем поисковую операцию успешной.

На основе предложенного алгоритма индексации текстовой информации реализовано два варианта поиска:

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

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

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

 

Рис. 1. Схема процедуры точного поиска.

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

Для каждой проиндексированной страницы на основе полученного списка символов считаем сумму:

где lengthk - это длина в ASCII символах k-ого элемента списка символов, 

countk – количество k-ого элемента списка на странице 

i, а α и β – внешние параметры. 

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

                Программная реализация и применение. В настоящее время описанный выше алгоритм обработки текста и алгоритмы полнотекстового поиска реализованы и используются в программных продуктах CCT Archive и CCT Publisher компании Controlling Chaos Technologies. Программные продукты предназначены для создания электронных архивов неструктурированных документов с возможностью полнотекстового поиска информации, а также для создания и подготовки к изданию на CD и DVD электронных книг, энциклопедий, архивов журналов. Примерами успешного использования программных продуктов стали электронные архивы журналов «Химия и Жизнь», «Квант», «Знание-Сила».

                На рис. 2  приведен пример результатов работы поисковой системы на примере электронного архива журнала «Квант». Вверху слева представлен запрос на естественном языке, по которому осуществлялся поиск , ниже изображен ранжированный список найденных документов. Слева – страница документа с выделенными входами.

Рис. 2. Пример результатов работы поисковой системы на примере электронного архива

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

Максимальный размер индексируемого текста: ~100 мБ

Скорость индексации тексов: ~ 1 мБ в мин. (средняя скорость при индексации 100 мБ)

Время открытия индекса: не более 1 мин.

Время поиска: порядка 1 сек.

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


Литература

  1. Dmutriev A.S., Panas A.I., Starkov S.O. Storing  and recognition information based on stable cycles of 1-D map// Phys. Lett.A.-1991-. V.155, -№8-pp.494-499.
  2. Дмитриев А.С. Запись и распознавание информации в одномерных динамических системах// РЭ. -1991-Т.36- №1-сс.101-108.
  3. Andreev Y.V., Dmitriev A.S., Chua L.O., Wu C.W. Associative and random access memory using ome-dimensional maps// IJBC-1992-V.3-№3-pp.483-504.
  4. Andreyev Yu.V., Dmitriev A.S., and Starkov S.O., Information Processing in 1-D Systems with Chaos, IEEE Transactions on Circuits and Systems, 1997, vol. 44, No. 1, pp. 21-28.
  5. Андреев Ю.В., Бельский Ю.Л., Дмитриев А.С. Запись и восстановление информации с использованием устойчивых циклов двумерных многомерных отображений// РЭ-1994-Т.39-№1-сс.114-123.
  6. Andreyev Yu.V., Dmitriev A.S., and Ovsyannikov A.V. Information searching system "Forget-Me-Not" based on complex dynamics of nonlinear systems, Proc. 7th Int. Workshop NDES-99, 1999. Ronne, Denmark. pp.273-276.

  Copyright Controlling Chaos Technologies 2001-2010 Разработка и поддержка - Auroom Group