Введение к работе
Проблема поиска, сбора и обработки информации принадлежит к числу основных задач информатики. Ее актуальность возрастает с ростом объема информации в электронном виде, с ростом ресурсов, доступных в сети Internet. Особую актуальность приобрели вопросы, связанные с поиском и распознаванием оцифрованной информации различного формата и типа данных, включая текстовую, графическую, аудио- и видеоинформацию. Существующие методы и подходы не вполне обеспечивают точность, релевантность результатов поиска запросу, не совмещают в требуемой мере поиск с распознаванием. В частности, это относится к поиску данных различных несовместимых типов, к обработке плохо структурированной информации. Поэтому актуальна разработка новых методов, позволяющих повысить эффективность, расширить область применения схем поиска, включая полнотекстовый поиск при организации электронных библиотек и каталогов, где проблема определяется растущим количеством пользователей, не обладающих профессиональными навыками при поиске информации на языке запросов. Наиболее масштабные исследования в области информационного поиска относятся к 90-м годам прошлого века, они интенсивно продолжаются в настоящее время. При этом характерно, что большинство предлагаемых методов эффективны на больших объемах данных, которые не могут быть подвергнуты анализу по выделению структуры. Одним из направлений исследования является применение известных методов распознавания к поиску оцифрованной информации различного типа. Методы адаптивного распознавания образов и семантические сети, опирающиеся на теорию нейронных сетей, осуществляют поиск текстовой, графической, аудио и видео, а также числовой информации. В диссертационной работе наряду с данными вопросами рассматривается обратная задача – применение методов поиска к распознаванию. При этом предполагается не только расширение области поиска до объектов различных типов, но включается поиск и распознавание отдельных фрагментов объектов и их свойств, а также детерминированный поиск неисправностей. Актуальность последней задачи обусловлена тенденцией увеличения объема передаваемой информации, повышением функциональной и аппаратурной насыщенности сетей передачи данных, ростом требований на скорость и надежность передачи и, как следствие, на техническое, в частности, тестовое диагностирование сетей. В данном контексте актуальна задача разработки схем поиска и распознавания на единой основе.
Цель диссертационной работы заключается в разработке и исследовании единой алгоритмической схемы поиска на основе применения сортировки в качестве конструктивного алгоритма. Более точно, исследуется использование подстановок индексов, формируемых сортировками, с целью применения к поиску данных различных типов. На основе исследования конструируются схемы с условиями поиска семантического характера, разрабатываются видоизменения схем поиска для распознавания и идентификации. Конструируемые схемы должны включать как схемы текстового поиска, поиска файлов, так и схемы поиска данных вещественного типа, а также должны осуществлять идентификацию объектов одновременно по нескольким разнотипным признакам, при этом отличаясь единством конструкции, устойчивостью и параллелизмом.
Для достижения цели в диссертационной работе поставлены следующие задачи:
-
Сконструировать распараллеливаемый метод применения сортировки для поиска на ее основе локально минимальных и локально максимальных значений элементов числовой последовательности. Применить метод для детерминированного поиска символов, слов и словосочетаний в тексте, для обнаружения скрытых закономерностей плохо структурированного текста.
-
На основе взаимно однозначного соответствия индексов в форме подстановки, определяемой сортировкой, сконструировать схемы с использованием обработки числовых выражений для поиска данных строкового и вещественного типа, сконструировать поиск в тексте как алгоритм поиска нулей и экстремумов числовой последовательности, сопоставленной тексту.
-
Сконструировать схему, позволяющую выполнить поиск по математическим условиям чисел и векторов как минимумов нормы разности между искомым элементом многомерного пространства и эталонным элементом из этого пространства.
-
Сконструировать метод индексной идентификации текстовых фрагментов по условиям в виде сложных математических выражений и выражений, включающих особенности семантического характера, совместить поиск с распознаванием текстовых особенностей.
-
Синтезировать схему детерминированного поиска одновременно по нескольким маскам с учетом взаимного расположения полных и частичных комбинаций масок, расстояний между ними и изменяемости словоформ.
-
Разработать видоизменение схемы поиска для случая поиска текстовых файлов, содержащих совокупность масок с заданными условиями относительно их взаимного расположения.
-
Разработать видоизменение схемы поиска для случая поиска объектов (и их свойств) различных типов, включая поиск группы разнотипных файлов, адаптировать схему для идентификации объектов общего вида на основе формализации признаков.
-
Разработать видоизменение базовой схемы поиска для распознавания и идентификации плоских растровых изображений.
-
На той же основе синтезировать распараллеливаемый алгоритм идентификации неисправностей цифровых устройств.
-
Выполнить сравнительный анализ схем с известными методами поиска, включая оценки временной сложности с проведением программных экспериментов.
Методы исследования опираются на теоретические основы информатики, методы распознавания образов, современные информационные технологии, методы параллельных сортировок и поиска.
Достоверность результатов обосновывается математическими доказательствами, оценками временной сложности, результатами программного моделирования и эксперимента.
Научная новизна диссертационной работы вытекает из применения сортировки в качестве конструктивной основы поиска, при этом поиск строится как алгоритм идентификации нулей и экстремумов числовой последовательности, сопоставленной объектам произвольного типа, включая растровые изображения и неисправности электронных устройств. На основе идентификации всех локальных и глобальных экстремумов, а также идентификации структуры окрестности каждого экстремума числовой последовательности, сопоставленной множеству исследуемых объектов, формируется вектор признаков, включающий все отличительные экстремальные особенности искомых объектов и их свойств. Отличие подхода от известных методов в том, что предложенные схемы, достигая результатов обычного поиска по вхождению подстрок в строки, включают поиск данных вещественного типа с заданной границей погрешности, позволяют выполнить поиск векторов как минимумов нормы разности между искомым элементом многомерного пространства и эталонным вектором в этом пространстве, включают поиск данных различных типов, распространяются на идентификацию объектов и их свойств, включая неисправности цифровых устройств.
Конкретно, научная новизна характеризуется следующим образом:
-
Сконструирован распараллеливаемый метод применения сортировки для поиска на ее основе локально экстремальных элементов числовой последовательности. С использованием кодовой таблицы символов метод применяется для детерминированного поиска в тексте элементов строкового типа. Метод отличается от известных применением сортировки в качестве конструктивной базовой части схемы поиска, использованием индексов сортируемых элементов в качестве адресных идентификаторов искомых элементов, включением в единую схему поиска элементов строкового и числового (вещественного) типа.
-
Предложена схема на основе сортировки с использованием обработки числовых выражений для поиска данных строкового и вещественного типа, которая отличается от известных по построению в форме алгоритма поиска нулей и экстремумов числовой последовательности, сопоставленной тексту, а также тем, что распространяет поиск на числовые данные с плавающей точкой при заданной границе погрешности. Схема распространяется на последовательность точек многомерного нормированного пространства, где осуществляется поиск минимумов нормы разности между текущим элементом последовательности и эталонным элементом пространства.
-
Разработан метод индексной идентификации множества произвольных текстовых фрагментов по условиям, включающим семантические особенности, и отличающийся совмещением поиска с распознаванием заданных особенностей искомых объектов.
-
Предложена схема детерминированного поиска одновременно по нескольким маскам с учетом их взаимного расположения и изменяемости словоформ. Схема отличается построением поиска по экстремальным особенностям сопоставленных тексту числовых последовательностей, а также качеством идентификации составных объектов в произвольном взаимном расположении элементов.
-
Предложена схема поиска текстовых файлов по совокупности масок с заданным взаимным расположением, которая отличается от известных методов по построению без анализа вхождений подстроки в строку, детерминированными результатами поиска и параллелизмом.
-
Сконструирована мультипликативная схема поиска по множеству масок с заданным взаимным расположением, для которой доказаны теоремы единственности и взаимно однозначного соответствия исследуемому тексту результатов поиска. Единственность идентификации по группам взаимно упорядоченных масок отличает схему от известных методов поиска.
-
Предложена схема поиска конечного множества объектов различных типов, включая разнотипные файлы и объекты общего вида, на основе формализации признаков. Множественность типов искомых объектов отличает схему от известных методов поиска.
-
Разработано преобразование основной схемы поиска для идентификации свойств объектов различного типа, включая идентификацию плоских оцифрованных изображений. Преобразованная схема, в частности, отличается применимостью к произвольному геометрическому месту точек на плоскости и обратимым преобразованием матрицы изображения в вектор размерности .
-
Схема идентификации свойств объектов различного типа преобразована в распараллеливаемый алгоритм идентификации неисправностей цифровых устройств, который отличается применимостью к устройствам сравнительно общего вида.
-
Выполнены программные эксперименты с предложенными схемами поиска и идентификации объектов на основе экстремальных закономерностей, извлекаемых с помощью сортировки из сопоставленных числовых последовательностей. Показан параллелизм предложенных схем, даны оценки временной сложности их максимально параллельной формы.
Основные положения, выносимые на защиту:
-
Распараллеливаемый метод применения сортировки для поиска всех локально экстремальных и произвольно заданных элементов числовой последовательности с допустимой погрешностью, который распространяется на последовательности элементов многомерных нормированных пространств.
-
Схема на основе сортировки с использованием обработки числовых выражений для поиска данных одновременно как строкового, так и вещественного типа, которая сводится к алгоритму поиска нулей и экстремумов числовой последовательности, сопоставленной тексту, обеспечивая поиск числовых данных с плавающей точкой при заданной границе погрешности.
-
Мультипликативная схема текстового поиска по множеству масок с заданным взаимным расположением, для которой доказаны теоремы единственности и взаимно однозначного соответствия исследуемому тексту результатов поиска.
-
Схема поиска конечного множества объектов различных типов, включая разнотипные файлы и объекты общего вида, на основе формализации признаков и извлечения скрытых экстремальных закономерностей данных с помощью сортировки.
-
Преобразование основной схемы поиска для идентификации свойств объектов различного типа, включая идентификацию плоских оцифрованных изображений и поиск неисправностей. Преобразование, в частности, применимо к произвольному геометрическому месту точек на плоскости и осуществляет обратимое преобразование матрицы изображения в вектор размерности .
Связь с плановыми исследованиями, проводимыми по месту выполнения диссертационной работы. Диссертационная работа выполнялась в рамках госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО «ТГПИ» в рамках приоритетного направления развития науки и техники в РФ «Информационные и телекоммуникационные системы» в соответствии с перечнем критических технологий РФ «Технологии обработки, хранения, передачи и защиты информации» по направлению фундаментальных исследований «Информатика. Искусственный интеллект, системы распознавания образов, принятие решений при многих критериях».
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. Разработанные схемы поиска могут быть составляющими редакторов языков программирования, операционных систем, их компьютерная реализация актуальна для систем автоматизации научных исследований, включая компьютерную обработку результатов физических экспериментов и компьютерное тестирование электронных устройств. Предложенные схемы применимы для упрощения и повышения эффективности навигации в существенных объемах информации на Web-серверах, при создании больших электронных архивов, включая электронные библиотеки. В целом, разработанные методы могут использоваться в системах электронного документооборота при росте массивов обрабатываемых полнотекстовых документов, могут применяться в качестве средств организации доступа к информации, включая те из них, которые примыкают к разряду систем искусственного интеллекта. В частности, представленные схемы могут играть роль при поиске документов по их содержанию в Internet для обеспечения адекватного выбора информации по запросу пользователя. Предложенные схемы идентификации разнотипных данных, включая изображения в формате BMP, могут использоваться для повышения эффективности поиска по содержанию.
Внедрение и использование результатов работы. Полученные в работе результаты использованы:
-
В отделе автоматизации библиотеки Таганрогского государственного педагогического института при создании электронной библиотеки и информационного центра ГОУВПО «ТГПИ».
-
В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО «ТГПИ».
-
В учебном процессе кафедры информатики ГОУВПО «ТГПИ» в рамках курсов «Информатика», «Информационные системы», «Информационные технологии в математике», «Элементы абстрактной и компьютерной алгебры», «Использование информационных и коммуникационных технологий в образовании».
Апробация работы. Основные результаты работы докладывались на: I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г.); IX-XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2003-2006 гг.); IV международной научно-практической конференции по программированию УкрПРОГ’ 2004 (Украина, Киев, 2004 г.); международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.); международной научной конференции «Оптимальные методы решения научных и практических задач» (Таганрог, ТРТУ, 2005 г.); семинарах «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2001 – 2006гг.).
Публикации. По материалам диссертационной работы опубликовано 14 печатных работ общим объёмом 14,4 п. л., в том числе, 1 статья в журнале из списка допущенных ВАК РФ.
Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 5 приложений. Основное содержание работы изложено на 156 страницах, включая список литературы из 149 наименований.
