автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Способы и устройства поиска и сжатия символьной информации

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

^ ЕМЕЛЬЯНОВА

ИРИНА НИКОЛАЕВНА

СПОСОБЫ И УСТРОЙСТВА ПОИСКА И СЖАТИЯ СИМВОЛЬНОЙ ИНФОРМАЦИИ

Специальность 05.13.05 "Элементы и устройства вычислительной техники и систем управления"

Диссертация на соискание ученой степени кандидата технических наук

Научные руководители : доктор физ.-мат. наук, профессор

На правах рукописи УДК 681.3

ЗАХАРОВ И.С.

кандидат технических наук, доцент ДОВГАЛЬ В.М.

КУРСК 1999

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.................................................................................5

ГЛАВА 1. ОБЗОР МЕТОДОВ, АЛГОРИТМИЧЕСКИХ И ТЕХНИЧЕСКИХ СРЕДСТВ ПОИСКА И СЖАТИЯ СИМВОЛЬНОЙ ИНФОРМАЦИИ

1.1. Анализ структур информационных конструктов.................15

1.2. Методы и алгоритмы поиска и сжатия символьной информации...............................................................20

1.3. Технические средства поиска и технические

средства сжатия информации.........................................24

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

1.5. Выводы...................................................................39

ГЛАВА 2. ИССЛЕДОВАНИЕ ПРОЦЕССОВ И РАЗРАБОТКА ЭФФЕКТИВНЫХ СПОСОБОВ ПОИСКА И СЖАТИЯ СИМВОЛЬНОЙ ИНФОРМАЦИИ

2.1. Разработка методики оценки эффективности

объединения разноплановых процедур...............................41

2.2. Разработка способов сопоставления

2.2.1. Анализ конструктивных объектов и разработка способов сопоставления с множеством образцов и выполнения процедуры сжатия.......................................45

2.2.2. Анализ процессов сопоставления с образцом и

способов сопоставления с аннулированием коллизий............54

2.3. Разработка и обоснование способа поиска с игнорированием лексикографических ошибок....................61

2.4. Разработка алгоритма одноэтапного вычисления кодов Хаффмена в процессе сжатия информации.........................70

2.5. Исследование и разработка обобщенных моделей процессов поиска и сжатия символьной информации.............81

2.6. Выводы.....................................................................91

ГЛАВА 3. РАЗРАБОТКА ВАРИАНТОВ ТЕХНИЧЕСКОЙ

РЕАЛИЗАЦИИ ПРОЦЕДУР ПОИСКА И СЖАТИЯ СИМВОЛЬНОЙ

ИНФОРМАЦИИ

3.1. Разработка устройства с параллельной по словам или образцам и последовательной по их символам обработкой

3.1.1. Разработка структурной схемы устройства.......................93

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

его функционирования...............................................104

3.2. Разработка устройства с параллельной по образцам обработкой

3.2.1. Разработка структурной схемы устройства.....................114

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

его функционирования................................................131

3.3. Описание способов программирования устройств...............142

3.4. Разработка схем сопряжения устройств с вычислительной средой................................................144

3.5. Исследование аппаратной сложности

разработанных устройств.............................................147

3.6. Выводы...................................................................152

ГЛАВА 4. МОДЕЛИРОВАНИЕ И АНАЛИЗ РАЗРАБОТАННЫХ УСТРОЙСТВ

4.1. Разработка моделирующих программ...............................154

4.2. Исследование скоростных характеристик

устройств..................................................................156

4.3. Интерпретация результатов исследования

устройств..............................................................168

4.4. Рекомендации по применению и усовершенствованию разработанных устройств..........................................170

4.5. Выводы...............................................................171

ЗАКЛЮЧЕНИЕ........................................................................173

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

ПРИЛОЖЕНИЕ 1. Листинг программного эмулятора устройства с параллельной по словам или образцам и

последовательной по их символам обработкой................185

ПРИЛОЖЕНИЕ 2. Листинг программного эмулятора устройства с

параллельной по образцам обработкой.........................191

ПРИЛОЖЕНИЕ 3. Листинг программы генерации текстов..................203

ВВЕДЕНИЕ

Актуальность работы.

Информация является стратегическим ресурсом общества. Средства ее обработки во многом определяют скорость и качество принимаемых решений в различных сферах человеческой деятельности. Одной из фундаментальных проблем современных компьютерных информационных систем является обработка символьной информации, объем которой составляет до 95% от всей информации, циркулирующей в системах обработки данных [1]. Следует отметить, что ежеминутно в мировой практике создаются до 500 тысяч страниц текстовых документов с тенденцией роста в 25% ежегодно [2].

Огромные объемы символьной информации и тенденции ее роста и разнообразия требуют создания адекватных методов и алгоритмов поиска для акселерации доступа к данным и сжатия, как с целью сокращения затрат памяти, так и для разгрузки каналов передачи информации в компьютерных сетях. Фундаментальным проблемам поиска и сжатия символьной информации посвящены работы отечественных и зарубежных авторов (Кнут Д.Е. (Knuth D.E.), Кричевский P.E., Рябко В.А., Файн B.C., Хаффмен Д.А. (Huffman D.A.), Лемпель A. (Lempel А.), Зив Дж. (Ziv J.), Шеннон К.Е. (Shannon С.Е.)). В академических изданиях и специальных трудах имеются достаточные научные основания для решения проблемы высокоскоростного поиска и эффективного сжатия символьной информации. Между тем существующие алгоритмические, технические и программные средства поиска и сжатия не обеспечивают требуемой практикой производительности, что является предпосылкой для постановки актуальной и перспективной задачи по созданию высокоскоростных устройств поиска и сжатия при паритете аппаратных затрат.

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

Основная часть диссертационной работы выполнялась в рамках госбюджетной НИР по распоряжению ГОСКОМВуза №10-36-41, ИН/10-20-03 от 16.09.95 (пролонгация до 1999 г.) "Разработка и исследование скоростных характеристик процессорных элементов систем обработки символьной информации ".

Целью_работы является создание и исследовании

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

Задачи исследования:

- Разработать методику оценки эффективности объединения

разноплановых процедур;

- Создать способ выполнения продукций, обеспечивающий корректность процедуры сжатия;

- Обосновать способы сопоставления с образцом, обеспечивающие корректность процедур поиска;

- Разработать способ и алгоритм поиска символьной информации с игнорированием лексикографических ошибок;

- Разработать алгоритм вычисления кодов Хаффмена;

- Построить обобщенную алгоритмическую модель процессов поиска и сжатия;

- Синтезировать специализированные устройства, совмещающие

функции поиска и сжатия;

- Исследовать скоростные характеристики разработанных устройств.

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

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

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

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

3. Обоснованы способы сопоставления с образцом, позволяющие обеспечить корректность процедур поиска.

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

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

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

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

Практическая ценность работы состоит в том, что результаты теоретических исследований позволили разработать структурно -функциональные схемы специализированных устройств поиска и сжатия, что открывает перспективы для инженерных разработок промышленных образцов в виде СБИС устройств названного класса. Разработанные устройства целесообразно использовать в качестве акселераторов в компьютерных системах обработки символьной информации. Реализация и внедрение результатов исследований. Результаты диссертационной работы нашли применение при выполнении госбюджетных НИР Курского государственного технического университета (г/б Г7), практически реализованы и внедрены в СКБ ПС

АО «СЧЕТМАШ» и учебном процессе Курского государственного технического университета.

Апробация работы. Материалы работы апробированы на Юбилейной конференции ученых Курского политехнического института (Курск, 1994 г.), второй Международной конференции "Распознавание 95" (Курск, 1995 г.), Юбилейной научной конференции (Курск, 1995г.) и I Всероссийской научно- технической конференции (Нижний Новгород, 1999 г.).

Публикации. По материалам диссертации опубликовано 8 работ, из них 1 патент и 1 положительное решение на выдачу патента.

Структура и объем работы.

Диссертационная работа состоит из введения, 4 глав и заключения, содержащих 110 страниц основного текста, 56 рисунков и 25 таблиц, а также списка литературы из 117 наименований и 3 приложений на 23 страницах.

На защиту выносится:

Методика оценки эффективности объединения разноплановых процедур;

- Способ выполнения процедуры сжатия, позволяющий определить структуру и функции исполнительного устройства;

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

- Алгоритм вычисления кодов Хаффмена, позволяющий определить структуру и функции исполнительного устройства;

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

Специализированные устройства, совмещающие функции поиска и сжатия.

Аннотация работы.

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

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

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

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

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

поиска и сжатия к списку операций, на основе которого произведена оценка объединения процессов поиска и сжатия, обосновавшая эффективность данной агрегации.

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

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

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

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

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

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

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

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

Устройство У1 с обработкой параллельно по образцам или словам текста и последовательно по их символам с поддержкой безотступного способа сопоставления с аннулированием коллизи�