Структура

Обзор классических алгоритмов контекстного моделирования

LOEMA

Судя по всему, впервые алгоритм контекстного моделирования был реа­лизован в 1982 г. Робертсом (Roberts) [2]. Автор назвал свой алгоритм Local Order Estimation Markov Analysis (марковский анализ посредством оценива­ния локального порядка). В LOEMA используется полное смешивание оце­нок КМ различного порядка, при этом веса представляют собой значения уровня доверия к оценке в том смысле, как это понимается в математиче­ской статистике. Сравнение степени сжатия LOEMA с другими алгоритма­ми затруднено, так как, с одной стороны, программа, реализующая алго­ритм, не стала ...

Структура словаря LZW

До этого момента считалось, что словарем LZW служит массив из строк переменной длины. Чтобы понять, почему специальное дерево будет являться лучшей структурой для словаря, следует напомнить работу кодера. Он считывает символы и добавляет их в строку I до тех пор, пока I находится в словаре. В некоторый момент строка 1х в словаре не обнаруживается, и тогда строка 1х помещается в словарь. Значит, при добавлении новых строк в словарь поступает всего один новый символ х. Это предложение можно перефразировать еще так: для каждой словарной строки в словаре найдется «родительская» строка, ...

Циклическая очередь

Циклическая очередь является важной структурой данных. Физически это массив, но его индекс используется особым способом. Рис. 2.1 иллюстрирует простой пример. На нем показан массив из 16 байт с символами, из которых одни добавлены в «конец», а другие -удалены из «начала». Обе позиция конца и начала перемещаются, и два указателя s и е все время на них указывают. На рис. (а) имеется 8 символов sid_east, а остаток буфера пуст. На рис. (Ь) все 16 символов заняты, а е указывает на конец буфера. На (с) первая буква s была удалена, а буква 1 в easily была вставлена. Заметьте, что указатель е ...