Перейти к содержимому
Doob

Задачка (алгоритм: ASCII-компрессор)

Рекомендуемые сообщения

Я использую пропущенный через минификатор - слов меньше, получается 3951 байт. Самый примитивный декомпрессор - 152 байта, но он не эффективен, т. к. работает в несколько проходов.   P.S. извиняюсь, невнимательно скопировал, декомпрессор занимает 305 байт.

Выполнил я кое-какие расчеты на основе LZ77. Есть мнение, что файл из примера (8615 байт) после сжатия не будет превышать 3300 байт  :smile9: вместе с распаковщиком.

crunch, к примеру, жмет этот файл лишь до 4581 байт.

 

Вопрос: Насколько востребован такой упаковщик? И стоит ли его доводить до работоспособного состояния?

 

Сейчас я могу примерно оценить итоговый объем сжатого файла.

Можно довести и до выдачи сжатого кода.

Далее есть несколько участков кода, явно требующих оптимизации, т. к. сейчас всё писалось исключительно для проверки идеи.

В OpenComputers не запускал, и как будет тормозить упаковщик, даже не представляю.

Распаковщик вряд ли будет тормозить, т. к. поток распаковывается в один проход, и его алгоритм немногим сложнее того, что встроен в crunch.

Юникод, само-собой, поддерживается.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

crunch - вообще крипота, я хотел его использовать, но он повреждает текст при распаковке (не знаю, исправили это или нет), да и алгоритм для текста там не самый лучший.

 

Алгоритм взял не с потолка, сжимал код автозаменой в n++, потом сделал макрос и увидел, что нужен анализ всего словаря, затем каждого слова в отдельности. А все потому-что могут попасться схожие слова, с разной эффективностью, например end - 350 слов (1400 символов), end[пробел] - 300 слов (1200 символов), LZ сначала возьмет то слово, которое больше и эффективность сжатия этого места получится на 14% ниже. Поэтому надо для каждого совпадения проводить сравнение в словаре, чтобы исключать пересекающиеся слова с меньшим коэффициентом сжатия.

Изменено пользователем Doob

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Отличие от алгоритмов типа LZ - использование эвристического анализатора текста (который я так и не взялся сделать), LZ просто ест все, что ему даешь, а этот алгоритм предназначен специально для сжатия текста, а урезание диапазона кодировки повышает эффективность. (хотя, я об этом уже сказал не один раз - меня никто не понял) crunch - вообще крипота, я хотел его использовать, но он повреждает текст при распаковке (не знаю, исправили это или нет), да и алгоритм для текста там не самый лучший.

 

Алгоритм взял не с потолка, сжимал код автозаменой в n++, потом сделал макрос и увидел, что нужен анализ всего словаря, затем каждого слова в отдельности. А все потому-что могут попасться схожие слова, с разной эффективностью, например end - 350 слов (1400 символов), end[пробел] - 300 слов (1200 символов), LZ сначала возьмет то слово, которое больше и эффективность сжатия этого места получится на 14% ниже. Поэтому надо для каждого совпадения проводить сравнение в словаре, чтобы исключать пересекающиеся слова с меньшим коэффициентом сжатия.

1) Разве всеядность LZ77 является недостатком? Вот, урезание диапазона входных данных это скорее минус, нежели плюс. Но если настаивать на нем как на «плюсе», то с его помощью слегка модифицированный LZ77 дополнительно отожмет еще две-три сотни символов. Но сейчас даже без этого сомнительного трюка LZ77 выглядит более эффективным.

 

2) Не знаю, портит ли crunch код, но его реализация LZ77 точно не самая эффективная. Особенно учитывая, что в самораспаковывающемся коде можно сколь угодно далеко уйти от стандартного алгоритма. Главное, код восстановить. Так вот, пример crunch демонстрирует, что потенциал LZ77 еще не исчерпан. По крайней мере, реально впихнуть 8615 байт уже минизированного Lua-кода в 3300 вместе с шустрым распаковщиком. Вот эти циферки в сравнении с твоими я и предлагаю обсудить.

 

3) Недословарь, ограниченный 127 словами, будет сильно тебя сдерживать. Отказавшись от фиксированных размеров как словарей, так и ссылок, мне удалось заметно увеличить степень сжатия. Разумеется, моя версия LZ77 тоже имеет ограничения – упаковщик слишком медлителен на больших файлах, но главной задачей я поставил подготовку кода для EEPROM, где хороши все средства ради входа в заветные 4096 байт.

 

4) Нет смысла говорить об эффективности LZ, не имея в виду конкретную его разновидность и реализацию. Одних только LZ77 я встретил три разных описания, и то, я был не сильно настойчивым в поиске. Предпочтет ли LZ более или менее эффективное слово, сильно зависит от примененных эвристик и зачастую даже не требует изменений в формате файла. Поэтому сейчас я бы предпочел рассуждать не об абстрактных преимуществах алгоритма, а его числовых характеристиках. Мне интересно, улучшилась ли твоя оценка сжатия для тех файлов, что я скинул, и насколько. На раскрытии деталей можешь пока не заморачиваться, достаточно указать выходной размер вместе с распаковщиком.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

crunch - вообще крипота, я хотел его использовать, но он повреждает текст при распаковке (не знаю, исправили это или нет), да и алгоритм для текста там не самый лучший.

Можешь скинуть пример повреждаемого файла? Хочу проверить, на каком этапе crunch повреждает файл.

 

Не смотря на значительное улучшение LZ77, без предварительного синтаксического сжатия lua-кода всё равно не обойтись, а у меня пока нет сил морочиться с ним. Надеюсь, crunch с этим хорошо справляется.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Это было очень давно, помню только, что при распаковке в конце текста был шум, в чем была проблема я не стал разбираться.

 

Все время руки не доходят до компрессоров, вроде-бы все проблемы обнаружил и исправил, но надо проверить работоспособность.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Написаны алгоритмы LZ78 и LZW на Lua, вот собственно что получилось (надеюсь вам это поможет). Исходный файл http://pastebin.com/cCrJVYt9 (в моем примере он называется tresh). LZ78 - http://pastebin.com/X6h2jCda . LZW - http://pastebin.com/E8Qt8HZ9 . Вот собственно результат на скриншоте.

http://clip2net.com/s/3IdK7SX

 

UPD

Из источников стало известно, что алгоритмы не доделаны, но работают.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Написаны алгоритмы LZ78 и LZW на Lua, вот собственно что получилось (надеюсь вам это поможет). Исходный файл http://pastebin.com/cCrJVYt9 (в моем примере он называется tresh). LZ78 - http://pastebin.com/X6h2jCda . LZW - http://pastebin.com/E8Qt8HZ9 . Вот собственно результат на скриншоте.

http://clip2net.com/s/3IdK7SX

Может, и пригодится кому-то. Но для EEPROM не годится.

8615->4967 LZ78 жмёт хуже версии LZ77 в crunch.

8615->3881 LZW жмёт чуть лучше, но всё равно хуже моей версии LZ77.

Это при том, что часть EEPROM потратится на SFX-модуль.

8615->4581 crunch вместе с SFX

8615->3300 можно сжать вместе с SFX по моим расчетам (не точно, но очень близко к реальности)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Eu_tomat, мне тут подсказал 1 идейку товарищ: поставь в комп дата-карту и использую вот такую библиотеку http://pastebin.com/r7fvtPTA . Может быть это поможет. =)

 

UPD

Вот собственно результаты тестирования этой либы http://c2n.me/3IMOFRd.
Исходный файл тот же. Собственно результат на скрине. А применяется эта библиотека следующим образом:
WinRar.compress(filename,newfilename,limit) - Компрессит файл, нарезая его на фрагменты длины равной лимиту и сжимает его.
WinRar.decompress(filename, newfilename) - Декомпрессит файл.

Изменено пользователем MeXaN1cK

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Eu_tomat, мне тут подсказал 1 идейку товарищ: поставь в комп дата-карту и использую вот такую библиотеку http://pastebin.com/r7fvtPTA . Может быть это поможет. =)

 

Обязательно рассмотрю этот вариант через неделю-две, как доберусь до полноценного компа.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В 26.01.2017 в 10:03, eu_tomat сказал:

По крайней мере, реально впихнуть 8615 байт уже минизированного Lua-кода в 3300 вместе с шустрым распаковщиком.

Есть пара вопросов - какой алгоритм используется? lz77? И все же, теме хоть и 4 года - но компрессор был доделан и остался ли его код? Или заброшен в долгий ящик?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
9 часов назад, BrightYC сказал:

Есть пара вопросов - какой алгоритм используется? lz77? И все же, теме хоть и 4 года - но компрессор был доделан и остался ли его код? Или заброшен в долгий ящик?

Да, проект был приостановлен, но код я могу поискать. Пользуясь этим напоминанием, проверю на днях, не сдох ли тот комп.

 

За основу был взят алгоритм LZ77, к нему я добавил несколько "своих" улучшений. Слово "своих" я беру в кавычки, потому что имею базовое представление об алгоритмах сжатия, но не помню никакой конкретики, и тем более, названий. Поэтому могу легко впасть в иллюзию, будто бы смог придумать свой алгоритм.

 

Улучшения "придумывались" разные, но я оставлял из них только те, для которых мог представить компактный алгоритм распаковки на lua. По сути, это было главным требованием, учитывая размер EEPROM.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...