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

ВВЕДЕНИЕ

I. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОЦЕССОВ ОБРАБОТКИ ТЕКСТОВОЙ

ИНФОРМАЦИИ .15

1.1. Формализация понятий символьной и текстовой информации

1.2. Основы формальной теории строк

1.2.1. Определение формального языка

1.2.2. Множество аксиом и правила вывода

1.2.3. Семантика

1.3. Вычислительные процессы в системах автоматизированной обработки текстов

П. ИЕРАРХИЧЕСКИЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ В СИСТЕМАХ ОБРАБОТКИ ТЕКСТОВОЙ ИНФОРМАЦИИ.

2.1. Виды и уровни абстракции

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

2.3. Текст как иерархия абстрактных типов данных .70:

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

Ш. МЕТОДОЛОГИЯ РАЗРАБОТКИ СИСТЕМ АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ТЕКСТОВ, ОСНОВАННАЯ НА ИЕРАРХИИ АБСТРАКТНЫХ ТИПОВ ДАННЫХ. 86?

3.1. Цели методологии

3.2. Средства поддержки структуры проекта

3.3. Использование абстракций в процессе проектирования

3.4. Формальные спецификации и контроль корректности проекта

3.5. Система нотации и документирование проекта.

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

4.1. Функции и выбор структуры системы.

4.2. Выбор абстрактных типов данных для эффективной организации процессов обработки данных в системе обработки текстов .i

4.3. Построение формальных спецификаций для абстрактных типов данных и абстрактных машин .ИЗ

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

Функции по генерированию, редактированию и печатному оформлению текстов чаще всего объединяются в системах автоматизированной обработки текстов (СЛОТ). Функции по созданию печатного образа текста (форматирование) включают вертикальное и горизонтальное табулирование текста, т.е. его распределение по строкам стандартной длины с выравниванием по правому и левому полю, распределение текста по страницам, нумерация страниц,оформление таблиц и иллюстраций, ведение предметных и именных указателей, выделение заглавий частей, сбор и выдача оглавления, выделение аннотации, оформление заглавных и других стандартных листов и др.

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

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

В области проектирования СЛОТ наблюдаются два основных напраВ' ления развития - разработка систем автоматизированного проектирования и разработка универсальных систем. Системы редактирования типа ТВСО (разработка MIТ ), ЕйРУ (фирмы MOU ) и др. обеспечивают только автоматизирование создания и редактирования текстовой информации.

Универсальные СЛОТ обеспечивают автоматизированное исполнение всех основных функций по подготовке текстового материала. Во многих случаях, они проектируются для работы на больших ЭВМ. Типичными примерами в этом отношении являются нашедшая широкое применение в полиграфической промышленности СССР система АСТРА, автоматизированная система подготовки публикаций и документов АСПИД для БЭСМ-6, система DPS для Unlvac и пр.

В последние годы, однако, все больше возрастает интерес к вопросам проектирования универсальных САОТ для мини-ЭВМ класса СМ-4-. Ряд показателей мини-ЭВМ таких, как относительно невысокая стоимость, возможность управления широким спектром внешних уст ройств, простота обслуживания, высокая надежность, ориентация на "неискушенного" пользователя, определяет их как особо привлекательных для разработчиков САОТ. Самыми известными универсальными системами для мини-ЭВМ яаляются WORD-]} *f?UNOFF *WP5-11 Д"Я PDP-11/3*,D0CPRER ДЛЯ С/350 иЦРЗООО* Общей особенностью всех этих систем является тот факт, что все они спроектированы для работы в режиме диалога. Основной их недостаток в том, что они не являются полными системами. Для реализации ряда функций , таких как вывод текста и ведение каталога текстовых файлов используются стандартные возможности соответствующей операционной системы.

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

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

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

Для достижения этой цели в диссертации ставились и решались следующие задачи:

- исследование теоретических основ и формализация основных понятий области обработки текстов;

- исследование аппарата иерархических АТД как методологических основ организации процессов обработки текстов;

- разработка методологии, использующей иерархию представления АТД;

- разработка и опробование САОТ по предложенной методологии.

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

Во-первых, для объектов вша строки характерно, что их длина не ограничена и может сильно изменяться во время работы программ. Отсюда и проблемы при их представлении в памяти ЭВМ.

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

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

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

Одни из самых мощных методологических средств, позволяющих овладеть сложностью процесса разработки программного обеспечения является декомпозиция проекта на обозримые компоненты, которые в сочетании обеспечивают исполнение основных функций общего продукта. Декомпозицию можно проводить по разным критериям, например, связанным с ограничениями, налагаемыми операционной системой или аппаратной частью. Большее методологическое значение, однако, имеют методы декомпозиции проекта, позволяющие выделить в нем функционально законченные компоненты, которые имеют самостоятельный д u смысл в контексте предметной области. Среди посленых методов особо перспективными для разработки систем подготовки текстов являются методы иерархической декомпозиции проекта на уровни абстрак-. ции, использующие аппарат абстрактных типов данных (АТД).

Основания для подобного заключения следующие. Расслоение проекта на уровни абстракций в сочетании со стратегией программирования сверху-вниз предполагает создание на каждом этапе работы полного описания решения поставленной задачи в терминах использованных на этом уровне абстракций программ и данных. Далее, в процессе пошагового уточнения, описание решения постепенно развивается и на заключительном этапе дается в терминах выбранного языка программирования. Такая организация работы требует четкое определение конечных целей разработки и предполагает известную предварительную подготовку по определению общей стратегии решения. Другими словами, как методологические средства декомпозиция проекта на уровни абстракции в сочетании с методом проектирования сверху-вниз "явно проблемно-ориентированные" /16/ т.е. подходящие для разработки специализированных систем и, в частности, систем подготовки текстов.

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

Предлагаемый в ряде работ /10, 22/ подход моделирования АТД в терминах фоксированной области формальных объектов, таких как множества, графы и пр. является мало пригодным для целей представления текста, так как полученные формальные описания будут громоздкими, перегруженными деталями и плохо будут передавать смысл определяемых понятий.

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

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

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

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

Статистические исследования показывают, что в программировании существует ярко выраженная тенденция возрастания объема т.н. "нечисловых задач" /21/, т.е. задач обработки символьной и в частности текстовой информации. В связи с этим в практических разработ-кая особое внимание обращается на создание эффективных аппаратных средств реализации процессов обработки символьной и текстовой информации. Исследования ведутся в двух основных направлениях: расширение возможности традиционных ЭВМ фон Неймановского типа путем добавления средств (кипы данных и операций) для обработки строк и создание специализированных процессоров, ориентированных на языки обработки строк (СНОБОЛ-процессор, многопроцессорная система СИМВОЛ и цр.) •

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

Диссертационная работа выполнена на кафедре ПМ МЭИ по тематике следующих НИР:

- "Языки и системы программирования. Исследование структур проблемно-ориентированных языков программирования" (Координационный план НИР АН СССР по ВТ на 1981-85г.г. п. I.12.2.2).

- "Разработка программного и методического обеспечения решения студенческих задач на массовых потоках с применением ЕС ЭВМ, микроЭВМ и терминальных систем". (Координационный план НИР Минвуза СССР на 1981-85г.г. по проблемам высшего образования, проблема П. 6.4.3.2).

В работе получены следующие основные результаты:

1. Определены характерные операции систем обработки текстовой информации и выделен базисный набор таких операций;

2. Разработаны основы формальной теории преобразования текстов и на их базе исследованы свойства элементарных операций обработки текстовых фрагментов;

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

Разработана система подготовки документации программных продуктов для СМ ЭВМ на основе развитой в работе методологии.

Научная новизна работы

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

2. Формализованы базисные понятия из области обработки текстов (литера, строка, печатная строка, абзац, страница и пр.).

3. Предложено и обосновано использование аппарата иерархических ЛТД как методологической основы надежностного проектирования систем обработки текстов и эффективной организации вычислительных процессов в таких системах.

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

5. Предложена методология проектирования СЛОТ, использующая аппарат иерархических АТД.

Практическая ценность работы определяется:

- разработанной методологией проектирования систем подготовки текстов, позволяющей сократить сроки проектирования подобных систем на 40-60$ при одновременном повышении их качества;

- разработанной системой подготовки документов ДОСМ для СМ ЭВМ. Система ДОСМ включена в состав программного обеспечения АОС ВУЗ, работающего в среде ДЙАМС-2, а также в состав специализированного программного обеспечения ПОК ИНФОРЕГ, разработанного в Центральном институте вычислительной техники (София).

По своим функциональным возможностям и техническим показателям ДОСМ сравнима с уже существующими системами подготовки текстов для класса мини-ЭВМ типа СМ-4 и превосходит их по степени автоматизации процессов обработки текстовой информации.

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

ВЫВОДЫ ПО ЧЕТВЕРТОЙ ГЛАВЕ

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

2. Обоснован выбор представления текстовой информации на основе структуры последовательного файла и АТД string как средства построения эффективных процессов обработки данных в системе подготовки текстов.

3. Разработаны и описаны полные спецификации использованных абстрактных машин, АТД и программ для созданной системы обработки текстов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

- позволяет решить задачу проектирования системы подготовки текстов на таком уровне абстракции, которое лучше всего соответствует ее природе.

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

7. Показано, что в методологическом плане декомпозиция проекта на основе иерархии АТД дает следующие преимущества:

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

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

8. Разработана методология проектирования систем обработки текстов, использующая последовательную декомпозицию проекта на основе иерархии представления использованных АТД в сочетании с методами проектирования сверху-вниз и пошагового уточнения программ и данных. Предложенная методология предусматривает соблюдение ряда принципов, которые обеспечивают:

- получение легко понимаемой и модифицируемой структуры проекта;

- возможности верификации свойств программ обработки текстов по их формальным спецификациям;

- повышение надежности и эффективности конечного программного продукта,

9. По предложенной методологии разработана система подготовки текстов ДОСМ для СМ-4, включенная в состав СПО ПОК ИНФОРЕГ, разработанного в Центральном институте вычислительной техники (София), а также включенная в состав программного обеспечения АОС ВУЗ, работающего в среде ДЙАМС-2.

Опытная разработка системы ДОСМ показала, что цредлокенная методология позволяет получить сокращение сроков разработки на 40-60% с одновременным повышением качества программного продукта.

1. I. Агафонов В.Н. Типы и абстракция данных в языках программирования (обзор). -В кн.: Данные в языках программирования. Абстракция и типология. М.:Мир, 1982. 327 с.

2. Баррон Д. Введение в языки программирования. -М.:Мир, 1980. 190 с.

3. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. -М.:Мир, 1981. -319 с.

4. Вирт Н. Систематическое программирование. -М.:Мир,1977. 184 с.

5. Вульф В., Лондон Р., Шоу М. Введение в построение и верификацию программ на языке Альфард. В кн.: Данные в языках программирования. Абстракция и типология. М.:Мир, 1982.- 327 с.

6. Грогоно П. Программирование на языке Паскаль. М.: Мир, 1982. - 384 с,

7. Дейкстра Э. Дисциплина программирования. -М.: Мир,1978. 275 с.

8. Йенсен К., Вирт Н., Паскаль. Руководство для пользователя и описание языка. -М: Финансы и статистика, 1982. 151с.

9. Йодан Э. Структурное программирование и конструирование программ. -М.:Мир, 1979. 416 с.

10. Лисков Б., Зиллес С. Методы спецификации, используемые для абстракции данных. В кн.: Данные в языках программирования. Абстракция и типология. М.:Мир, 1982, - 327 с.

11. Мейер Б., Бодуен К. Методы программирования: В 2-х томах. -М.: Мир, 1982. 712 с.

12. Мендельсон Э. Введение в математическую логику. -М.: Наука, 1970. 320 с.

13. Рякин О.М. Основы методологии проектирования корректных программ /Учебное пособие по курсу "Системное программирование". М.: МЭИ, 1980. - 82 с.

14. Парнас Д. Метод спецификации модулей программного обеспечения (с примерами). -В кн.: Данные в языках программирования. Абстракция и типология. М.: Мир, 1982. 327 с.

15. Пратт Т. Языки программирования: разработка и реализация. М.: Мир, 1979. 574 с.

16. Турский В. Методология программирования. М.: Мир, 1981. - 264 с.

17. Уэзерелл Ч. Этюды для программистов. -М.: Мир, 1982.- 287 с.

18. Уирт Н. Алгоритми + структури от данни ~ програми. -София: ДИ Техника, 1980. 391 с.

19. Фрид Э. Элементарное введение в абстрактную алгебру.- М.:Мир, 1979. 260 с.

20. Хоар Ч. Доказательство правильности представлений данных. В кн.: Данные в языках программирования. Абстракция и типология. М.: Мир, 1982. - 327 с.

21. Янков Б. Средства за обработка на символна информация. -София: ДИ Техника, 1981. 191 с.

22. Вzrg Н-К. , Giioi У.К. Hierarchical. Speci-ftcatfcn of /407".- Acta In for mat tea , 1Я77 , V lO.-pZO

23. Воус/ b>L-, PizzareLLo Д.,Wood W.T. Abstraction and refinement in PDM.^ln = Proc The Use о/ lormol Specification of Software and Firmware, Vlest Berlin f June 1979

24. Воус/ D.L., PiizareLLo А-, Wood An Overview of

25. RDM • Rational Design Nethodoiogy.-ln •• Proc The Use of formal Speci-ficabcon of Software and Firmware y West leriin June 1979

26. Constable R.L^O'DonneL M.J. A Programm ing Logic with an. Introduction to the PL /CM yeri-fcer~-Winthrop Publishers me

27. Corcoran , tran< W., Moloney M> String Theory.-1 he Journal of SymboLic Logic , V .33 ,NU ,Dec {974

28. Dungan D.M. bibliography on data types.-SIG PLAN Notices , H , 1979 ,No 11.- p.3/S3.28. tioyd 12.W. Assigning Meaning io Prorgrams . -Proc of Symposia in Applied Mathematics } American Mathematical Society ,)/19 , 1967pp. 19 -32

29. Good D., London H.}bledsoeW. An interactive program verification systemProc .~lnl. on ReliabLe 5o-fiwaret Los Ang. , 1975

30. Guttag 3.)/.} Horowitz E., Husser D. Abstract data types and software volidationCACH ,2.1, I97S, AU2.-pp 10Ц$-(06Ь

31. Guitog J.y.t MorningJJ. The algebraic specification of abstract data types. Acta Informotica , I3T8 , y, JO 9- p. 27

32. Henderson P , Snowdon PJ. A tool {or structured program developmentIn Proc. If TP Congress , /974. p. 204

33. Jones D. W. A note on some limits of algebraic specification method. — S1GPLAN Motic.es t 15, i97s, No. 4 . p. 64-67

34. LiSKOV b. ,Snyder A.,AiKinson £., Scha-fler C. Abstract Mechanisms in CLUCACM, vbo, Ыо.8}!977

35. Ilskov ylilles 5. Programming with Abstract Data Types .„S19PLAM Motices, v.9,Mo.A , 1974.-pp50 -59

36. Hilles ИЛ lop-Down Programming in large 5ystems. ■ Debugging Techniques in Large Systems/

37. Austin fed.), Prentice HqU , /971 .~pp hi -55

38. Pamas D.L. On the criteria to be Used in Decomposing Systems into Modules.-CACM, V./5, Me )2 J97Z.-pp. 1053-10583S. Proc. of Conference on Data : Abstraction, definition and StructureSIGPLAN Noiices , ti, \976 , spec . issue

39. Man Leer P. Top-Down development using о program desing Language .-IBM Sysi.J. ,V. 15 pp /55

40. AO. V/irt N. Program development by step- wise refinement.-CACM M4 (april !CJ71 pp ZZiггт