|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
11.01.2008, 00:27
|
#31
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Как я писал самопальный архиватор (тутор-рассказ)
2FrankH
чем-то похоже на преобразование Барроуза — Уилера
2Fla
интересная идея, но архиватор узконаправленный (ориентирован на кириллический текст), для файла же с равномерным распределением значений байтов - архивация ->0 (ну собсно, этим все архиватор страдают в той или иной степени)
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
11.01.2008, 15:03
|
#32
|
Модератор
Регистрация: 23.10.2005
Сообщений: 219
Написано 62 полезных сообщений (для 247 пользователей)
|
Ответ: Re: Как я писал самопальный архиватор (тутор-рассказ)
Сообщение от impersonalis
Не люблю это слово - но это невозможно.
Тому можно привести много подтверждений из различных дисциплин, все они, так или иначе поднимаются в курсе Теории Передачи Информации.
|
Можно проще объяснить: с помощью 16 бит можно задать 2^16 разных значений (например целое число 0...65535), с помощью 15 бит - 2^15 разных значений, т. е. в 2 раза меньше.
Значит хотя бы для двух исходных последовательностей получим одну и ту же на выходе. Но тогда как ее разархивировать? Ведь неизвестно, какой из 2 вариантов был заархивирован.
|
(Offline)
|
|
11.01.2008, 15:08
|
#33
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Ответ: Как я писал самопальный архиватор (тутор-рассказ)
легких путей не ищем, трудностей не боимся
я тоже как то писал самопальный архиватор для карт (2д). там идейка такая была, что карта очень большая, и очень часто встречаются одинаково закрашенные отрезки. наверное самое первое что приходит на ум при написании самопального архиватора
|
(Offline)
|
|
11.01.2008, 15:15
|
#34
|
|
Ответ: Как я писал самопальный архиватор (тутор-рассказ)
Matt Merkulov
если возьмем функцию хеширования F(data)
только с одним словием :
y = F(data)
при одном и том же y может быть несколько значений data
но все ети data имеют разную длину
или возможно есть несколько комбинаций data одинаковой длины
но ихнее количество сведено к минимуму
для передачи информации нам нужен y,размер и комбинация етой data
ну вот мой мозг не может пока опровергнуть существование такой функции
|
|
|
11.01.2008, 15:52
|
#35
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Сообщение от HolyDel
часто встречаются одинаково закрашенные отрезки. наверное самое первое что приходит на ум при написании самопального архиватора
|
RLE )
Сообщение от jimon
Matt Merkulov
если возьмем функцию хеширования F(data)
только с одним словием :
y = F(data)
при одном и том же y может быть несколько значений data
но все ети data имеют разную длину
или возможно есть несколько комбинаций data одинаковой длины
но ихнее количество сведено к минимуму
для передачи информации нам нужен y,размер и комбинация етой data
ну вот мой мозг не может пока опровергнуть существование такой функции
|
ты и описал принцип работы архиватора. Он реален.
Я лишь утверждаю - что не существует и не может существовать вообще алгоритма, кторый всегда сжимает W байт в Q байт (Q<W).
Для твоего случая: описатель комбинации data может быть эквивалентен по длине самой data, да в придачу к нему надо передать ещё и хеш.
Если уж мы начали строить всё более абстрактные модели:
вспомните золотое правило механики (именно равновесие, описанное этим правилом является ключевым для природы). Вечных двигателей не бывает - кпд не досигнет 100%
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
11.01.2008, 16:18
|
#36
|
Модератор
Регистрация: 23.10.2005
Сообщений: 219
Написано 62 полезных сообщений (для 247 пользователей)
|
Ответ: Как я писал самопальный архиватор (тутор-рассказ)
У меня была идея о том, что можно сделать архиватор, в котором будут собраны всевозможные алгоритмы сжатия, каждый из которых наиболее эффективен для опр. "структуры" данных. Он будет подбирать наиболее эффективный алгоритм, архивировать данные и ставить номер алгоритма в начале. Если не удалось найти алгоритм, то ставить 0 (т. е. данные без сжатия).
Т. о. в самом неудачном случае длина выходного потока данных будет на 1 байт больше.
|
(Offline)
|
|
11.01.2008, 19:08
|
#37
|
ПроЭктировщик
Регистрация: 18.12.2007
Сообщений: 157
Написано 24 полезных сообщений (для 27 пользователей)
|
Ответ: Как я писал самопальный архиватор (тутор-рассказ)
"тоесть чтобы всегда ,при любом раскладе из 16 бит получалось 15.
изобретал, изобретал так ничего путного и не смог сделать, но я всеравно верю что это можно сделать (если очень захотеть, можно в космос полететь)". Имхо можно примерно так сделать, и указывать при распаковке, какой тип файла в архиве. Например jpeg, mp3, wav... А архиватор подбирает несколько подходящих под сжатый файл последовательностей ищет сигнатуру заданного типа. Разумеется в архиве только один файл.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 09:04.
|