Статья: Алгоритмы сжатия для информационных технологий АСУ

Орловский государственный технический университет

Алгоритмы сжатия для информационных технологий АСУ

Студент Рябинкин Е.В.

г. Орёл

Аннотация

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

Annotation

In work working algorithms of compression of texts (the initial information) for the organization of managerial processes are considered

Основная часть

В АСУ, как правило, реализуются процессы трёх видов [1]: преобразования информации, взаимодействия с человеком, взаимодействия с техническими агрегатами различных средств управления. При этом важная функция отводится вопросам кодирования сообщений независимо от того являются ли они отдельными данными каких-либо измерений или потоком лингвистических массивов от человека.

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

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

1. Алгоритм CRC. Основной замысел по модернизации алгоритма сжатия основывается на замене арифметического действия при формировании контрольной суммы сообщения: вместо сложения используется деление при условии, что делитель имеет ширину регистра контрольной суммы. Основная идея алгоритма CRC состоит: 1) в представлении всего сообщения независимо от его объёма в виде двоичного числа, 2) делении его на другое фиксированное двоичное число и 3) использовании остатка этого деления в качестве контрольной суммы.

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

Степень полинома W (Width - ширина), то есть позиция самого старшего единичного бита, является важным показателем, поскольку от нее зависят все остальные расчеты. Обычно, выбирается степень, равная 16 или 32, что облегчает реализацию алгоритма на современных компьютерах. Степень полинома - это действительная позиция старшего бита, например, степень полинома 10011 равна 4, а не 5. Если в качестве примера использовать именно этот полином, то демонстрация работы алгоритма CRC - это простое деление в терминах CRC арифметики исходного сообщения (текста) на этот полином. Единственное, что надо сделать до начала работы, так это дополнить исходное сообщение нулевыми битами, количеством, равным степени полинома.

2. Алгоритм CR. Этот Метод описывается следующим образом: Пусть a(1), a(2),a(3),...,a(k). массив данных, расположенный в ячейках с адресами соответственно Adr(1), Adr(2),...,Adr(k), <H,L> - содержимое регистровой пары H,L, используемой при вычислении контрольной суммы (КС). Порядок вычисления: 1) i=1,2,...,[k/2], где [ ] - целая часть. 2) КС(0):= 00 00, если k - четно, иначе КС(0):= FF a(k), то есть FF и последнее данное значение в массиве. Но при этом из массива это последнее данное а(к) удаляется, поскольку оно зафиксировано в начальном значении контрольной суммы КС(0), и к:=к-1. 3) <H>:= <Adr(2i)>, <L>:= <Adr(2i-1)>. 4) КС(i):= КС(i-1) + <H,L>, причем, если при сложении возникает бит переноса Carry из крайнего левого разряда регистровой пары <Н,L>, то он добавляется к младшему разряду: КС(i):= КС(i) + Carry. 5) КС=КC(i) - результат, если i=[k/2].

3. Алгоритм BT. Этот предложенный алгоритм реализуется следующим образом: Пусть есть символ или, говоря точнее, байт входящего потока информации, тогда для расчета сигнатуры считаем количество битов, стоящих на четных местах и добавляем полученное значение в верхний регистр H пары <H,L>, количество битов на нечетных позициях добавляется в регистр L. Полученное значение складываем со значением уже рассчитанной на предыдущем этапе сигнатуры, причем пара <H,L> не обнуляется ни на каком этапе (кроме начала). Если возникает бит переноса, то он добавляется в младший разряд <H,L>.

4. Сравнение алгоритмов.

Проведем исследование на предмет различий в качестве расчета сигнатур. Возьмем для исследования словарь русского языка из 93392 слов. Для каждого слова вычислим двухбайтовую сигнатуру с помощью различных алгоритмов и проведем анализ полученных данных. Результаты по различным критериям представлены в таблице [Табл. 1]. Использовались описанные выше алгоритмы: CRC, CR, BT, а также алгоритм SUM, основанный на сложении кодов символов, приведенный для наглядности.

Как показал анализ таблицы, алгоритмы CRC (в варианте CRC-16) и CR по своим возможностям приблизительно одинаковы. От них отличаются два остальных алгоритма: SUM в худшую сторону (алгоритм основан на сложении ASCII-кодов символов), BT - в более удачную по столбцам таблицы (1) и (4).

Выводы

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

Таблица 1

Сравнительная оценка

Литература

1. Глушков В.М. Введение в АСУ. 2-е изд. К.,1974. 290 с.

2. Раков В.И. Об идее нелингвистического восприятия лингвистических «сигналов» в АСУ. // Технологии гуманитарного поиска: сб. ст./ Под ред. Проф. Харченко В.К. Белгород: Ин-т лингвистики, 2000. С. 54-59.

3. Шуваев А.В., Рябинкин Е.В. Программная среда лингвистического процессора управления: отчет по учебной практике. // Кафедра Информационных систем факультета электроники и приборостроения. Руководитель к.т.н. Раков В.И. Орёл: гос. тех. ун-т, 2003. 13 с.