ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм архивирования древоподобных данных
13 сообщений из 13, страница 1 из 1
Алгоритм архивирования древоподобных данных
    #35954160
PC_2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PC_2
Участник
Есть большое дерево элементов.
Известно что некоторые ветки этого дерева могут быть друг на друга очень похожи.
Разница между двумя ветками например может для примера заключаться всего лишь в одной маленькой подветочке "где-то там в глубине".

Есть ли какаято мат часть как такое дело лучше всего сжимать ?
...
Рейтинг: 0 / 0
25.04.2009, 20:18:26
| Ответить | Цитировать | Написать  
Алгоритм архивирования древоподобных данных
    #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
25.04.2009, 21:51:57
| Ответить | Цитировать | Написать  
Алгоритм архивирования древоподобных данных
    #35954338
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
PC_2Есть большое дерево элементов.
Известно что некоторые ветки этого дерева могут быть друг на друга очень похожи.
Разница между двумя ветками например может для примера заключаться всего лишь в одной маленькой подветочке "где-то там в глубине".

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

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

Выгрузить каждую ветку в текстовый файл и пройтись DIFF'ом. Одну взять за базу, а остальные хранить как дельту от базовой ветки.
...
Рейтинг: 0 / 0
26.04.2009, 01:33:11
| Ответить | Цитировать | Написать  
Алгоритм архивирования древоподобных данных
    #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, 01:42:09
| Ответить | Цитировать | Написать  
Алгоритм архивирования древоподобных данных
    #35954378
PC_2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PC_2
Участник
что-то я даже в замешательстве.
Взял XML в 48 мегабайт сжал его ВинРаром и получил после сжатия 1.1 мегабайта ...

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

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


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