Главный Каталог Статей РФ
85933 авторов, размещено 47073 статей, сейчас на сайте пользователей: 114 Статистика
Аватар shkurkin

Поиск объектов различных типов по нескольким признакам на основе сортировки

Категория:  Техника и технологии  | Автор:  shkurkin | Опубликовано: 05.11.2009

Введение и постановка вопроса

Оператор локализации экстремальных элементов последовательности

j:=1; while j<= n do begin
FOR L:=1 TO j-1 do if abs(e[j]-e[j-L])<=eps then goto 22; Writeln ('',c[e[j]],' ',e[j]);
22: j:=j+1; end;

. Проблема поиска, сбора и обработки информации принадлежит к числу основных задач информатики. Ее актуальность возрастает с ростом объема информации в электронном виде, с ростом ресурсов, доступных в сети Internet. Особую актуальность приобрели вопросы, связанные с поиском и распознаванием оцифрованной информации различного формата и типа данных, включая текстовую, графическую, аудио- и видеоинформацию. Существующие методы и подходы не вполне обеспечивают точность, релевантность результатов поиска запросу, не совмещают в требуемой мере поиск с распознаванием. В частности, это относится к поиску данных различных типов. . В основе схемы лежит применение адресной устойчивой распараллеливаемой сортировки по ключу, сохраняющей на выходе входные индексы упорядоченных элементов, причем в порядке их расположения после сортировки. Одна из таких сортировок представляет собой разновидность сортировки подсчетом, для выполнения которой применяется матрица сравнений (МС). На пересечении i -й строки и j -го столбца МС находится результат сравнения элементов c[i] и c[ j], отмечаемый знаком « + », если c[i] < c[ j] , знаком «–», если c[i] > c[ j] , и знаком « 0 », если c[i] = c[ j] . Число нулей и плюсов в j-м столбце над диагональю, включая диагональный элемент, складывается с числом минусов j-й строки справа от диагонали. Значение суммы k становится индексом j-го элемента в отсортированном массиве: c1[k]:= c[j], с тем же индексом запоминается входной номер переставленного элемента: e[k ]:= j . Дополнительной составляющей схемы поиска является оператор локализации экстремальных элементов. Локально минимальный элемент массива (в дальнейшим –минимум) определяется как элемент меньший предшествующего и не больший последующего по отношению «<=». Оператор локализации минимумов последовательности из n элементов имеет вид:

Присоединение к процедуре сортировки оператора локализации минимумов влечет программную идентификацию всех локально минимальных элементов входного массива в окрестности радиуса

Поиск объектов различных типов одновременно по нескольким признакам

При этом индексы элементов

Мультипликативная схема

Пусть дан массив

Процесс продолжается.

Изложенную схему можно следующим образом перевести в схему поиска по совпадению с множеством признаков или свойств

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

Схема видоизменяется для объектов.

Каждому набору признаков

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

На основе совпадения индексов числового массива и массива исходных объектов выполняется переход от числовых экстремумов к искомым объектам в исходном виде

Числовые идентификаторы

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

, присущих объекту, соответствует единственное значение произведения элементов столбца, образующее элемент сопоставленной числовой последовательности (4). , на этой основе выполняется поиск по полному и частичному набору заданных свойств. После сортировки массива c из (4) применяется оператор локализации минимумов, который по наличию локальных минимумов идентифицирует индексы искомых объектов по аналогии с тем, как идентифицируются индексы слов, совпадающих с масками поиска [1,2]. . , по которым локализуются экстремальные значения, могут быть рассчитаны наперед. Поэтому анализ результатов поиска может вестись по совпадению с такими числовыми значениями в локализованной окрестности. , но и по их частичному набору. При этом путем анализа окрестности локализованных минимумов можно идентифицировать не только один объект, но и группу таких объектов.. С помощью соотношений (3), (4) массив (2) переводится в одномерный числовой массив при условии, что при каждом i исследуемому объекту с номером i соответствует i -й столбец массива mass , в котором не более одного единичного значения. Формирование массива mass происходит с помощью проверки соответствия или несоответствия исследуемого объекта заданному признаку при фиксированном порядке обхода объектов [1]. , в более общем случае, объектов, характеризуемых свойствами различной природы. Схема имеет то ограничение, что каждый объект может удовлетворять не более чем одному признаку (ниже «признак» и «свойство» –синонимы). , обладающих набором свойств. Каждому объекту с заданным набором признаков следующим единственным образом сопоставляется числовое значение. Пусть дано проиндексированное множество V из m однотипных объектов, в котором требуется выполнить поиск по заданной последовательности из n признаков ( ) n M m ,m , ... ,m 1 2 = , расположенных в определенном фиксированном порядке. Как и прежде, формируются массивы mass, mass1 и c , но при этом соотношения (2), (3) заменяются соотношениями (5), (6).c[i] совпадают с индексами элементов Sl[i]. К отсортированному массиву c применяется оператор локализации минимумов. Если локализация минимума выполняется в окрестности наперед заданного радиуса, не меньшего числа сгруппированных масок, то идентифицированным окажется искомое сочетание одновременно нескольких масок. Тем самым можно вести поиск не по разрозненному сочетанию нескольких масок, а по их взаимосвязанному положению в исследуемом массиве слов. [1,2] позволяет выполнить поиск объекта в том случае, если объект обладает не более чем одним свойством и при этом принадлежит одному типу данных. В частности, слово исследуемого текста может совпадать не более, чем с одной маской. С целью видоизменения поиска для объектов различных типов мультипликативная схема поиска модифицируется следующим образом. Sl из m слов, в котором требуется выполнить поиск по заданной последовательности из n масок ( ) n M m ,m ,...,m 1 2 = , расположенных в определенном и фиксированном порядке. На первом шаге массиву слов Sl сопоставляется двумерный числовой массив mass[n,m] , где n –число масок поиска, m–число слов в исследуемом массиве. Элементы массива mass первоначально полагаются равными нулю. Рассматривается первая маска поиска 1 m . Исследуемый массив слов просматривается, начиная с номера i =1, и i -е слово строки сравнивается с первой маской поиска 1 m . Если i -е слово массива Sl совпадает с маской 1 m , то элементу mass[1,i] присваивается число 1, в противном случае значение равно 0. Затем номер i увеличивается на 1 и выполняется переход к следующему слову.  , пока не будут просмотрены все слова исследуемого массива. Второй проход повторяет действия, описанные в первом проходе, для второй маски поиска 2 m . Такой процесс выполняется для всех n масок поиска и массиву Sl сопоставляется массив mass[n,m].. Исходная (мультипликативная [1,2]) схема строится следующим образом. Исследуемой строке сопоставляется одномерный числовой массив, количество элементов которого совпадает с количеством слов заданной строки. Элементы сопоставленного числового массива, соответствующие различным маскам, перемножаются, причем сомножители априори задаются так, чтобы произведения взаимно однозначно соответствовали различным маскам, а локальные минимумы в их последовательности единственным образом соотносились с полным набором масок. Сопоставление массиву слов Sl числового массива c = (c1 ,c2 ,...,cm ).eps. При этом eps задается априори и произвольно фиксировано. Аналогично могут быть идентифицированы локальные максимумы [1,2], с изменением знака неравенства на противоположный –глобальные экстремумы [1]. На основании параллелизма сортировки экстремумы идентифицируются по максимально параллельной схеме.
Полную статью с графиками, изображениями и формулами вы можете получить на сайте books.eldirect.ru. Автор статьи Белоконова Светлана Сергеевна.
Комментарии
К этой статье пока нет комментариев. Станьте первым! У нас гости не могут комментировать статьи. Пожалуйста авторизуйтесь или зарегистрируйтесь, чтобы прокомментировать.
Интересные статьи по теме
Аватар NadezhdaB
Солнечная энергия – альтернативный источник энергии Проблемы окружающей среды сегодня как никогда волнуют человечество. Большое внимание уделяется поиску альтернативных источников энергии. Среди энергетики будущего энергия солнца по праву занимает одно...
Категория: Техника и технологии | Автор: NadezhdaB | Добавлено: 25.04.2021
Аватар techmagic
Схема мощной глушилки Если вам надоело слушать соседский радиоприёмник - сделайте ФМ глушитель! Собрав несколько схем ФМ - глушителей из интернета, в итоге разработал и испытал свою, с гораздо лучшим эффектом....
Категория: Техника и технологии | Автор: techmagic | Добавлено: 08.03.2010
Аватар injener3d
Cоветы по улучшению качества 3D печати ABS пластиком В статье приведены некоторые советы по улучшению качества 3D печати при использовании в качестве филамента АБС пластика...
Категория: Техника и технологии | Автор: injener3d | Добавлено: 01.04.2015
Аватар Vladskiniskij
История и перспективы Оригами Данная статья нацелена на популяризацию идей о использовании оригами для обучения математике и применения его принципов в инженерии, среди школьников и студентов, обучающихся на математическом и инжен...
Категория: Техника и технологии | Автор: Vladskiniskij | Добавлено: 16.12.2021
Аватар vfs2009
Экспертиза технологической документации В статье рассмотрены вопросы организации работ по проведению экспертизы технологической документации в соответствии с лицензией Ростехнадзора на проведение экспертизы проектной, конструкторской и...
Категория: Техника и технологии | Автор: vfs2009 | Добавлено: 12.08.2009
Лучшие авторы
Аватар o_style
Компания персонального фитнеса.

Читать

Аватар krasota24.com
Красота спасет мир!

Читать

Аватар vladstraychenko
редставьте себе, что жизнь – это игра, построенная...

Читать

Аватар PokerPro
Играю в покер в свободное время.
Являюсь админи...

Читать

Аватар garminych
Мы готовы помочь Вам, сделать правильный выбор GPS...

Читать

Свежие комментарии
Талантливый человек талантлив во всём! Будь как Паша! А ещё ты можешь ...

Читать

Можно выбрать.

Читать

Ой, шутник.

Читать

https://priornews.ru/zastrojshhik-iz-hmao-sravnil-ufas-s-prestupnoj-gr...

Читать

https://ura-news.turbopages.org/turbo/ura.news/s/news/1052688335

Читать

Напишите нам