Способ и устройство для множественной подборки текстовых данных в хранилищах на основе продукционного подхода тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Гришин Дмитрий Сергеевич

• Гришин Дмитрий Сергеевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Гришин Дмитрий Сергеевич

ВВЕДЕНИЕ

2

3

5

ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ АЛГОРИТМИЧЕСКИХ И АППАРАТНЫХ СРЕДСТВ ДЛЯ МНОЖЕСТВЕННОЙ ПОДБОРКИ ТЕКСТОВЫХ ДАННЫХ В ХРАНИЛИЩАХ. ОБОСНОВАНИЕ И ВЫБОР НАПРАВЛЕНИЯ ИССЛЕДОВАНИЯ

1.1. Хранение данных в корпоративных информационных системах. Общие принципы организации хранилищ данных и вычислительные средства обработки запросов

1.1.1. Хранилища данных и их оперативный анализ

1.1.2. Отличительные особенности операционных систем и хранилищ данных

1.1.3. Множественная подборка данных и представление результатов

1.2. Обзор аппаратных архитектур устройств для высокопроизводительных вычислений

1.2.1. Гарвардская архитектура

1.2.2. Суперскалярные и УЫШ-процессоры

1.2.3. Символьные процессоры и архитектуры

1.2.4. Интегральные схемы с программируемой структурой

1.3. Обзор алгоритмов подборки данных

1.3.1. Алгоритм Бойера — Мура

1.3.2. Алгоритм подборки данных в суффиксном дереве

1.3.3. Алгоритм подборки данных в позиционном представлении текста

1.3.4. Требования предьявляемые к алгоритмам для множественной подборки текстовых данных в хранилищах. Сравнение основных алгоритмов подборки данных

1.4. Сущность предлагаемого подхода

1.5. Выводы по главе

ГЛАВА 2 РАЗРАБОТКА СПОСОБОВ ДЛЯ МНОЖЕСТВЕННОЙ ПОДБОРКИ

ТЕКСТОВЫХ ДАННЫХ В ХРАНИЛИЩАХ

2.1. Продукционная парадигма вычислений

2.2. Модифицированное суффиксное дерево

2.3. Гибридное позиционное представление текста

2.4. Модифицированное позиционное представление текста

2.5. Выводы по главе

46

ГЛАВА 3 ПРОГРАММНОЕ МОДЕЛИРОВАНИЕ СПОСОБОВ ПОДБОРКИ

3.1. Описание среды разработки приложения

3.2. Описание приложения моделирования

3.3. Моделирование работы способов подборки данных и анализ полученных результатов

3.3.2. Анализ средних временных затрат подборки и предобработки данных

3.3.3. Анализ зависимости временных затрат подборки данных относительно размера входного текста

3.3.4. Анализ зависимости временных затрат подборки данных относительно размера входной подстроки

3.3.5. Анализ зависимости временных затрат подборки данных относительно размера входного алфавита

3.3.6. Анализ зависимости временных затрат предобработки входного текста относительно размера входного текста

3.3.7. Анализ зависимости временных затрат предобработки входного текста относительно размера входного алфавита

3.4. Выводы по главе

ГЛАВА 4 РАЗРАБОТКА СПЕЦИАЛИЗИРОВАННОГО АССОЦИАТИВНОГО УСТРОЙСТВА ДЛЯ МНОЖЕСТВЕННОЙ ПОДБОРКИ ТЕКСТОВЫХ ДАННЫХ В ХРАНИЛИЩАХ. МОДЕЛИРОВАНИЕ ЕГО РАБОТЫ

4.1. Разработка специализированного ассоциативного устройства

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

4.1.2. Разработка структурно-функциональной организации ассоциативного устройства

4.1.3. Разработка структурных схем основных блоков ассоциативного устройства

4.1.4. Разработка алгоритма работы ассоциативного устройства

4.2. Расчет аппаратной сложности устройств

4.3. Моделирование работы устройств

4.3.1. Описание моделирующей среды

4.3.2. Синтез имитационных моделей операционных блоков устройств

4.3.3. Анализ характеристик разработанного ассоциативного устройства

4.4. Выводы по главе

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЕ

150

ВВЕДЕНИЕ

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

Актуальность.

Важным направлением развития средств вычислительной техники является создание аппаратно-вычислительных средств для поддержки оперативной обработки запросов и доступа к данным в информационных системах, содержащих базы и хранилища текстовых данных [1, 2, 3, 4, 5]. Среди хранимой информации значимая роль принадлежит текстовой и гипертекстовой информации, базовым обработчиком которой являются продукционные системы, учитывающие структурные и лингвистические отношения между символами. Кроме того, продукционная схема вычислений «условие ^ действие» имеет потенциальные возможности для распараллеливания процессов подборки данных по набору шаблонов и модификации данных.

Особый интерес представляют базы и хранилища с неизменяемыми текстовыми и гипертекстовыми данными — электронные библиотеки, коллекции документов, электронные архивы, справочная информация и т. д. Одномерные формы представления текстовых данных, их размер (сотни мегабайт), многообразие связей, вариативность границ отдельных информационных единиц и др., приводят к экспоненциальным и другим времяемким пропорциям доступа к базам и хранилищам, сложным запросам на доступ к данным [3, 6, 7]. Как итог, запрос на аппаратном уровне декомпозируется последовательностью связанных поисковых процессов по набору шаблонов, уточняемых в процессе поиска.

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

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

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

Теоретические и прикладные исследования продукционных систем рассматривались в работах А. А. Маркова, Н. М. Нагорного, Н. А. Шанина, В. И. Городецкого, Дж. Люгера и др. Существенный вклад в изучении вопросов, связанных с базами и хранилищами данных, внесли W. H. Inmon, R. Kimball, E. F. Codd, C. J. Date, R. Wrembel, М. Р. Когаловский, А. А. Барсегянян, М. С. Куприянов, В. В. Степаненко, И. И. Холод и др. Вопросы создания перспективных архитектур и схемотехнических решений для микропроцессоров отражены в работах Е. П. Угрюмова, К. Г. Самофалова, Е. А. Зельдина, В. А. Потехина, В. В. Корнеева, А. В. Киселева и др. Разработка специализированных устройств, в том числе на программируемых интегральных схемах, и параллельной обработки данных рассматривалась в трудах ученых И. А. Каляева, И. И. Левина, В. В. Сташина, И. С. Еремеева и др.

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

несоответствия между непродуктивными временными затратами на поисковые операции обработки запросов и структурой микропроцессоров общего назначения отражает основное противоречие современных алгоритмических и аппаратных средств для оперативной реализации продукционных операций под обработку запросов к базам и хранилищам текстовых данных [8]. На разрешение данного противоречия направлено диссертационное исследование.

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

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

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

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

Основные задачи диссертационного исследования:

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

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

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

4. Моделирование работы разработанного способа для множественной подборки текстовых данных в хранилищах. Разработка программных средств для моделирования.

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

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

Научная новизна и результаты, выносимые на защиту:

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

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

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

Практическая ценность работы состоит в следующем:

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

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

3. Разработанное ассоциативное устройство позволяет сократить временные затраты модификации данных относительно устройства-прототипа на 14 % и на 80 % относительно устройства-аналога.

Реализация результатов работы. Результаты диссертационной работы внедрены в:

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

2. ООО «Инновационные системы управления», (г. Курск). в части реализации способа, алгоритмов и схемотехнических решений основных блоков и узлов устройства для множественной подборки данных, реализованные на ПЛИС 5SGSED8I2F45C2 семейства Stratix.

3. Учебный процесс федерального государственного бюджетного образовательного учреждения высшего образования «Юго-Западный государственный университет» по дисциплине «Интеллектуальные системы и технологии» магистров направления «Информационные системы и технологии» в части реализации средств направленной обработки строковых данных.

Соответствие паспорту специальности. Диссертационная работа соответствует паспорту научной специальности 05.13.05 — «Элементы и устройства вычислительной техники и систем управления» по второму пункту «Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико-экономических и эксплуатационных характеристик» в части разработки способа и специализированного ассоциативного устройства для множественной подборки текстовых данных в хранилищах для

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

Апробация работы. Основные научные результаты работы докладывались и обсуждались на региональной заочной научно-практической конференции «Интеллектуальные информационные системы: тенденции, проблемы, перспективы» (г. Курск, 2013), IX международной научно-практической конференции «Передовые научные разработки» (г. Прага, 2013), XII международной научно-технической конференции «Распознавание — 2015: Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2015), III региональной заочной научно-практической конференции «Интеллектуальные информационные системы: тенденции, проблемы, перспективы» (г. Курск, 2015), XIII международной научно-технической конференции «Распознавание — 2017: Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2017), а также рассматривались на семинарах кафедры программной инженерии и кафедры информационных систем и технологий Юго-Западного государственного университета в 2013-2017 гг.

Публикации по работе. По результатам выполненных разработок и исследований опубликованы 11 работ, в том числе 4 работы в рецензируемых научных журналах и изданиях, получено свидетельство о регистрации программы для электронно-вычислительных машин, а также патент Российской Федерации на изобретение.

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

ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ АЛГОРИТМИЧЕСКИХ И АППАРАТНЫХ

СРЕДСТВ ДЛЯ МНОЖЕСТВЕННОЙ ПОДБОРКИ ТЕКСТОВЫХ ДАННЫХ В ХРАНИЛИЩАХ. ОБОСНОВАНИЕ И ВЫБОР НАПРАВЛЕНИЯ ИССЛЕДОВАНИЯ.

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

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

1.1. Хранение данных в корпоративных информационных системах. Общие принципы организации хранилищ данных и вычислительные средства

обработки запросов

Хранение информации в большинстве корпоративных информационных системах (ИС) построены на базе систем управления базами данных (СУБД), которая служит для повседневной деятельности подразделений организации [1, 3, 9, 10]. Эти ИС называют транзакционными или OLTP-системами (Online Transaction Processing). Информатизация всех профессиональных сторон деятельности и внедрение баз данных (БД) и хранилищ данных (ХД) определили сверхогромные объемы цифровой, вводимой информации, а также необходимость средств, и оперативного релевантного извлечения данных из хранилища по запросу [9, 11, 12, 13].

Среди хранимой информации доминирующая роль принадлежит текстовой и гипертекстовой информации [9, 14, 15, 16, 17, 18] как основной форме, участвующей в организационных, информационно-вычислительных

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

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

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

В общем случае, с точки зрения проектирования информационно-аналитических систем [2, 5] имеется два подхода для интеграции корпоративной информации, децентрализованное (схема спагетти) и централизованное (общая куча данных) объединение источников. Последний подход дал толчок для появления технологии ХД, которая позволяет получать, обрабатывать и представлять информацию из общей кучи данных [2, 19].

1.1.1. Хранилища данных и их оперативный анализ

ХД и их оперативный анализ представляют собой инструменты для систематической организации и использования этих данных для принятия стратегических решений. Это позволяет «работникам знаний» (менеджерам, аналитикам и руководителям) использовать хранилище для быстрого

получения данных в удобном представлении, на основе которых уже принимаются обоснованные решения.

По словам Уильяма Г. Инмона (William H. Inmon), ведущего архитектора в области построения систем ХД, «ХД — это предметно-ориентированная, интегрированная, зависимая от времени и не изменяемая БД, предназначенная для подготовки отчётов и бизнес-анализа с целью поддержки принятия управленческих решений» [20]. Это краткое, но исчерпывающее определение включает основные функции ХД:

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

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

3. Зависимость от времени. Данные в хранилищах предназначены для предоставления информации с исторической точки зрения (например, за последние 5-10 лет). Каждая запись в хранилище всегда относится к какому-либо моменту времени или временному промежутку.

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

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

Таким образом ХД представляет собой семантически согласованную БД, которая содержит информацию, загруженную из неоднородных источников, и которая также является физической моделью данных для поддержки принятия решений [21].

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

1.1.2. Отличительные особенности операционных систем и хранилищ данных

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

С другой стороны, системы ХД служат пользователям или специалистам для анализа данных и принятия решений. Такие системы могут организовывать и представлять данные в различных форматах для соответствия определенным потребностям пользователя [22, 23]. Эти системы известны как системы оперативного анализа данных или OLAP-системы (Online Analytical Processing,).

Основными различиями между OLTP-системами и OLAP-системами являются:

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

2. OLTP-система управляет текущими данными, которые, как правило, слишком детализированы, чтобы их можно было легко использовать для принятия решений [2, 5, 24]. OLAP-система управляет большими объемами исторических данных, предоставляет средства для их обобщения и агрегации, а также хранит и управляет информацией на разных уровнях детализации. Эти функции упрощают использование данных для принятия обоснованных управленческих решений.

3. OLTP-системы обычно используют схему сущностных связей (Entity-Relationship Model) и имеют прикладную структуру БД. OLAP-системы обычно используют модель «звезда» или «снежинка» и имеют предметно-ориентированную БД.

4. OLTP-система нацелена главным образом на работу с текущими данными в рамках предприятия или отдела, не ссылаясь на исторические данные или данные в разных организациях. В то время как OLAP-система часто включает в себя несколько схем БД из-за эволюционного процесса организации. OLAP-системы также работают с информацией разных организаций, интегрируя эту информацию из многочисленных ХД [25, 26]. Из-за огромного объема данных, содержащихся в OLAP-системах, эти данные хранятся на множестве носителей.

5. Запросы к OLTP-системам состоят в основном из коротких транзакций. Такая система требует механизмы параллельного управления и восстановления данных. Однако запросы к OLAP-системам в основном выполняются только для чтения (поскольку большинство ХД хранят

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

Эти и другие различия, между OLTP-системами и OLAP-системами приведены в сводной таблице 1.1.

Таблица 1.1 — Сравнительная характеристика OLTP-систем и OLAP-систем

OLTP-системы OLAP-системы

Используются работниками Используются руководством

Тактическое значение Стратегическое значение

Обеспечивают повседневную деятельность Обеспечивают стратегическое направление развития бизнеса

Предназначены для обработки транзакций Предназначены для интерактивного анализа

Ориентированы на приложения Предметно-ориентированные

Содержат актуальные данные Содержат исторические данные

Предсказуемые запросы Непредсказуемые запросы

1.1.3. Множественная подборка данных и представление результатов

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

В большинстве случаев, эти агрегатные функции образуют нереляционный, многомерный набор данных (называемый метакубом или гиперкубом), на осях которого содержатся параметры данных, а в ячейках — связанные с этими параметрами данные [7, 27, 28]. Между элементами (частями) агрегатных данных устанавливаются (определяются) отношения, ассоциации, что существенно повышает логическую и иную связность данных

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

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

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

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

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

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

При объединении данных учитывается их физическое расположение (таблица в БД, плоский файл и т. д), особенности работы SQL, который поддерживается БД и сложности (аналитической) запроса. Кроме того, подборка данных в хранилище, как правило, обращена к большим объемам данных, что требует больших объемов памяти, мощности процессора и ресурсов для визуализации результатов поиска.

Обычно составную выборку данных стараются максимально перенести на серверы источников данных, т. к. процесс выборки включает часто используемые операции поиска и модификации данных [13, 18, 29, 30]. Хотя аналитический сервер может выполнять OLAP-вычисления и анализ, лучше для этого использовать отдельный OLAP-сервер, а при работе с наборами данных сверхбольшого размера лучшим решением будет использование высокопроизводительной реляционной СУБД. Поэтому при возможности подборка выполняется именно этими технологиями, а не аналитическим сервером, который в этом случае отвечает за получение запросов от клиентских приложений и их перевод в предложения SQL для исходных баз данных.

Список литературы диссертационного исследования кандидат наук Гришин Дмитрий Сергеевич, 2017 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Когаловский, М. Р. Энциклопедия технологий баз данных. Эволюция и стандарты. Инфраструктура. Терминология. / М. Р. Когаловский. — М.: Финансы и статистика, 2005. — 800 с.

2. Inmon, W. H. Building the Data Warehouse / William H. Inmon. — 4th Edition-Wiley, 2005. — 576 p.

3. Grant, Gerald. ERP & Data Warehousing in Organizations: Issues and Challenges / Gerald Grant. — IRM Press, 2003. — 284 p.

4. Аносова, Н. П. Распределенные базы и хранилища данных [Электронный ресурс] / H. П. Аносова, O. O. Бородин, E. C. Гаврилов [и др.]. — ИНТУИТ, 2009. — Режим доступа: www.intuit.ru/department/database/olap.

5. Inmon, W. H. Data Architecture: A Primer for the Data Scientist: Big Data, Data Warehouse and Data Vault. / W. H. Inmon, D. Linstedt. — Morgan Kaufmann, 2014. — 378 с.

6. Армстронг, Роб. Семь этапов оптимизации производительности хранилища данных // Открытые системы. — 2002. — № 1.

7. Chevalier, M. et al. How Can We Implement a Multidimensional Data Warehouse Using NoSQL? // International Conference on Enterprise Information Systems. — Springer International Publishing, 2015. — С. 108-130.

8. Balamurugan, M. Analysis of High Performance Parallel Computing Instruction Sets / M. Balamurugan, S. Vijaykumar, S. G. Saravanakumar // Indian Journal of Science and Technology. — 2016. — Т. 9. — № 48.

9. Спирли, Эрик. Корпоративные хранилища данных. Планирование, разработка, реализация. Том. 1 / Эрик Спирли; пер. с англ. — М.: Вильямс, 2001. — 400 c.

10. Vaisman, A. Data Warehouse Systems / A. Vaisman, E. Zimanyi. — Springer, Heidelberg, 2014. — 625 с.

11. Хоббс, Л. Oracle9iR2: разработка и эксплуатация хранилищ баз данных / Л. Хоббс, С. Хилсон, Ш. Лоуенд; пер. с англ. — М.: КУДИЦ-ОБРАЗ, 2004. — 592 с.

12. Барсегян, А. А. Методы и модели анализа данных: OLAP и Data Mining: учебное пособие / А. А. Барсегян, М. С. Куприянов, В. В. Степаненко [и др.]. — СПб.: БХВ-Петербург, 2004. — 336 с.

13. Lopes, C. C. et al. Processing OLAP queries over an encrypted data warehouse stored in the cloud // International Conference on Data Warehousing and Knowledge Discovery. — Springer International Publishing, 2014. — С. 195-207.

14. Шокин, Ю. И. Проблемы поиска информации / Ю. И. Шокин,

A. М. Федотов, В. Б. Барахнин. — Новосибирск: Наука, 2010. — 220 с.

15. Титенко, Е. А. Общие характеристики процессов обработки символьной информации / Е. А. Титенко, И. С. Зерин, К. С. Скорняков [и др.] // Известия Юго-Западного государственного университета. Серия: управление, вычислительная техника, информатика. Медицинское приборостроение. — 2012. — № 2. ч. 3 — С. 151-156.

16. Гордиенко В. В. Инструментальные средства организации символьных вычислений. Краткая история и перспективы / В. В. Гордиенко,

B. М. Довгаль, И. С. Зерин [и др.] // Информационно-измерительные и управляющие системы. — М.: Радиотехника, 2009. — Том 7, № 11 — С. 72-76.

17. Holmes, J. H. et al. Clinical research data warehouse governance for distributed research networks in the USA: a systematic review of the literature // Journal of the American Medical Informatics Association. — 2014. — Т. 21. — № 4. — С. 730-736.

18. Sitaridi, E. A. GPU-accelerated string matching for database applications / E. A. Sitaridi, K. A. Ross // The VLDB Journal. — 2016. — Т. 25. — №. 5. —

C. 719-740.

19. Батьков, В. О. Анализ проблем современных хранилищ данных // Труды Международного симпозиума «Надежность и качество». — 2013. — Том 1 — С. 259-261.

20. Devlin, B. A. An architecture for a business and information system /

B. A. Devlin, P. T. Murphy. — IBM System Journal — 1988. — 27(1) — P. 60-80.

21. Codd, E. F. Providing OLAP to User-Analysts: An IT Mandate / E. F. Codd, S. B. Codd, C. T. Salley // Technical Report. — E. F. Codd Associates, 1993.

22. Wrembel, R. Data Warehouses and OLAP: Concepts, Architectures and Solutions / Robert Wrembel, Christian Koncilia. — IRM Press, 2006. — 360 p.

23. Alkharouf, N. W. Online Analytical Processing (OLAP): A Fast and Effective Data Mining Tool for Gene Expression Databases / N. W. Alkharouf, D. C. Jamison, B. F. Matthews // Journal of Biomedicine and Biotechnology. — 2005(2) — P. 181-188.

24. Wang, J. Encyclopedia of Data Warehousing and Mining / John Wang. — 2nd ed. (4 Volumes) — Information Science Reference, 2008. — 2542 p.

25. Jiawei, Han. Data Mining: Concepts and Techniques / Han Jiawei, Micheline Kamber, Jian Pei. — 3rd Edition — Elsevier, 2011. — 744 p.

26. Kantardzic, Mehmed. Data Mining: Concepts, Models, Methods, and Algorithms / Mehmed Kantardzic. — 2nd Edition — Wiley, 2011. — 552 p.

27. Kimball, R. The data warehouse toolkit: The definitive guide to dimensional modeling. / R. Kimball, M. Ross. — John Wiley & Sons, 2013. — 600 с.

28. Na, J. C. Indexed Two-Dimensional String Matching. — 2016. — С. 1-6.

29. Konda, S. Augmenting Data Warehouse Security Techniques — A Selective Survey / S. Konda, R. More — 2015. С. 2209-2213.

30. Liu, J. A Parallel Algorithm of Multiple String Matching Based on Set-Partition in Multi-core Architecture / J. Liu, F. Li, G. Sun // International Journal of Security and Its Applications. — 2016. — Т. 10. — № 4. — С. 267-278.

31. Сергеев, С. Л. Архитектуры вычислительных систем: учебник /

C. Л. Сергеев. — СПб. БХВ-Петербург, 2010. — 240 с.

32. Гузик, В. Ф. Реконфигурируемые вычислительные системы: учеб. пособие / В. Ф. Гузик, И. А. Каляев, И. И. Левин; под общ. ред. И. А. Каляева. — Ростов-на-Дону: Изд-во ЮФУ, 2016. — 472 с.

33. Дордопуло, А. И. Параллельно-конвейерная форма программы для программирования вычислительных систем гибридного типа / А. И. Дордопуло, И. И. Левин, И. А. Каляев [и др.] // Вестник Уфимского государственного авиационного технического университета — 2016. — Том 20, № 3(73) — С. 122-128.

34. Sidler, D. et al. Accelerating Pattern Matching Queries in Hybrid CPU-FPGA Architectures. — SIGMOD, 2017.

35. Левин, И. И. Современные и перспективные высокопроизводительные вычислительные системы с реконфигурируемой архитектурой / И. И. Левин, А. И. Дордопуло, И. А. Каляев [и др.] // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2015)», г. Екатеринбург, 31 марта — 2 апреля 2015 г. — Челябинск: Издательский центр ЮУрГУ, 2015. — С. 188-199.

36. Moussalli, R. et al. High performance FPGA and GPU complex pattern matching over spatio-temporal streams // GeoInformatica. — 2015. — Т. 19. — № 2. — С. 405-434.

37. Дордопуло, А. И. Программирование вычислительных систем гибридного типа на основе метода редукции производительности / А. И. Дордопуло, И. И. Левин, И. А. Каляев [и др.] // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта — 1 апреля 2016 г.). — Челябинск: Издательский центр ЮУрГУ, 2016. — С. 131-140.

38. Новиков, Ю. В. Основы микропроцессорной техники: учебное пособие / Ю. В. Новиков, П. К. Скоробогатов. — 4-е изд., испр. — М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. — 357 с.

39. Горнец, Н. Н. Организация ЭВМ и систем: учебное пособие для студ. высш. учеб. заведений / Н. Н. Горнец, А. Г. Рощин, В. В. Соломенцев. — М.: Издательский центр «Академия», 2006. — 320 с.

40. Степанов, А. Н. Архитектура вычислительных систем и компьютерных сетей: учебное пособие / А. Н. Степанов. — СПб.: Питер, 2007. — 509 c.

41. Таненбаум, Э. Архитектура компьютера / Э. Таненбаум, Т. Остин. — 6-е изд. — СПб.: Питер, 2013. — 816 с.

42. Blem, E. Power struggles: Revisiting the RISC vs. CISC debate on contemporary ARM and x86 architectures / E. Blem, J. Menon, K. Sankaralingam // High Performance Computer Architecture (HPCA2013), 2013 IEEE 19th International Symposium on. — IEEE, 2013. — С. 1-12.

43. Heath, S. Microprocessor Architectures: RISC, CISC and DSP. — Elsevier, 2014. — 302 с.

44. Gallopoulos, E. Parallelism in Matrix Computations / Efstratios Gallopoulos, Bernard Philippe, Ahmed H. Sameh. — Springer, 2016. — 473 p.

45. Евсюков, В. С. Методы параллельного поиска вхождений и пересечений символьных данных и специализированные устройства для их реализации: дис. канд. тех. наук: 05.13.05 — Курск, 2009. — 184 с.

46. Burattini, E. NSP: a Neuro-Symbolic Processor / E. Burattini, M. De Gregorio, V. M. G. Ferreira [и др.] // Lecture Notes in Computer Science. — Heidelberg: Springer-Verlag GmbH, 2003. — vol. 2687. — P. 9-16.

47. King, A. Distributed Parallel Symbolic Execution / A. King. — B.S., Kansas State University, 2005. — 115 p.

48. Максфилд, К. Проектирование на ПЛИС. Курс молодого бойца / перевод с анг. — М.: Издательский дом «Додека-XXI», 2007. — 408 с.

49. Грушвицкий, Р. И. Проектирование систем на микросхемах программируемой логики. / Р. И. Грушвицкий, А. Х. Мурсаев, Е. П. Угрюмов. — СПб.: БХВ-Петербург, 2002. — 608 c.

50. Бродин, В. Б. Системы на микроконтроллерах и БИС программируемой логики / В. Б. Бородин, А. В. Калинин. — М.: Издательство ЭКОМ, 2002. — 400 c.

51. Каляев, И. А. Реконфигурируемые вычислительные системы на основе плис / И. А. Каляев, И. И. Левин, Е. А. Семерников // Перспективы развития РЛС дальнего обнаружения и интегрированных систем и комплексов информационного обеспечения Воздушно-космической обороны (РТИ Системы ВКО-2013): сборник материалов всероссийской научно-технической конференции. ОАО «РТИ». 2013. — 2013. — С. 172-188.

52. Kim, H. J. A Pipelined Non-Deterministic Finite Automaton-Based String Matching Scheme Using Merged State Transitions in an FPGA / H. J. Kim, K. I. Choi // PloS one. — 2016. — Т. 11. — № 10.

53. Каляев, И. А Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев, И. И. Левин, Е. А. Семерников [и др.]; под общ. ред. И. А. Каляева. — 2-е изд., перераб. и доп. — Ростов н/Д: ЮНЦ РАН, 2009. — 344 с.

54. Гришин, Д. С. Исчислительная продукционная система и организация параллельных выводов / Д. С. Гришин, Е. А. Титенко, С. Ю. Сазонов // Передовые научные разработки — 2013: сборник трудов IX международной научно-практической конференции. — Прага, 2013. — С. 5-8.

55. Евсюков, В. С. Архитектуры и аппаратные решения обработки символьной информации / В. С. Евсюков, Е. А. Титенко // Инфокоммуникационные системы. — 2009. — № 3. — С. 77-80.

56. Гришин, Д. С. Модифицированная продукционная система для параллельных символьных вычислений / Д. С. Гришин, Е. А. Титенко, М. А. Шевченко // ИИС-2015: материалы докладов III региональной заочной научно-практической конференции / ЮЗГУ. — Курск, 2015. — С. 128-130.

57. Гришин, Д. С. Алгоритм поиска подстроки на основе позиционного представления текста для архивно-текстовых данных / Д. С. Гришин,

Е. А. Титенко, Н. А. Милостная [и др.] // Известия Юго-Западного государственного университета. — 2015. — № 3(16). — С. 43-48.

58. Гришин, Д. С. Алгоритм построения структуры, представляющей строку в виде хеш-таблицы, состоящей из хешей подстрок данной строки и алгоритм поиска в ней / Д. С. Гришин, Е. А. Титенко // Известия Юго-Западного государственного университета. — 2015. — № 6(63). — С. 62-69.

59. Гришин, Д. С. Модифицированный цикл работы машины вывода / Д. С. Гришин, Е. А. Титенко, В. С. Фастов // Интеллектуальные информационные системы: тенденции, проблемы, перспективы: сборник материалов региональной заочной научно-практической конференции — Курск, 2013. — С. 102-105.

60. Choi, B. et al. DFC: Accelerating string pattern matching for network applications // NSDI 16. — USENIX Association, 2016. — С. 551-565.

61. Смит, Уильям. Методы и алгоритмы вычислений на строках / Уильям Смит; пер. с англ. — М.: Вильямс, 2006. — 496 с.

62. Crochemore, M. Algorithms on Strings / M. Crochemore, C. Hancart, T. Lecroq. — Cambridge University Press, 2007. — 392 p.

63. Гасфилд, Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Дэн Гасфилд; пер. с англ. — СПБ.: Невский Диалект; БХВ-Петербург, 2003. — 654 с.

64. Кормен, Т. Х. Алгоритмы: построение и анализ / Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест [и др.]; пер. с англ. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.

65. Graham, A. Stephen. String searching algorithms: Lecture Notes Series on Computing, Vol. 3 — Singapore: World Scientific, 1994. — 256 p.

66. Chen, K. H. Bit-parallel algorithms for exact circular string matching / K. H. Chen, G. S. Huang, R. C. T. Lee // The Computer Journal. — 2014. — Т. 57. — № 5. — С. 731-743.

67. Breslauer, D. Simple real-time constant-space string matching /

D. Breslauer, R. Grossi, F. Mignosi // Theoretical Computer Science. — 2013. — Т. 483. — С. 2-9.

68. Гришин, Д. С. Ассоциативное матричное устройство для обработки строковых данных в хранилищах текстовой информации / Д. С. Гришин,

E. А. Титенко // Информационные системы и технологии. — 2017. — № 3 (101). — С. 72-81.

69. Гришин, Д. С. Способ и устройство аппаратной поддержки процессов распознавания образов / Д. С. Гришин, Е. А. Титенко, С. Г. Емельянов [и др.] // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы XIII международной научно-технической конференции «Распознавание — 2017» / ЮЗГУ. — Курск, 2017. — С. 148-150.

70. Зерин, И. С. Метод, алгоритм и техническое решение параллельного поиска и подстановки на ассоциативной памяти / И. С. Зерин, О. И. Атакищев, Е. А. Титенко [и др.] // В мире научных открытий — Красноярск: Научно-инновационный центр, 2012 — № 1.1. — С. 166-180.

71. Воеводин, Вад. Вл. Характеристики типовых алгоритмических структур // Вестник Нижегородского университета им. Н. И. Лобачевского. — 2011. — № 2(1). — С. 181-189.

72. Левин, И. И. Комплексная минимизация цифровых автоматов при решении задачи поиска шаблонов / И. И. Левин, Д. Н. Ильченко // Вестник компьютерных и информационных технологий. — № 5 — 2014. — С. 3-7.

73. Титенко, Е. А. Устройство и алгоритм ассоциативного поиска вхождений / Е. А. Титенко, В. С. Евсюков, Е. А. Семенихин // Известия Курского государственного технического университета. — 2009. — № 2(27). — С. 56-62.

74. Бовкун, А. В. Методы структурной оптимизации для повышения удельной производительности прикладных программ // Труды десятой

юбилейной ежегодной научной конференции студентов и аспирантов базовых кафедр. — Ростов н/Д: Изд-во ЮНЦ РАН, 2014. — С. 60-61.

75. Le, H. A memory-efficient and modular approach for large-scale string pattern matching / H. Le, V. K. Prasanna // IEEE Transactions on Computers. — 2013. — Т. 62. — № 5. — С. 844-857.

76. Титенко, Е. А. Структурно-лингвистический подход определения продукционных исчислительных систем для задания недетерминированных вычислительных процессов / Е. А. Титенко, М. В. Шиленков // Инфокоммуникационные системы. — 2009 — № 3. — С. 77-80.

77. Довгаль, В. М. Быстрые символьные вычисления: Акселерация работы формул подстановок // Изв. Вузов. Сер Приборостроение. — 2005. — Т. 48. № 2. — С. 44-49.

78. Титенко, Е. А. Продукционная система для реализации параллельных символьных вычислений / Е. А. Титенко, В. М. Довгаль. // Системы управления и информационные технологии. — 2006. — № 1 (23) — С. 185-187.

79. Марков, А. А., Теория Алгорифмов / А. А. Марков, Н. М. Нагорный. — М.: Наука, 1984. — 432 с.

80. Гришин, Д. С. Способ подборки данных в хранилищах текстовых данных на основе продукционного подхода и моделирование его работы // Интернет-журнал «НАУКОВЕДЕНИЕ» Том 9, № 3 (2017) http://naukovedenie.ru/PDF/77TVN317.pdf (доступ свободный).

81. Шилдт, Г Искусство программирования на Java / Г. Шилдт, Дж. Холмс. — М.: Диалектика, 2005. — 336 с.

82. Пат. 2569567 Российская Федерация, МПК G11C 15/00. Способ и ассоциативное матричное устройство для обработки строковых данных / Д. С. Гришин, Е. А. Титенко, А. В. Белокопытов [и др.]; заявитель и патентообладатель Юго-Западный государственный университет. — № 2014110753/08; заявл. 21.03.2014; опубл. 27.11.2015, Бюл. № 33.

83. Гришин, Д. С. Алгоритм поиска подстроки, использующий позиционное представление текста в качестве дополнительной структуры / Д. С. Гришин, Е. А. Титенко, В. А. Ханис // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы XII международной научно-технической конференции «Распознавание — 2015» / ЮЗГУ. — Курск, 2015. — С. 107-110.

84. Вирт, Никлаус. Алгоритмы и структуры данных. Новая версия для Оберона + CD / Никлаус Вирт; пер. с англ. — М.: ДМК Пресс, 2010. — 272 с.

85. Макконнелл, Дж. Основы современных алгоритмов / Дж. Макконнелл; пер. с англ. — 2-е доп. изд. М.: Техносфера, 2004. — 368 с.

86. Кнут, Дональд Эрвин. Искусство программирования, том 3. Сортировка и поиск / Дональд Эрвин Кнут; пер. с англ. — 2-е изд. — М.: Вильямс, 2007. — 832 с.

87. Дасгупта, С. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани; пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2014. — 320 с.

88. Pachocki, J. Where to use and how not to use polynomial string hashing / J. Pachocki, J. Radoszewski // Olympiads in informatics, Vol. 7. — Warsaw, 2013. — P. 90-100.

89. Sarkar P. A trade-off between collision probability and key size in universal hashing using polynomials / P. Sarkar // Des. Codes Cryptography — 2011 — № 58. — P. 271-278.

90. Троелсен, Э. Язык программирования C# 2010 и платформа .NET 4.0 / Э. Троелсен; пер. с англ. — 5-е изд. — М.: Вильямс, 2011. — 1392 с.

91. Рихтер, Д. CLR via C#. Программирование на платформе Microsoft .NET Framework 4.5 на языке C#— 4-е изд. — СПб.: Питер, 2013. — 896 с.

92. Capek, P. Towards an empirical analysis of. NET framework and C# language features' adoption / P. Capek, E. Kral, R. Senkerik // CSCI, 2015 International Conference on. — IEEE, 2015. — С. 865-866.

93. Troelsen, A. Advanced C# Language Features/ A. Troelsen, P. Japikse // C# 6.0 and the. NET 4.6 Framework. — Apress, 2015. — С. 399-437.

94. Doyle, B. C# Programming: From Problem Analysis to Program Design. — Cengage Learning, 2013. — 1088 с.

95. Гришин, Д. С. Программа тестирования поисковых алгоритмов с применением хэш-данных / Д. С. Гришин, Е. А Титенко, А. В. Гривачев [и др.] // Свидетельство о государственной регистрации программы для ЭВМ № 2016663385, РФ. Зарегистр. в Реестре программ для ЭВМ 07.12.2016 г. Правообладатель: Юго-Западный государственный университет.

96. Пат. 2509383 Российская Федерация, МПК G11C 15/00. Способ параллельного поиска и замены строки и однородная запоминающая матрица для его реализации / Е. А. Титенко, И. С. Зерин, В. С. Евсюков [и др.]; заявитель и патентообладатель Юго-Западный государственный университет. — № 2012113755/08; заявл. 06.04.2012; опубл. 10.03.2014, Бюл. № 7.

97. Рабаи, Жан М. Цифровые интегральные схемы. Методология проектирования / Жан М. Рабаи, Ананта Чандракасан, Боривож Николич; пер. с англ. — 2-е изд. — М.: Вильямс, 2007. — 912 с.

98. Пат. № 2296366 Российская Федерация, МПК G06F 17/30, G06F 17/21. Устройство параллельного поиска и замены вхождений в обрабатываемых словах / Шевелев С. С.; заявитель и патентообладатель Курский государственный технический университет. — № 2005125327/09; заявл. 09.08.2005; опубл. 27.03.2007 Бюл. № 9.

99. Потехин, В. А. Схемотехника цифровых устройств: учеб. пособие для вузов / В. А. Потехин — Томск: В-Спектр, 2012. — 250 с.

100. Угрюмов, Е. П. Цифровая схемотехника: учеб. пособие для вузов / Е. П. Угрюмов. — 3-е изд., перераб. и доп. — СПб.: БХВ-Петербург, 2010. — 816 с.

101. Лехин, С. Н. Схемотехника ЭВМ: учеб. пособие для вузов / С. Н. Лехин. — СПб.: БХВ-Петербург, 2010. — 672 с.

102. Новожилов, О. П. Электротехника и электроника: учебник для бакалавров / О. П. Новожилов. — 2-е изд., исправ. и доп. — М.: Издательство Юрайт, 2016. — 653 с. — Серия: Бакалавр. Базовый курс.

103. Аверченков, О. Е. Схемотехника: аппаратура и программы / О. Е. Аверченков. — М.: ДМК Пресс, 2012. — 588 с.

104. Щука, А. А. Электроника: учеб. пособие для вузов / А. А. Щука. — 2-е изд., перераб. и доп. — СПб.: БХВ-Петербург, 2008. — 752 с.

105. Потемкин, И. С. Функциональные узлы цифровой автоматики / И. С. Потемкин. — М.: Энергоатомиздат, 1988. — 320 с.

106. Комолов, Д. А. Системы автоматизированного проектирования фирмы Altera MAX+plus II и Quartus II. Краткое описание и самоучитель / Д. А. Комолов, Р. А. Мяльк, А. А. Зобенко [и др.]. — М.: ИП РадиоСофт, 2002 — 352 с.

107. Стешенко, В. Б. ПЛИС фирмы ALTERA: проектирование устройств обработки сигналов / В. Б. Стешенко. — М.: ДОДЕКА, 2000. — 128 с.

ПРИЛОЖЕНИЕ 1

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

Mogyflb Testing.cs

using System;

using System.Collections.Generic; using System.Linq;

using Microsoft.Office.Interop.Excel;

using System.Reflection;

using System.Runtime.InteropServices;

using System.IO;

using AlgTest.Algorithms;

using System.Xml.Serialization;

using System.Runtime.Serialization;

using System.Xml;

using System.Text;

namespace AlgTest {

public class Testing {

public Dictionary<string, TestResult> TestResults { get; set; }

public Testing() {

TestResults = new Dictionary<string, TestResult>();

}

public string GenerateString(int stringLength, int alpabetLength) {

char[] charArray = new char[stringLength]; Random random = new Random();

for (int i = 0; i < charArray.Length; i++) {

char c = Convert.ToChar(random.Next(0, alpabetLength) + 65); charArray[i] = c;

}

return new string(charArray);

}

public string GetStringPart(string fullString, int partLength) {

int maxIndexOfPartStart = fullString.Length - partLength; Random rand = new Random();

string stringPart = fullString.Substring(rand.Next(maxIndexOfPartStart + 1),

partLength);

List<char> uncorrectChars = new List<char>();

for (int i = 0; i < stringPart.Length; i++) {

if ((int)stringPart[i] > 255) {

uncorrectChars.Add(stringPart[i]);

}

uncorrectChars = uncorrectChars.Distinct().ToList();

foreach (var uncorrectChar in uncorrectChars) {

stringPart = stringPart.Replace(uncorrectChar, (char)rand.Next(256));

}

return stringPart;

}

public List<int> CorrectSearch(string text, string pattern) {

List<int> indexes = new List<int>();

for (int index = 0; ; index += 1) {

index = text.IndexOf(pattern, index); if (index == -1)

return indexes; indexes.Add(index);

}

}

public bool CompareResults(List<int> correctResult, Dictionary<string,

List<int>> results) {

foreach (var item in results) {

if (item.Value.Count != correctResult.Count) {

return false;

}

else {

for (int i = 0; i < correctResult.Count; i++) {

if (correctResult[i] != item.Value[i]) {

return false;

}

}

}

}

return true;

}

private string GetExcelColumnName(int columnNumber) {

int dividend = columnNumber; string columnName = String.Empty; int modulo;

while (dividend > 0) {

modulo = (dividend - 1) % 26;

columnName = Convert.ToChar(65 + modulo).ToString() + columnName; dividend = (int)((dividend - modulo) / 26);

}

return columnName;

}

public void CreateDiagram(Worksheet workSheet, GroupedResult result) {

ChartObjects xlCharts = (ChartObjects)workSheet.ChartObjects(Type.Missing); ChartObject myChart = (ChartObject)xlCharts.Add(200, 10, 1200, 500);

Chart chartPage = myChart.Chart; myChart.Select();

chartPage.ChartType = XlChartType.xlXYScatterLines; SeriesCollection seriesCollection = chartPage.SeriesCollection();

for (int i = 0; i < result.GroupedParameter.Length; i++) {

workSheet.Cells[i + 1, 1] = result.GroupedParameter[i];

}

int colIndex = 2;

foreach (var item in result.GroupedTime) {

for (int i = 0; i < item.Value.Length; i++) {

workSheet.Cells[i + 1, colIndex] = item.Value[i];

}

colIndex++;

}

int startIndex = 1;

int finishIndex = result.GroupedParameter.Length; int valueColumnIndex = 1;

string cellStart = GetExcelColumnName(valueColumnIndex) + startIndex; string cellFinish = GetExcelColumnName(valueColumnIndex) + finishIndex; int cellIndex = 2;

foreach (var item in result.GroupedTime) {

Series series = seriesCollection.NewSeries(); series.Name = item.Key;

series.XValues = workSheet.get_Range(cellStart, cellFinish); series.Values = workSheet.get_Range(GetExcelColumnName(cellIndex) + startIndex, GetExcelColumnName(cellIndex) + finishIndex);

cellIndex++;

}

}

public void CreateTable(Worksheet workSheet, AverageResult result) {

ChartObjects xlCharts = (ChartObjects)workSheet.ChartObjects(Type.Missing); int row = 1;

foreach (var item in result.AverageTime) {

workSheet.Cells[row, 1] = item.Key; workSheet.Cells[row, 2] = item.Value; row++;

}

}

public double GetMedian(double[] array) {

double[] tempArray = array; int count = tempArray.Length; Array.Sort(tempArray); double medianValue = 0;

if (count % 2 == 0) {

double middleElement1 = tempArray[(count / 2) - 1]; double middleElement2 = tempArray[(count / 2)]; medianValue = (middleElement1 + middleElement2) / 2;

}

else {

medianValue = tempArray[(count / 2)];

return medianValue;

}

public string CreateReport(TestResult testResult) {

var path = Path.Combine(Environment.CurrentDirectory, DateTime.Now.ToString().Replace(".", "").Replace(":", "") + ".result");

XmlTextWriter xw = new XmlTextWriter(path, Encoding.UTF8); xw.Formatting = Formatting.Indented;

XmlDictionaryWriter writer = XmlDictionaryWriter.CreateDictionaryWriter(xw);

DataContractSerializer ser = new DataContractSerializer(typeof(TestResult));

ser.WriteObject(writer, testResult);

writer.Close();

xw.Close();

object misValue = Missing.Value;

_Application xlApp = new Application();

Workbook xlWorkBook = xlApp.Workbooks.Add(misValue);

Worksheet textLengthWS = (Worksheet)xlWorkBook.Worksheets.get_Item(1);

textLengthWS.Name = "textLengthWS";

GroupedResult GroupedByTextLength = new GroupedResult(GroupedType.SearchTimeByTextLength, testResult);

CreateDiagram(textLengthWS, GroupedByTextLength);

Worksheet patternLengthWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing, 1, Type.Missing);

patternLengthWS.Name = "patternLengthWS";

GroupedResult GroupedByPatternLength = new GroupedResult(GroupedType.SearchTimeByPatternLength, testResult);

CreateDiagram(patternLengthWS, GroupedByPatternLength);

Worksheet alphabetLengthWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing, 1, Type.Missing);

alphabetLengthWS.Name = "alphabetLengthWS";

GroupedResult GroupedByAlphabetLength = new GroupedResult(GroupedType.SearchTimeByAlphabetLength, testResult);

CreateDiagram(alphabetLengthWS, GroupedByAlphabetLength);

Worksheet resultCountWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing, 1, Type.Missing);

resultCountWS.Name = "resultCountWS";

GroupedResult GroupedByResultCount = new GroupedResult(GroupedType.SearchTimeByResultCount, testResult);

CreateDiagram(resultCountWS, GroupedByResultCount);

Worksheet iniTextLengthWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing, 1, Type.Missing);

iniTextLengthWS.Name = "iniTextLengtWS";

GroupedResult GroupedByIniTextLength = new GroupedResult(GroupedType.IniTimeByTextLength, testResult);

CreateDiagram(iniTextLengthWS, GroupedByIniTextLength);

Worksheet iniAlphabetLengthWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing, 1, Type.Missing);

iniAlphabetLengthWS.Name = "iniAlphabetLengthWS";

GroupedResult GroupedByIniAlphabetLength = new GroupedResult(GroupedType.IniTimeByAlphabetLength, testResult);

CreateDiagram(iniAlphabetLengthWS, GroupedByIniAlphabetLength);

Worksheet averageSearchTimeWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing, 1, Type.Missing);

averageSearchTimeWS.Name = "averageSearchTimeWS";

AverageResult averageSearchTime = new AverageResult(AverageType.AverageSearchTime, testResult);

CreateTable(averageSearchTimeWS, averageSearchTime);

Worksheet averageIniTimeWS = (Worksheet)xlWorkBook.Sheets.Add(Type.Missing, Type.Missing); averageIniTimeWS.Name = "averageIniTimeWS";

AverageResult averageIniTime = new AverageResult(AverageType.AverageIniTime,

CreateTable(averageIniTimeWS, averageIniTime);

string filePath = Path.Combine(Environment.CurrentDirectory, DateTime.Now.ToString().Replace(".", "").Replace(":", "") + ".xlsx");

xlWorkBook.SaveAs(filePath, XlFileFormat.xlWorkbookDefault, misValue, misValue, misValue, misValue, XlSaveAsAccessMode.xlExclusive, misValue, misValue, misValue, misValue, misValue);

xlWorkBook.Close(true, misValue, misValue); xlApp.Quit();

Marshal.ReleaseComObject(textLengthWS); Marshal.ReleaseComObject(alphabetLengthWS); Marshal.ReleaseComObject(resultCountWS); Marshal.ReleaseComObject(patternLengthWS);

Marshal.ReleaseComObject(iniTextLengthWS); Marshal.ReleaseComObject(iniAlphabetLengthWS);

Marshal.ReleaseComObject(averageSearchTimeWS); Marshal.ReleaseComObject(averageIniTimeWS);

Marshal.ReleaseComObject(xlWorkBook); Marshal.ReleaseComObject(xlApp);

return filePath;

}

}

[DataContract]

public class TestResult {

[DataMember]

public List<int> TextLength { get; set; } [DataMember]

public List<int> PatternLength { get; set; } [DataMember]

public List<int> AlphabetLength { get; set; } [DataMember]

public Dictionary<string, List<double>> SearchTimeInMilliseconds { get; set; } [DataMember]

public Dictionary<string, List<double>> IniTimeInMilliseconds { get; set; } [DataMember]

public List<int> ResultCount { get; set; }

public TestResult() {

TextLength = new List<int>(); PatternLength = new List<int>(); AlphabetLength = new List<int>();

SearchTimeInMilliseconds = new Dictionary<string, List<double>>(); IniTimeInMilliseconds = new Dictionary<string, List<double>>();

Type.Missing, 1, testResult);

ResultCount = new List<int>();

public void Add(int textLength, int patternLength, int alphabetLength, int resultCount, Dictionary<string, double> searchTimeInMilliseconds, Dictionary<string, double>

iniTimeInMilliseconds) {

TextLength.Add(textLength); PatternLength.Add(patternLength); AlphabetLength.Add(alphabetLength); ResultCount.Add(resultCount);

foreach (var item in searchTimeInMilliseconds) {

List<double> searchTimeInMillisecondsValue; if (SearchTimeInMilliseconds.TryGetValue(item.Key, out

searchTimeInMillisecondsValue))

{

searchTimeInMillisecondsValue.Add(item.Value);

}

else {

SearchTimeInMilliseconds.Add(item.Key, new List<double>() {

item.Value });

}

}

foreach (var item in iniTimeInMilliseconds) {

List<double> iniTimeInMillisecondsValue; if (IniTimeInMilliseconds.TryGetValue(item.Key, out

iniTimeInMillisecondsValue))

{

iniTimeInMillisecondsValue.Add(item.Value);

}

else {

IniTimeInMilliseconds.Add(item.Key, new List<double>() { item.Value

}

}

}

public class GroupedResult {

public GroupedType Type { get; set; }

public int[] GroupedParameter { get; set; }

public Dictionary<string, double[]> GroupedTime { get; set; }

public GroupedResult(GroupedType type, TestResult testResult) {

GroupedTime = new Dictionary<string, double[]>(); GroupResultBy(testResult, type);

}

public void GroupResultBy(TestResult testResult, GroupedType groupedType) {

List<int> parameterList = new List<int>();

Dictionary<string, List<double>> timeList = new Dictionary<string,

List<double>>();

switch (groupedType) {

}

case GroupedType.SearchTimeByTextLength: parameterList = testResult.TextLength; timeList = testResult.SearchTimeInMilliseconds; break;

case GroupedType.SearchTimeByPatternLength: parameterList = testResult.PatternLength; timeList = testResult.SearchTimeInMilliseconds; break;

case GroupedType.SearchTimeByAlphabetLength: parameterList = testResult.AlphabetLength; timeList = testResult.SearchTimeInMilliseconds; break;

case GroupedType.SearchTimeByResultCount: parameterList = testResult.ResultCount; timeList = testResult.SearchTimeInMilliseconds; break;

case GroupedType.IniTimeByAlphabetLength:

parameterList = testResult.AlphabetLength; timeList = testResult.IniTimeInMilliseconds; break;

case GroupedType.IniTimeByTextLength:

parameterList = testResult.TextLength; timeList = testResult.IniTimeInMilliseconds; break;

default: break;

}

GroupedParameter = parameterList.Distinct().ToArray();

Dictionary<string, List<double>> tempTime;

for (int i = 0; i < GroupedParameter.Length; i++)

{

tempTime = new Dictionary<string, List<double>>();

for (int j = 0; j < parameterList.Count; j++)

{

if (GroupedParameter[i] == parameterList[j]) {

item.Value[j] });

}

}

foreach {

double[] groupedTimeValue;

if (GroupedTime.TryGetValue(item.Key, out groupedTimeValue)) {

groupedTimeValue[i] = item.Value.Average();

}

else {

double[] array = new double[GroupedParameter.Length]; array[i] = item.Value.Average();

foreach (var item in timeList) {

List<double> tempTimeValue;

if (tempTime.TryGetValue(item.Key, out tempTimeValue)) {

tempTimeValue.Add(item.Value[j]);

}

else {

tempTime.Add(item.Key, new List<double>() {

}

}

(var item in tempTime)

GroupedTime.Add(item.Key, array);

}

var tempGroupetParameter = GroupedParameter; var tempGroupetTime = GroupedTime;

QuickSort(ref tempGroupetParameter, ref tempGroupetTime, 0, GroupedParameter.Length - 1);

GroupedParameter = tempGroupetParameter; GroupedTime = tempGroupetTime;

}

void QuickSort(ref int[] groupedParameter, ref Dictionary<string, double[]>

groupedTime, int first, int last) {

int p = groupedParameter[(last - first) / 2 + first]; int temp;

int i = first, j = last;

while (i <= j) {

while (groupedParameter[i] < p && i <= last) ++i;

while (groupedParameter[j] > p && j >= first) --j; if (i <= j)

temp = groupedParameter[i]; groupedParameter[i] = groupedParameter[j]; groupedParameter[j] = temp;

double temp1;

foreach (var item in groupedTime) {

temp1 = item.Value[i]; item.Value[i] = item.Value[j]; item.Value[j] = temp1;

}

++i; --j;

}

}

if (j > first) QuickSort(ref groupedParameter, ref groupedTime, first, j); if (i < last) QuickSort(ref groupedParameter, ref groupedTime, i, last);

}

}

public enum GroupedType {

SearchTimeByTextLength, SearchTimeByPatternLength, SearchTimeByAlphabetLength, SearchTimeByResultCount, IniTimeByTextLength, IniTimeByAlphabetLength

}

public class AverageResult {

public AverageType Type { get; set; }