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

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

Белоконова Светлана Сергеевна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ СХЕМ ДЕТЕРМИНИРОВАННОГО ПОИСКА НА ОСНОВЕ СОРТИРОВКИ С ПРИЛОЖЕНИЕМ К ИДЕНТИФИКАЦИИ ОЦИФРОВАННЫХ ОБЪЕКТОВ РАЗЛИЧНЫХ ТИПОВ

Специальность

05 13 17 - Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Таганрог 2007

003069252

Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт»

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

профессор Ромм Яков Евсеевич

Официальные оппоненты доктор технических наук,

профессор Финаев Валерий Иванович

кандидат технических наук,

старший научный сотрудник Сапрыкин Владимир Абрамович

Ведущая организация Ростовский государственный университет путей сообщения (РГУПС)

Защита состоится «¿4» ¡М й <Я 2007 г в //.¿¿часов на заседании диссертационного сове-га Д 212 208 21 при федеральном государственном образовательном учреждении высшего профессионального образования «Южный федеральный университет» по адресу 347928, г. Таганрог, пер Некрасовский, 44, ауд Д-406

С диссертацией можно ознакомиться в библиотеке Технологического института федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г Таганроге

Автореферат разослан «20» СШМШУ 2007 г

Ученый секретарь

дассертационного совета Д 212 208 21 доктор технических наук, профессор

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

Проблема поиска, сбора и обработки информации принадлежит к числу основных задач информатики Ее актуальность возрастает с ростом объема информации в электронном виде, с ростом ресурсов, доступных в сети Internet Особую актуальность приобрели вопросы, связанные с поиском и распознаванием оцифрованной информации различного формата и типа данных, включая текстовую, графическую, аудио- и видеоинформацию Существующие методы и подходы не вполне обеспечивают точность, релевантность результатов поиска запросу, не совмещают в требуемой мере поиск с распознаванием В частности, это относится к поиску данных различных несовместимых типов, к обработке плохо структурированной информации Поэтому актуальна разработка новых методов, позволяющих повысить эффективность, расширить область применения схем поиска, включая полнотекстовый поиск при организации электронных библиотек и каталогов, где проблема определяется растущим количеством пользователей, не обладающих профессиональными навыками при поиске информации на языке запросов Наиболее масштабные исследования в области информационного поиска относятся к 90-м годам прошлого века, они интенсивно продолжаются в настоящее время При этом характерно, что большинство предлагаемых методов эффективны на больших объемах данных, которые не могут быть подвергнуты анализу по выделению структуры Одним из направлений исследования является применение известных методов распознавания к поиску оцифрованной информации различного типа Методы адаптивного распознавания образов и семантические сети, опирающиеся на теорию нейронных сетей, осуществляют поиск текстовой, графической, аудио и видео, а также числовой информации В диссертационной работе наряду с данными вопросами рассматривается обратная задача - применение методов поиска к распознаванию При этом предполагается не только расширение области поиска до объектов различных типов, но включается поиск и распознавание отдельных фрагментов объектов и их свойств, а также детерминированный поиск неисправностей Актуальность последней задачи обусловлена тенденцией увеличения объема передаваемой информации, повышением функциональной и аппаратурной насыщенности сетей передачи данных, ростом требований на скорость и надежность передачи и, как следствие, на техническое, в частности, тестовое диагностирование сетей В данном контексте актуальна задача разработки схем поиска и распознавания на единой основе

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

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

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

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

3 Сконструировать схему, позволяющую выполнить поиск по математическим условиям чисел и векторов как минимумов нормы разности менаду искомым элементом многомерного пространства и эталонным элементом из этого пространства

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

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

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

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

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

9 На той же основе синтезировать распараллеливаемый алгоритм идентификации неисправностей цифровых устройств

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

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

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

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

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

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

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

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

4 Предложена схема детерминированного поиска одновременно по нескольким маскам с учетом их взаимного расположения и изменяемости словоформ Схема отличается построением поиска по экстремальным особенностям сопоставленных тексту числовых последовательностей, а также качеством идентификации составных объектов в произвольном взаимном расположении элементов

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

6 Сконструирована мультипликативная схема поиска по множеству масок с заданным взаимным расположением, для которой доказаны теоремы единственности и взаимно однозначного соответствия исследуемому тексту результатов поиска Единственность идентификации по группам взаимно упорядоченных масок отличает схему от известных методов поиска

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

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

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

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

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

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

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

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

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

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

Связь с плановыми исследованиями, проводимыми по месту выполнения диссертационной работы. Диссертационная работа выполнялась в рамках госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ го с регистрации 01 2 00106436, код ГРНТИ 28 23 15), проводимой на кафедре информатики ГОУВПО «ТГПИ» в рамках приоритетного направления развития науки и техники в РФ «Информационные и телекоммуникационные системы» в соответствии с перечнем критических технологий РФ «Технологии обработки, хранения, передачи и защиты информации» по направлению фундамен-

тальных исследований «Информатика Искусственный интеллект, системы распознавания образов, принятие решений при многих критериях»

Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов Разработанные схемы поиска могут быть составляющими редакторов языков программирования, операционных систем, их компьютерная реализация актуальна для систем автоматизации научных исследований, включая компьютерную обработку результатов физических Экспериментов и компьютерное тестирование электронных устройств Предложенные схемы применимы для упрощения и повышения эффективности навигации в существенных объемах информации на Web-cepeepax, при создании больших электронных архивов, включая электронные библиотеки В целом, разработанные методы могут использоваться в системах электронного документооборота при росте массивов обрабатываемых полнотекстовых документов, могут применяться в качестве средств организации доступа к информации, включая те из них, которые примыкают к разряду систем искусственного интеллекта В частности, представленные схемы могут играть роль при поиске документов по их содержанию в Internet для обеспечения адекватного выбора информации по запросу пользователя Предложенные схемы идентификации разнотипных данных, включая изображения в формате BMP, могут использоваться для повышения эффективности поиска по содержанию

Внедрение « использование результатов работы. Полученные в работе результаты использованы

1 В отделе автоматизации библиотеки Таганрогского государственного педагогического института при создании электронной библиотеки и информационного центра ГОУВПО «ТГПИ»

2 В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос регистрации 01 2 00106436, код ГРНТИ 28 23 15), проводимой на кафедре информатики ГОУВПО «ТГПИ»

3 В учебном процессе кафедры информатики ГОУВПО «ТГПИ» в рамках курсов «Информатика», «Информационные системы», «Информационные технологии в математике», «Элементы абстрактной и компьютерной алгебры», «Использование информационных и коммуникационных технологий в образовании»

Апробация работы. Основные результаты работы докладывались на I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г ), IX-XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2003-2006 гг), IV международной научно-практической конференции по программированию УкрПРОГ' 2004 (Украина, Киев, 2004 г), международной научно-практической конференции «Модернизация отечественного педагогического образования проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г ), международной научной конференции «Оптимальные методы решения научных и практических задач» (Таганрог, ТРТУ, 2005 г ), семинарах «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2001 - 2006гг)

Публикации. По материалам диссертационной работы опубликовано 14 печатных работ общим объёмом 14,4 п л, в том числе, 1 статья в журнале из списка допущенных ВАК РФ

Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 5 приложений Основное содержание работы изложено на 156 страницах, включая список литературы из 149 наименований

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

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

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

В основе схемы лежит применение адресной устойчивой распараллеливаемой сортировки по ключу, сохраняющей на выходе входные индексы упорядоченных элементов (свойство обратной адресности), т е обладающей взаимно однозначным соответствием входных и выходных индексов Одна из таких сортировок представляет собой разновидность сортировки подсчетом, для описания которой применяется матрица сравнений (МС) На пересечении /-й строки и j -го столбца МС находится результат сравнения элементов с[/] и c[j], отмечаемый знаком « + », если c[i] < c[j], знаком « - », если c[i] > c[j], и знаком « 0 », если с[(] = с[у] Число нулей и плюсов в j -м столбце над диагональю, включая диагональный элемент, складывается с числом минусов j -й строки справа от диагонали Значение суммы к становится индексом j -го элемента в отсортированном массиве cl[i] =с[/], с тем же индексом запоминается входной номер переставленного элемента е[к] = j

Дополнительной составляющей конструируемой схемы поиска является оператор локализации экстремальных элементов Локально минимальный элемент массива определяется как элемент меньший предшествующего и не больший последующего по отношению «<-» Оператор локализации минимумов последовательности из п элементов имеет вид

j -l.while j<- n do begin FOR L -1 TO j-1 do if abs (e[j)-e[ j-L) )<=eps then goto 22, Wnteln С \c[ell]],' ' ,e[j]). 22 j -j+1, end.

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

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

В случае числового массива оператор локализации минимумов осуществляет поиск заданного числа как идентификацию нуля абсолютной величины разности между текущим элементом массива и заданным искомым числом Пусть в числовой последовательности а = (о,, я2, ,я„) требуется найти заданное число b Последовательность а преобразуется к виду

г=(К-Ч1а2-Ч О)

и поступает на вход сортировки, после ее выполнения оператор локализации минимумов идентифицирует все нули, если они есть По индексам j идентифицированных нулей последовательности (1) можно обратился к элементам исходного массива Writeln (а[е[3 ] ], е [] ]) 5 се такие элементы совпадут с числом Ь, если оно было элементом входной последовательности а, Описанный способ поиска применим к числам любого типа, его можно осуществлять с точностью до заданной гранглы погрешности Схема выполняет поиск локально минимальных элементов числовой последовательности, отличающиеся от искомого не более чем на epsl (идентификатор границы погрешности) Например, чтобы в последовательности (2 0060007770 9, 2 0060007770 9, 31123, 2 0060007770 8,7-25) найти число 2006 с точностью до е/м1=0 0003000000 1, на вход схемы подается последовательность, сформированная согласно (1) с = (0 00000077709, 0 00000077709, 29 117, 000000077708, 5 244) Полученный массив сортируется, применяется оператор локализации минимумов, затем выполняется просмотр идентифи-

цированных минимумов Условие if cl [у] <= eps 1 выводит элементы, отличающиеся от искомого не более чем на eps\ При eps = 1 будут найдены элементы 2,00600077709 с индексом 1 и 2,00600077708 с индексом 4 Изменение в операторе локализации минимумов заголовка цикла на For L •= 2 to j ~\do позволит выводить последовательно повторяющиеся (соседние) элементы, отличающиеся от искомого не более чем на epsl Способ применим для поиска чисел в заданном диапазоне с идентификацией максимума и минимума отклонения от искомого значения Схема следующим образом переносится на поиск слов в массиве строковых элементов Входному строковому массиву с сопоставляется числовой массив из абсолютных величин разностей ASCII-кода символа, стоящего на заданной позиции слова входного массива, и ASCII-кода символа, указанного в маске поиска

r[¡] = abs (ord (ф[*]])- ord (w)>, (2)

В (2) с - входной массив, к - номер позиции, заданной в маске, i - номер элемента массива с, w - символ, заданный в маске, r[i] - элемент сопоставляемого числового массива г Поиск символов происходит как поиск локальных минимумов, которые в данном случае все оказываются нулями Используя обратную адресацию, по индексам идентифицированных нулей можно обратиться к элементам входного массива строковых элементов, поскольку нумерация элементов обоих массивов сохраняется если i -й элемент массива с удовлетворяет маске поиска, то г[/] = 0, отсюда искомые слова находятся по индексам нулевых элементов числового массива Принципиально, что адресоваться к строковым элементам входного массива в рамках излагаемой схемы можно исключительно благодаря взаимно однозначному соответствию входных и выходных индексов сортируемых элементов, схема поиска существенно опирается на прямую и обратную адресность сортировки, которая используется не косвенно, а как основная конструктивная составляющая алгоритма поиска.

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

rli] = ±\ord(nk[j]])-°rd("íj]) (3)

!• 1

где r[i]- числовое значение, сопоставленное i-му слову, /- i-e слово, k\j]- номер позиции на которой расположена j -я маска поиска, j -я маска поиска Идентификация искомой комбинации символов основана на том, что сумма нулевых разностей сохранит нулевое значение В сопоставленном числовом массиве выполняется поиск нулевого значения по описанной схеме Искомые слова могли быть идентифицированы без применения оператора локализации минимумов, поскольку нули (если они есть) составляют первые элементы отсортированного массива, обратиться к соответствующим строковым элементам можно по сохраненным на выходе сортировки входным индексам (е[/]) этих нулей Однако условие локализации может включать произвольно задаваемое значение радиуса локализации eps, который можно использовать в качестве одного из условий поиска В дальнейшем использование оператора локализации минимумов будет положено в основу определения меры сходства искомых элементов, затем этот оператор явится основой идентификации искомых элементов непосредственно по локальным и глобальным экстремумам сопоставленной числовой последовательности Его описание в предварительно сконструированной схеме - существенная часть развиваемого в диссертации метода

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

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

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

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

Описанный поиск может выполняться максимально параллельно по всем фрагментам текста и по всем сравнениям, требуемым сортировкой, при этом используемая модификация сортировки подсчетом обладает максимальным параллелизмом В главе и в приложении к диссертации представлены программные реализации всех описанных выше схем, включая поиск чисел произвольного типа, поиск по комбинации символов в массиве строковых элементов, поиск текстовых фрагментов и файлов Примеры поиска содержат полные коды разработанных программ Во второй главе разработанные в главе 1 схемы модифицируются для поиска одновременно по нескольким маскам с учетом изменяемости словоформ Как и описанные ранее схемы, их видоизменения строятся на основе сортировки и идентификации экстремальных элементов последовательности чисел, сопоставленных просматриваемым текстовым фрагментам Поиск сводится к программной идентификации всех локально экстремальных (в общем случае не обязательно нулевых) элементов данной последовательности Известные поисковые системы реализуют поиск по произвольному числу масок, не детерминируя взаимное расположение масок в общем виде Конструируемые в главе схемы свободны от данного ограничения Они выполняют поиск одновременно по нескольким маскам, представляющим собой строковые элементы, априори указывая произвольно фиксированные расстояния между масками (взаимное расположение масок раскрыто в виде дополнительного условия поиска) Исходная схема строится следующим образом Задается последовательность слов, принимаемых в качестве масок поиска, и порядок их взаимного расположения, неизменный до конца поиска. Исследуемая строка «нормируется» - удаляются все знаки препинания, между словами оставляется один пробел Строка переводится в одномерный массив тех же слов с сохранением порядка Массиву слов взаимно однозначно по номерам элементов сопоставляется одномерный числовой массив Пусть число масок равно п На первом шаге алгоритма массив формируется из нулевых элементов, нумерация элементов начинается с единицы Выбирается первая из п масок Просматривается сопоставленный строковый массив, начиная с номера ( = 1, для /—го слова этого массива проверяется совпадение с выбранной маской В случае несовпадения к /-му элементу числового массива прибавляется значение равное 1, иначе этот числовой элемент не меняется Выполняется переход к 1 + 1-му слову, процесс продолжается для всех слов строкового массива при сравнении с первой маской Затем процесс воспроизводится для второй и, аналогично, последующих масок

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

Таким образом, поиск слов, совпадающих с заданными масками, сводится к поиску в числовом массиве значения л-1 Этот поиск может осуществляться как поиск минимальных (по отношению к л) элементов, оператор локализации минимумов позволяет найти не только все строковые элементы, совпадающие с заданными масками, но и найти те из них, которые содержатся в заданной окрестности текущего индекса В главе дано обобщение схемы на случай поиска по сходству с учетом изменяемости маски поиска, причем оператор локализации минимумов используется в качестве инструмента оценки меры сходства Сопоставление числового массива происходит следующим образом Задается эталон - искомое слово - и слова, которые имеют отличия от эталона Каждому заданному слову ставится во взаимно однозначное соответствие число (вес), определяющее меру сходства Эталону ставится в соответствие 0 Первому слову из допустимого набора (в количестве л) отличных от эталонного, ставится в соответствие 1, следующему отличному от эталона слову ставится в соответствие число 2 и т д Полное отсутствие допустимых отличий оценивается числом, заведомо большим выбранных весов Весовые отличия определяются априори Для сопоставления числового массива строка «нормируется» и переводится в массив, по ходу его просмотра 1-е слово сравнивается с эталоном, начиная с »= 1, если оно полностью совпадает с эталоном, то / -му элементу числового массива ставится в соответствие число 0, иначе этому элементу ставится в соответствие число, определенное в качестве меры сходства (путем сравнения со словарем) В сопоставленном числовом массиве оператор локализации минимума идентифицирует все слова, совпадающие с эталонной маской поиска (значение 0), слова, сходные с маской (значения 1,2, л) В этой схеме оператор локализации минимума используется уже по существу, как идентификатор значений экстремумов с указанием индексов, по которым идентифицируются искомые по мере сходства элементы и особенности их взаимного положения Сохраняется возможность вложений рассмотренных схем при совпадении минимума с нулем (совпадение с эталоном) и при его совпадении с произвольно задаваемым весом (с точностью до заданной меры сходства) Предложенные схемы переносятся на поиск в текстовых файлах и поиск с учетом «опечаток». В последнем случае, если слово полностью совпадает с эталоном, то I -му элементу сопоставленного числового массива ставится в соответствие 0, если слово совпадает нечетко, то ему ставится в соответствие 1 Иначе этому элементу ставится в соответствие заведомо большое число

{0, если з1[г] — точно совп адает с ма екай

1, если 51[1] - частично с овпадает с маской (4)

100, если зЦг] -не совпадает с маской

В результате исходной строке ставится во взаимно однозначное соответствие числовой массив, каждый элемент которого равен 0, 1 или 100 Оператор локализации минимумов определит все слова, совпадающие с эталоном (значение 0), слова, сходные с ним (значение 1) Индексы экстремумов позволят включить условие взаимного положения искомых слов Для оценки нечеткого совпадения можно использовать известные способы В главе дана схема поиска одновременно по нескольким маскам с априори указанным расстоянием между ними Рассматривается фраза из т слов и заданы л масок поиска, между словами, отвечающими 1-й и 2-й маскам, должно быть расположено кг слов, между словами, отвечающими 1-й и 3-й маскам, -к, слов, , между словами, отвечающими 1-й и л-ой маскам, - к„ слов Первой маске поиска сопоставляется число 0, второй - 1, , л-ой - число л-1 Фразе, как и раньше в схеме поиска с учетом словоформ, ставится в соответствие числовой массив с из т элементов При каждом значении /, начиная с 1 = 1,1 -му элементу массива с сопоставляется элемент массива с1 по соотношению

['] = |(ф] - 0)|+|(с[» + Л2 +1] -1)|+ +|(ф + *„ + 1]-(«-1))| (5)

По построению массива (5) элемент с1[/] принимает нулевое значение в том и только в том случае, если для (-го слова существуют все заданные маски с априори заданным расстоянием если

i -му слову соответствует 1 -я маска, i + к2 +1 -му слову - 2-я маска, , i+к„ +1 -му слову - п -я маска, то, соответственно, c[i]- 0 = 0, c[i + к2 + IJ-1 = 0, , cfi+A„+17-(n-l) = 0 Отсюда cl[i] = О Таким образом, поиск группы слов с априори заданным расстоянием между ними сводится к поиску нулей в числовом массиве размерности т-кя-1

В главе дана еще одна схема текстового поиска одновременно по нескольким маскам, которая отличается тем, что по идентифицированным индексам экстремумов без дополнительного просмотра окрестности локализованного значения и без сверки с масками дает однозначный ответ, какое именно слово было найдено В дальнейшем именно эта схема будет преобразована для поиска объектов различных типов по нескольким свойствам Схема строится следующим образом Исследуемой строке сопоставляется (описываемым ниже способом) одномерный числовой массив, количество элементов которого совпадает с количеством слов заданной строки Элементы сопоставленного числового массива, соответствующие различным маскам, перемножаются, причем сомножители априори задаются так, чтобы произведения взаимно однозначно соответствовали различным маскам, а локальные минимумы в их последовательности единственным образом соотносились с полным набором масок Сопоставление массиву слов S1 числового массива с = (с,, с2, ,ст ) выполняется по соотношениям

|у + 1, если i - е слово совпадает

с j-й маской поиска ) +1 + п, если i - е слово не совпадает с j — й маской поиска

При этом индексы элементов ф] совпадают с индексами элементов £/[/] К отсортированному массиву с применяется оператор локализации минимумов Если локализация минимума выполняется в окрестности наперед заданного радиуса, не меньшего числа сгруппированных масок, то идентифицированным окажется искомое сочетание одновременно нескольких масок Тем самым оказывается возможным вести поиск не по разрозненному сочетанию нескольких масок, а по их взаимосвязанному положению в исследуемом массиве слов Схема формализуется следующим образом Пусть / - номер текущего элемента исследуемого массива слов Пусть л -количество масок поиска и / -му слову сопоставлено одно из двух значений a¡ и bt

щ =2,Oj =3, ,aj =у+1,. ,а„=л+1, b¡ =п+2,Ь2 =п+3, ,,bj=n+j+l, ,Ь„ = п+п+1 (7)

При этом в (7) Oj = j+1, если i-e слово совпадает с j -й маской поиска, b¡=n+j +1, если i-e слово не совпадает с j-й маской поиска, / = 1, 2, Данные соотношения устанавливаются по ходу просмотра по всем i = 1, 2, с одним зафиксированным значением j Начальное значение j принимается равным 1 При следующем просмотре значение j увеличивается на 1 Процесс продолжается до исчерпания значения всех и масок поиска С учетом (7)

с,=Пб,ха, (8)

j-1

Данный способ формирования масок по соотношениям (6)-(8), или, что то же самое, по соотношению (6) будет именоваться мультипликативной схемой (6) Имеет место

Лемма 1. Пусть для заданных масок сформирован массив (6) Тогда при любом выборе элемента (6) значения произведений с, не совпадают при различных значениях индекса к из (8) Иными словами, при / Ф г выполнено с,*сг в случае совпадения í-го и г-го слов массива si с какими бы то ни было соответственно различными масками из заданного набора

По лемме 1 значения с, взаимно однозначно соответствуют словам, совпадающим с масками В данной схеме число масок произвольно Значения с, оказываются заведомо равны для тех номеров слов i, которые не совпадают ни с одной из масок (8) При этом данные значения с, превосходят по величине значения, соответствующие словам, совпадающим с масками Данную числовую схему определения признаков маски можно применить к любому

наперед заданному числу масок путем подбора начального сомножителя факториального отрезка и конечного значения числового признака маски Имеет место

Теорема 1. Пусть количество масок, заданных в виде строковых элементов, равно п и для них сконструировано соотношение (6) Тогда оператор локализации минимума в окрестности радиуса грА = п идентифицирует все локально минимальные элементы, соответствующие группе из п подряд расположенных масок _

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

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

Теорема 2. Если в условиях леммы 1 I -е слово соответствует к -ой маске поиска, а /+1 -е слово соответствует £ + 1 -ой маске поиска, то с, < см

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

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

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

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

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

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

ного числового массива без изменения конечного результата выполняется иначе, чем это было сделано в главе 2. Пусть дан массив SI из т слов, в котором требуется выполнить поиск по заданной последовательности п масок М = (m,,m2, ,тп), расположенных в определенном и фиксированном порядке На первом шаге массиву SI сопоставляется двумерный числовой массив mass[n,m]

г I _ р, если I- е слово совпадает с j-й маской поиска, . (9) lJ' ' ~ (0, если г-е слово не совпадает cj-ймаской поиска

В (9) и ниже / = 1,2, ,т, /=1,2, ,п На основе (9) формируется промежуточный двумерный

массив mass!

__,г, ,i_/i + l, если mass[j,i\ = \, nfn

Затем путем перемножения элементов столбцов (10) формируется одномерный массив с

(11)

У-1

Данным приемом любой массив, состоящий из нулей и единиц, переводится в одномерный числовой массив, где при каждом i исследуемому объекту (слову) с номером / соответствует / -й столбец массива mass, в котором не более одного единичного значения При этом несущественно, какова природа рассматриваемых объектов Поэтому ниже данная конструкция используется не для поиска строковых элементов, а для идентификации объектов одновременно различных типов или, в более общем случае, объектов, характеризуемых свойствами различной природы Непосредственно ниже, для определенности, идет речь об объектах не обязательно текстового типа, но все объекты рассматриваемого множества должны иметь один и тот же тип В дальнейшем это условие не будет обязательным, будут рассмотрены объекты с признаками множественной природы Вначале конструируется поиск объекта из упорядоченного множества по группе признаков, заданных в фиксированном порядке При этом признаки и объекты могут быть произвольно фиксированного типа или характеризоваться произвольно фиксированным свойством Ограничение заключается в том, что каждый объект может соответствовать одному и не более чем одному признаку В конструируемой схеме заполнение соответствующих массивов mass и massl ведется с помощью проверки соответствия или несоответствия исследуемого объекта заданному признаку согласно (9), (10), где наличие (отсутствие) соответствия кодируется единицей (нулем) так же, как кодировалось совпадение (несовпадение) с маской, проверка выполняется при фиксированном порядке обхода объектов После сортировки массива с из (11) применяется оператор локализации минимумов, который по наличию локальных числовых минимумов идентифицирует индексы искомых объектов так, как раньше он идентифицировал индексы слов, совпадающих с масками поиска. По идентифицированным индексам на основе совпадения индексов числового массива и массива исходных объектов выполняется переход от числовых экстремумов к искомым объектам в исходном виде Непосредственно ниже этот подход видоизменяется для поиска объекта с одновременно несколькими его признаками

Согласно (9) - (11) каждому исследуемому объекту сопоставляется единственное число В случае если объект обладает одновременно несколькими искомыми свойствами, эта единственность нарушается Требуется модифицировать схему, чтобы каждому объекту с заданным набором признаков числовое значение сопоставлялось единственным образом Пусть дано проиндексированное множество V из т однотипных объектов, в котором требуется выполнить поиск по заданной последовательности признаков М = (m,,m2, ,m„)> расположенных в определенном и фиксированном порядке Пусть число признаков равно п Как и прежде, формируются массивы mass, massl и с, но при этом (10) заменяется на следующее соотношение

та„1Г, ¿i-JpUl если mass\j,i] = 1, (т

mass]U'4-\ p[j+ri\, если massl/,i] = 0, {U>

где p - конечная последовательность из 2л упорядоченных простых чисел (2,3, 5, ) Имеет место взаимно однозначное соответствие между набором признаков, присущих исследуемому объекту V[i], и сопоставленным чиповым значением ф] значение ф] по теореме о простых чис-

лах единственным образом разложимо на простые множители, по этому разложению данное число обратимо указывает на те признаки (9), которыми обладает объект соответственно простым сомножителям тамЦу,»] из (12) Обратно, каждому набору признаков, присущих объекту, в силу той же теоремы и по построению (9), (11), (12) соответствует единственное значение произведения элементов столбца, образующее элемент сопоставленной числовой последовательности (11) Числовые идентификаторы наборов признаков (при полном и частичном совпадении) могут быть априори рассчитаны, на этой основе выполняется поиск не только по полному набору заданных свойств, но и по их частичному набору Путем анализа окрестности локализованных минимумов можно, помимо того, выполнить поиск не только одного объекта, но и группы таких объектов по нескольким признакам одновременно

Мультипликативную схему в форме (9), (И), (12) можно адаптировать к поиску группы объектов, типы которых различны между собой В качестве примера можно взять поиск каталога, содержащего файлы различных типов Каталог рассматривается как объект исследования, а наличие требуемого файла в исследуемом каталоге - как признак поиска. Каталог с такими признаками идентифицируется по мультипликативной схеме (9), (11), (12) При анализе каталога для каждого файла из этого каталога описанная ранее схема поиска без изменения применима к файлам различного типа в том случае, если типы объектов совместимы или могут быть приведены к одному типу в операционной системе, например, * txt, * dpr, *.pas, * xls, * doc Для реализации поиска объектов, которые не приводятся к одному и тому же типу, например, *.dat, * bmp предлагается описываемая в дальнейшем специальная схема

, Для поиска на рассматриваемой основе файлов, содержащих разнотипные данные внутри файла, включая данные текстового типа, рисунки в формате * bmp, числа с плавающей точкой, программные коды в различных языках программирования, можно поступить следующим образом Исследуемому файлу сопоставляется группа файлов, например, текстовый файл * txt, непосредственно содержащий текст исследуемого файла, графические файлы * bmp, содержащие внедренные в исследуемый файл рисунки, типизированный файл * dat, который содержит все числовые значения, присутствующие в данном файле и т д Поиск в исходном файле в результате сводится к поиску в файлах сопоставленной группы. Каждая группа рассматривается как объект со многими признаками поиска, а наличие или отсутствие в объекте файла, соответствующего маске поиска, как признак объекта для его идентификации Таким образом, используется рекуррентное вложение схем поиска Объединенный результат поиска можно получить по схеме с использованием (9), (11), (12), что позволяет свести поиск к идентификации локальных экстремумов числовой последовательности и в этом сравнительно общем случае

Поиск в файлах * dat искомого числового значения с точностью до epsl можно выполнить на основе схемы поиска элемента в числовом массиве с заданной границей погрешности Информация из типизированного числового файла считывается в числовой массив с сохранением порядка следования элементов Далее без изменений применяется схема, описанная в главе 1 Схема обобщается на поиск самих типизированных числовых файлов по признаку ш~.ичия в нем заданного числового значения с допустимой границей точности С целью поиска файлов типа * bmp каждому файлу (предполагается, что файл содержит только один рисунок) сопоставляется вектор распознавания Этот вектор можно сформировать на основе какой-либо известной схемы В главе показано (как поясняется ниже), что вектор распознавания может быть сформирован с использованием мультипликативной схемы Если вектор сформирован, то для текущего рисунка находится норма разности между вектором исследуемого рисунка и эталонным вектором Рисунок считается найденным, если норма разности соответственной пары векторов не превосходит заданной границы погрешности Мультипликативная схема (9), (11), (12) может следующим образом применяться для формирования векторов распознавания при поиске растровых двуцветных изображений Первоначально рассматриваются плоские изображения, дня определенности размера 16x16 пикселей, в растровом формате BMP Изображению сопоставляется двумерная числовая матрица mass, 16x16, каждый элемент которой принимает только два значения 0 или 1 Значением 0 кодируется белый цвет, значением 1 - черный Полученной матрице mass согласно (11), (12) сопоставляется двумерный массив mass\ и одномерный числовой массив с

Элемент этого массива с номером / образуется как произведение простых чисел столбца с тем же номером из матрицы massl Таким образом, по отношению к матрице из нулей и единиц, кодирующей исходное двуцветное изображение, полностью воспроизводится алгоритм (11), (12) сопоставления числовой последовательности, который ранее применялся для поиска по отношению к матрице mass из (9) Данное приложение алгоритма позволяет сформировать для каждого рисунка вектор распознавания в виде массива с из(11)ис его помощью решить две задачи поиск плоских двуцветных изображений и распознавание плоских двуцветных изображений с помощью сопоставленного вектора При данном подходе изображение может быть идентифицировано вектором, роль которого играет массив с Набор таких векторов может храниться в виде эталонов, с которыми по соответственному выходному массиву с сравниваются искомые объекты Такая схема поиска переходит в способ распознавания, отличающийся двумя аспектами Первый из них заключается в построении, второй - в том, что вектор распознавания дает сжатие идентифицируемого изображения с квадратичного (по размеру матрицы изображения их я) до линейного (по размеру вектора распознавания и ) В главе обоснованы следующие утверждения Предложение 2. Массив с единственным образом идентифицирует изображение Следствие 2. Описанное сжатие изображения обратимо

Пример формирования вектора распознавания для символа «и*» -

{Матрица пикселей (массив mass ) | Массив простых чисел massl |Векгор распознавания j

□□□□□□□□□□а - □□□ 59 59 59 59 59 59 59 59 59 59 59 ИИи59 ]591 59 2 098951589832 ЕЗО

61 61 61 61 61 61 61 61 61 61 ■внддрМдиб! 11 mil рвб7 61 67 71 73 1,63662668958544 Е28

□ШЕШЕНЗЕШСШЕК а ЕШ 67 67 67 67 67 67 67 67 67 67 5,38849355573104 Е29

ИЬ! ооооо 0 0 □ИИ И 71 71 71 71 71 71 71 71 71 71 71 |71 ИЩИ— НМ1Ш1нй~ 2 27253858654744 ЕЗО

ГоТо1 0 0 0 0 0 0 0 □ □□ 73 73*1 73 73 73 73 73 73 73 73 9 19424008297818 Е29

II 0 | 0 ооооо 0 0 |0|0|0|0|0|0|0|1 79 79 79 79 79 79 79 79 79 79 |?9 |79 |79 |79 [79 79 2 27253858654744 ЕЗО

ЕШЕШППЕШЕШИЕШЕ] □ЕШЕШЕШЕШ-ЕШ □ - □ СЗЕШЕШ И . □ н? □ гЕШЕШЕШП' О 'ЕГ. □ilQQQGlDEIQD '' ^СШСШЕШИП ЕШЕШ ЕЯЕИЕнасяЕШЕИша. О ' -ь,. ¡51ВЯЕЯЕШада! ¡v._ 01..: ЕШ ш *■>■ папшшпшапашшзр ни... ¿l t пят,-: пта ?! ltikll№lllikll(iMlliUI№llik|lliH -'Г 1 > ■ li/JIOHl[<yjlItJTJII'/ilL'lilI'M}. |IM lt>MI[*JrJI(»/ilIM 2,27253858654744 ЕЗО 2,27253858654744 ЕЗО 2 94789090036831 Е29 3,05069466322996 Е28 853432018900399 Е27 904025304631169 Е24

ИММо|о|о|о|о|оМо|о|о|о|о|о| - Hi'.'llliMlliMHi'jllirjllliM ii ' 1||Ц»|.']Ц|ИЦ|Ы1||И1[|Ы 1 74834375400699 Е24

u ' ■ [¡шшьшьшы ЕШ ЕНЭЕШЕШЕШ ЕШСШ'СШСШЕШЕШШСШ 1Ш ' - ШИЕГ ШНОЩШН M, • iiuhhiihiihiihiihiihiih v гедгсяпягеягептониист] шптгепгептнинииннниншт 7 60368904395812 Е25 4 96457187333091 Е27 7 05907679038715 Е28

Рис 1

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

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

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

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

разновидности логических функций по таблицам истинности и объекты других предметных областей В диссертации приводятся примеры такой программной идентификации Достаточным условием идентификации является выполнимость кодирования по схеме (9), (И), (12) тех свойств, по которым требуется выполнить поиск или распознавание В главе даны примеры приложения метода к поиску объектов в изображении гербария, к распознаванию диагностических экстремальных особенностей электрокардиограмм, к распознаванию отпечатков пальцев Применимость схемы (9), (11), (12) к идентификации логических функций позволяет перенести ее на случай тестирования логических и цифровых устройств При этом объекты должны иметь фиксированный порядок взаимного расположения до конца процесса рассматриваемой обработки В главе даны конкретные схемы и алгоритмы с формализованным описанием

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

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

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

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

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

Работа включает следующие научные результаты.

1 Сконструирован распараллеливаемый метод применения сортировки для поиска на ее основе Локально экстремальных элементов числовой последовательности Метод применяется с использованием кодовой таблицы символов для детерминированного поиска строковых элемен-

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

2 Сконструирована схема с использованием обработки числовых выражений для поиска данных строкового и вещественного типа на основе подстановки индексов отсортированных элементов

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

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

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

6 Представлено преобразование основной схемы поиска для распознавания, идентификации и сжатия плоских оцифрованных изображений

7 На основе преобразования схемы поиска и идентификации разнотипных объектов синтезирован распараллеливаемый алгоритм идентификации неисправностей цифровых устройств

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

1 Ромм Я Е, Белоконова С С Поиск и распознавание текстовых фрагментов на основе адресной сортировки и локализации экстремальных значений asc-кодов / ТГПИ - Таганрог, 2001 - 22 с Деп в ВИНИТИ от 06 12 2001, № 2537 - В2001 (лично автора - 0,75 п л )

2 Ромм Я Е , Белоконова С С Схема поиска на основе сортировки и локализации экстремальных элементов / ТГПИ - Таганрог, 2003 - 31 с Деп в ВИНИТИ 12 03 2003, № 436-В2003 (лично автора - 1 п л )

3 Ромм Я Е, Белоконова С С Применение сортировки и локализации экстремальных элементов к поиску - В кн Сборник материалов 1-й международной научно-практической конференции 15-17 сентября 2003 г подред А К Юрова - Таганрог -2003 - С 100-105 (лично автора - 0,08 пл )

4 Ромм Я Е, Белоконова С С Схема поиска на основе сортировки и локализации экстремальных элементов - В кн Сборник научных трудов 9-й международной конференции «Математические модели физических процессов» - Таганрог, ТГПИ -2003 - С 100- 103 (лично автора-0,15 пл)

5 Ромм Я Е, Гуревич M Ю , Белоконова С С , Соловьёва И А Вычисление нулей и полюсов функций на основе устойчивой адресной сортировки с приложением к поиску и распознаванию//Проблемы программирования -2004 -№2-3 -С 462-472 (личноавтора-0,36пл)

6 Ромм Я Е, Белоконова С С Схема поиска и распознавания на основе идентификации экстремумов с помощью сортировки - В кн Сборник научных трудов 10-й международной конференции «Математические модели физических процессов» - Таганрог, ТГПИ - 2004 - С 167 - 172. (лично автора - 0,2 п л )

7 Ромм Я Е , Белоконова С С Метод поиска на основе адресной сортировки и идентификации экстремумов в приложении к распознаванию / ТГПИ - Таганрог, 2004 - 46 с Деп в ВИНИТИ от 05 08 2004 №1361-В2004 (личноавтора-1,4пл)

8 Ромм Я Е , Белоконова С С Поиск по произвольному количеству масок на основе локализации экстремумов при помощи сортировки - В кн Модернизация отечественного педагогического образования проблемы, подходы, решения Сб науч тр Ч II «Технологические основы образовательного процесса в современной высшей школе - Таганрог -2005 - С 24-29 (лично автора - 0,2 п л )

9 Ромм Я Е, Белоконова С С. Схема поиска текста на основе локализации экстремумов при помощи сортировки - В кн Материалы международной научной конференции «Оптимальные методы решения научных и практических задач» - часть 2 - Таганрог Изд-во»Антон», ТРТУ, 2005 - С 58-63 (лично автора - 0,2 п л )

10 Ромм Я Е, Белоконова С С Поиск по группам масок на основе сортировки и локализации экстремальных элементов / ТГПИ - Таганрог, 2005 - 56 с Деп в ВИНИТИ от 28 06 05, № 916 - В2005 (лично автора - 1,5 п л )

11 Ромм Я Е, Белоконова С С Схема поиска данных различных типов по нескольким маскам на основе сортировки // Известия вузов Северо-Кавказский регион Техн науки Специальный выпуск «Математическое моделирование и компьютерные технологии», 2006 - С 3 - 8 (лично автора - 0,4 п л )

12 Ромм Я Е, Белоконова С С Совмещение схемы поиска на основе сортировки с идентификацией двуцветных изображений - В кн Материалы Международной научно-технической конференции «ММА-2006» - «Математические модели и алгоритмы для имитациифизических процессов» Т 1 Физико-математические и физико-технические модели и алгоритмы для имитациифизических процессов - Таганрог -2006 - С 329 - 333 (лично автора - 0,2 п л )

13 Белоконова С С Схема текстового поиска с учетом словоизменяемости на основе сортировки - В кн Материалы Международной научно-технической конференции «ММА-2006» -«Математические модели и алгоритмы для имитациифизических процессов» Т 1 Физико-математические и физико-технические модели и алгоритмы для имитациифизических процессов -Таганрог -2006 - С 333-336

14 Ромм Я Е, Белоконова С С Схемы поиска данных различных типов по т маскам - В кн Информационные технологии в образовании и консультационной деятельности в сельскохозяйственном производстве -Новочеркасск -2006 - С 164-171 (личноавтора — 0,2пл)

Соискатель

Белоконова С С

Тип ТТИ ЮФУ

Подписано к печати Объем 1,1 уч -изд л

Заказ В Тираж 100 экз

Введение

Глава 1. Базовые схемы поиска и распознавания на основе адресной сортировки.

1.1. Алгоритмы локализации экстремумов на основе сортировки.

1.2. Выполнение поиска в числовой последовательности по схеме идентификации экстремумов и нулей с помощью сортировки.

1.3. Видоизменение поиска на случай массива строковых элементов.

1.4. Поиск в текстовом файле с помощью идентификации экстремумов и нулей на основе сортировки.

1.5. Поиск текстовых файлов с заданными фрагментами.

1.6. Сравнение с известными схемами поиска.

1.7. Выводы.

Глава 2. Мультипликативная схема поиска текстовых фрагментов на основе идентификации локальных экстремумов числовой последовательности.

2.1. Поиск на основе сортировки одновременно по нескольким маскам строкового типа.

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

2.3. Поиск с мерой сходства по нескольким маскам при заданном между ними расстоянии и поиск с учетом «опечаток».

2.4. Мультипликативная форма схема поиска в строковом массиве одновременно по нескольким маскам.

2.5. Применение мультипликативной схемы для поиска в текстовых файлах и поиска файлов.

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

2.7. Выводы.

Глава 3. Применение мультипликативной схемы поиска к ^ идентификации данных и объектов различных типов.

3.1. Модификация мультипликативной схемы на случай поиска объектов различных типов одновременно по нескольким признакам.

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

3.3. Поиск группы объектов различных типов и разнотипных файлов.

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

Актуальность проблемы. Проблема поиска и сбора информации является одной из важнейших задач информатики. Первые работы [1-3], касающиеся поиска текста, появились во второй половине XX века. Более подробный обзор был сделан позднее в работах [4-6]. В дальнейшем поток работ на эту тему сохранял устойчивую тенденцию к росту [7-9]. Развитие компьютерной техники привело к существенному увеличению объема информации, представленной в электронном виде [10-12]. Приобрели актуальность вопросы, связанные с проблемой поиска информации на электронных носителях, функция поиска значительно упрощает пользователям навигацию в огромных массивах документов [13,14], хранящихся на \Veb-cepBepax, включая электронные библиотеки [15,16]. В частности, функция поиска слов в тексте существенно облегчает редактирование документов и поиск требуемой информации. В настоящее время функция поиска является составляющей многих программных продуктов, редакторов языков программирования. Актуальны задачи поиска объектов, хранящихся в оцифрованном виде по нескольким признакам одновременно, однако, поиск изображений сводится к поиску в тексте по названию изображения [17].

Можно выделить следующие разновидности поиска: поиск в массиве записей [7 - 9], поиск подстроки в строке или поиск по образцу [8,9,18], алгоритмы информационного поиска [15,12,19,21], алгоритмы поисковой системы [15,2225].

I. Классические схемы поиска в массиве записей. Поиск необходимой информации в массиве - одна из фундаментальных задач информатики. В классических методах поиска [7 - 9] поиск рассматривается как нахождение данных, удовлетворяющих определенному свойству. В [7-9] предполагается, что информация содержится в записях, которые представляют собой массив данных в программе и каждая запись содержит поле, которое называется ключом. Записи идут в массиве последовательно, номера записей в списке идут от 1 до ТУ — полного числа записей. Массив записей может быть неотсортированным или отсортированным по значению ключевого поля. В неотсортированном массиве порядок записей случаен, в отсортированном они идут в порядке возрастания ключа. При этом известные схемы поиска [7, 8] реализуют поиск только однотипных данных. Кроме того, в этих схемах поиск ведется только по одному ключу (признаку поиска). В [7] предложена следующая классификация методов поиска. 1. Внутренний и внешний поиск с разделением используемых сортировок. 2. Статические и динамические методы поиска. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять размерность. 3. Методы, основанные на сравнении ключей и на цифровых свойствах ключей. 4. Методы, использующие истинные ключи и преобразованные ключи.

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

Линейный поиск [7 - 9,26] заключается в простом последовательном просмотре всех элементов массива и сравнении с эталоном (ключом) X. Эта процедура выдает либо значение индекса для найденного элемента массива, либо нулевое значение, когда требуемый элемент не найден. При прямом последовательном поиске в среднем проверяются я/2 элементов. В лучшем случае будет проверяться один элемент, в худшем - п элементов. Если данные не отсортированы, то линейный поиск является единственным возможным.

Классические способы поиска в отсортированном массиве: а) бинарный поиск; б) поиск по «дереву Фибоначчи»; в) интерполяционный поиск.

Бинарный поиск [7 - 9,26] сравнивает эталон (ключ) с элементом в середине массива и в зависимости от результата сравнения (больше или меньше) дальнейший поиск проводится в левой или в правой половине массива:

L:=0; R:=N; f:= false;Repeat m:=(L+R) div 2; if a[m]=x then f:=true;If a[m]<X then L:=m+1 else r:=m;

Writeln (m, L,R);Until (L>=R) or(f);

If f then write ('найден элемент на', m, 'месте') else write ('такого элемента в массиве нет');

Например, поиск в массиве (1, 5,12,17,21,25,32,42,45,47, 51,54,57,65,78,94) числа 51 можно проиллюстрировать следующим образом.

1 5 12 17 21 25 32 42 45 47 51 54 57 65 78 94]

1 5 12 17 21 25 32 42 [45 47 51 54 57 65 78 94]

1 5 12 17 21 25 32 42 [45 47 51] 54 57 65 78 94

1 5 12 17 21 25 32 42 45 47 [51] 54 57 65 78 94

Сначала делается проверка среднего элемента, которым является число 42. Этот элемент меньше 51, поиск будет продолжен во второй половине массива (45,47,51,54,57,65,78,94), иначе бы проверялась первая половина. Процесс продолжается, пока искомый элемент не будет найден. Число сравнений в худшем случае log«, в лучшем случае - 1. Алгоритм представим бинарным деревом [7]:

Рис. 1.

Поиск по «дереву Фибоначчи». В дереве Фибоначчи [7,27] числа в дочерних узлах отличаются от числа в родительском узле на одну и ту же величину, а именно на число Фибоначчи. Суть метода в том, что в ходе сравнения искомого значения с очередным значением в массиве, новая зона поиска не делится пополам, как в бинарном поиске, а происходит смещение от предыдущего значения, с которым сравнивали, в нужную сторону на число Фибоначчи.

Дерево Фибоначчи порядка 6

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

Интерполяционный поиск [18,27,28]. Если известно, что К лежит между К, и Ки, то следующую пробу делаем на расстоянии (и-1\К-К1)/(Ки-К,) от /, предполагая, что ключи являются числами, возрастающими приблизительно в арифметической прогрессии. Интерполяционный поиск асимптотически предпочтительнее бинарного, так как один шаг бинарного поиска уменьшает количество записей, среди которых находится искомая, с п до и/2, а один шаг интерполяционного поиска с п до Гп. Интерполяционный поиск требует в среднем около 1о§21о%2Ы шагов. Скорость интерполяционного метода начинает существенно превышать скорость метода половинного деления при больших значениях N.

Кроме перечисленных методов поиска можно также назвать метод цифрового поиска, который вместо непосредственного сравнения ключей использует их представление в виде последовательности цифр и букв - поиск по дереву [7]. Частным случаем поиска по бору является цифровой поиск по дереву. Еще одна группа методов поиска позволяет произвести над ключом к арифметические вычисления и получить функцию /{к), указывающую адрес в таблице, где хранится к и ассоциированная с ним информация. В идеале, для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом [7,29].

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

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

Алгоритм последовательного поиска в тексте [7,8,30,31]. Идея метода заключается в следующем: проверяется, совпадают ли т символов текста (начиная с выбранного) с символами строки. Стандартный алгоритм начинает со сравнения первого символа текста с первым символом подстроки. Если они совпадают, то происходит переход ко второму символу текста и подстроки. При совпадении сравниваются следующие символы. Так продолжается до тех пор, пока не окажется, что подстрока целиком совпала с отрезком текста, или пока не встретились несовпадающие символы. В первом случае задача решена, во втором - указатель текущего положения в тексте перемещается на один символ, и сравнение начинается заново. Время работы алгоритма есть 0((п-т+1)т)[8].

Алгоритм Рабина-Карпа [8]. В алгоритме предлагается поставить в соответствие каждой строке некоторое уникальное число и вместо сравнения строк сравнивать числа. Недостаток метода в том, что искомая строка может быть длинной, и строк в тексте может быть много. Так как каждой строке нужно сопоставить уникальное число, то чисел должно быть много, числа будут большими и работать it с ними будет неудобно. Проблема больших чисел может быть решена, если производить все арифметические действия по модулю какого-то простого числа (брать остаток от деления на это число). В этом случае находится не число, характеризующее строку, а его остаток от деления на простое число. Число ставится в соответствие не одной строке, а целому классу, но так как классов много (столько, сколько различных остатков от деления на это простое число), то дополнительная проверка производится редко. Алгоритм реализует следующая программа:

JP Program RabinKarpSearch; Var t,s: string; i,j,n,m,v,w6 k: longint; const P: longint = 7919; D: longint = 256; Begin writeln('введите текст'); readln(t); writeln('введите искомый текст');readln(s); n:= length(t);m:= length(s); v:=0; w:=0; for i:=l to m do begin v:=(v*D+ord(S[i])) mod P; w:=(w*D+ord(T[i])) mod P; end; k:=l; for i:=l to m-1 do k:=k*D mod P; for i:=m+l to n+1 do begin if w=v then begin j:=0; while (j<m) and (S[j +1]=T[i-m+j]) do j:=j+l; if j=m then writeln('Образец входит в текст с 1,i-m,'-ого символа'); end; if i<=n then w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P; end; End.

Время работы О тпл m + n +— ч P J так что сложность работы почти линейная.

Алгоритм Кнута-Морриса-Пратта [8,18] (далее КМП) основывается на том, что после частичного совпадения начальной части образа с соответствующими символами образ сдвигается на все пройденное расстояние, так как меньший сдвиг не может привести к полному совпадению. Алгоритм КМП иллюстрирует пример, приведенный на рис. 3. Выполняется поиск слова format в заданном тексте.

Алгоритм Кнута - Морриса - Пратта gin format текст f о г t о f О г W А г d b шаг 1 f о г ш а t шаг 2 f о г m а t шаг 3 f О г m а t шаг 4 f о г m а t шаг 5 f О г m а Т шаг 6 f о г ш А t шаг 7 f о г mat шаг л format

Рис. 3.

Алгоритм КМП работает со сложностью 0(п + т) на любом тексте. Алгоритм Бойера-Мура [32,33] считается более быстрым среди алгоритмов, предназначенных для поиска подстроки в строке. Отличием алгоритма БМ от алгоритма КМП является то, что для поиска выполняется сравнение символов с конца образа, а не с начала. На первом шаге строится таблица смещений для искомого образца. Совмещая начало строки и образца, выполняется проверка с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с наложенными символами строки, значит, найдена подстрока и поиск окончен. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, то сдвигается образец на один символ вправо и снова начинается проверка с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки. Величина сдвига в случае несовпадения последнего символа вычисляется следующим образом: сдвиг образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, то образец смещается таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если образец вообще не содержит этого символа, то образец сдвигается на величину, равную его длине, так что первый символ образца накладывается на следующий за проверявшимся символом строки. Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Алгоритм иллюстрируется следующим примером.

Алгоритм Бойера-Мура текст for to forward begin format шаг 1 format шаг 2 format шаг 3 format шаг 4 format шаг 5 format шаг б format

Рис. 4.

Число сравнений алгоритма 0(п + гт), где г - число вхождений.

III. Алгоритмы информационного поиска. Информационный поиск текстов - одна из самых востребованных задач обработки текстов [13]. Центральная проблема - помочь пользователю найти ту информацию, в которой он заинтересован [35]. Задача поиска состоит в определении по запросу пользователя множества текстов из некоторой фиксированной базы, релевантных запросу. Запрос представляется набором ключевых слов. Основным вопросом при этом является определения релевантностей текстов запросу и сортировки документов по этим значениям [19]. Классическая задача информационного поиска, с которой и началось развитие этой области, - это поиск документов, удовлетворяющих запросу в рамках некоторой статической (на момент выполнения поиска) коллекции документов. Эта задача решается в рамках большинства современных справочных систем, включая Windows. [12]. Модели информационного поиска делятся на три класса [12,36]:

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

Булев поиск опирается на использование инвертированного индекса ключевых слов, то есть таблицы, в которой для каждого ключевого слова перечисляются все документы, где оно встречается [37]. Главным достоинством этого алгоритма является возможность связывания слов запроса логическими операциями и получения в результате объединение множеств документов, содержащих искомые слова. К недостаткам следует отнести невозможность определения релевантности запросу полученной выборки документов. При поиске из инвертированного индекса извлекаются списки документов, соответствующие каждому слову запроса. Над полученными множествами проводятся операции, соответствующие логическим операциям, связывающим слова запроса, в результате чего образуется список найденных документов. Как правило, данный алгоритм используется совместно с другими алгоритмами.

Векторная модель является классическим представителем класса алгебраических моделей, реализована в 1968 г. Джерардом Солтоном в поисковой системе SMART (Saltan's Magical Automatic Retriever of Text). Сокращенное обозначение

TF*IDF - синоним наиболее распространенной современной векторной модели [38], основанной на математическом аппарате геометрии, в которой индексируемые текстовые ресурсы и запросы пользователей рассматриваются как векторы в пространстве слов, а релевантность как расстояние между ними [21]. Векторные модели, в отличие от булевых, позволяют ранжировать результирующее множество документов запроса. В векторной модели каждому документу ставится в соответствие вектор Di = где wtj - вес у-го ключевого слова в i-м документе, обычно вычисляемый по формуле нормированного представления TF*IDF 1 N

Wy = atj log—, где ay — частота появления j -го ключевого слова в i-м документе; dj dj - количество документов, в которых встречается j-e ключевое слово; N - общее количество рассматриваемых документов. Аналогично, для запроса Q вводится вектор Q={ql,q2>—>q„}> где q}= 1, если j-e ключевое слово присутствует в запросе Q, иначе qj = 0. Мера схожести документа Di и запроса Q вычисляется как косинус угла между соответствующими векторами r(DpQ) = (Ц,Q)/(||£>.||• ||g||), где (Z>, Q) - скалярное произведение, || Д ||, \\Q\\- нормы векторов.

Вероятностная модель информационного поиска основана на теории вероятности и использует статистические показатели, характеризующие вероятность соответствия проиндексированных текстовых ресурсов запросу пользователя. Преимущество в том, что модель располагает документы в порядке убывания «вероятности оказаться релевантным». На практике эти модели не получили большого распространения. В рамках моделей вычисляется условная вероятность события, что документ соответствует данному запросу, то есть P(d \ q) Р (документ D релевантен! запрос Q) [13,36]. Для расчета используется формула Байеса и то, что вероятность P(q) постоянна на протяжении всего поиска. Таким образом, P(d | q) = aP(d)P(q | d), a = const. В качестве факторов, влияющих на безусловную релевантность документа P{d), можно рассматривать его размер, источник, дату публикации. Вероятность запроса q при условии релевантности документа d зависит главным образом от веса ключевых слов запроса в документе d. Для ее расчета обычно принимают гипотезу независимости слов документа и запроса, что приводит к следующей формуле релевантностей R(d\q) = \ogP{d) + Y^ogP{wkd), к где P(wk | d) — вероятность появления к -го слова запроса в документе d.

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

IV. Алгоритмы поисковой системы [22-25]. Поисковая система (ПС) оперирует со структурами данных и исполняет алгоритм одного из четырех классов. Три из них требуют «индексирования», предварительной обработки документов, при котором создается вспомогательный файл, т.е. «индекс», который позволяет упростить и ускорить поиск. Сюда относятся алгоритмы инвертированных файлов, суффиксных деревьев, сигнатур. В случае, когда предварительный этап индексирования отсутствует и поиск происходит при помощи последовательного просмотра документов, поиск называется прямым. Прямой поиск развивается [39,40], применяется в Internet, например, норвежской поисковой системой Fast (www.fastsearch.com). Кроме того, есть множество программ, комбинирующих индексный поиск для нахождения блока текста с дальнейшим прямым поиском внутри блока. Преимуществом прямых алгоритмов является работа непосредственно с оригиналом документа, в то время как алгоритмы индексирования влекут за собой упрощение терминов, а, следовательно, потерю информации.

По типу логической структуры индекса ПС можно разделить на категории: инвертированные файлы (ИФ) [22 - 25], сигнатурные файлы (СФ) [23 - 25].

Инвертированные или обратные файлы (ИФ) [22] по своей структуре аналогичны предметному указателю книги и состоят из словаря и списков вхождений ключевых слов в документы, которые называются инвертированными списками или пост-листами. В случае инвертирования «-грамм, словарь содержит всевозможные п-граммы (подстроки фиксированной длины), встречающиеся в тексте, причем для каждой «-граммы, как и в случае ключевых слов, хранится список вхождений. Процесс поиска заключается в считывании инвертированных списков, номеров документов, позиций слова в документах и соответствующем ранжировании полученной выборки. Чтобы сэкономить на дисковом пространстве и ускорить поиск, обычно прибегают к двум приемам. Во-первых, чем подробнее задана пози-^ ция, тем больше места потребуется для хранения инвертированного файла (инвертированный файл может хранить номер слова, смещение в байтах от начала текста, цвет, размер шрифта). Чаще указывают только номер документа и число употреблений этого слова в нем. Именно такая упрощенная структура считается основной в классической теории информационного поиска. Во-вторых, используется сжатие путем упорядочения позиции для каждого слова по возрастанию адресов и для каждой позиции хранится не полный ее адрес, а разница от предыдущего. Дополни-4 тельно на разностный способ хранения адресов накладывают какой-нибудь способ упаковки (арифметический алгоритм Хафмана).

Сигнатурные файлы (СФ) основаны на преобразовании документа в битовый массив - сигнатуру. Обычно используется массив постоянного размера, у которого /-ый бит равен 1, если какой-либо минимальный индексируемый элемент документа («-грамма, основа, или нормальная форма слова) преобразуются хеш-функцией И/(м>) в число /. СФ задумывались как альтернативный индекс, более компактный чем ИФ. Поиск в СФ во многом аналогичен поиску в ИФ. Если запрос содержит ключевые слова м?х, м>2, то поиск заключается в считывании всех сигнатур, у которых хотя бы один из битов с номерами /г/^,), /г/(и>2), Ь/(м>3),. ,/г/(и^) равен 1. Множество сигнатур однозначно идентифицирует множество документов, однако в силу неоднозначности хеш-функции далеко не каждый такой документ содержит хотя бы одно ключевое слово (или п-грамму) запроса. Окончательное формирование и ранжирование выборки происходит после считывания и обработки текста соответствующих документов.

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

41]. Основным элементом любой задачи распознавания изображений является определение, относятся ли входные данные изображения к классу, который представляет данный эталон. Распознавание - чаще всего конечный этап обработки, лежащий в основе процессов интерпретации и понимания. Входными для распознавания являются изображения, выделенные в результате сегментации и, частично, отреставрированные. Они отличаются от эталонных геометрическими и яркостными искажениями, а также сохранившимися шумами. В [42 - 49] представлена различная типология методов распознавания образов, состояние проблем распознавания изображений освещено в [41, 50-52], методы стохастической геометрии в распознавании освещены в [53], технические аспекты идентификации отпечатков пальцев представлены в [54 - 56]. Использование для распознавания рядов Фурье описано в [57], корреляционные методы освещены в [58 - 60], нейросетевые методы в [61,62]. По классификации [63] методы распознавания представляются схемой, представленной на рис. 5.

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

Рис. 5.

Первая группа методов - геометрическая. На основе анализа расположения точек в пространстве объектов, предлагается несколько алгоритмов обучения и решающих правил. Обучение в этих методах сводится к линейной или нелинейной деформации пространства признаков. Геометрический метод распознавания основан на использовании некоторой функции подобия (принадлежности) £ объекта данному классу. Эта функция определяет некоторую меру близости объекта Ь] с координатами х = (х,, х2,.хп) к множеству эталонов ут = {у™За меру близости принимается среднеквадратическое расстояние з(х,,-). Мефика </в каж

М т=1 дом отдельном случае может быть разной, но должна удовлетворять условиям: с!(а,Ь) = с1(Ь,а); ¿(а,с)<с1(а,Ь)+с1(Ь,с); с!(а,Ь)> 0; с1(а,Ь) = 0 при а = Ь. Обучение трактуется как задача ^ } где У «Г /й и V т ) эталон т-го класса. Как правило, рассматривается класс метрик вида Р

МКЕ со](ап -Ьп)2. Требуется найти коэффициенты со„, чтобы последнее вы

Щ ражение стало минимальным, физический смысл коэффициентов чаще всего имеет эвристическое содержание. В общем случае схема распознавания весьма сложна. Как отмечается в [63], вследствие сложности вычислений геометрические методы обучения не находят широкого применения, а служат в основном для интерпретации других методов. Одной из наиболее распространенных концепций распознавания является байесовская, заимствуемая из теории статистических решений. Применительно к задаче распознавания эта концепция может быть сформулирована следую-ф щим образом. Имеется полная группа несовместных гипотез, роль которых при распознавании выполняют образы: А1,А2,. Д,. Ам . Известны априорные распределения вероятностей этих гипотез, то есть известно, с какой вероятностью появляется м данный образ: Р(Д), р(а2),., р(ам), причем ^/5(д ) = 1. В результате опыта на1 блюдается какое-то событие у. В данном случае таким событием является появление конкретной реализации объекта. Требуется определить, как изменяется вероятность появления образов после этого опыта. В общем случае считаются заданными услов-^ ные вероятности Р(&у / Д.) / = 1,2,., м, ] = 1,2,., Г, требуется определить вероятность р{А1/Ь]). В [63] отмечается, что реализовать строго байесовский алгоритм обучения практически невозможно, поскольку для этого требуется запоминать многомерные законы распределения вероятностей, которые в общем случае имеют бесконечные интервалы. На практике многомерные законы аппроксимируются более простыми функциями, которые легко запомнить в вычислительной машине. Тогда, по существу, получается метод дискриминантных функций. На практике могут применяться другие частные методы типа корелляционного и регрессионного. Не детализируя базовые соотношения байесовского метода [63], остановимся на основных положениях метода дискриминантных функций. Он имеет две модификации: метод ► решающих функций и метод потенциальных функций на единой основе. Считается, что существуют поверхности условных плотностей распределения вероятностей Р(х/Д.) = Ра (х), то есть вероятностей появления значений признака х при условии, что объект принадлежит к классу Д . Для упрощения многомерную функцию аппроксимируют функциями, которые называются решающими, потенциальными или дискриминантными функциями £, (*)• Практически задача заключается в разработке методов построения потенциальных функций, если задан набор эталонов или обучающая последовательность. Сами функции должны выбираться так, чтобы облегчить процесс их практического получения. При детерминированном распознавании задается некоторое количество эталонов и требуется любой новый объект отнести к определенному классу. Здесь предполагается существование разделительных поверхностей. На этом множестве эталонов определяются потенциальные функции £,(х). Разделительная поверхность определяется из уравнений gi(x) = Sj(x\ 3 •

В методе дискриминантных функций в качестве решающего правила выбирают знак разности = g¡ - gj. Если эта величина положительна, то объект относят к классу если отрицательна - к классу /. Разделяющие функции, как правило, полагаются линейными, квадратичными или кусочно-линейными. Соответственно, различают линейное, квадратичное и кусочно-линейное распознавание. Для линейного распознавания в общем случае разделяющая поверхность может быть записана в виде g(x) = со,х, + со2х2 +. + а>пхп + соя+1. Процесс обучения заключается в определении коэффициентов со. Общая черта разновидностей метода дискриминантных функций -некоторая неопределенность при выборе аппроксимирующих функций и эталонных последовательностей.

К числу распространенных методов распознавания относятся нейросетевые методы, базирующиеся на применении различных типов нейронных сетей (НС). НС применяются для извлечения ключевых характеристик (признаков) образов, для классификации самих образов или их характеристик [61,64-68]. НС состоит из элементов, называемых формальными нейронами, которые просты и связаны с другими нейронами. Все элементы НС могут функционировать параллельно, повышая эффективность обработки изображений. НС позволяют эффективно решать различные задачи распознавания, предоставляя мощные, гибкие и универсальные механизмы обучения, что является их преимуществом перед другими методами [69]. Нейрон характеризуется своим текущим состоянием по аналогии с нервными клетками мозга, может быть возбужден или заторможен, имеет несколько входов (денд-риты) и один выход (аксон). Он обладает группой синапсов - однонаправленных входных связей, соединенных с выходами других нейронов. По аксону сигнал возбуждения или торможения поступает на синапсы следующих нейронов:

Формальный нейрон

Сома

Л finer) V

Дентригы

Аксон

Рис. 6.

На рис. 6 - входные сигналы; w, - весовые коэффициенты; NET - взвешенная сумма входных сигналов (значение передается на нелинейный элемент); 0 - пороговый уровень нейрона; F{net) - нелинейная функция активации. Функционирование нейрона определяется формулами NET = ^jwixl, OUT = F(NET-Q). Некотоi рые виды функций активации представлены ниже [70]:

Функции активации а б в г а) Жесткая ступенька; б) сигмоида в) Гиперболический тангенс г) Пологая ступенька

Рис. 7

0, NET < 0,

Нейроны с жесткой ступенькой OUT = j ^ ^^ ^ ^ (рис. 7а) требуют малых вычислительных затрат, но не позволяют моделировать схемы с непрерывными сигналами. Логистическая функция (сигмоида) OUT =-—(рис. 76)

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

NET -NET е — е ческий тангенс OUT = -—:-— (рис. 7г) применяется для сетей с непрерывные +е~ ми сигналами, симметричен относительно точки (0, 0), в этом преимущество по сравнению с сигмоидой, принимает значения различных знаков, что оказывается выгодным для ряда сетей. Пологая ступенька

OUT =

0, NET< 0, NET -0

-, 0 < NET < 0 + А легко рассчитывается, но имеет разрывную

1, NET>Q + A.

NET производную, что усложняет алгоритм обучения. SOFTMAX OUT = NET , сум

2> ' / мирование производится по всем нейронам данного слоя сети. Такой выбор функции обеспечивает единичную сумму выходов слоя при любых значениях сигналов NETt данного слоя, что позволяет ее трактовать как вероятность события из совокупности, образующей полную группу. Всем НС присущ принцип параллельной обработки сигналов, который осуществляется путем объединения большого числа нейронов в так называемые слои и соединения различных слоев. Пример простейшей НС - трехнейронный перцептрон (рис.8):

Трехнейронный перцептрон

Рис. 8.

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

Двухслойный перцептрон

Рис. 9.

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

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

Изображение (а) и его иерархическое структурное описание (б) с окружность

-0 я \ дуга а дуга b

Изображение О прямоугольник H отрезок отрезок отрезок отрезок прямой с прямой й/ прямой е прямой j а) б)

Рис. 10.

Совокупность геометрических характеристик изображения и множество правил их соединения представляют собой специальный язык PDL (picture description language). Его синтаксис [72] имеет графическую интерпретацию, на основе которой строится распознавание. Рассматриваемый язык используется в рамках иерархического описания изображений. Простейшие элементы, из которых строятся слова, а затем и предложения, принято называть непроизводными элементами. Правила конструирования композиций из непроизводных элементов задаются с помощью специальных грамматик, называемых грамматиками описания изображений. Например, для т классов изображений У1,У2,.,Ут можно построить т соответствующих грамматик (7,, (72,.,(7т, таких, что цепочки, порожденные грамматикой будут представлять изображения только из класса . Тогда для произвольного изображения, описываемого цепочкой X, задача распознавания сводится к вопросу: верно ли, что X € Ь{р] \ ] -1,2,.т. Алгоритм распознавания имеет вид X е V., если Ф

X и X <£ Iгде ь[р]) - язык, порожденный грамматикой Самый простой способ распознавания состоит в сопоставлении входной цепочки, соответствующей распознаваемому изображению, с эталоном каждого образа. Цепочка X относится к тому образу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с цепочкой X. В этом случае требуется либо точное совпадение цепочки X с эталоном, либо выполнение подходящего критерия согласования. Подход целесообразно применять только когда существует гарантия того, что непроизводные элементы могут быть легко выделены и распознаны, а выделение и распо знавание непроизводных элементов существенно проще распознавания всего изображения в целом. Помимо обозначенных выше, основы существующих методов распознавания составляют схемы, использующие: локальные адаптивные элементы [73], выделение ключевых точек контуров [74], параметрический поиск [75]. Применяются: симультанная модель распознавания [76]; алгоритмы, основанные на вычислении оценок [77]; стохастические методы [53]; алгоритмы на основе решающих правил [78]. Для решения прикладных задач распознавания успешно используются методы, основанные на комбинаторном анализе признаковых описаний объектов [79].

Можно утверждать [63], что в охарактеризованных методах распознавания имеют место неопределенности в построении распознающих схем и в выборе эталонных последовательностей, при этом схемы отличает существенная вычислительная сложность. Целесообразно исследовать возможность построения единого метода, объединяющего алгоритмы поиска и задач распознавания, в качестве основы в дальнейшем рассматривается использование алгоритмов сортировок.

Как отмечалось, к одной из целей диссертационной работы относится распространение схемы поиска на распознавание и идентификацию изображений. В 4 этом контексте необходимо отметить уже существующие подходы, которые в основном решают обратную задачу - применения известных методов распознавания к поиску оцифрованной графической, а также аудио и видео информации [80,81]. Отличие излагаемого в диссертации метода от рассматриваемых известных подходов [82, 83] заключается в том, что данные подходы используют методы адаптивного распознавания образов (APRP) и семантические сети, опираются на теорию нейронных сетей и позволяют осуществлять бинарную индексацию, при которой ф размер индекса даже при обработке неструктурированной информации не превышает 30% от размера исходных данных. При этом на этапе выполнения запросов исключается большая часть нерелевантных документов; процент документов, признанных нерелевантными, зависит от эффективности применяемых алгоритмов анализа, в результате гарантируется лишь отсеивание большей части исходной информации. В то же время излагаемый метод, напротив, схему поиска распространяет на распознавание, при этом предоставит детерминированный результат как поиска, так и распознавания [84, 85].

VI. Схемы сжатия на основе кодирования. Одной из задач диссертационной работы является применение конструируемой схемы поиска к распознаванию и сжатию плоских растровых изображений. Необходимо соотнести подход с известными схемами сжатия. Растровая графика широко используется для представления изображений в цифровом виде. Задача сжатия графических данных возникает в связи с тем, что изображения в несжатом виде занимают большой объем памяти. Статические растровые изображения представляют собой двумерный массив чисел. Изображения можно разделить на две группы - с палитрой и без нее. У изображений с палитрой в пикселе хранится число - индекс в некотором одномерном векторе цветов, называемом палитрой. Чаще всего встречаются палитры из 16 и 256 цветов. Основными техническими характеристиками схем сжатия и результатов их работы являются: а) степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков; Ь) скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока до получения из него эквивалентного выходного потока; с) качество сжатия - величина, показывающая насколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму. Все методы кодирования и сжатия изображений можно разделить на две категории [86, 87]: 1) обратимое сжа-4 тие или сжатие без потерь (восстановленное изображение полностью идентично исходному); 2) необратимое сжатие (при восстановлении данных не происходит полное восстановление изображения). Сжатие с потерями возможно, когда допустимы некоторые искажения. Характерными форматами сжатия с потерей информации являются JPG для графических данных, .MPG для видеоданных, .МРЗ для звуковых данных. Характерными форматами сжатия без потери информации являются .GIF, .TIP, .PCX для графических данных, .AVI для видеоданных, .ZIP, .ARJ, .RAR, * .LZH, .LH, .CAB для любых типов данных. Для сжатия информации алгоритмы первой группы используют статистические свойства обрабатываемых данных [88].

Групповое сжатие (RLE) - это кодирование серий последовательностей (Run Length Encoding - RLE) [89,90]. При таком подходе изображение вытягивается в цепочку байт по строкам растра. Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных. Любой последовательности повторяющихся входных символов ставится в соответствие набор из трех выходных символов: первый - байт префикса, говорящий о том, что встретилась входная повторяющаяся последовательность, второй - байт, определяющий длину входной последовательности, третий - сам входной символ <prefix, length, symbol>. Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета.

Алгоритм LZW [91] использует дерево для представления и хранения цепочек. Это достаточно сильное ограничение на вид цепочек, и не все одинаковые подцепочки в изображении будут использованы при сжатии. В излагаемом алгоритме выгодно сжимать даже цепочки, состоящие из 2 байт. Процесс сжатия состоит в следующем. Считываются последовательно символы входного потока и проверяются, есть ли в созданной таблице строк такая строка. Если строка есть, то считывается следующий символ, а если строки нет, то заносится в поток код для предыдущей найденной строки, и заносится строка в таблицу и начинается поиск снова. Особенность LZW заключается в том, что для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен так, что можно восстановить таблицу строк, пользуясь только потоком кодов. Для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.

Алгоритм Хаффмана [92 - 94] при помощи составления таблицы вероятностей символов входного потока формирует бинарное дерево, на основе которого символы входного потока заменяются последовательностями из 0 и 1. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину. Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Изначально алгоритм создавался для сжатия текстов, но он успешно применяется и для сжатия изображений. Основной идеей этого алгоритма является замена данных более эффективными кодами. Каждой уникальной величине присваивается двоичный код, причем длина этих кодов различна: чем чаще используется величина, тем короче код. Присвоения хранятся в таблице перекодировки, которая записана перед самими запакованными данными. Сжатие с помощью кодов переменной длины имеет некоторые недостатки. Наиболее значимые из них - это достаточно медленные процессы компрессии и декомпрессии, а также чувствительность к измененным битам, так как замена одного бита сделает невозможной декомпрессию всей оставшейся части файла, а не только этого символа. Достоинствами метода Хаффмана являются достаточно высокая скорость и хорошее качество сжатия. Недостатком - зависимость степени сжатия от близости вероятностей символов к отрицательным степеням 2.

Алгоритм арифметического кодирования [95 - 98] имеет схожую с кодированием Хаффмана функцию, но обладает несколькими свойствами, которые дают возможность достичь значительного превосходства в сжатии. Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия. Разница метода Хаффмана и арифметического метода [99 -101] становится заметна тогда, когда частота встречаемости символов во входном сообщении сильно отличается друг от друга. Эксперименты на различных типах данных показывают, что арифметическое кодирование дает результаты не хуже, чем кодирование Хаффмана. В силу того, что объем вычислений, необходимых при работе алгоритма арифметического кодирования, значительно выше, чем при кодировании по методу Хаффмана, он работает медленнее. Арифметическое кодирование может быть использовано в тех случаях, когда степень сжатия важнее, чем временные затраты на сжатие информации [102, 103]. В большинстве современных архиваторов для сжатия без потерь используется не один, а два и более алгоритмов кодирования [103].

Сжатие с потерями основано на том, что допустимо некоторое искажение цвета и изменение мелких деталей. Сжатие на основе дискретного косинусного преобразования (ДКП) реализовано в алгоритмах JPEG, Motion JPEG, Н-263. Используется во множестве форматов изображений и видео. Формат JPEG фактически является единственным общепринятым стандартом сжатия изображений с потерями. ДКП является алгоритмом кодирования с преобразованием. Методы, в основе которых лежат алгоритмы кодирования с преобразованием, показывают более высокие степени сжатия изображений по сравнению с другими методами кодирования при хорошем визуальном качестве восстановленного изображения. Фрактальные алгоритмы сжатия основаны на поиске подобных областей изображения, они намного эффективней сжатия на основе ДКП, особенно для больших степеней сжатия. Реализованы в форматах FIF, IFS, Sting (в последнем случае в комбинации с волновым преобразованием). Главный недостаток этого подхода - медленная процедура сжатия, в которой для каждого фрагмента изображения (ранговой области) производится поиск наиболее похожего фрагмента большего размера (доменной области). В настоящее время ведутся исследования по ускорению процесса поиска подходящих областей. Распаковка изображения происходит очень быстро. Это делает алгоритм удобным, например, для размещения изображений в сети Интернет или длительного хранения в базах данных, но мало подходящим для бытового использования (например, сжатия отсканированных изображений) и совершенно непригодным для использования в цифровых фотокамерах. Сжатие на основе волнового (wavelet) преобразования по эффективности примерно соответствует фрактальному сжатию. Алгоритм ориентирован на цветные и черно-белые изображения с плавными переходами. Идея алгоритма заключается в том, что в файл сохраняется число между средними значениями соседних блоков в изображении, которое обычно принимает значения, близкое к 0 [86]. Числа a2i и а2м можно представить в виде bu=0,5(a2¡ + а2М) и b2i=0,S(a2¡ -a2i+¡). Аналогично последовательность a¡ может быть попарно переведена в последовательность bl2r Значения b2i достаточно близки к 0. Операция повторяется путем рассмотрения Ьи как a¡. Данные действия выполняются рекурсивно. Полученные коэффициенты, округляя до целых и сжимая, можно поместить в файл. Сжатие и распаковка занимают приблизительно одинаковое время. Алгоритм реализован в форматах LuraWave, DjVu, JPEG 2000.

VII. Тестовое диагностирование цифровых устройств. Конструируемые в дальнейшем схемы распространяются на поиск неисправностей, поэтому потребуется обзорная информация на эту тему. Одной из разновидностей диагностирования цифровых узлов и блоков является тестовое диагностирование [104,105], применение которого на этапе проектирования и изготовления цифровых узлов позволяет определить правильность их функционирования и осуществить процедуру поиска неисправностей, цель которой определить место и вид неисправности. Тестовое диагностирование предполагает подачу на контролируемое устройство специальных проверяющих воздействий (тестов), позволяющих по его выходным сигналам путем сравнения полученных результатов с заранее известными эталонами выявить заданный класс неисправностей в устройстве. Тесты подразделяют на проверочные и тесты поиска дефекта, последние позволяют производить локализацию неисправностей с заданной глубиной. Для проведения тестового диагностирования цифровое устройство должно быть выведено из рабочего состояния и переведено в режим тестирования. Проблемы, связанные с тестированием, описаны в [106 - 108], в [109] рассматривается возможность одновременности поиска ошибок в режиме on-line и тестирования при диагностическом проектировании. Состояние разработки и исследования средств диагностики излагается в [109-112]. Известны оптимальные алгоритмы диагностики, основанные на сокращенных переборах возможных многошаговых вариантов поиска. Эти алгоритмы разработаны для диагностики уже изготовленных, находящихся в эксплуатации объектов, опираются на методы динамического программирования, метод ветвей и границ, на их сочетание [113]. При разработке тестовой диагностики возникает сложность в определении эталонных реакций, в определении оптимального числа контрольных точек для снятия выходной реакции диагностируемой цифровой схемы. Это можно сделать, либо создавая прототип разрабатываемого цифрового устройства и проводя его диагностику аппаратурными методами, либо осуществляя моделирование на ЭВМ как цифрового устройства, так и процесса диагностики. Классификация методов тестовой диагностики может быть представлена следующей диаграммой.

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

Рис. 11.

Классическая стратегия тестирования цифровых схем основана на формировании тестовых последовательностей, позволяющих обнаруживать заданные множества их неисправностей. Для проведения процедуры тестирования хранятся как сами тестовые последовательности, так и эталонные выходные реакции схем на их воздействие. В процессе тестирования при соответствии полученных реакций схемы эталонным она считается исправной, в противном случае схема содержит неисправность и находится в неисправном состоянии. Проблема тестового диагностирования цифровых схем (ЦС) возникает на различных этапах их производства и эксплуатации и включает взаимосвязанные задачи. Первая из них заключается в определении состояния исследуемой схемы. Если установлено, что схема неисправна, то решается вторая задача: осуществляется поиск неисправной схемы, цель которого - определение места и вида неисправности. Неисправности ЦС появляются в результате неисправности компонентов, таких, как логические элементы, элементы памяти и др. Кроме того, причиной неисправностей могут быть разрывы или короткие замыкания в межкомпонентных соединениях, нарушение условий эксплуатации схемы, наличие ошибок при проектировании и производстве и ряд других факторов. Для реализации генератора тестовой последовательности желательно Л использовать простейшие методы, позволяющие избежать сложной процедуры их синтеза. К ним относятся следующие алгоритмы: 1) формирование всевозможных входных тестовых наборов, т.е. полного перебора двоичных комбинаций, в результате применения которых генерируются счётчиковые последовательности; 2) формирование случайных тестовых наборов с требуемыми вероятностями единичного и нулевого символов по каждому входу цифровой схемы; 3) формирование псевдослучайных тестовых последовательностей. Основным свойством распространён-Р ных алгоритмов формирования тестовых последовательностей является то, что в результате их применения воспроизводятся последовательности очень большой длины. Поэтому на выходах проверяемой цифровой схемы формируются её реакции, имеющие ту же длину. Естественно возникают проблемы их запоминания и хранения. Простейшим решением, позволяющим значительно сократить объём хранимой информации об эталонных выходных реакциях, является получение интегральных оценок, имеющих меньшую размерность.

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

VIII. Алгоритмы сортировки. В диссертационной работе конструктивной основой схемы поиска является алгоритм сортировки. Сортировка [7, 8, 75] обеспечивает эффективную обработку в больших наборах данных, позволяет представить массивы данных в форме, удобной для анализа, группировать элементы по некоторому признаку [114, 115]. Сортировки делятся на внутренние и внешние [78]. Внутренние сортировки выполняются в оперативной памяти. Внешние сортировки приемлемы для файлов данных, которые превосходят размер основной памяти, и ^ поэтому должны в течение процесса сортировки располагаться на устройствах внешней памяти. В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешние устройства. Во всех внешних сортировках используются внутренние сортировки. Временная сложность алгоритмов в дальнейшем будет измеряться количеством последовательных шагов их выполнения, временная сложность сортировки измеряется числом последовательно выполняемых сравнений, при этом для параллельных алгоритмов она будет оцениваться на модели неветвящихся параллельных программ [116,117] без учета обмена. Временная сложность параллельной сортировки будет обозначаться T(R) = k т, где т - время бинарного сравнения, к - количество последовательных сравнений, R - число используемых процессорных элементов (при описании параллельных сортировок иногда их называют компараторами).

Сортировка вставками. Элементы просматриваются по одному, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов (временная сложность - Г(1) = 0(N2), где 0(f) - класс функций, растущих не быстрее /). Усовершенствованием сортировки вставками является сортировка Шелла [7] - многопроходная сортировка, при которой список разбивается на подсписки, каждый из которых сортируется отдельно (сортировкой вставками), причем на каждом проходе число подсписков уменьшается, а их длина растет.

Обменная сортировка [7, 118, 119]. Предусматривает систематический обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется. Выделяют обменную сортировку с выбором ("метод пузырька"), поразрядную сортировку, обменную сортировку с разделением ("быстрая сортировка" Хоара), обменная сортировка со слиянием (параллельная сортировка Бэтчера). Пузырьковая сортировка (Г(1) = 0(N2)) сравнивает элементы попарно, переставляя между собой элементы тех пар, порядок в которых нарушен. Быстрая сортировка Хоара представляет собой рекурсивный алгоритм, который выбирает в списке осевой элемент, а затем разбивает список на две части, состоящие из элементов соответственно меньших или больших выбранного. Поразрядная сортировка (Г(1) = O(N)) [9] выполняется при условии, что длина ключа невелика по сравнению с числом ключей. Список разбивается на стопки и при каждом проходе используется отдельная часть ключа. Сортировка Бэтчера [7] производит параллельное слияние пар отсортированных подпоследовательностей (T(N) = 0(logj N)). Сортировка слиянием (T(\) = 0(N log2 N)) берет два уже отсортированных списка и создает, сливая их, новый отсортированный список.

Сортировка выбором [7]. Из последовательности выделяется наименьший (наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся, процесс повторяется до тех пор, пока все элементы последовательности не будут отсортированы.

Пирамидальная сортировка (T(\) = 0(N log2W)) строит бинарное дерево, значение каждого узла в котором превышает значение потомков. В результате наибольший элемент списка помещается в корень, при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Процесс повторяется, пока все элементы не окажутся в отсортированном списке.

Сортировка подсчетом [7, 120]. При сортировке подсчетом (Т(\) = 0(N2)), каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей.

Современные методы последовательных сортировок обсуждаются в [121 -124]. Кроме схемы параллельной сортировки Бэтчера [7] (T(N) = 0(1 og* N)), можно отметить параллельные варианты сортировок подсчетом [120] (T(N2 /2) = 0(1)) и слиянием [125-127] (T(N2/4)=0(log27V)). Параллелизм сортировок обсуждается в [118, 128- 130].

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

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

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

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

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

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

3. Сконструировать схему, позволяющую выполнить поиск по математическим условиям чисел и векторов как минимумов нормы разности между искомым элементом многомерного пространства и эталонным элементом из этого пространства.

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

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

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

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

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

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

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

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

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

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

Конкретно, научная новизна характеризуется следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы

1. В отделе автоматизации библиотеки Таганрогского государственного педагогического института при создании электронной библиотеки и информационного центра ГОУВПО «ТГПИ».

2. В госбюджетной ПИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.

3. В учебном процессе кафедры информатики ГОУВПО «Таганрогский государственный педагогический институт» в рамках курсов «Информатика», «Информационные системы», «Информационные технологии в математике», «Элементы абстрактной и компьютерной алгебры», «Использование информационных и коммуникационных технологий в образовании».

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

- I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г.);

- 1Х-Х1 международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2003-2006 гг.);

- IV международной научно-практической конференции по программированию УкрПРОГ' 2004 (Украина, Киев, 2004 г.)

- международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.)

- международной научной конференции «Оптимальные методы решения научных и практических задач» (Таганрог, ТРТУ, 2005 г.)

- семинарах «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2001 - 2007гг.).

Публикации. По материалам диссертационной работы опубликовано 14 печатных работ общим объёмом 14,4 п. л., в том числе, 1 статья в журнале из списка допущенных ВАК РФ.

Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 5 приложений. Основное содержание работы изложено на 156 страницах, включая список литературы из 149 наименований.

3.10. Выводы

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

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

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

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

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

142

ЗАКЛЮЧЕНИЕ

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

Работа включает следующие научные результаты.

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

2. Сконструирована схема с использованием обработки числовых выражений для поиска данных строкового и вещественного типа на основе подстановки индексов отсортированных элементов.

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

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

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

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

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

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

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

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

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

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

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

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

Практическое использование результатов работы.

1. В отделе автоматизации библиотеки Таганрогского государственного педагогического института при создании электронной библиотеки и информационного центра ГОУВПО «ТГПИ».

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.

3. В учебном процессе кафедры информатики ГОУВПО «Таганрогский государственный педагогический институт» в рамках курсов «Информатика», «Информационные системы», «Информационные технологии в математике», «Элементы абстрактной и компьютерной алгебры», «Использование информационных и коммуникационных технологий в образовании».

145

1. Dumi A.1. Computers & Automation, 5, 12 (December 1956), P. 6-9.

2. Peterson U.U. IBM J.Research & Development, 1 (1957), P. 130-146.

3. But E.D. Information and Control, 1 (1958), P. 159-164.

4. Duglas A.C. Comp.J., 2 (1959), P. 1-9.

5. Ajverson K.E. A Programming Language (New York: Wiley, (1962)), P. 133158

6. Buhholxc B. IBM Systems J., 2 (1963), P. 86-111.

7. Кнут Д. Искусство программирования. Т.З. Сортировка и поиск (второе издание). М.: Вильяме, 2000. - 844 с.

8. Вирт Н. Алгоритмы и структуры данных. М.; Мир, 1989. - 360 с.

9. Макконнелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002.-304 с.

10. Ю.Сизиков Е.В. Структура поискового индекса, основанного на нечетком сравнении терминов // Перспективные информационные технологии и интеллектуальные системы, № 3 (19), 2004, http://pitis.tsure.ru/

11. П.Задорожный В.В. Идентификация по отпечаткам пальцев. Часть 1. / PC Magazine.Russian Edition № 1. - 2004.

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

13. Аграновский A.B., Арутюнян Р.Э., Хади P.A. Современные аспекты проблемы поиска в текстовых базах данных // Телекоммуникации. №3. - 2003. - С. 25-30.

14. Бойцов Л.М., Использование хеширования по сигнатуре для поиска по сходству // Прикладная математика и информатика. М.: Изд-во факультета ВМиК.-МГУ.-№ 8.-2001.-С. 135-154

15. Кизянов А.Ф. Разработка и исследование методов и средств полнотекстового индексирвания информации с учетом морфологии естественногоязыка / Автореферат диссертации на соискание ученой степени кандидата технических наук. Таганрог: ТРТУ. - 2005. - 16 с.

16. П.Кутовенко А. Интернет-поиск: изображения. http://msk.nestor.minsk.bv/kg/2006/47/kg64718.html

17. Кантор И. Поиск. Строки и последовательности. Точный подстроки в строке, http://algolist.manual.ru/search/esearch/

18. Аграновский А.В., Арутюнян Р.Э. Алгоритмы поиска и рубрикации текстовых документов // Телекоммуникации. №9. - 2003. - С. 2-7.

19. Некрестьянов И., Пантелеева Н. Системы текстового поиска для Веб // Программирование. -№28(4). 2002. - С. 207-225.

20. Захаров Д.Е., Разработка интеллектуальной нейросетевой поисковой системы «Нейропоиск», тезисы молодежной научно-технической конференции «Наукоемкие технологии и интеллектуальные системы -2002», С. 32-38

21. Озкарахан Э., Машины баз данных и управление базами данных, М.: Мир 1989.-696 с.

22. Christos Faloutsos and Douglas Oard. Survery of Information Retrieval and Filtering Methods. University of Maryland.

23. C.J. van Rijsbergen. Information Retrieval. London, Butterworths, 1979. (http://www.dcs.glasgow.ac.uk/Keith/Preface.html)

24. Бондарев B.M. Основы программирования. Ростов-на-Дону: Феникс, 1997.-384 с.

25. Воробьев Н.Н. Числа Фибоначчи. Популярные лекции по математике. -М.: Наука, 1969.

26. Р.Альсведе, И.Вегенер. Задачи поиска. М.: Мир, 1982.

27. Hellerman H., Digital. Computer System Principles. McGraw-Hill, 1967.

28. Sunday D.M. A very fast substring search algorithm // Communications of the ACM. Vol. 33. - №. 8. - August 1990. - P. 132-42.

29. Gonnet G.H., Baeza-Yates R. Handbook of Algorithms and Data Structures in Pascal and С . Chapter 7. Text algorithms. (2nd edition). Wokingham UK: Addison-Wesley, 1991.-P. 251-88.

30. Axo A.B. Алгоритмы для поиска подобных строк. -Amsterdam: ESP, 1990.

31. Пилкбауэр К. Обучение примерно похожим алгоритмам // SP, NY- 1992.

32. Boyer R.S., Moore J.S. A fast string searching algorithm // Comm. ACM. Vol. 20. - №10. - Oct. 1977. - P. 762-72.

33. Salton G. and McGill. M. J. Introduction to modern Information Retrieval // McGraw-Hill Computer Science Series. New York: McGraw-Hill, 1983.

34. Аграновский A.B., Арутюнян Р.Э. Способы индексации и поиска документов в интернет-порталах // Труды X Всероссийской научно-методической конференция «Телематика-2003». Санкт-Петербург. 2003. - т.1. - С. 204-206.

35. Salton G., Fox Е., Wu Н. Extended Boolean information retrieval. Cornell University, 1982.

36. Karen Sparck Jones. A Statistical Interpretation of Term Specificity and Its Application in Retrieval // Journal of Documentation. 1972.

37. Robert Sedgewick. Algorithms in С++. Addison-Wesley, 1992.

38. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ-МЦНМО. 2000 (http://www.ozon.ru/?context=detail&id=l 14200).

39. Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. М: Машиностроение, 1990. - 320 с.

40. Барабаш Ю.Л. Вопросы статистической теории распознавания. // Под ред. Б.В. Барского. М.: Советское радио, 1967. - 400 с.

41. Васильев В.И. Распознающие системы: Справочник. Киев: Наукова думка, 1983. -230 с.

42. Горелик А.Л., СкрипкинВ.А. Методы распознавания. М.: Высшая школа, 1984.-219 с.

43. Дуда Р., ХартП. Распознавание образов и анализ сцен. -М.: Мир, 1978. -510 с.

44. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989. - 367 с.

45. Темников Ф.Е. Теоретические основы информационной техники. М.: Энергия, 1979.-511 с.

46. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. -411 с.

47. Уинстон П. Искусственный интеллект. М.: Мир, 1980. - 520 с.

48. Рудаков П.И., Сафонов В.И. Обработка сигналов и изображений. М.: ДИАЛОГ-МИФИ, 2000. - 416 с.

49. Petrou М. Learning in Pattern Recognition. Lecture Notes in Artificial Intelligence Machine Learning and Data Mining in Pattern Recognition, 1999, P. 1-12.

50. Plamondon R, Srinari S. On-Line and Off-Line Handwriting Recognition: A Comprehensive Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, № 1, January 2000.

51. Федотов Н.Г. Методы стохастической геометрии в распознавании образов. М.: Радио и связь, 1990. - 299 с.54.3адорожный В.В. Идентификация по отпечаткам пальцев. Часть 2. // PC Magazine. Russian Edition. № 2. - 2004.

52. Nanni L., Lumini A. A novel method for fingerprint verification that approaches the problem as a two-class pattern recognition problem. Neurocomputing, Volume 69, Issues 7-9, March 2006, P. 846-849.

53. Nanni L., Lumini A. Two-class fingerprint matcher. Pattern Recognition, Volume 39. Issue 4. April 2006. - P. 714-716.

54. Mills R.L. Novel method and system for pattern recognition and processing using data encoded as Fourier series in Fourier space. Engineering Applications of Artificial Intelligence, Volume 19, Issue 2, March 2006. - P. 219-234.

55. Гиренко А.В., Ляшенко В.В., Машталир В.П., Путятин Е.П. Методы корреляционного обнаружения объектов. Харьков: АО "БизнесИнформ", 1996. - 112 с.

56. Yang Jenn-Hwai, Yang Miin-Shen. A control chart pattern recognition system using a statistical correlation coefficient method. Computers & Industrial Engineering, Volume 48, Issue 2 , March 2005, P. 205-221.

57. Chernukhin Y.V., SamarinM.A. Program environment for neural network modeling. Proceedings int. KRINC/LACOS Work-shop on Robot Vision, Rostov-on-Don, Russia, 21-23 May, 1996. P. 105-109.

58. Kobayashi Norihiko, Iwata Akira. Multimodule neural network model for higher order association // Proc. Int. Jt. Cont. Neural Networks, Nagoya, 1993. P. 233-236.

59. Кузин Jl.Т. Основы кибернетики: в 2-х т. Т.2. М.: Энергия, 1979. - 584 с.

60. Головко В.А. Нейроинтеллект: Теория и применения. Книга 1. Организация и обучение нейронных сетей с прямыми и обратными связями Брест: БПИ, 1999.-260 с.

61. КурейчикВ.М., Лебедев Б.К., БожичВ.И. Обучение нейронных сетей методами генетического поиска. В кн.: Труды Всероссийской конференции «Интеллектуальные информационные системы». - Воронеж. - 1999.

62. Чернухин Ю.В. Искусственный интеллект и нейрокомпьютеры. Таганрог: ТРТУ, 1997.-273 с.

63. Kuchariew G., Forczmanski P. Hierarchical method of Reduction of Features Dimensionality for Image Recognition and Graphical Data Retrieval // Pattern Recognition and Image Processing, 2002. Vol. 1. - P. 57-72.

64. Jacobsen X., Zscherpel U. and Perner P. A Comparison between Neural Networks and Decision Trees. Lecture Notes in Artificial Intelligence Machine Learning and Data Mining in Pattern Recognition, 1999, P. 144-158.

65. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. М.: Мир, 1992.-184 с.

66. Feng Shauhui, ShenDongri, ChenYijun. Метод идентификации на основе однослойного перцептрона // Fushun shiyou xueyuan xuebao = J. Fushun Petrol. Inst. -1999. 19, №2-P. 58-61.

67. ФуК. Структурные методы в распознавании образов. М.: Мир, 1977. -320 с.

68. KohE., MetaxasD., BaldevN. Hierarchical shape representation using locally adaptive finite elements // Lect. Notes Comput. Sci. 1994. - №300. - P. 441-446.

69. Li S.Z. The role of key-points in finding contours // Lect. Notes Comput. Sci. -1994.-№300.-P. 371-382.

70. Ахо A.B., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. -М.: Вильяме, 2000. 384 с

71. Белоусов В.А., Калядин Н.И. Обобщенная симультанная модель распознавания изображений. В кн.: Тез. докладов Всесоюзной конференции «Методы и средства обработки сложной графической информации». - Горький. -1988.-С. 34-35.

72. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. -1971,- №3. С. 1-11.

73. Белоусов В.А., Калядин Н.И., Шумилов Е.Е. Игровые решающие правила для отношений и распознавания конечных множеств / Москва, 1996. 16 с. - Деп. в ВИНИТИ, №333-В96.

74. Вайнцвайг М.Н., Полякова М.П. Ассоциативная память и пирамидальный алгоритм установления поточечного соответствия изображений // Recognition and Image Analysis, 1995, 5(2), МАИК Наука/Интерпериодика, Москва.

75. Ткачук В., Пилипенко О. Искусство поиска // CHIP. 2003. - С. 64-75.

76. Карташева Е. Интеллектуальные поисковые системы Excalibur // Сети. -1997.-№6.

77. Lange D.,Oshima M. Programming and deploying Java mobile agents with aglets // Addison-Wesley, 1998.

78. Eugster P., Guerraoui R., Kermarrec A., Massouline L. Epidemic Information Dissemination in Distributed System // Computer, May 2004. P. 60-66.

79. РоммЯ.Е., Гуревич М.Ю., Белоконова С.С., Соловьёва И.А. Вычисление нулей и полюсов функций на основе устойчивой адресной сортировки с приложением к поиску и распознаванию // Проблемы программирования. 2004. - №2-3. -С. 462-472.

80. Ватолин Д., РатушнякА., Смирнов М., ЮкинВ. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ МИФИ, 2002.-384 с.

81. СеменюкВ.В. Экономное кодирование дискретной информации.— СПб: СПб ГИТМО (ТУ), 2001. 115 с.

82. Ярославский Л.П. Введение в цифровую обработку изображений. М.: Сов.радио, 1979.-312 с.

83. Golomb S.W. Run-length encoding. // IEEE Tr. Inf. Theory IT-12, (1966), P. 399-401.

84. Е.А.Бутаков, В.И.Островский, И.Л.Фадеев. Обработка изображений на ЭВМ. М.: Радио и связь, 1987. - 240 с.

85. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding //IEEE Trans. 1978. - №.5.

86. Huffman D.A. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40,9(Sept.), 1952.-P. 1098-1101.

87. Новик Д.А. Эффективное кодирование. M. - Л.: Энергия, 1965. - 236 с.

88. Яглом A.M., Яглом И.М. Вероятность и информация. М.: Наука, 1973. -512 с.

89. Guazzo М. A general minimum-redundancy source-coding algorithm. // IEEE Trans.Inf.Theory IT-26, l(Jan.), 1980.-P. 15-25.

90. Langdon G.G. An introduction to arithmetic coding. IBM J.Res.Dev. 28, 2(Mar.),- 1984.-135-149.

91. Langdon G.G. and Rissanen J.J. A simple general binary source code. // IEEE Trans.Inf.Theory IT. 28 (Sept.). - 1982. - P. 800-803.

92. Pasco R. Source coding algorithms for fast data compression. Ph.D. disserta-tion.Dept.of Electrical Engineering, Stanford Univ. An early exposition of the idea of arithmetic coding, but lacking the idea of incremental operation 1976.

93. Rissanen J.J. Generalized Kraft inequality and arithmetic coding. IBM J.Res.Dev.20,(May.), 1976.-P. 198-203.

94. Rissanen J.J. Arithmetic codings as number representations. Acta Polytechnic Scandinavica, Math 31 (Dec.). 1979. - P. 44-51.

95. Rissanen J.J. and Langdon G.G. Arithmetic coding. IBM J.Res.Dev.23,2(Mar.). -1979. -149-162.

96. Rubin F. Arithmetic stream coding using fixed precision registers // IEEE Trans.Inf.Theory IT-25,1979, 6(Nov.). P. 672-675.

97. Мастрюков Д. Алгоритмы сжатия информации //Монитор. № 1. -1994.-С. 15-20.

98. Щербаков Н.С. Достоверность работы цифровых устройств. М.: Машиностроение, 1989. - 224 с.

99. Geisseihardt W. Fehlerdiagnose in Geraten der Digitaltechnik. München, Hanser Verlag, 1978.

100. Roth, J.P. Computer Logic Testing and Verification. Pontomac,Maryland, Computer Science Press, 1980.

101. Reinert D. Pruftheorie diskreter Systeme. Berlin, VEB Verlag Technik,1979.

102. Hubener D., E. Schonherr. Diagnostik in der Digitaltechnik. Berlin, VEB Verlag Technik, 1982.

103. Reinert D. Entwurf und Diagnose komplexer digitaler Systeme. Berlin, VEB Verlag Technik, 1983.

104. Пархоменко П.П., Согомонян E.C. Основы технической диагностики. М.: Энергоатомиздат, 1981.- 320 с.

105. Литиков И.И., Согомонян Е.С. Тестово-функциональное диагностирование цифровых устройств и систем // А и Т. №3. - 1985. -С. 111-112

106. Сперанский Д.В. О совмещенных схемах для функционального и тестового диагностирования дискретных устройств // А и Т. №1. - 1985. - С. 122126.

107. Давыдов П. С. Техническая диагностика радиоэлектронных устройств и систем. М.: Радио и связь, 1988. - 256 с.

108. Климова Л.М. Pascal 7.0. Практическое программирование. Решение типовых задач. М.: КУДИЦ-ОБРАЗ, 2000. - 528 с.

109. ЛоринГ. Сортировка и системы сортировки. М.: Наука, 1983. -384 с.

110. Миклошко Й. Связь между алгоритмами, программами и структурой параллельных ЭВМ. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. М.: Наука, 1982.-С. 6-36.

111. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений. В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. - Л., 1982, т. 118. - с. 159 - 187.

112. РоммЯ.Е., Виноградский В.В. Преобразование сортировок в форму устойчивых схем со свойствами прямой и обратной адресности / ТГПИ. Таганрог, 2003. - 43 с. Деп. в ВИНИТИ 8. 12.2003, № 2130-В2003.

113. Ромм Я.Е., Виноградский В.В. Преобразование сортировок к устойчивой форме без перемещения элементов и параллельное видоизменение сортировки Хоара / ТГПИ. Таганрог, 2004. - 44 с. Деп. в ВИНИТИ 17. 06. 2004, № 1020-В2004.

114. Ромм Я.Е., Заика И.В., Соловьева И.А. Метод программной оптимизации в приложении к математическим моделям экономики. / «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». Т.2. Таганрог. - 2005. - С. 17 - 26.

115. Biedl Th., Chan T., DemaineE.D., Fleischer R., GolinM., King J.A., Munro J. I. Fun-Sort —or the chaos of unordered binary search. Discrete Applied Mathematics, Volume 144. Issue 3 ,15 December 2004. - P. 231-236.

116. Gerbessiotis A.V., Siniolakis C. J. Probabilistic integer sorting. Information Processing Letters , Volume 90. Issue 4,31 May 2004. - P. 187-193.

117. Sanguthevar Rajasekaran, Sandeep Sen. A generalization of the 0-1 principle for sorting. Information Processing Letters. Volume 94, Issue 1. 15 April 2005. - P. 43-47.

118. YijieHan. Deterministic sorting in 0(n\og\ogri) time and linear space. -Journal of Algorithms, Volume 50, Issue 1, January 2004. P. 96-105.

119. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. II // Кибернетика и системный анализ. 2001. - № 5. - С. 81 - 101.

120. РоммЯ.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. 1994. - № 5. - С. 3 - 23.

121. РоммЯ.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. 1995. - № 4. - С. 13 - 37.

122. Цейтлин Г.Е. Введение в алгоритмику. Киев: Сфера, 1998. 473 с.

123. Цейтлин Г.Е. Распараллеливание алгоритмов сортировки // Кибернетика. 1989. - № 6. - С. 67-74.

124. Nardelli Е., Proietti G. Efficient unbalanced merge-sort. Information Sciences, Volume 176. Issue 10 .22 May 2006.-P. 1321-1337.

125. Ромм Я.Е., Белоконова C.C. Поиск и распознавание текстовых фрагментов на основе адресной сортировки и локализации экстремальных значений asc-кодов / ТГПИ. Таганрог, 2001. - 22 с. Деп. в ВИНИТИ от 06.12.2001, № 2537 -В2001.

126. Ромм Я.Е., Белоконова С.С. Схема поиска на основе сортировки и локализации экстремальных элементов / ТГПИ. Таганрог, 2003. - 31 с. Деп. в ВИНИТИ 12.03.2003, № 436-В2003

127. Ромм Я.Е., Белоконова С.С. Схема поиска на основе сортировки и локализации экстремальных элементов. В кн.: Сборник научных трудов 9-й международной конференции «Математические модели физических процессов». - Таганрог, ТГПИ. - 2003. - С. 100 - 103.

128. Ромм Я.Е., Белоконова С.С. Метод поиска на основе адресной сортировки и идентификации экстремумов в приложении к распознаванию / ТГПИ. Таганрог, 2004.-46 с. Деп. в ВИНИТИ от 05.08.2004. №1361-В2004

129. Ромм Я.Е., Белоконова С.С. Применение сортировки и локализации экстремальных элементов к поиску. В кн.: Сборник материалов 1-й международной научно-практической конференции 15-17 сентября 2003 г. под ред. А.К. Юрова. -Таганрог.-2003.-С. 100-105.

130. Trados, computer aided translation software, http://www.trados.com/

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

132. Fred J. Damerau. A technique for computer detection and correction of spelling errors. In Communications of ACM, volume 7(3). 1964. - P. 171-176.

133. Ромм Я.Е., Белоконова C.C. Поиск по группам масок на основе сортировки и локализации экстремальных элементов / ТГПИ. Таганрог, 2005. - 56 с. Деп. в ВИНИТИ от 28.06.05, № 916 - В2005.

134. Porter M.F. An algorithm for suffix stripping // Program. 14, no. 3 .- 1980. -PP. 130-137.

135. Ромм Я.Е., Соколов И.Н. Локализация экстремальных элементов дискретной последовательности на основе адресной сортировки / ТГПИ. Таганрог, 2003. - 38 с. Деп. в ВИНИТИ от 12.05.2003, № 907 - В2003.

136. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. Таганрог: ТРТУ. - 1998. - 546 с.; ВНТИ Центр. - № 05.990.001006.