eu_tomat 2 148 Опубликовано: 26 января, 2017 Я использую пропущенный через минификатор - слов меньше, получается 3951 байт. Самый примитивный декомпрессор - 152 байта, но он не эффективен, т. к. работает в несколько проходов. P.S. извиняюсь, невнимательно скопировал, декомпрессор занимает 305 байт.Выполнил я кое-какие расчеты на основе LZ77. Есть мнение, что файл из примера (8615 байт) после сжатия не будет превышать 3300 байт вместе с распаковщиком. crunch, к примеру, жмет этот файл лишь до 4581 байт. Вопрос: Насколько востребован такой упаковщик? И стоит ли его доводить до работоспособного состояния? Сейчас я могу примерно оценить итоговый объем сжатого файла. Можно довести и до выдачи сжатого кода. Далее есть несколько участков кода, явно требующих оптимизации, т. к. сейчас всё писалось исключительно для проверки идеи. В OpenComputers не запускал, и как будет тормозить упаковщик, даже не представляю. Распаковщик вряд ли будет тормозить, т. к. поток распаковывается в один проход, и его алгоритм немногим сложнее того, что встроен в crunch. Юникод, само-собой, поддерживается. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob Автор темы 2 748 Опубликовано: 26 января, 2017 (изменено) Отличие от алгоритмов типа LZ - использование эвристического анализатора текста (который я так и не взялся сделать), LZ просто ест все, что ему даешь, а этот алгоритм предназначен специально для сжатия текста, а урезание диапазона кодировки повышает эффективность. (хотя, я об этом уже сказал не один раз - меня никто не понял) crunch - вообще крипота, я хотел его использовать, но он повреждает текст при распаковке (не знаю, исправили это или нет), да и алгоритм для текста там не самый лучший. Алгоритм взял не с потолка, сжимал код автозаменой в n++, потом сделал макрос и увидел, что нужен анализ всего словаря, затем каждого слова в отдельности. А все потому-что могут попасться схожие слова, с разной эффективностью, например end - 350 слов (1400 символов), end[пробел] - 300 слов (1200 символов), LZ сначала возьмет то слово, которое больше и эффективность сжатия этого места получится на 14% ниже. Поэтому надо для каждого совпадения проводить сравнение в словаре, чтобы исключать пересекающиеся слова с меньшим коэффициентом сжатия. Изменено 26 января, 2017 пользователем Doob Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 26 января, 2017 Отличие от алгоритмов типа 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 более или менее эффективное слово, сильно зависит от примененных эвристик и зачастую даже не требует изменений в формате файла. Поэтому сейчас я бы предпочел рассуждать не об абстрактных преимуществах алгоритма, а его числовых характеристиках. Мне интересно, улучшилась ли твоя оценка сжатия для тех файлов, что я скинул, и насколько. На раскрытии деталей можешь пока не заморачиваться, достаточно указать выходной размер вместе с распаковщиком. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 7 марта, 2017 crunch - вообще крипота, я хотел его использовать, но он повреждает текст при распаковке (не знаю, исправили это или нет), да и алгоритм для текста там не самый лучший. Можешь скинуть пример повреждаемого файла? Хочу проверить, на каком этапе crunch повреждает файл. Не смотря на значительное улучшение LZ77, без предварительного синтаксического сжатия lua-кода всё равно не обойтись, а у меня пока нет сил морочиться с ним. Надеюсь, crunch с этим хорошо справляется. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob Автор темы 2 748 Опубликовано: 7 марта, 2017 Это было очень давно, помню только, что при распаковке в конце текста был шум, в чем была проблема я не стал разбираться. Все время руки не доходят до компрессоров, вроде-бы все проблемы обнаружил и исправил, но надо проверить работоспособность. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
MeXaN1cK 53 Опубликовано: 7 марта, 2017 Написаны алгоритмы LZ78 и LZW на Lua, вот собственно что получилось (надеюсь вам это поможет). Исходный файл http://pastebin.com/cCrJVYt9 (в моем примере он называется tresh). LZ78 - http://pastebin.com/X6h2jCda . LZW - http://pastebin.com/E8Qt8HZ9 . Вот собственно результат на скриншоте. http://clip2net.com/s/3IdK7SX UPD Из источников стало известно, что алгоритмы не доделаны, но работают. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 7 марта, 2017 Написаны алгоритмы 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 по моим расчетам (не точно, но очень близко к реальности) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
MeXaN1cK 53 Опубликовано: 23 марта, 2017 (изменено) Eu_tomat, мне тут подсказал 1 идейку товарищ: поставь в комп дата-карту и использую вот такую библиотеку http://pastebin.com/r7fvtPTA . Может быть это поможет. =) UPD Вот собственно результаты тестирования этой либы http://c2n.me/3IMOFRd.Исходный файл тот же. Собственно результат на скрине. А применяется эта библиотека следующим образом:WinRar.compress(filename,newfilename,limit) - Компрессит файл, нарезая его на фрагменты длины равной лимиту и сжимает его.WinRar.decompress(filename, newfilename) - Декомпрессит файл. Изменено 23 марта, 2017 пользователем MeXaN1cK Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 24 марта, 2017 Eu_tomat, мне тут подсказал 1 идейку товарищ: поставь в комп дата-карту и использую вот такую библиотеку http://pastebin.com/r7fvtPTA . Может быть это поможет. =) Обязательно рассмотрю этот вариант через неделю-две, как доберусь до полноценного компа. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Chebuya 415 Опубликовано: 22 марта, 2020 В 26.01.2017 в 10:03, eu_tomat сказал: По крайней мере, реально впихнуть 8615 байт уже минизированного Lua-кода в 3300 вместе с шустрым распаковщиком. Есть пара вопросов - какой алгоритм используется? lz77? И все же, теме хоть и 4 года - но компрессор был доделан и остался ли его код? Или заброшен в долгий ящик? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 23 марта, 2020 9 часов назад, BrightYC сказал: Есть пара вопросов - какой алгоритм используется? lz77? И все же, теме хоть и 4 года - но компрессор был доделан и остался ли его код? Или заброшен в долгий ящик? Да, проект был приостановлен, но код я могу поискать. Пользуясь этим напоминанием, проверю на днях, не сдох ли тот комп. За основу был взят алгоритм LZ77, к нему я добавил несколько "своих" улучшений. Слово "своих" я беру в кавычки, потому что имею базовое представление об алгоритмах сжатия, но не помню никакой конкретики, и тем более, названий. Поэтому могу легко впасть в иллюзию, будто бы смог придумать свой алгоритм. Улучшения "придумывались" разные, но я оставлял из них только те, для которых мог представить компактный алгоритм распаковки на lua. По сути, это было главным требованием, учитывая размер EEPROM. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах