В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 11
Текст из файла (страница 11)
К счастью, это единственнаяпроблема,– нетрудно понять, что если искомого кода в словаре еще нет, то случиться этоможет только в случае, если мы не успели туда добавить соответствующую цепочку.Деваться ей некуда – кроме как временно «висеть» в неопределенном пока состоянии.Поэтому становится понятно, что первый символ цепочки с несуществующим кодом – вточности равен первому символу еще не добавленной цепочки. Соответственно описаннаяпроблема решается просто – если цепочки с нужным номером нет, то полагаем последнийЛекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год35символ текущей цепочки равным ее первому символу и добавляем ее в словарь – она как раззаймет место, где мы только что искали цепочку. В приведенном примере мы цепочки скодом 300 не найдем, следовательно полагаем, что JOHNA(?) – это JOHNAJ и добавляемJOHNAJ в словарь – и эта цепочка окажется под кодом 300 автоматически, что сразу сниметпроблему. Как было показано, это – единственная проблемная ситуация (все сказанное допримера декомпрессии – корректно, просто там не учтена «задержка» добавления цепочки всловарь)Итак, полностью корректный алгоритм распаковки:1.
Вначале словарь заполнен только кодами односимвольных цепочек; на входеалгоритма – некоторая последовательность байт, указатель на текущий элементвходной последовательности стоит на первом символе, входная цепочка пуста.2. Пока во входной последовательности есть символы - берем текущий входнойсимвол. Если в словаре он есть - то декодируем его в соответствии со словарем изаписываем в выходную последовательность, после чего дописываем к текущейцепочке первый символ декодированной последовательности и добавляем текущуюцепочку в словарь (за исключением самого первого добавления такой цепочки всловаре еще нет). Если в словаре символа нет, то дописываем к текущей цепочкепервый символ текущей цепочки, записываем в словарь текущую цепочку, выводимтекущую цепочку в выходную последовательность (при этом автоматическиполучится, что код текущей цепочки окажется равным коду текущего входногосимвола)3.
Заменяем текущую цепочку на последовательность, соответствующую текущемусимволу, затем переходим к следующему символу входной последовательности ивозвращаемся к шагу 2.Вернемся к вопросу о эффективности LZW. На практике входная последовательностьобычно кодируется байтами (т.е. цепочками по 8 бит), выходная – кусками некоторойфиксированной длины (n>8 бит, часто применяют n=12). Проблема в том, что словарьполучается в 2 n записей и если n достаточно мало то он может закончиться до окончаниясжатия. Вместе с тем, чем меньше n, тем эффективнее сжатие.
Поэтому применяютследующий прием: вводят специальный символ – CLC (например, последний символсловаря), который ничего не кодирует, а служит сигналом о необходимости очиститьсловарь, т.е. «сбросить» словарь в начальное состояние и продолжать кодировать /декодировать дальнейшую последовательность с этим словарем.
Может применяться иальтернативный способ – если словарь заполнился, то очистить его.LZW очень удобен своей простотой и скоростью работы (при грамотной организациисловаря), а главное – он может применяться для сжатия потоковых данных, поскольку дляего работы требуется всего один проход по входной последовательности (для Хаффмана –два, кроме адаптивного варианта, для арифметического кодирования – то же самое, 2 длянеадаптивного, 1 для адаптивного, и RLE – тоже один), причем данные на выход поступают«постоянно» - задержка потока при сжатии весьма мала (Хаффман и арифм.
кодированиенакладывают ощутимую задержку, связанную с тем, что данные на их выходе появятсятолько после обработки некоторого блока входных данных, для Хаффмана к тому жетребуется достаточно много дополнительной памяти). Но по степени сжатия он достаточнослаб, поэтому используется обычно вместе с другими алгоритмами, например,RLE+LZW+Арифметическое кодирование (адаптивное) – уже достаточно эффективныйалгоритм.Для достижения лучших результатов при сжатии данных необходимо использоватьболее сложные алгоритмы сжатия со словарем, использующие статистическуюинформацию.Лекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год362.3. КомпиляцияВо-первых, отметим, что существуют контекстно-свободные языки (не зависящие отситуации, в которой они применяются, более строгое определение – см. далее). В такихязыках можно выделить 2 больших раздела:1. Синтаксис – некоторые правила, по которым задаются конструкции в языке2.
Семантика – внутренний смысл языковых конструкцийЛюбой алгоритмический язык обладает семантикой – поскольку любая алгоритмическаяконструкция задает некий порядок действий, целиком определяющий смысл этойконструкции.Для задания алгоритмических языков сегодня используются только два подхода – LRразбор на основе формальных грамматик и рекурсивный разбор. Рекурсивный разборнесколько проще, но медленнее и область его применимости уже, в данном курсе онрассматриваться не будет).
LR-разбор весьма сложен, поэтому здесь приводятся только егоосновы.Формальной грамматикой называется тройка {A, M, R}, где A – алфавит языка (наборэлементарных символов, из которых строятся выражения языка), M – множествометасимволов ( M M t M n - множество метасимволов состоит из множестватерминальных и нетерминальных метасимволов). Метасимволы – некоторые конструкцииязыка – терминальные M t метасимволы – «неделимые единицы языка» (например,ключевые слова в C), нетерминальные метасимволы – состоят из других метасимволов. R –множество правил вывода – то, как следует интерпретировать метасимволы. Любоевыражение языка должно являться метасимволом этого языка, для любого метасимволадолжно существовать правило вывода.Например, возьмем тексты по русскому языку – их можно представить формальнойграмматикой. За метасимвол самого верхнего уровня можно взять текст, текст будетсостоять из абзацев, абзацы – из предложений, предложения – из слов, слова – из приставок,корней, суффиксов и окончаний.
Все перечисленные объекты будут метасимволами,приставки, корни, суффиксы и окончания – терминальными, остальные – нетерминальными.На этом примере кроме того понятно, что один и тот же язык можно задать несколькимиграмматиками – например, мы могли остановить разбор на словах, или рассмотреть такиеметасимволы как словосочетания.Ясно, что элементы M должны как-то быть друг с другом связаны, например, указаниемтерминальных метасимволов и способов разложения нетерминальных метасимволов натерминальные.
Такие способы указываются в R. Для их описания был придуманспециальный язык записи правил – НФБНСтрогое определение контекстно-свободного языка: язык называется контекстносвободным, если1. его можно записать в формальной грамматике в виде набора правил виданетерминальный метасимвол = конечная цепочка метасимволов2. среди нетерминалов выделен один или несколько символов, называемых начальными(главными) метасимволами грамматики (см. далее)3. для каждого главного метасимвола есть хотя бы одно правило; общее число правилконечноНФБН (Нормальная форма Бэкуса-Наура) – специальный язык записи правилразбора языковых выражений. Язык очень простой – все, что заключено в треугольныескобки – метасимвол; все, что вне этих скобок – элементы из алфавита языка (кромеспециального символа |, означающего «или» и пробелов, которые при разбореинтерпретируются как разделители), определения для метасимволов записываются как<метасимвол> ::= выражение.Например, опишем в НФБН, что такое целое число в стандарте C:<целое> ::= <целое_беззнаковое>|<знак><целое_беззнаковое><целое_беззнаковое> ::= <цифра>|<цифра><целое_беззнаковое>Лекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год37<цифра> ::= 0|1|2|3|4|5|6|7|8|9<знак> ::= +|-При этом легко проверить, что -54 – это целое число: при разборе-54 – целое?- это знак54 – целое беззнаковое?5 – цифра4 – целое беззнаковое?4 – цифразначит 4 – целое беззнаковое, 54 – целое беззнаковое, -54 – целое.Легко видеть, что формальная грамматика может быть рекурсивной – именно так мыопределили <целое_беззнаковое>.
Приведем чуть более сложный пример – определениеимени в языке C:<имя>::=<буква>|<имя><буква>|<имя><цифра><буква> ::= a|b|c|…|x|y|z<цифра> ::= 0|1|2|…|8|9Проверим, что abc1 – это имя в языке Cabc1 (<имя>)ab (<имя>)a (<буква>)a (<имя>)1 (<цифра>)b (<буква>)Буквы и цифры при этом у нас являются терминальными метасимволами, имена –нетерминальными.К сожалению, в «чистом» виде НФБН неудобна. Поэтому вводят некоторыесокращения.
Например, [выражение] – необязательное выражение. В частности, пример сцелыми числами мы могли бы переписать проще:<целое> ::= [<знак>]<целое_беззнаковое><целое_беззнаковое> ::= <цифра>|<цифра><целое_беззнаковое><цифра> ::= 0|1|2|3|4|5|6|7|8|9<знак> ::= +|-Кроме того, в любой грамматике можно выделить самые крупные метасимволы – ихназывают главными метасимволами, ради их разбора и строится вся грамматика.Например, в примере выше главный метасимвол - <целое>. Цель разбора с использованиемформальной грамматики – построение для главных метасимволов дерева разбора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
