ВУЗ:
Составители:
64
пусть в заданной последовательности значения часто повторяются.
Если способ вычисления F(x) достаточно сложен, то нужно избежать
повторных вычислений одного и того же значения. Для этого следу-
ет по ходу кодирования строить таблицу (справочник) уже найден-
ных кодов. Организация таблицы должна обеспечивать:
• быстрый поиск элемента с заданным значением или устанав-
ливать
факт отсутствия такого элемента в таблице;
• просто добавлять в таблицу новые элементы.
Этим требованиям удовлетворяет представление таблицы в ви-
де двоичного дерева, в вершинах которого расположены различные
элементы последовательности и их коды.
Процесс построения двоичного дерева идет так: первое число и
его код образуют корень дерева. Дерево пока состоит
из одного кор-
ня. Следующее число, которое нужно кодировать, сравнивается с
числом в корне, и если они равны, то дерево не разрастается и код
может быть взят из корня. Если новое число меньше первого, то
проводится ребро из корня влево вниз, иначе – вправо вниз. В обра-
зовавшуюся вершину помещаются это новое
число и его код.
Пусть уже построено некоторое дерево, и нужно закодировать
число х. Сначала х сравниваем с корнем. В случае равенства поиск
заканчиваем, и код числа извлекается из корня. В противном случае
переходим к рассмотрению вершины слева внизу, если х меньше
корня, или справа внизу, если х больше корня.
Сравниваем х с чис-
лом в этой вершине и т.д. Процесс заканчивается в одном из сле-
дующих случаев: найдена вершина, содержащая число, равное х; в
дереве отсутствует вершина, к которой нужно перейти для выполне-
ния очередного шага поиска. В первом случае из найденной верши-
ны извлекается код числа х. Во
втором – кодируется число х кодом
F(x) и к дереву присоединяется новая вершина.
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
