Содержание к диссертации
Введение
Глава 1 Обзор существующих алгоритмических и аппаратных средств для множественной подборки текстовых данных в хранилищах. обоснование и выбор направления исследования 12
1.1. Хранение данных в корпоративных информационных системах. Общие принципы организации хранилищ данных и вычислительные средства обработки запросов 12
1.1.1. Хранилища данных и их оперативный анализ 13
1.1.2. Отличительные особенности операционных систем и хранилищ данных 15
1.1.3. Множественная подборка данных и представление результатов 17
1.2. Обзор аппаратных архитектур устройств для высокопроизводительных вычислений 22
1.2.1. Гарвардская архитектура 24
1.2.2. Суперскалярные и VLIW-процессоры 27
1.2.3. Символьные процессоры и архитектуры 31
1.2.4. Интегральные схемы с программируемой структурой 32
1.3. Обзор алгоритмов подборки данных 37
1.3.1. Алгоритм Бойера — Мура 37
1.3.2. Алгоритм подборки данных в суффиксном дереве 39
1.3.3. Алгоритм подборки данных в позиционном представлении текста 40
1.3.4. Требования предьявляемые к алгоритмам для множественной подборки текстовых данных в хранилищах. Сравнение основных алгоритмов подборки данных 42
1.4. Сущность предлагаемого подхода 43
1.5. Выводы по главе 45
Глава 2 Разработка способов для множественной подборки текстовых данных в хранилищах 46
2.1. Продукционная парадигма вычислений 46
2.2. Модифицированное суффиксное дерево 50
2.3. Гибридное позиционное представление текста 53
2.4. Модифицированное позиционное представление текста 61
2.5. Выводы по главе 72
Глава 3 Программное моделирование способов подборки 74
3.1. Описание среды разработки приложения 74
3.2. Описание приложения моделирования 78
3.3. Моделирование работы способов подборки данных и анализ полученных результатов 79
3.3.2. Анализ средних временных затрат подборки и предобработки данных 83
3.3.3. Анализ зависимости временных затрат подборки данных относительно размера входного текста 88
3.3.4. Анализ зависимости временных затрат подборки данных относительно размера входной подстроки 91
3.3.5. Анализ зависимости временных затрат подборки данных относительно размера входного алфавита 94
3.3.6. Анализ зависимости временных затрат предобработки входного текста относительно размера входного текста 95
3.3.7. Анализ зависимости временных затрат предобработки входного текста относительно размера входного алфавита 98
3.4. Выводы по главе 100
Глава 4 Разработка специализированного ассоциативного устройства для множественной подборки текстовых данных в хранилищах. моделирование его работы 101
4.1. Разработка специализированного ассоциативного устройства 101
4.1.1. Разработка способа модификации данных на основе ассоциативной памяти 102
4.1.2. Разработка структурно-функциональной организации ассоциативного устройства 105
4.1.3. Разработка структурных схем основных блоков ассоциативного устройства 106
4.1.4. Разработка алгоритма работы ассоциативного устройства 112
4.2. Расчет аппаратной сложности устройств 120
4.3. Моделирование работы устройств 127
4.3.1. Описание моделирующей среды 128
4.3.2. Синтез имитационных моделей операционных блоков устройств 129
4.3.3. Анализ характеристик разработанного ассоциативного устройства 132
4.4. Выводы по главе 134
Заключение 136
Библиографический список 138
Приложение 1 150
- Множественная подборка данных и представление результатов
- Модифицированное позиционное представление текста
- Анализ средних временных затрат подборки и предобработки данных
- Разработка структурных схем основных блоков ассоциативного устройства
Введение к работе
Актуальность.
Важным направлением развития средств вычислительной техники является создание аппаратно-вычислительных средств для поддержки оперативной обработки запросов и доступа к данным в информационных системах, содержащих базы и хранилища текстовых данных. Среди хранимой информации значимая роль принадлежит текстовой и гипертекстовой информации, базовым обработчиком которой являются продукционные системы, учитывающие структурные и лингвистические отношения между символами. Кроме того, продукционная схема вычислений «условие действие» имеет потенциальные возможности для распараллеливания процессов подборки данных по набору шаблонов и модификации данных.
Особый интерес представляют базы и хранилища с неизменяемыми
текстовыми и гипертекстовыми данными — электронные библиотеки,
коллекции документов, электронные архивы, справочная информация и т. д.
Одномерные формы представления текстовых данных, их размер (сотни
мегабайт), многообразие связей, вариативность границ отдельных
информационных единиц и др., приводят к экспоненциальным и другим времяемким пропорциям доступа к базам и хранилищам, сложным запросам на доступ к данным. Как итог, запрос на аппаратном уровне декомпозируется последовательностью связанных поисковых процессов по набору шаблонов, уточняемых в процессе поиска.
Как правило, в обрабатывающих серверах БД операции безотступного перебора элементов данных, проверки структурно-лингвистических свойств, установления отношений между шаблонами не имеют соответствующей аппаратной поддержки в виде специализированных устройств ассоциативной обработки текстовых операндов, управления режимами адресаций ячеек оперативной памяти, параллельной обработки безадресных структур, мультиплексирования массивов текстовых данных и др. Итерационный характер организации поиска по набору связанных шаблонов приводит к необходимости учета множественных вариантов в следующем цикле вычислений, что требует динамической буферизации данных непосредственно в устройстве, обеспечивающем параллельную обработку запросов в хранилищах данных.
Несмотря на впечатляющие успехи развития современных
микропроцессоров CISC-, RISC-архитектур продукционные операции,
реализованные в типовой системе команд, приводят к непродуктивным временным и емкостным затратам на их реализацию вследстви обработки текстов как линейных объектов в одномерном пространстве.
Теоретические и прикладные исследования продукционных систем
рассматривались в работах А. А. Маркова, Н. М. Нагорного, Н. А. Шанина,
В. И. Городецкого, Дж. Люгера и др. Существенный вклад в изучении вопросов,
связанных с базами и хранилищами данных, внесли W. H. Inmon, R. Kimball,
E. F. Codd, C. J. Date, R. Wrembel, М. Р. Когаловский, А. А. Барсегянян,
М. С. Куприянов, В. В. Степаненко, И. И. Холод и др. Вопросы создания
перспективных архитектур и схемотехнических решений для микропроцессоров
отражены в работах Е. П. Угрюмова, К. Г. Самофалова, Е. А. Зельдина,
В. А. Потехина, В. В. Корнеева, А. В. Киселева и др. Разработка
специализированных устройств, в том числе на программируемых
интегральных схемах, и параллельной обработки данных рассматривалась в трудах ученых И. А. Каляева, И. И. Левина, В. В. Сташина, И. С. Еремеева и др.
Вместе с тем вопросы исследования продукционных систем для реализации запросов к базам и хранилищам текстовых данных и аппаратной реализации продукционных операций под обработку неизменяемых текстовых данных нашли только частичное отражение в трудах этих ученых. Сложившееся в современной вычислительной технике проблемная ситуация несоответствия между непродуктивными временными затратами на поисковые операции обработки запросов и структурой микропроцессоров общего назначения отражает основное противоречие современных алгоритмических и аппаратных средств для оперативной реализации продукционных операций под обработку запросов к базам и хранилищам текстовых данных. На разрешение данного противоречия направлено диссертационное исследование.
Научно-техническая задача — разработка программно-аппаратных средств, реализующих строковые операции подборки и модификации текстовых данных в хранилищах.
Объект исследования — способы, вычислительные процессы и технические средства реализации множественной подборки и модификации текстовых данных.
Предмет исследования — способы, алгоритмы и схемотехнические решения реализации базовых продукционных операций для множественной подборки и модификации текстовых данных на основе ассоциативной памяти.
Цель работы — сокращение временных затрат на операции
множественной подборки текстовых данных в хранилищах путем разработки модифицированного позиционного представления текста, а также способа и специализированного устройства для параллельного поиска и модификации текстовых данных.
Основные задачи диссертационного исследования:
-
Анализ современных алгоритмических и аппаратных средств, используемых или обеспечивающих множественную подборку текстовых данных в хранилищах. Обоснование направления исследования.
-
Разработка модифицированного позиционного представления текстовых данных для хранилищ, содержащего дополнительную информацию о внутренней организации текста.
-
Разработка способа для множественной подборки текстовых данных в хранилищах на основе разработанного модифицированного позиционного представления текста.
-
Моделирование работы разработанного способа для множественной подборки текстовых данных в хранилищах. Разработка программных средств для моделирования.
-
Разработка структурно-функциональной организации специализированного устройства для множественной подборки текстовых данных в хранилищах, разработка схемотехнических решений основных блоков
и узлов устройства, а также экспериментальная проверка его
работоспособности, анализ его временных затрат и аппаратной сложности.
Методы исследования. Для решения поставленных задач использовались методы, основанные на теории проектирования электронно-вычислительных машин, схемотехнике, ассоциативной памяти, математической логике, теории множеств, математической статистики, аппарата продукционных систем, а также теории алгоритмов и прикладного программирования.
Научная новизна и результаты, выносимые на защиту:
-
Модифицированное позиционное представление текста, дополняющее классическое позиционное представление новыми элементами, обеспечивающее тем самым направленность поиска и исключающее ряд неперспективных операций.
-
Способ для множественной подборки данных в модифицированном позиционном представлении текста, позволяющий вычислять сокращенный набор позиций возможных вхождений, разбиением входной подстроки на собственные не пересекающиеся подстроки размером ограниченным константой разработанного представления и получением набора с минимальным количеством элементов среди наборов позиций вхождений этих подстрок.
-
Структурно-функциональная организация специализированного устройства для множественной подборки текстовых данных в хранилищах, отличающаяся в аппаратной реализации операций последовательного и межстрочного сдвига при строковом и матричном представлении обрабатываемых текстовых данных с возможностью временной буферизации граничных элементов строк, выходящих за пределы операционного блока устройства, что позволяет ускоренно реализовывать шаги обработки текстовых данных при различных сочетаниях размеров подстроки и строки-модификатора, в том числе выполнять реверсивные межстрочные сдвиги.
Практическая ценность работы состоит в следующем:
-
Разработанное модифицированное позиционное представление текста для хранилищ текстовых данных позволяет выполнять гибкую настройку соотношения временных затрат подборки к временным затратам его построения, установкой значения максимального размера подстрок, хранящихся в данном представлении, что позволяет расширить область его применения и использовать априорные знания о входных данных для сокращения временных затрат множественной подборки. Если такая информация отсутствует задаваемый пользователем размер подстроки рекомендуется выбирать равным 5, что эмпирически обеспечивает оптимальное соотношение временных затрат подборки данных и предобработки входного текста.
-
Разработанный способ для множественной подборки данных в модифицированном позиционном представлении текста, позволяет вычислять сокращенный набор позиций возможных вхождений. Проведенный анализ временных затрат разработанного способа показал, что данный способ позволяет сократить временные затраты относительно способа подборки на
основе суффиксного дерева на 10 % для искусственно построенных данных и на 17 % для естественных данных.
3. Разработанное ассоциативное устройство позволяет сократить
временные затраты модификации данных относительно устройства-прототипа на 14 % и на 80 % относительно устройства-аналога.
Реализация результатов работы. Результаты диссертационной работы внедрены в:
-
Комитет информатизации, государственных и муниципальных услуг Курской области, в части оказания государственных и муниципальных услуг населению и оперативной обработке обращений к базам межведомственных запросов и статистики оказания государственных и муниципальных услуг Курской области.
-
ООО «Инновационные системы управления», (г. Курск). в части реализации способа, алгоритмов и схемотехнических решений основных блоков и узлов устройства для множественной подборки данных, реализованные на ПЛИС 5SGSED8I2F45C2 семейства Stratix.
-
Учебный процесс федерального государственного бюджетного образовательного учреждения высшего образования «Юго-Западный государственный университет» по дисциплине «Интеллектуальные системы и технологии» магистров направления «Информационные системы и технологии» в части реализации средств направленной обработки строковых данных.
Соответствие паспорту специальности. Диссертационная работа
соответствует паспорту научной специальности 05.13.05 — «Элементы и
устройства вычислительной техники и систем управления» по второму пункту
«Теоретический анализ и экспериментальное исследование функционирования
элементов и устройств вычислительной техники и систем управления в
нормальных и специальных условиях с целью улучшения
технико-экономических и эксплуатационных характеристик» в части
разработки способа и специализированного ассоциативного устройства для множественной подборки текстовых данных в хранилищах для реализации массовых вычислительных операций и обеспечения/обработки запросов, а также проверки работоспособности разработанного способа и устройства.
Апробация работы. Основные научные результаты работы докладывались
и обсуждались на региональной заочной научно-практической конференции
«Интеллектуальные информационные системы: тенденции, проблемы,
перспективы» (г. Курск, 2013), IX международной научно-практической
конференции «Передовые научные разработки» (г. Прага, 2013), XII
международной научно-технической конференции «Распознавание — 2015: Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2015), III региональной заочной научно-практической конференции «Интеллектуальные информационные системы: тенденции, проблемы, перспективы» (г. Курск, 2015), XIII международной научно-технической конференции «Распознавание — 2017: Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2017), а
также рассматривались на семинарах кафедры программной инженерии и
кафедры информационных систем и технологий Юго-Западного
государственного университета в 2013–2017 гг.
Публикации по работе. По результатам выполненных разработок и исследований опубликованы 11 работ, в том числе 4 работы в рецензируемых научных журналах и изданиях, получено свидетельство о регистрации программы для электронно-вычислительных машин, а также патент Российской Федерации на изобретение.
Личный вклад. Все выносимые на защиту научные результаты получены
соискателем лично. В работах по теме диссертации, опубликованных в
соавторстве, личный вклад соискателя сводится к следующему: в [1, 7]
разработан способ подборки в позиционном представлении текста,
использующий направленный порядок сравнения символов, проведен анализ
временных затрат подборки разработанным способом; в [2] разработано
модифицированное позиционное представление текста, разработан способ
подборки в разработанном представлении, проведен анализ временных затрат
подборки разработанным способом; в [3] разработана организация устройства
для множественной подборки и модификации данных, обеспечивающее
аппаратную поддержку способов подборки и модификации данных; в [4]
проведено моделирование работы продукционного способа подборки в
модифицированном позиционном представлении текста при различных
размерах хранимых подстрок; в [5] модифицирован управляющий цикл работы
абстрактной машины поиска данных для поддержки вычислений в хранилищах
текстовых данных; в [6] описана организация вычислений в продукционной
системе применительно к хранилищам данных; в [8] описана
модифицированная продукционная система для текстовых вычислений; в [9] предложен способ и организация матричного устройства параллельной обработки данных, которое позволяет совместить глобальную подборку и локальную модификацию данных; в [10] разработано ассоциативное матричное устройство для множественной подборки данных; в [11] разработано специализированное приложение моделирования работы способов подборки и анализа их временных затрат от параметров входных данных.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Основное содержание диссертации изложено на 149 страницах машинописного текста, содержит 48 рисунков, 24 таблицы, список литературы из 107 наименований.
Множественная подборка данных и представление результатов
Информационные системы поддержки принятия решений как правило имеют функции обеспечивающие предоставления пользователям данных в агрегированном виде, предназначенных для сложных (составных) выборок из входного (исходного) множества в удобном для анализа и восприятия виде.
В большинстве случаев, эти агрегатные функции образуют нереляционный, многомерный набор данных (называемый метакубом или гиперкубом), на осях которого содержатся параметры данных, а в ячейках — связанные с этими параметрами данные [7, 27, 28]. Между элементами (частями) агрегатных данных устанавливаются (определяются) отношения, ассоциации, что существенно повышает логическую и иную связность данных в многомерных построениях и позволяет провести результативный поиск даже по отдельной связи или некоторому свойству. Данные вдоль всех осей могут иметь иерархическую структуру, которая представляет разные уровни детализации. Благодаря этой модели данных пользователи могут формировать сложные запросы, получать подмножества данных и генерировать на их основе отчеты.
Составная выборка данных представляет собой связанный набор нерегламентированных запросов, при котором каждый следующий запрос к данным, а также вид их представления определяются, результатами предыдущих запросов. Для выборки данных используются сложные статистические алгоритмы искусственного интеллекта и поиска, которые используются для получения данных, их скрытых закономерностей, создание моделей на основе этих закономерностей, а также для прогнозирования развития ситуаций.
Результатом выборки или множественной подборки является организованное подмножество данных — система связанных объектов, релевантных запросу, но имеющих различную количественную, качественную, структурную степень близости/ассоциации с поисковыми данными.
Запрос представляет собой процесс отбора из массива индексируемых фрагментов данных таких его элементов, которые удовлетворяют определенным поисковым значениям. При этом большинство современных способов и алгоритмов подборки не ориентированы на параллельную аппаратную обработку входных данных большого размера, таких как данные, находящиеся в хранилищах текстовых данных.
Программные средства множественной подборки данных как правило выполняют две важные функции: компиляцию входящих от пользователей запросов в исполняемый код и выполнение скомпилированного кода. Компиляция и разбор запроса состоят из пяти основных стадий: синтаксический анализ, формирование логического запроса, навигация, оптимизация и генерации результирующего кода. При этом самой важной и основной является стадия оптимизации или переписывания запросов. Во время выполнения этой стадии сервер оптимизирует запрос, учитывая свойства всех источников.
При объединении данных учитывается их физическое расположение (таблица в БД, плоский файл и т. д), особенности работы SQL, который поддерживается БД и сложности (аналитической) запроса. Кроме того, подборка данных в хранилище, как правило, обращена к большим объемам данных, что требует больших объемов памяти, мощности процессора и ресурсов для визуализации результатов поиска.
Обычно составную выборку данных стараются максимально перенести на серверы источников данных, т. к. процесс выборки включает часто используемые операции поиска и модификации данных [13, 18, 29, 30]. Хотя аналитический сервер может выполнять OLAP-вычисления и анализ, лучше для этого использовать отдельный OLAP-сервер, а при работе с наборами данных сверхбольшого размера лучшим решением будет использование высокопроизводительной реляционной СУБД. Поэтому при возможности подборка выполняется именно этими технологиями, а не аналитическим сервером, который в этом случае отвечает за получение запросов от клиентских приложений и их перевод в предложения SQL для исходных баз данных.
Когда исходные БД возвращают результаты запросов, аналитический сервер выполняет сведение данных и при необходимости, выполняет какие-либо вычисления, выполняет форматирование данных после чего отправляет эти данные клиентскому приложению.
Режимы функционирования БД для решения аналитических задач требуют особых настроек параметров, обработки запросов и способов индексирования. К числу которых относятся параллелизм, позволяющий максимально использовать возможности многопроцессорных серверов, эффективное битовое индексирование и различные специализированные алгоритмы обеспечения запросов, такие как хэш-соединения, многократно повышающие производительность обработки для аналитических подборок. В некоторых СУБД имеется возможность секционирования данных, которая значительно ускоряет выполнение обработки таблиц, имеющих очень большой размер, а также индексов. Существуют и другие более новые средства оптимизации, которые преобразуют запросы к типу «звезда».
Еще одним важнейшим усовершенствованием является технология управления суммарными данными, основанное на материализованных представлениях. Данная технология анализирует статистику работы СУБД и предлагает администратору произвести необходимые объединения данных, создает и периодически их обновляет.
Во время выполнения агрегированной подборки система переписывает их таким образом, чтобы они использовали суммарные данные, которые хранятся в материализованных представлениях. Как правило этот подход повышает производительность ХД для конечных пользователей на несколько порядков.
Другими подходами и методами, ориентированными на оперативную обработку сложных запросов, выступают специальные операции вычисления результатов и промежуточных результатов в отчетах, функциональные индексы, широкий набор встроенных аналитических средств и т. д.
Далее приводятся иллюстрации множественной подборки данных среди естественных текстов по системе связанных поисковых ключей, имеющих следующие значения:
1. «БОРОДИНО», «ПОРАЖЕНИЕ», «МОСКВА» (рисунок 1.1).
2. «ВОРОНА, «ЛИСИЦА», «СОЛОВЕЙ», «СЫР» (рисунок 1.2).
3. «АДА», «АЛИСА», «ЭЛЬБРУС», «ЭВЕРЕСТ» (рисунок 1.3).
Отличительная особенность множественных подборок связана с добавлением на следующей итерации поиска, к ключу найденных предыдущих подборок в результате выборка систематизируется (за счет увеличения ключа), но процесс поиска приобретает необходимую направленность, при этом множественная выборка по-прежнему включает в себя результаты поиска по отдельному ключу. В частном случае подборка сводится к реализации простой выборки, т. е. организации поиска по отдельному ключу или по множеству независимых ключей. Другими словами, такую выборку можно понимать, как операцию поиска вхождения по образцу.
Модифицированное позиционное представление текста
В данном разделе развивается позиционное преставление текста, как представление текста, позволяющее сократить количество операций множественной подборки данных за счет выполнения подборки только в тех позициях текста, в которых имеется пересечение подстроки и текста как минимум в одной позиции.
Известно, что основным недостатком подборки данных в ППТ является подборка подстроки полным и многократным, в том числе избыточным, просмотром списков с позициями вхождений каждого символа. Для его устранения в работе предлагается расширить ППТ за счет хранения всех собственных подстрок текста размером до задаваемого пользователем размера , с соответствующим набором позиций вхождений этих подстрок. Такое представление получило название, модифицированное ППТ (МППТ). Разрабатывается способ для множественной подборки данных в МППТ, позволяющий вычислять сокращенный набор позиций возможных вхождений что достигается, разбиением входной подстроки на собственные не пересекающиеся подстроки размером ограниченным константой разработанного представления и получением набора позиций возможных вхождений с минимальным количеством элементов среди наборов, полученных по хеш-значению этих подстрок.
В зависимости от значения временные затраты подборки и предобработки входного текста для способа подборки в МППТ могут значительно изменяться.
Разработанная модификация ППТ, позволяет дополнить классическое позиционное представление новыми элементами, что обеспечивает направленность поиска и исключение ряда неперспективных альтернатив.
Пример модифицированного позиционного представления текста «abcabaabca» при = 3 изображен на рисунке 2.10.
Данная модифицированное ППТ является информационной основой для способа множественной подборки данных, в котором можно выделить следующие шаги:
1. Построение модифицированного позиционного представления.
Построение МППТ осуществляется последовательным обходом текста, во процессе которого для каждой позиции текста получаются его собственные подстроки размером равным до символов, начинающиеся с текущей позиции, после чего в набор МППТ (пустое/недостроенное) для каждой полученной подстроки добавляется позиция ее начала.
2. Вычисление набора позиций возможных вхождений.
Набор позиций возможных вхождений вычисляется на основе набора с минимальным количеством элементов, полученным из МППТ по собственным не пересекающимся подстрокам входной подстроки, размер которых равен
Решение использовать непересекающиеся подстроки обусловлено тем, что при реализации построения МППТ, для хранения позиций вхождений подстрок используется их хеш-значение, а операция хеширования требует трудоемких вычислений.
Набор с минимальным количеством элементов, по которому вычисляется набор позиций возможных вхождений, извлекается из МППТ по подстроке Tf...f+t-1, где ft — позиция ее начала. Такая позиция равна
3. Подборка на основе позиций возможных вхождений. Подборка данным способом выполняется на классическом представлении текста и отличается от подборки наивным способом, только тем, что осуществляется только в вычисленных позициях возможных вхождений. Вычисление и использование направленного порядка сравнения символов, которое использовалось способом подборки данных в ГППТ, для данного способа не используется, поскольку в данном способе порядок сравнения символов играет второстепенную роль и временные затраты на вычисление такого порядка как правило не окупаются [58]. Таким образом набор позиций вхождений подстроки в текст равен Блок-схема алгоритма подборки на основе позиций возможных вхождений изображена на рисунке 2.13. После завершения работы алгоритма переменная будет содержать все позиции вхождений подстроки в текст .
Реализация построения модифицированного позиционного представления текста требует особого внимания т. к. несмотря на то, что идея модификации довольно простая, реализовать такое представление способом реализации ГППТ не получится. Для реализации ГППТ используется массив списков, в котором индексом ячейки для получения списка с позициями является двоичное представление символа в использующейся кодировке. Однако для хранения подстрок текста, размер которых больше одного символа такая реализация не подходит. Даже если считать, что строка так же, как и символ имеет двоичный код (поскольку хранится в памяти как последовательность подряд идущих разрядов), реализация МППТ таким способом имеет большой недостаток — такая реализация требует огромный объем памяти. Для ГППТ размер массива в худшем случае равен 28 для кодировки, в которой каждый символ занимает 1 байт или 216 для кодировки в которой каждый символ занимает 2 байта. Для реализации МППТ этим способом при = 5, требуется массив размером равным 240 для кодировки, в которой каждый символ занимает 1 байт и 280 для кодировки, в которой каждый символ занимает 2 байта. При увеличении значения , размер массива для хранения МППТ таким способом многократно увеличивается.
Анализ средних временных затрат подборки и предобработки данных
В результате данного моделирования получены средние временные затраты подборки данных для каждого способа таблица 3.2.
Из таблицы 3.2 следует, что самым медленным способом, как и следовало ожидать оказался способ подборки Бойера — Мура. Далее идет способ подборки данных в ГППТ. Одним из основных преимуществ данного способа является направленный порядок сравнивания символов текста и подстроки. Данный способ сравнивает символы текста и подстроки в порядке возрастания символов подстроки в текст, этот порядок не сокращает временные затраты подборки для искусственно построенных данных т. к. для них характерно равномерное распределения символов алфавита, в связи с чем, способ подборки в ГППТ больше подходит для естественных данных, где вероятность распределения символов алфавита не является равномерной, это предположение подтверждается полученными результатами, приведенными в таблице 3.2. Несмотря на это, данный способ имеет относительно небольшие временные затраты подборки даже для искусственно построенных данных. Следом с большой разницей по временным затратам идет способ подборки данных в МСД. Самым быстрым способом оказался способ подборки в МППТ. Временные затраты подборки данных для всех способов (кроме способа подборки данных в МСД) для естественных данных оказались меньше, чем для искусственно построенных данных.
По полученным средним временным затратам подборки вычислен процент сокращения временных затрат разработанным способом подборки в МППТ относительно быстрейшего способа подборки данных, использующего предобработку входного текста — способа подборки данных в МСД. Сокращение временных затрат подборки вычисляется по формуле:
В результате данного моделирования также получены средние временные затраты предобработки входного текста для каждого способа таблица 3.3.
Из таблицы 3.3 следует, что самую медленную предобработку входного текста среди способов, участвующих в моделировании имеет способ подборки данных в МСД. Далее идет способ подборки данных в МППТ. Самую быструю предобработку входного текста имеет способ подборки данных в ГППТ. Стоит отметить, что только у данного способа временные затраты предобработки входного текста для естественных данных больше, чем для искусственно построенных данных. Такое отличие связано с тем, что для естественных данных символы алфавита в тексте распределяются неравномерно, соответственно увеличение размера списков позиций вхождений символов, входящих в текст большее количество раз, происходит чаще. Данная операция при большом количестве элементов в списке является затратной т. к. в C# структура списка (List) реализована через массив [90, 91, 93].
Текстовые данные в хранилищах как правило не изменяются, поэтому предобработка таких данных т. е. построение структуры для подборки с целью получения дополнительной информации о внутренней организации данных, которая используется для сокращения временных затрат подборки, является правильным и логичным решением [57, 58, 83]. Однако иногда некоторые текстовых данные в хранилищах не предполагают большого количества операций подборки т. к. они могут изменяться или даже удаляться из хранилища по истечению какого-то определенного времени [3, 9, 24], поэтому для принятия решения о использовании способов предобрабатывающих входной текст необходимо знать какое количество операций подборки потребуется, чтобы общие временные затраты работы с текстом таких способов стали меньше, чем общие временные затраты работы с текстом одного из самых быстрых способов подборки данных общего назначения (способа БМ, не использует предобработку входного текста).
Произведем расчет необходимого значения используя средние временные затраты подборки и предобработки входного текста. Количество необходимых операций подборки вычисляется при помощи неравенства:
Таким образом формула вычисления количества операций подборки данных имеет вид:
Результаты вычисления приведены в таблице 3.4.
По результатам моделирования работы способов подборки данных так же построены графики зависимости суммарных временных затрат работы с текстом (суммарные временные затраты подборок + временные затраты предобработки входного текста) относительно количества операций подборки для искусственно построенных (рисунок 3.4) и естественных (рисунок 3.5) данных.
Рисунки 3.4 и 3.5, а также результаты, приведенные в таблице 3.4 подтверждают на алгоритмическом уровне достижение цели исследования — сокращение временных затрат на операции множественной подборки. Действительно, анализ способов для множественной подборки текстовых данных в хранилищах показал, что количество операций подборки, которое необходимо разработанному способу, чтобы его общие временные затраты работы с текстом стали меньше, чем общие временные затраты работы с текстом способа подборки БМ, для искусственно построенных данных равно 451 (рисунок 3.4), а для естественных данных 341 (рисунок 3.5).
Разработка структурных схем основных блоков ассоциативного устройства
БСУ является схемой управления, синтезируемая известным способом [97], основываясь на алгоритмах управления, которые разработаны в следующих разделах данной работы. Внешними сигналами управления БСУ и соответственно всего ассоциативного устройства являются:
STOP — входной сигнал устанавливающий все элементы памяти устройства в начальное состояние;
LAUNCH — входной сигнал запуска устройства.
БА содержит адресные регистры, для хранения номеров битовых подстрок в БХП, битовых строк-модификаторов в БХМ и битовых строк текста в БХТ и их внутренних счетчиков, значение которых увеличивается с каждой записью. БА предназначен для чтения/записи битовых подстрок и битовых строк текста, для передачи адресов строк текста, для чтения/записи в АМ ОБ устройства, а также для передачи адресов строк текста, на основе которых формируется маска, необходимая чтобы выделить рабочую область АМ.
БХП, БХМ и БХТ содержат регистры, предназначенные для хранения и чтения битовых подстрок, битовых строк-модификаторов и битовых строк текста соответственно. Разрядность регистров БХП равна количеству бит во входных подстроках — , разрядность регистров БХМ равна 2, разрядность регистров БХТ равна . БХП, БХМ и БХТ подключаются к внешним шинам данных устройства для подачи битовых подстрок, битовых строк-модификаторов и битовых строк текста соответственно, а также к ОБ УМПД для подачи текущей битвой поисковой подстроки, текущей битовой строки-модификатора и битовой строки текста в параллельном коде.
БР состоит из D-триггеров для хранения результатов проверки строк и D-триггеров для хранения результатов проверки столбцов АМ ОБ устройства.
ОБ (рисунок 4.3) содержит ассоциативных запоминающих элементов 1 (АЗЭ) ( — число битовых строк, которое необходимо для представления исходного текста, — размер битовой подстроки) с входами с первого 2 по четвертый 5 и с выходами с первого 6 по второй 7, четвертые входы 5 АЗЭ подключены к внешнему входу синхронизации CLOCK, третьи входы 4 АЗЭ подключены к внешнему входу RESET, вторые входы 3 АЗЭ подключены к выходам 18 соответствующих по столбцу элементов-селекторов 12 (ЭС), первые входы 2 АЗЭ подключены к адресным входам 8 в соответствующей строке АМ, первые выходы АЗЭ в соответствующих столбцах АМ объединены и являются соответствующими информационными выходами устройства 9, первые выходы 6 АЗЭ первой строки АМ являются внешними выходами 21 устройства, коммутационных элементов 10 (КЭ), представляющих собой 1–-полюсники, первые входы КЭ подключены ко вторым выходам 7 соответствующих АЗЭ, вторые входы КЭ подключены к внешнему входу RESET, третьи входы КЭ подключены к внешнему входу CLOCK, а выходы КЭ соответственно объединены и являются соответствующими выходами результатов проверки 11, ЭС, первые входы 13 в соответствующих столбцах АМ являются соответственно первыми информационными входами 19 устройства, вторые входы ЭС подключены к первым выходам АЗЭ соответствующей строки АМ, однако вторые входы ЭС крайнего правого столбца АМ подключены к первым выходам соответствующих АЗЭ крайнего левого столбца АМ, расположенных строкой ниже, третьи входы ЭС подключены к внешнему входу MODE, четвертые входы ЭС подключены к внешнему входу SHIFT, пятые входы ЭС, кроме -й строки АМ, подключены в соответствующем столбце к первым выходам АЗЭ, расположенных строкой ниже в АМ, пятые входы ЭС -й строки АМ являются внешним входами 20 устройства, выходы ЭС являются входами АЗЭ соответствующей строки АМ, маскирующего элемента 36 (МЭ) с входами с первого 37 по третий 39 и с выходом 40, элемента И 44, первый вход которого подключен к выходу результата проверки -й строки АМ, второй вход — к выходу 40 МЭ, а выход является маскируемым выходом проверки -й строки АМ, ограничительного резистора 32, соединенного с вторым входом 14 последнего ЭС и источником питания, преобразователя кода 45 (ПК), состоящего из ячеек 53, каждая ячейка 531–53-2 имеет первый 47, второй 50 и третий 49 входы, а также первый 51, второй 48 и третий 52 выходы, ячейка 530 имеет такие же входы и выходы, как и выше обозначенные ячейки 531–53-2, кроме второго выхода 48, ячейка 53-1 имеет такие же входы и выходы, как и выше обозначенные ячейки 531–53-2, кроме первого выхода 51, АМ имеет внешние входы 46, внутренние адресные входы 8, первые 19 и вторые 20 информационные входы, внешний вход MODE, который определяет размерность АМ, внешний вход CLOCK, внешний вход RESET, информационные выходы 9, выходы 11 результатов проверки, внешний управляющий вход START1, соединенный с первым входом 47 ячейки 530, внешний управляющий вход START2, соединенный со вторым входом 50 ячейки 53-1.
АЗЭ (рисунок 4.4) состоит из двухвходового элемента И 22, D-триггера 23, двухвходового элемента И-НЕ 24, двухвходового элемента И-НЕ 25. Первый вход элемента И 22 подключен к первому входу 2 АЗЭ, второй вход элемента И 22 подключен к четвертому входу 5 АЗЭ, а выход элемента И 22 подключен к входу синхронизации D-триггера, информационный вход которого подключен ко второму входу 3 АЗЭ, а третий вход 4 АЗЭ подключен к асинхронному входу сброса D-триггера и асинхронному входу сброса регистра 28 в КЭ, прямой выход D-триггера подключен к двум входам элемента И-НЕ 24 и к первому входу элемента И-НЕ 25, на второй вход которого подан второй вход 3 АЗЭ, выход элемента И-НЕ 24 через резистивный элемент 26, подключенный к источнику питания, является первым выходом 6 АЗЭ, второй выход 7 которого является выходом элемента И-НЕ 25.
КЭ (рисунок 4.4) состоит из двухвходового элемента И 27, регистра 28 и -элементов И-НЕ 31, регистр 28 имеет -входов данных 29, входы сигналов записи 30, установки в начальное состояние, -выходов полученного результата проверки АЗЭ. Первый вход двухвходового элемента И 27 подключен к четвертому входу 5 АЗЭ, на который поступает внешний сигнал CLOCK, на второй вход элемента И 27 подан сигнал записи 30, а выход двухвходового элемента И 27 подключен к C-входу регистра 28. Первый вход каждого из -элементов И-НЕ 31 подключен ко второму выходу 7 АЗЭ, а второй вход каждого из -элементов И-НЕ 31 подключен к соответствующему выходу данных регистра 28, а выход каждого из -элементов И-НЕ 31 является соответствующим выходом КЭ. На рисунке 4.4 также представлены ограничительные элементы 26 в виде резисторов, подключенных к -выходам КЭ, и к источникам питания.
ЭС (рисунок 4.5) состоит из мультиплексора 35, имеющего четыре однобитовых входа данных и два однобитовых адресных входа, 2 двухвходовых элемента И-НЕ 33 и 34. При этом адресные входы мультиплексора 35 подключены к третьему 15 и четвертому 16 входам ЭС, т. е. к внешнему входу MODE и внешнему входу SHIFT соответственно, а выход мультиплексора 35 является выходом 18 ЭС. Первый вход данных мультиплексора 35 подключен к первому входу 13 ЭС, второй вход данных мультиплексора 35 подключен к пятому входу 17 ЭС через инвертирующий элемент И-НЕ 33, третьи и четвертые входы данных мультиплексора 35 подключены ко второму входу 14 ЭС через инвертирующий элемент И-НЕ 34.
МЭ (рисунок 4.6) состоит из двухвходового элемента И 41, двоичного -разрядного счетчика 42, элемента ИЛИ-НЕ 43 с -входами. Первый вход элемента И 41 подключен к первому входу 37 МЭ, второй вход элемента И 41 подключен ко второму входу 38 МЭ. Первый вход двоичного счетчика 42 подключен к выходу элемента И 41, второй вход двоичного счетчика 42 подключен к третьему входу МЭ, а -выходов счетчика подключены к -входам элемента ИЛИ-НЕ 43. Выход элемента ИЛИ-НЕ 43 подключен к выходу 40 МЭ.