Словарная технология

Г. С. Уткин
Словарная технология

УДК 623.45
ББК 68.8
 
У84
Рецензенты:
начальник лаборатории ФГУП ЦНИИмаш 
д-р техн. наук В.Г. Динеев;
ведущий научный сотрудник ПАО РКК «Энергия» 
д-р техн. наук Р.А. Евдокимов
Уткин, Г. С.
У84	
	 Словарная технология / Г. С. Уткин. — Москва : Издательство МГТУ им. Н.Э. Баумана, 2019. — 215, [1] с. : ил.
ISBN 978-5-7038-5119-7
Предложено использовать динамический словарь как средство 
расширения стандартных структур данных языка C++. Словарь реализуется как сложная структура данных, представленная в виде 
класса. Использование в  структуре данных статистики слов, которые разбиваются на узлы, позволяет существенно расширить 
спектр решаемых задач. Подход, при котором данные представляются в виде словаря и для работы с которыми используются функ-      
ции словарного класса, назван автором «Словарная технология».
Дается описание словарных функций и приводятся примеры 
решаемых на основе словарной технологии задач. Возможности 
словарной технологии по хранению и доступу к данным использованы для построения модели постреляционной системы управления базами данных. Дается описание постреляционной базы 
данных и особенностей представления информации. Предлагается язык управления данными, в основе которого лежит словарное 
представление.
Приложения содержат описание функций словарной технологии, 
сервисных функций, упрощающих работу с данными, функции 
работы с постреляционной базой данных, язык управления и язык 
запросов к базе данных.
Приводится программный материал по решению разнообразных 
задач в словарной технологии и  перечень примеров по работе 
с постреляционной базой данных.
Для студентов и специалистов, интересующихся вопросами, 
связанными с обработкой информации.
УДК 623.45
ББК 68.8
© Уткин Г.С., 2019
© Оформление. Издательство 
ISBN 978-5-7038-5119-7 
МГТУ им. Н.Э. Баумана, 2019

Оглавление
Введение........................................................................................ 
    6
Обозначения.................................................................................. 
  12
Словарь.......................................................................................... 
  13
Статистика .
.............................................................................. 
  16
Ограничения............................................................................ 
  17
Реализация словаря................................................................. 
  17
Создание словаря.
............................................................... 
  18
Основные функции словаря.............................................. 
  18
Поиск слова в словаре с возвратом номера .
.................... 
  18
Добавить слово в словарь.................................................. 
  19
Вывести слово по заданному номеру............................... 
  19
Удалить слово из словаря.................................................. 
  19
Возврат диапазона по началу слова .
................................ 
  20
Сохранение словаря .
.......................................................... 
  20
Решение задач в словарной технологии..................................... 
  22
Решение простых задач в среде C++ Builder........................ 
  22
Сервисные функции................................................................ 
  29
Решение задач на основе словарного представления
информации............................................................................. 
  30
Работа с числовой информацией...................................... 
  30
Спеллер .
.............................................................................. 
  34
Подвод, поиск и отображение статистики .
..................... 
  38
Работа с большим количеством слов............................... 
  41
Работа с древовидной информацией................................ 
  52
Решение задачи учета в словарном представлении.
....... 
  58
Информационно-поисковые системы ............................. 
  60
СУБД на основе словарной технологии..................................... 
  65
Модель представления данных.
............................................. 
  65
Бинарное отношение в словарном представлении .
............. 
  66
Словарное представление реляционного отношения 
(таблицы).................................................................................. 
  70
3

Представление реляционной алгебры в словарной
технологии .
.............................................................................. 
  77
Реляционные операции: произведение, деление 
и соединение............................................................................ 
  87
Ведение номеров записей....................................................... 
  97
Оптимизация хранения информации.
................................... 
  98
Диспетчеризация словарей.
.................................................... 
102
Логическая структура базы данных.
..................................... 
103
Управление базой данных...................................................... 
104
Другие аспекты построения СУБД....................................... 
105
Постреляционная база данных на основе словарной 
технологии .
................................................................................... 
107
Модель постреляционной СУБД на основе словарной 
технологии.
............................................................................... 
111
Блочное представление данных в TGRBD...................... 
111
Постреляционные таблицы в TGRBD.
.................................. 
112
Словари данных.
...................................................................... 
116
Диспетчер в TGRBD.
............................................................... 
118
Файл базы данных.
.................................................................. 
119
Справочник базы данных в TGRBD.
..................................... 
119
Управление базой данных в TGRBD.
.................................... 
121
Практическая работа с постреляционной СУБД TGRBD.
....... 
122
Создание базы данных.
........................................................... 
122
Создание таблиц базы данных.
.............................................. 
126
Загрузка в базу данных реляционных таблиц из текстового файла.
............................................................................ 
127
Работа со справочником базы данных.................................. 
135
Получение справочной информации по запросу.
........... 
136
Пополнение словаря справочной информацией .
............ 
137
Разворот справочника .
...................................................... 
139
Сборка справочника .
......................................................... 
139
Работа с постреляционными таблицами.............................. 
145
Таблицы с повтором одного атрибута.
............................. 
147
Таблицы с повтором атрибутов в связке.
......................... 
150
Таблицы с произвольными вложениями......................... 
150
Поисковый сервис.
................................................................... 
153
Команды словаря действий............................................... 
154
Вывод информации о базе данных.
.................................. 
155
Вывод полной информации для каждой записи............. 
157
Вывод значений атрибутов в различных форматах....... 
163
Формат “PKKK.P”.............................................................. 
164
4

Формат “PKKK.N”............................................................. 
165
Формат “PKKK.K”............................................................. 
165
Вывод номеров записей..................................................... 
166
Запросы к базе данных........................................................... 
170
Запрос на поиск информации в заданном блоке............. 
175
Запросы к полям на совпадение.
....................................... 
176
Запросы к полям на сравнение.
......................................... 
176
Запросы к полям на наличие и отсутствие 
информации........................................................................ 
178
Отбор и преобразование информации....................................... 
180
Удаление и изменение значений атрибутов.
......................... 
181
Управление выводом информации из базы данных............ 
183
Другие команды управления................................................. 
187
Клиент-серверная реализация постреляционной СУБД......... 
191
Реализация СУБД TGRBD.
.......................................................... 
194
Литература.................................................................................... 
194
Приложения.
.................................................................................. 
195
Приложение 1. Словарные функции библиотеки TGR....... 
195
Приложение 2. Описание сервисных функций библиотеки TGRSRV.
.............................................................................. 
200
Приложение 3. Информационные сервисные функции...... 
208
Приложение 4. Команды языка управления.
........................ 
211
Приложение 5. Запросы к базе данных................................. 
214

Введение
Первоначально предполагалось, что компьютеры должны помочь решать задачи со сложными математическими расчетами. Но 
постепенно с увеличением памяти все больше начинают использовать компьютеры для хранения и обработки различной информации. Эта функция компьютеров стала значительно преобладать над 
их применением для расчетов. Хранимая информация стала разнообразной. К работе с текстами добавилась работа с изображениями 
и другой мультимедийной информацией.
В этой работе рассматривается хранение и обработка текстовой 
информации. При этом многие положения могут быть применены 
к работе с информацией более сложной структуры.
Представленный подход носит название “Словарная технология”. Решение зарегистрировано как “Программа автоматизации 
работы с данными в словарном виде (словарная технология)”. Свидетельство о регистрации электронного ресурса № 22181 от 11 октября 2016 г.
Словарная технология — это набор программ эффективной работы с информацией, представленной в виде специальных динамических словарей.
В качестве языка программирования будем рассматривать язык 
C++. Все примеры будут демонстрироваться в среде C++ Borland 
Builder. При этом использование библиотеки VCL в функциях словарной технологии не предполагается.
В данной разработке преследовалась задача упростить работу 
с текстовой информацией, добиться плотного хранения и быстрого 
поиска. В языке C просто решаются задачи с использованием элементарных структур данных. К ним можно отнести число (целое) байт. 
Число в памяти представляется фиксированным числом байт, поэтому очень просто реализуется такая структура, как массив чисел.
Например, в 32-разрядной памяти число будет представляться 
4 байтами, и мы очень просто определяем адрес любого элемента 
6

массива. Так, 12-й элемент массива будет на расстоянии 48 байт от 
начала массива.
Аналогично просто работать с массивом байт. Но со словами 
уже сложнее. Каждое слово состоит из набора байт, при этом длина 
слов обычно различная. Поэтому вычислить адрес 12-го слова существенно сложнее, чем адрес 12-го числа.
Возникает вопрос, почему в языке C просто решен вопрос работы с массивом чисел и массивом байт, но нет таких же простых 
инструментов при работе со словами. Работа со словами это и работа с текстами, состоящими из набора слов. Поэтому решение вопросов работы со словами должно было войти в язык на самом низком 
уровне и быть очень эффективным. 
Если использовать представление слова как массив байт с нулевым символом в конце слова (строка в стиле языка C), то нет простой 
структуры для массива слов. Так, если образуем двумерный массив 
байт, где один размер — это адрес слова, а второй — адрес байта 
(буквы) в слове, то потребуется достаточно большой объем памяти. 
Например, пусть имеем 999 слов длиной 10 символов и одно слово 
длиной 1000 символов. Тогда двумерный массив байт для хранения 
этих слов будет содержать 1000*1001 = 1 001 000 байт памяти для 
хранения всего 10 990 символов, т. е. храним 990 010 пустых байт.
Конечно, есть решения хранения массива слов в виде:
• стека;
• связного (или двусвязного списка);
• очереди;
• других структур, определяемых пользователем.
Но если внимательно посмотреть на эти решения, то обнаруживаем определенные проблемы, связанные с доступом к элементам 
хранения. При этом на пользователя ложится задача выбора структуры хранения и программирование доступа к элементам при реализации алгоритма.
Можно уйти в язык C++ и использовать объектно ориентированное программирование, а в качестве строк использовать объектное представление string. Тогда текст можно рассматривать как 
набор строк или как одну большую строку. Это решает проблему 
хранения массива строк, но остаются проблемы поиска и выделения памяти.
Для решения этих задач в языке C++ можно воспользоваться 
методами обобщенного программирования, где используется стандартная библиотека шаблонов (STL — Standard Template Library).
7

STL — это библиотека контейнерных классов, которая включает 
последовательные контейнеры:
• векторы;
• списки;
• деки (очереди);
• стеки;
• строки типа string
и ассоциативные контейнеры:
• множество (set);
• мультимножество (multiset);
• карта (отображение) (mар);
• мультикарта (мультиотображение) (multimap).
Последовательные контейнеры решают задачу хранения массива строк, но не имеют эффективного алгоритма поиска. Ассоциативные контейнеры решают задачу хранения и поиска в массиве строк.
Мультиотображение, в котором ключи и значения относятся 
к строковому типу, называется словарем. 
В книге Т. Кормена, Ч. Лейзерсона, Р. Ривеста, К. Штайна “Алгоритмы. Построение и анализ” (2012) приводится следующее 
определение словаря: “Словарь — динамическое множество, поддерживающее операции вставки, удаления и принадлежности элемента множеству”.
Поддержка работы со словарями имеется во многих языках программирования: Perl, PHP, Python, Ruby, Tcl, JavaScript и др. Для 
других языков имеются реализации в виде библиотек.
Основной функцией работы со словарями является поиск. Наиболее популярны реализации, основанные на различных деревьях 
поиска. Так, например, в стандартной библиотеке STL языка С++ 
контейнер map реализован на основе красно-черного дерева. Другой популярной реализацией является использование хэш-таблицы 
(языки Ruby, Tcl, Python).
У каждой реализации есть свои достоинства и недостатки: 
• в реализациях на сбалансированных деревьях поиска много времени тратится на балансировку деревьев (при пополнении, 
а особенно при удалении элементов);
• в реализациях на хэш-таблицах операция вставки выполняется 
долго (зависит от коэффициента заполнения);
• многие реализации появились сравнительно недавно.
Реализация словаря в словарной технологии существенно отличается от всех известных реализаций. Некоторые особенности 
8

реализации словаря позволяют сделать работу с информацией более 
универсальной, а программирование с использованием такого представления словаря более технологичным.
Реализация словаря в словарной технологии обладает следующими свойствами:
• используется естественное разбиение слов на узлы (фактически разбиением на узлы управляет сама информация);
• используется многоуровневое хранение информации в виде графа словаря с применением высокоскоростных алгоритмов доступа 
к данным (образ хранения — файл в оперативной памяти и на диске);
• хранение вместе со словами статистики (самое существенное 
отличие, которое превращает данное хранение в основу словарной 
технологии).
Для того чтобы совокупность программ обработки данных можно было назвать технологией, требуется:
• универсальность представления информации;
• достаточно большой спектр задач, где можно использовать 
данный программный подход;
• возможность описания алгоритмов решения информационных 
задач на основе структур, представляемых данным подходом.
Всеми этими свойствами обладает совокупность программ, названных словарной технологией.
Данные, представленные в виде словаря, могут использоваться 
для решения очень большого круга задач:
• хранение информации. До массового применения компьютерной техники большое количество информации хранилось с использованием словарного представления. Это в первую очередь многочисленные энциклопедии и толковые словари. Принцип словарного 
хранения также очень эффективен и при использовании компьютерной техники. При этом словарная технология может существенно 
облегчить задачу построения разнообразных архивов информации;
• поиск информации. Словарный поиск информации также широко использовался еще до компьютерных технологий. В настоящее 
время применяются разнообразные сервисы поиска информации, 
где в основе интерфейса лежит словарное представление. Если для 
уже построенных поисковых систем словарная технология не так 
актуальна, то для быстрого и простого решения частных задач работы с информацией использование словарной технологии может 
существенно упростить и ускорить построение информационно-поисковых систем;
9

• проверка информации. В истоках построения словарной технологии была программа проверки грамматики — спеллер, где проверялось каждое слово и его грамматическая форма в предложении. 
Очень эффективно на основе словарной технологии решается задача проверки и исправления ошибок методом сканирования текста 
на некотором устройстве (сканере). Проверку информации можно 
существенно улучшить, если использовать словарную технологию 
при вводе информации (контроль по словарю) или при нахождении 
кодов, если информация кодируется. Проверка информации наиболее естественное применение словарной технологии;
• толкование информации. Просто и быстро можно на основе 
словарной технологии строить словари-справочники с возможностью использования хранимой информации непосредственно в самом объекте;
• кодирование информации. Здесь естественно решаются задачи, как по набору слов (предложению) получить код, если он был 
сформирован, и обратная задача, как вести кодирование информации. Это очень эффективно, когда исходная информация представляется в древовидном виде;
• сжатие информации. Замена текста его кодом является одним 
из методов сжатия информации. Хорошо известны словарные методы сжатия информации. Применение словарной технологии позволяет строить разнообразные системы сжатия информации. Эти 
подходы могут также использоваться при защите информации при 
ее передаче и контроле по словарным базам данных у отправителя 
и получателя информации;
• управление информацией. В словарь можно помещать как произвольную, так и управляющую информацию. Это очень эффективно работает в самой словарной технологии, когда словарями управляет словарь более высокого уровня.
Еще существует очень много задач, где использование словарной технологии очень эффективно. Постоянное использование словарного представления информации в решении разнообразных задач привело к определенному подходу при разработке алгоритмов, 
когда словари играют доминирующую роль — своего рода словарная философия.
Быстрый поиск и эффективное хранение информации используются при построении систем управления базами данных (СУБД). 
Естественно, возникает вопрос о возможности построения СУБД на 
основе словарной технологии.
10