Кстати есть интересная идея....

← →
Wild Wizard (2003-04-03 16:00) [0]

По поводу алгоритмов...Я как-то был на вечеринке и обсуждали мы арфиваторы...И пришла мне в голову одна идея...Правда не знаю насколько рабочая....Фишка вот в чем:
Насколько я знаю все архиваторы работают по принципу исключения избыточных данных...

А что если далать не так?

К премеру, у нас есть словарь в нем 256 "слов" по "256" букв,
открываем файл и ищем последовательность которая совпадет со словарем, заменяем её на <номер слова><позиция в слове><длинна>...
Дальше - больше, делаем 256 "словарей", потом 256 "томов" по 256 "словарей" и.т.д

Вопрос, реально ли таким образом запаковать файл и добиться большого сжатия?

← →
JibSkeart (2003-04-03 16:05) [1]

Но ведь это же для частного случая ...
А словарь хранить в упаковщике ?

← →
Wild Wizard (2003-04-03 16:09) [2]

Словарь хранить с кодером и почему частный?

← →
Шишкин Илья (2003-04-03 16:11) [3]

Это будет работать только для текстовых файлов.
А окончания, суффиксы слов и т.д.? Какой же потребуется словарь?!

← →
Wild Wizard (2003-04-03 16:13) [4]

Стоп...Кто сказал?Байт-он байт и есть!
Что у текстового что у бинарника...А словарик....берем штук 100 mpg по 700 мегов и ищем самые частые последовательности.....

← →
vuk (2003-04-03 16:15) [5]

Угу. А потом придём к идее адаптивного словаря и получим что-нибудь типа LZW. :o)

← →
blackman (2003-04-03 16:15) [6]

Не изобретай велосипед!
Вот здесь
Идея арифметического кодирования:
http://blackman.wp-club.net/docum/compress/arithm.php
Обратимое сжатие или сжатие без наличия помех
http://blackman.wp-club.net/docum/compress/modeling.php
Алгоритм расширяющегося префикса
http://blackman.wp-club.net/docum/compress/splay.php
Формат архивного файла RAR Техническая информация по RAR версии 2.50
http://blackman.wp-club.net/docum/rar.php

← →
pasha676 (2003-04-03 16:19) [7]

Меня приколбасило от фразы

> Я как-то был на вечеринке и обсуждали мы арфиваторы...

Прям настоящие лесорубы: в лесу о бабах, с бабами о лесе.

← →
Mike B. (2003-04-03 16:19) [8]

Идея, в общем, рабочая, правда тебе остался один шаг до изобретения алгоритма Лемпела-Зива :)

← →
Wild Wizard (2003-04-03 16:22) [9]

:)))
Это ты зря (в смысле о лесорубах), споры бывают разные...просто был старый знакомый, давно не виделись и.т.д....

Эээээ жаль :((((((
А я думал что крутой :)))))
Но нет добра без худа....у смысле наоборот...Зато пиво хорошее там было :)))

← →
Wild Wizard (2003-04-03 16:23) [10]

vuk © Нет, не придем....смысл в том чтобы словарь хранить на диске, а обмениваться только УКАЗАНИЕМ кусков словаря...

← →
Ru (2003-04-03 16:24) [11]

>Wild Wizard © (03.04.03 16:00)

мое мнение: маразм.

>К премеру, у нас есть словарь в нем 256 "слов" по "256" букв,

допустим, только непонятно, что имеется в виду. Тип словаря к примеру.

>открываем файл и ищем последовательность которая совпадет со словарем,

ну допусти если это алгоритм из семейства LZ, то в результате съэкономите от нескольких байт до нескольких мегабайт в зависимости от того, что пакуете

>заменяем её на <номер слова><позиция в слове><длинна>...

если: <символ><длина> - то это RLE - один из самых простых методов кодирования

>Дальше - больше, делаем 256 "словарей", потом 256 "томов" по 256 "словарей" и.т.д

уточните какие словари.

← →
vuk (2003-04-03 16:29) [12]

to Wild Wizard:
>смысл в том чтобы словарь хранить на диске
Тогда каков смысл такого "упаковщика", если для того, чтобы им что-то запаковать/распаковать нужно заранее знать весь словарь? И что вы будете делать нарвавшись на то, чего в словаре нет? :o)

← →
Wild Wizard (2003-04-03 16:30) [13]

Пересылка данных...Смысл в пересылке данных...

← →
Ru (2003-04-03 16:45) [14]

>Wild Wizard © (03.04.03 16:30)
>Пересылка данных...Смысл в пересылке данных...

LZW - лицензионный http://www.unisys.com/about__unisys/lzw/

можно порыть в направлении Хафмана или другого алгоритма семейства LZ. Но награмождать более одного словаря - туповато будет.
Теперь какие данные? Если текстовые сообщения то это одно, если, скажем архив какого-нибудь сайта это другое.
В общем случае экономии не будет, а скорее наоборот, в частностях можно достичь некоторой экономии, но за счет того, что вместь с запакованными данными не передается словарь.

← →
Wild Wizard (2003-04-03 16:49) [15]

Ru ©
почему тупо?Один словарь - один байт, который в идеале ты может заменить 256*256 байт пересылаемых данных...

Нужен математик для подсчета и статистические данные...нарно...хотя все вроде говорят что идея мертвая....жаль :( хнык...

← →
Danilka (2003-04-03 16:51) [16]

Ru © (03.04.03 16:45)
имеется ввиду, что словарь один, в архиваторе, и он не передается...

← →
vuk (2003-04-03 17:01) [17]

to Danilka:
>имеется ввиду, что словарь один, в архиваторе, и он не
>передается...
Как только встретилось, что-нибудь, чего в словаре нет - стреляемся. :o)

← →
Wild Wizard (2003-04-03 17:03) [18]

А с чего енто не встретиться то?

← →
vuk (2003-04-03 17:04) [19]

>А с чего енто не встретиться то?
И что делать будете?

← →
Wild Wizard (2003-04-03 17:06) [20]

Стоп.Во-первых словари на хосте 1 и 2 синхронезированны (неважно как этого добиться) тогда файл УСПЕШНО запакованный может быть распакован с другой стороны.

← →
DiamondShark (2003-04-03 17:09) [21]

Изобретаем LZW заново? Ню-ню...

← →
vuk (2003-04-03 17:15) [22]

to Wild Wizard:
>Во-первых словари на хосте 1 и 2 синхронезированны
Замечательно. Словари синхронизированы, но при упаковке встретился фрагмент, которого нет в словаре. Что будете делать? :o)

to DiamondShark:
Дык и я про то. :o)

← →
Ru (2003-04-03 17:20) [23]

>Wild Wizard © (03.04.03 16:49)
>почему тупо?

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

>Один словарь - один байт, который в идеале ты может заменить 256*256 байт пересылаемых данных...

2^8=256, 256^2=65536 как вы собираетесь их сравнять?????

← →
DiamondShark (2003-04-03 17:20) [24]

А вообще-то, человек молодец.
Если бы ему не мешать (типа, всё уже придумано до нас), в конце концов бы додумался.

← →
Wild Wizard (2003-04-03 17:23) [25]

>Один словарь - один байт, который в идеале ты может заменить 256*256 байт пересылаемых данных...

Это в смысле что один байт добавляет к <номер слова><позиция в слове><длинна> еще и <номер словоря>

теперь разберемся, что будет если не встретиться байт, оставим так...если встречаем байт (или последовательность которой нет в словаре, то запишем его в конец файла и укажем его смешение от начала....ну или как нибудь так)

← →
Ru (2003-04-03 17:34) [26]

>Wild Wizard © (03.04.03 17:23)
><номер слова><позиция в слове><длинна> еще и <номер словоря>

Сходи:
http://aforge.times.lv/alg/compression.html

Кстати есть интересная идея.... Найти похожие ветки