Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм архивирования древоподобных данных / 13 сообщений из 13, страница 1 из 1
25.04.2009, 20:18:26
    #35954160
PC_2
PC_2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
Есть большое дерево элементов.
Известно что некоторые ветки этого дерева могут быть друг на друга очень похожи.
Разница между двумя ветками например может для примера заключаться всего лишь в одной маленькой подветочке "где-то там в глубине".

Есть ли какаято мат часть как такое дело лучше всего сжимать ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.04.2009, 21:51:57
    #35954230
Kew
Kew
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
Если это дерево при сериализации всегда упорядочивать по значениям и иерархии узлов и устранить зависимость сериализованного значения узла от положения в тексте, то любой lz- или lzw-based алгоритм сжатия будет показывать хорошие результаты.
Например, вот такое дерево:
{a 5 {b 2 {c 1 {d 0}} {{c 1 {d 0}}}} {b 2 {c 1 {d 0}} {{c 1 {d 0}}}} {b 2 {c 1 {d 0}} {{c 1 {d 0}}}} {b 2 {c 1 {d 0}} {{c 1 {d 0}}}} {b 2 {c 1 {d 0}} {{c 1 {e 0}}}}}
, очевидно, неплохо сожмется :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 00:41:53
    #35954338
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
PC_2Есть большое дерево элементов.
Известно что некоторые ветки этого дерева могут быть друг на друга очень похожи.
Разница между двумя ветками например может для примера заключаться всего лишь в одной маленькой подветочке "где-то там в глубине".

Есть ли какаято мат часть как такое дело лучше всего сжимать ?
Если архивирование ставит своей целью уменьшить размер - то можно просто сериализовать дерево обходом в глубину и к полученному дампу применить классический LZW.

Если ты хочешь получить какие-то дополнительные бонусы вроде возможности работать со сжатыми узлами дерева в онлайне, то надо подумать...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 01:00:22
    #35954348
PC_2
PC_2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
бонусы бонусы ...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 01:20:04
    #35954358
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
PC_2Разница между двумя ветками например может для примера заключаться всего лишь в одной маленькой подветочке "где-то там в глубине".
Можешь привести пример? Желательно на реальных данных.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 01:33:11
    #35954363
Nikolay Kalmarskiy
Nikolay Kalmarskiy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
PC_2,

Выгрузить каждую ветку в текстовый файл и пройтись DIFF'ом. Одну взять за базу, а остальные хранить как дельту от базовой ветки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 01:42:09
    #35954370
Nikolay Kalmarskiy
Nikolay Kalmarskiy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
 
Пример
$ cat branch-a.txt
[src Ветка А]
ДОБАВИТЬ УЗЕЛ А
НАЧАТЬ ВЕТКУ
ДОБАВИТЬ УЗЕЛ А
ДОБАВИТЬ УЗЕЛ Б
ЗАКРЫТЬ ВЕТКУ
ДОБАВИТЬ УЗЕЛ Б
ДОБАВИТЬ УЗЕЛ В
ДОБАВИТЬ УЗЕЛ Д
[/src]
$ cat branch-b.txt
[src Ветка Б]
ДОБАВИТЬ УЗЕЛ А
НАЧАТЬ ВЕТКУ
ДОБАВИТЬ УЗЕЛ А
ДОБАВИТЬ УЗЕЛ Ё
ЗАКРЫТЬ ВЕТКУ
ДОБАВИТЬ УЗЕЛ Б
ДОБАВИТЬ УЗЕЛ В
ДОБАВИТЬ УЗЕЛ Д
[/src]
$ diff -e branch-a.txt branch-b.txt
5c
ДОБАВИТЬ УЗЕЛ Ё
.
1c
[src Ветка Б]
.

$
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 02:11:03
    #35954378
PC_2
PC_2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
что-то я даже в замешательстве.
Взял XML в 48 мегабайт сжал его ВинРаром и получил после сжатия 1.1 мегабайта ...

интересно что там за алгоритм, что жмет почти в 50 раз. Ведь там в каждой строчке например есть порядковый номер, 250 000 чисел, по 4-6 байт на каждое число получается метр, а ведь там в строчках еще куча разной информации ...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 02:19:37
    #35954382
Kew
Kew
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
Rar использует lzss (скользящее окно переменнго размера, управляется ключом -mX) и какую-то оригинальную схему оптимального кодирования его выхода. Скорее всего, адаптивного Хаффмана.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 04:02:27
    #35954401
tchingiz
tchingizПривилегированный пользователь
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
PC_2что-то я даже в замешательстве.
Взял XML в 48 мегабайт сжал его ВинРаром и получил после сжатия 1.1 мегабайта ...

интересно что там за алгоритм, что жмет почти в 50 раз. Ведь там в каждой строчке например есть порядковый номер, 250 000 чисел, по 4-6 байт на каждое число получается метр, а ведь там в строчках еще куча разной информации ...
это хмл такое, гм, такая хорошая вещь
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 14:32:28
    #35954593
Nikolay Kalmarskiy
Nikolay Kalmarskiy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
Вот! А если похожие ветки не выгружать целиком, а выгружать только дельту между ними, то размер ещё меньше будет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 14:38:02
    #35954599
Kew
Kew
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
Алгоритм lzw занимается именно этим :) Алгоритм lzss занимается этим по большей части :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.04.2009, 22:00:36
    #35954853
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм архивирования древоподобных данных
PC_2интересно что там за алгоритм, что жмет почти в 50 раз. Ведь там в каждой строчке например есть порядковый номер, 250 000 чисел, по 4-6 байт на каждое число получается метр, а ведь там в строчках еще куча разной информации ...
Зависит от сжимаемых данных. Для текста и в 500 раз будет не предел.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм архивирования древоподобных данных / 13 сообщений из 13, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 425ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1344514]:
 0ms
get settings:
 5ms
get forum list:
 13ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 157ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 30ms
get tp. blocked users:
 1ms
others: 206ms
total:  425ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]