Структура 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
    • 8,8k
    • 5
    Поделиться публикацией
    Комментарии 5
    • НЛО прилетело и опубликовало эту надпись здесь
        0
        Так было описано в ТЗ для большей ясности. Также, обратный процесс разархивирования, требует преобразования в расширенный граф из компактного.
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            Radix tree, Trie и DAWG по сути одно и тоже в смысле представления данных. То есть ключ хранится в нижнем листовом узле. Как представить цикличность DAWG для имеющейся структуры SG_Y_DigitElement не совсем понятно. И целесообразность подхода сомнительна, так как результат аналогичен, а построение промежуточной структуры усложняется.
        0
        А что за устройство, почему в него не влазят 8 тыщ записей без хитрого сжатия?

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое