Доброго времени суток.
Заранее извинюсь, если создал тему не в той ветке. Я у Вас впервые
И в программировании относительно новичок.
А вопрос мой вот в чем.
Я написал небольшую модификацию LZ алгоритма сжатия. Но возникла сложность со словарем.
На данном этапе в словарь сохраняются последовательности целиком, что на мой взгляд не эффективно.
Гуру посоветовали использовать дерево для хранения данных последовательностей. Сказали, что в таком случае
я избегу повтора символов, и, как следствие, при тех же размерах словаря — увеличу его вместительность.
Я полистал википедию, гугл. Получил общие представления о деревьях. А вот как их строить — ума не приложу.
Посоветуйте, что и как. Как лучше хранить элементы дерева(или листья как их называют),
и как лучше перемещаться по этому самому дереву? Основная проблема конечно в сохранении элементов.
Есть идея после каждого элемента ставить ссылку на след. элемент. Но что-то она мне не особо нравится.
Заранее благодарен
05.11.07 11:53: Перенесено модератором из 'C/C++' — Odi$$ey
На каждую хитрую функцию найдется параметр с резьбой.
Возможно, имеет смысл посмотреть в сторону стандартных контейнеров вообще, и в на std::map/std::set в частности — эти 2 контейнера реализуют бинарные деревья.
B>Возможно, имеет смысл посмотреть в сторону стандартных контейнеров вообще, и в на std::map/std::set в частности — эти 2 контейнера реализуют бинарные деревья.
Боюсь что человеку это не поможет. Лично я не знаю способов не хакая конкретные реализации stl использовать map/set в "деревянных" алгоритмах — к примеру, пройтись от конкретного узла к корню (а это первое что ему понадобится).
N>Гуру посоветовали использовать дерево для хранения данных последовательностей. Сказали, что в таком случае N>я избегу повтора символов, и, как следствие, при тех же размерах словаря — увеличу его вместительность.
Гуру тебе посоветовали сделать классическую реализацию LZW. Структура данных там приблизительно следующего вида:
struct node {
char ch;
node *parent, // указатель на родителя
*next, // указатель на следующего ребенка родителя ("брата")
*frist_child; // указатель на первого ребенка
};
#define BITS_PER_INDEX 12
#define N (1 << BITS_PER_INDEX];
node dictionary[N];
size_t nodes_used;
Поиск состоит следующим образом: положим тебе надо найти строчку "ABCD". Сначала находишь ноду с parent = 0 и ch = 'A'. Потом смотришь всех детей и ищешь того, у которого ch = 'B' и так далее... Вставка состоит из поиска и добавления некоторого количества нодов в словарик.
sch>struct node {
sch> char ch;
sch> node *parent, // указатель на родителя
sch> *next, // указатель на следующего ребенка родителя ("брата")
sch> *frist_child; // указатель на первого ребенка
sch>};
sch>#define BITS_PER_INDEX 12
sch>#define N (1 << BITS_PER_INDEX];
sch>node dictionary[N];
sch>size_t nodes_used;
sch>
Спасибо. Я тут вот подумал. Формально, обратное движение по дереву можно реализовать и без указателя на родителя. Достаточно простого статуса, мол, родитель или нет. И для экономии юзать не 1, а две структуры. Если RVA укладываются в 7 бит, то можно заюзать обычную структуру, если не укладываются, то расширенную.
Т.е. примерно так:
struct node {
BYTE ch; // элемент дерева
BYTE ExtStatus :1; // расширенная структура или обычная
BYTE parent :1; // родительский статус. Если 0 - первый узел, если 1 - не первый(есть родители)
WORD child_1 :7; // RVA на первого ребенка
WORD child_2 :7; // RVA на второго ребенка
};
struct node_ext {
BYTE ch; // элемент дерева
BYTE ExtStatus :1; // расширенная структура или обычная (1 бит)
BYTE parent :1; // родительский статус. Если 0 - первый узел, если 1 - не первый(есть родители) (1 бит)
WORD child_1 :15; // RVA на первого ребенка (15 бит)
WORD child_2 :15; // RVA на второго ребенка (15 бит)
};
И того от 3х до 5 байт на лист.
Что вы по этому поводу думаете?
На каждую хитрую функцию найдется параметр с резьбой.
sch
Спасибо. Я тут вот подумал. Формально, обратное движение по дереву можно реализовать и без указателя на родителя. Достаточно простого статуса, мол, родитель или нет. И для экономии юзать не 1, а две структуры. Если RVA укладываются в 7 бит, то можно заюзать обычную структуру, если не укладываются, то расширенную.
Т.е. примерно так:
struct node {
BYTE ch; // элемент дерева
BYTE ExtStatus :1; // расширенная структура или обычная
BYTE parent :1; // родительский статус. Если 0 - первый узел, если 1 - не первый(есть родители)
BYTE child_1 :7; // RVA на первого ребенка
BYTE child_2 :7; // RVA на второго ребенка
};
struct node_ext {
BYTE ch; // элемент дерева
BYTE ExtStatus :1; // расширенная структура или обычная (1 бит)
BYTE parent :1; // родительский статус. Если 0 - первый узел, если 1 - не первый(есть родители) (1 бит)
WORD child_1 :15; // RVA на первого ребенка (15 бит)
WORD child_2 :15; // RVA на второго ребенка (15 бит)
};
И того от 3х до 5 байт на лист.
Что вы по этому поводу думаете?
На каждую хитрую функцию найдется параметр с резьбой.
N>И того от 3х до 5 байт на лист. N>Что вы по этому поводу думаете?
Не получится выиграть ни в скорости, ни в производительности: придется динамически выделять память, что медленно. Либо выделить два массива по N, один с типом node и другой с типом node_ext, что тоже по большому счету медленнее, ибо увеличивает объем данных, которыми оперирует программа.
