C++
Algorithms
31 March 2012

Структура Radix Tree для сжатия данных

Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.


Техническое задание


Итак исходные данные.
Допустим у нас имеется телефонная книга, или проще говоря список контактов. С каждым контактом
связан набор атрибутов. Для программы «телефонный firewall» — это могут быть булевы атрибуты:
исходящий/входящий звонок, работа в рабочее/не рабочее время, разрешить/блокировать или автоответ
при звонке. Задача состоит в хранении списка контанктов и их атрибутов в памяти телефона, в сжатой форме. В условиях ограниченного объема доступной памяти.

Итак, более детализированное техническое задание выглядит таким образом:
— Имеется .INI файл с набором правил для каждого номера. Правило содержит телефонный номер
и собственно булевые атрибуты, применимые к нему. Номера уникальны.
Пример .INI файла, где 12345 — номер телефона:
[RULES]
R0000=12345,0,0,0,0,0,0,0,0,0,0
R0001=123764465,0,0,0,0,1,0,1,0,0,0

R0765=…

— Внутренее представление правила:
class NumberEntry
{
  string   number     ;
  bool   attCalledNumber    ;
  bool   attCallingNumber  ;
  bool   attInboundCall    ;
  bool   attOutboundCall    ;
  bool   attWorkingHours    ;
  bool   attNonWorkingHours  ;
  bool   attBlocked    ;
  bool   attAllowed    ;
  bool   attPrefix    ;
  bool   attAutoAnswer    ;
};


* This source code was highlighted with Source Code Highlighter.


— Для имеющегося набора правил, следует построить промежуточный расширенный граф.
В Графе, каждый узел может быть помечен как листовой. Для примера возьмем такой набор гипоптетических номеров:
012345
012346
01234567#
54647
5463
54638

Должен быть построен промежуточный граф:

Рисунок 1. Расширенный (не сжатый) граф из ТЗ.

— Расширенный Граф строится по следующим правилам:
Последняя цифра каждого номера в списке, обозначает листовой узел. Атрибуты связанные с номером откносяться только к листовому узлу. В графе, любой узел может быть помечен, как листовой. Для примера выше, цифра 5 в номере 012345 представляет листовой узел, несмотря на то, что также является частью номера 01234567#

— После того, как все номера добавлены в промежуточный граф (Expanded), следует его сжать. Таким образом, чтобы каждый узел промежуточного графа
(наример 0xxx5xxx#), заменяется последовательностью компактных узлов (Compact Nodes, без 'x').

Узлы расширенного и компактного графа представлены такими струтурами:
#pragma pack(push, 1)  // выравнивание структуры в 1 байт для MS C++
#define K_MAX_EXPANDED_NODES    12  // максимальное цифр в узле. Это цифры 0-9, * и #
struct SG_Y_DigitElement  // Узел промежуточного графа, 4 байта
{
  UINT  digit       : 4;  // Цифра 0-9 . '*' задана как 0xA, '#' как 0xB. Всего 12 значений, поэтому 4 бита
  UINT   nextNodeOffset     : 13;  // Адрес следующего узла графа, относительно первого байта графа
  BOOL  leafNode      : 1;  // Листовой узел?

  BOOL   attCalledNumber    : 1;  // Атрибуты. Заданы только у листового узла
  BOOL   attCallingNumber    : 1;
  BOOL   attInboundCall    : 1;
  BOOL   attOutboundCall    : 1;
  BOOL   attWorkingHours    : 1;
  BOOL   attNonWorkingHours  : 1;
  BOOL   attBlocked      : 1;
  BOOL   attAllowed      : 1;
  BOOL   attPrefix      : 1;
  BOOL   attAutoAnswer    : 1;
  BOOL   attReserved1    : 1;
  BOOL   attReserved2    : 1;
  BOOL   attReserved3    : 1;
  BOOL   attReserved4    : 1;
}

typedef SG_Y_DigitElement SG_Y_ExpandedNode[K_MAX_EXPANDED_NODES];

struct SG_Y_CompactNode  // сжатый узел размером 5 байт. Длинна последовательности+цифра
{
  UINT8  nodeLen   : 4;
  UINT8  reserved   : 4;
  /* Первая цифра в последовательности */
  SG_Y_DigitElement  digits;
} ;
#pragma pack(pop)


* This source code was highlighted with Source Code Highlighter.


— На основе расширенного графа, который представлен массивом из элементов типа SG_Y_ExpandedNode, строится компактный граф с узлами типа SG_Y_CompactNode. Таким образом и происходит сжатие данных, путем удаления пустых элементов, обозначенных как 'x', из SG_Y_ExpandedNode. Для расширенного графа из примера выше, компактный граф будет иметь такой вид после сжатия (зеленым обозначено количество цифр в компактном узле, поле nodeLen структуры SG_Y_CompactNode):

Рисунок 2. Сжатый граф из ТЗ.

— Следует отметить, что указатели на узлы (поле nextNodeOffset в SG_Y_DigitElement), в обоих графах представляют собой индекс относительно первого байта графа. Оба графа представлены массивами.

— Подытожим ТЗ:
  • На вход поступает .INI файл с правилами файрвола для телефонного номера.
  • Считываем правила в список типа NumberEntry
  • Формируем промежуточный расширенный граф на основе списка. Где листовой узел графа, содержит атрибуты относящиеся к номеру.
  • Генерируем сжатый граф, путем удаления пустых элементов из расширенного


Построение промежуточного графа


Первый шаг алгоритма — тривиален. Будем считать, что правила считаны и добавлены в список. Имеем набор номеров в list, который поступает на вход генератору графа. Здесь и в прилагаемых исходниках, используется термин генератор графа (GraphGenerator), для обозначения класса реализуещего алгоритм построения и сжатия.

Переходим непосредственно к построению промежуточного расширенного графа (Expanded).
Обратите еще раз внимание, на рисунок 1. Этот промежуточный граф, можно представить бинарным деревом, построенным по принципу Radix Tree (или русский аналог — дерево остатков). Давайте более подрбно остановимся на этой структуре данных.

Добавление элемента в Radix Tree происходит следующим образом:
— Берется каждый i-ый бит добавляемого значения.
— Элемент проталкивается вниз дерева, на основе текущего бита. Если i-ый бит — 0, значит идем влево, иначе вправо.
И так до тех пор, пока не будут обработаны все значимые биты значения.
— В итоге, листовой узел Radix Tree — будет обозначать само значение. Таким образом, проходя путь от корня к листовому узлу,
получаем все биты значения. Иллюстрацию подхода можно найти здесь. В русской wiki описания Radix Tree еще нет.

Для примера возьмем три номера: 0123, 01234, 123. Тогда на первой итерации, дерево построится сверху вниз, создав 4 узла (0,1,2,3-лист). На второй итерации, при добавлении номера 01234, мы пройдем по тому-же пути при добавлении элементов 0, 1, 2 и 3, так как узлы для этих цифр уже созданы. А вот при добавлении последнего элемента, находясь в узле со значением 3, мы создаем новый листовой узел 4. И на третей итерации, добавление номера 123, происходит вправую сторону.

Если представить полученное дерево в виде графа, где узел справа является «братом», а узел слева «сыном», то получим такую картину

Рисунок 3. Связи графа

Применим алгоритм добавления в Radix Tree для нашего расширенного графа. Узел графа представлен массивом из 12-ти возможных значений (0-9*#). То есть мы применяем отображение expandedNode[digit], для проверки и задания значения узла.
На рисунке ниже, expandedGraph — представлен в виде массива узлов expandedNode. '-' обозначает пустой элемент, голубой элемент — обозначает листовой узел. Напомню, листовой узел в нашей задаче содержит атрибуты номера.


Рисунок 4. Расширенный (несжатый) граф

Думаю идея использования Radix Tree становится уже более ясной и из самого рисунка понятно, что сжатие можно произвести путем удаления пустых элементов.

Сжатие. Построение компактного графа.


Алгоритм сжатия относительно прост, и может быть описан в двух предложениях. Имеем расширенный граф expandedGraph, представленный в виде массива из expandedNode.
— Берем непустые элементы (цифры) из узла expandedGraph[i]. Переносим их в сжатый граф, который представлен массивом из SG_Y_CompactNode. Задаем длину компактного узла как количество непустых элементов.
— Применяем процедуру сжатия для каждого дочернего узла. Меняем ссылки на дочерние элементы относительно начала CompactGraph.

Алгоритм сжатия — рекурсивный. Мы выбираем непустые элементы из узла, и выкладываем их последовательно в сжатом графе, задавая длину узла. Таким образом из расширенного узла вида
«01-----------», мы получаем компактный узел '[2]01', где [2] — длина узла.
Рекурсивно вызываем процедуру для дочерних элементов '0' и '1'. Затем связываем '0' и '1' с дочерними элементами относительно начала сжатого графа.


Рисунок 5. Результат — сжатый граф.

Заключение.


— Использование алгоритма оптимально подходит для сжатия и хранения телефонных номеров. Префиксы вроде кодов сотовых операторов, кода страны или города, повзоляет хранить эти самые кода в корневых узлах графа. Реализация непосредственно используется в софте крупной телекоммуникационной компании.
Однако, его можно использовать для любых последовательностей данных. Например для хранения символьных данных латиницы без учета регистра, размер узла графа нужно увеличить до 26-ти элементов. Соответственно и под поле digit выделить 5 бит.
Если атрибуты не требуются, то размер SG_Y_DigitElement можно уменьшить вплоть до 2-х байт. Например 5 бит для значения символа, 10 бит для указателя на следующий узел и 1 бит для маркера листа.
Очевидно, что ограничения на количество адресуемых записей ограничено полем nextNodeOffset. В нашем примере 13 бит, достаточно для адресации 8192 записи.

Здесь реализация алгоритма

+16
9.9k 93
Comments 5
Top of the day