Разработка и исследование схем детерминированного поиска на основе сортировки с приложением к идентификации оцифрованных объектов различных типов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Белоконова, Светлана Сергеевна

  • Белоконова, Светлана Сергеевна
  • кандидат технических науккандидат технических наук
  • 2007, Таганрог
  • Специальность ВАК РФ05.13.17
  • Количество страниц 230
Белоконова, Светлана Сергеевна. Разработка и исследование схем детерминированного поиска на основе сортировки с приложением к идентификации оцифрованных объектов различных типов: дис. кандидат технических наук: 05.13.17 - Теоретические основы информатики. Таганрог. 2007. 230 с.

Оглавление диссертации кандидат технических наук Белоконова, Светлана Сергеевна

Введение

Глава 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. Применение модифицированной мультипликативной схемы к поиску и распознаванию растровых изображений.

Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК

Введение диссертации (часть автореферата) на тему «Разработка и исследование схем детерминированного поиска на основе сортировки с приложением к идентификации оцифрованных объектов различных типов»

Актуальность проблемы. Проблема поиска и сбора информации является одной из важнейших задач информатики. Первые работы [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 наименований.

Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК

Заключение диссертации по теме «Теоретические основы информатики», Белоконова, Светлана Сергеевна

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

Список литературы диссертационного исследования кандидат технических наук Белоконова, Светлана Сергеевна, 2007 год

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.

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