FileCompressor Technical Preview build 13041 (ProgramId 0)

@Etyuhibosecyu · Регистрация: 13.07.2017

Студворк — интернет-сервис помощи студентам

Что-то меня утянуло в сторону от языка программирования... И я написал новую программу - компрессор файлов.
Как доказывается теоремами, абсолютно оптимальное количество бит, необходимое для представления какого-либо файла, начиная с некоторого числа является невычислимым, и это число также является невычислимым. Поэтому споры о том, какой метод сжатия лучше, наверное, не прекратятся никогда... И я подумал, что мне тоже не помешает внести свой вклад в них. Вот так и появился FileCompressor - программа, сочетающая проверенные временем методы - метод Хаффмана, метод Лемпеля-Зива, RLE (в разработке E-RLE), возможно, BWT (в разработке, но здесь мне не нравится длительная распаковка), однобитная гарантия - с авторскими - PseudoByte™ и FlexRegimes™ (в разработке). Абсолютный минимум размера файла составляет 8-9 байт, абсолютный максимум раздувания - 2 байта (байт для однобитных гарантий для четырех методов сжатия - не разрывать же байт! - и байт для версии - вдруг в этой версии компрессор раздувает, а в будущей будет сжимать?).

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

Преимущества в отношении степени сжатия:
- Авторская технология PseudoByte™, позволяющая добиться экономии, выраженной в долях бита (это может показаться абсурдным, но в контексте этой технологии это реально) - псевдобайт может иметь не 256 состояний (как байт), и даже не 2 (как бит), а абсолютно любое число, например, 147 или 25675, причем все псевдобайты в одном файле могут иметь разное число состояний.
Важно: "экономия, выраженная в долях бита" абсолютно не обозначает маленькую экономию, а означает только, что эта экономия выражается нецелым (и даже иррациональным) числом бит - например, 71.969173.
- Благодаря отсутствию архивации (только сжатие) экономится еще некоторое количество байт (невычислимое).
- Максимальные значения каких-либо величин в пределах файла (например, длины серии в методе RLE) хранятся отдельно, и все величины этого вида закодированы по "основанию" этого максимума (если нет порога - читайте ниже), что позволяет убить двух зайцев - не ограничиваться числом 255, если значение больше, и экономить 1-3 бита на каждом значении, если они маленькие.
- Также присутствует пороговое значение, отображающее, используются ли чаще значения, близкие к минимуму (к нулю) или к максимуму, и большинство значений закодированы по "основанию" порога, а меньшинство - по произведению: порог * (максимум - порог), что позволяет не использовать максимальный размер псевдобайта там, где можно обойтись меньшим (средняя экономия 2.573 бит на блок).
- При кодировании методом Лемпеля-Зива не выделяется память для дистанции меньше длины (средняя экономия 1 бит на блок) и для длины меньше 2 (средняя экономия 29 миллибит на блок).
- При RLE-кодировании не кодируются символы, которые Хаффман определил как очень редкие (вероятность, что они образуют серию, ничтожна, и средняя экономия 3.322 бит на каждый очень редкий символ или 100 миллибит на каждый символ).
- При кодировании Хаффмана (которое как раз и формирует псевдобайты) первый псевдобайт каждого блока имеет одно "лишнее" состояние, которое затем использует Лемпель-Зив, благодаря чему исключена иллюзия блока Лемпеля-Зива (встреча в тексте символа, совпадающего с управляющим для блока Лемпеля-Зива, но таким не являющегося) (при условии, что средний текст содержит 100 уникальных символов, и вероятность встретить конфликтный около 1/1000, а чтобы его раскрыть, требуется 2 символа, к чему можно добавить еще 1/50000 вероятности встретить иллюзию комбинации, которая "разоблачает" иллюзию, со средней длиной "разоблачения" около 5 символов, средняя экономия в моем методе 14 миллибит на каждый символ).

Что НЕ СЛЕДУЕТ делать с FileCompressor (это НЕ мои недоработки, а объективные невозможности любого подобного компрессора):
- Пытаться сжать уже сжатые файлы (например, PNG) - ничего не выйдет. Для сжатия необходимо предварительно разжать всеми другими методами, примененными к файлу.
- Сравнивать со сжатием с потерями - FileCompressor сжимает без потерь и точка.
- Сравнивать со специальными методами - универсальные средства всегда хуже специальных, вне зависимости от уровня разработчика.
- Сравнивать с методами, которые совершенствовались десятки лет, да еще и являются известными брендами (например, RAR) - FileCompressor разрабатывался лично мной и возможностей крупных корпораций у меня нет.
- Пытаться сжать белый шум или строку, сгенерированную из случайных символов - они являются несжимаемыми (во всяком случае, в настоящее время).

Недостатки в отношении степени сжатия:
- Если 60% файла являются "нормальными", а 40% - несжимаемыми, то файл либо сожмется на несколько процентов, либо сжатие будет заблокировано однобитной гарантией, и файл не сожмется совсем. Это могут устранить Flex-режимы, но эта авторская технология в разработке.
- При кодировании Лемпеля-Зива, если между исходным блоком и повтором есть другие блоки Лемпеля-Зива, они включаются в дистанцию полностью, а не как один символ, что уменьшает степень сжатия (средняя неиспользованная экономия 136 миллибит на блок). Исправление этого, опять же, находится в разработке.
- Если кодирование Хаффмана дало результат, а Лемпель-Зив "промолчал", лишнее состояние из первых псевдобайт в блоках Хаффмана не удаляется (исправление, опять же, в разработке) (средняя неиспользованная экономия 70 миллибит на блок Хаффмана, то есть на символ).
- Сильно ударяет по Хаффману таблица кодирования, где нужно передать незакодированными все встречающиеся в тексте символы. Возможно, стоит оптимизировать эту таблицу способом передачи только разности ANSI-кодов предыдущего и следующего символов или перечисления кодов Хаффмана всех подряд символов с указанием, какие символы не кодируются (не смог вычислить неиспользуемую экономию).
- Дистанция и длина по Лемпелю-Зиву ограничены 1000 символами, так как время сжатия этим методом в среднем случае пропорционально квадрату, в худшем - кубу этих величин.

Проблемы, не имеющие непосредственного отношения к степени сжатия:
- Чрезвычайно высокое время сжатия - по разным моим расчетам, при тактовой частоте процессора 2.7 ГГц (как у меня) файл размером 3 килобайта будет сжиматься от 30 секунд до минуты, 3 мегабайта - от 12 часов до суток, 3 гигабайта - несколько лет, при этом успех сжатия не гарантирован. Самый длительный процесс - преобразование псевдобайт в строку. Кто знает, как это исправить - пишите.
- Даже если вы нажали Esc, вам вероятно, все же придется ждать долго, если файл достаточно большой, ну или убить процесс.
- Если сжатый файл содержит больше 5000 псевдобайт, при его распаковке FileCompressor, скорее всего, вылетит. Исправление в разработке.
- Интересно, а какие недостатки или проблемы обнаружите вы?

@MrOnlineCoder · 08.12.2018, 16:25

Etyuhibosecyu, скачал, протестировал.
1.VirusTotal (0/69)
2. Программа работает.
3.

Сообщение от Etyuhibosecyu

Чрезвычайно высокое время сжатия

Подтверждаю.
4. Какова конечная цель этого проекта?
5. В чем смысл сжимать файлы по одному? Это же ой как не удобно и имеет очень узкое приминение.
6. Программа не использует несколько ядер, т.е. работает в 1 потоке.
7. Зачем целых 3 полоски? Либо 1, и тогда понятно зачем она, либо 3 с подписями, какая какой процесс показывает.
8. Желательно было бы выложить исходный код, который как я понял написан на C# и С++.
9. Прикрепляю архив с 7 тестами по сжиманию текстовых файлов FileCompressorом и обычным zip через WinRAR. (файлы есть и с случайным набором символов, не смотря на примечание в первом посту)

developer123 · 08.12.2018, 16:34

А как же собственный язык? Ведь столько было энтузиазма? Прошло 2 недели и УСЁ?

Что касается темы. Честно пытался прочитать и понять. Но после всяких миллибитов терпения не хватило. (обычно алгоритмы компрессии описывают математическими формулами, но я так понимаю не этот случай)

Чем ваш компрессор лучше например бесплатного 7z? Вы тесты делали?

А вообще есть 2 типа сжатия, с полным восстановлением и неполным. К неполным относятся всякие jpg, mpeg, mp3 и т.п. Я надеюсь вы понимаете что там сжатие идёт основываясь на совершенно других принципах.

P.S. TM - это торговая марка. Вы уже свою зарегистрировали? Не боитесь что кто то вперёд зарегистрирует и заберёт все миллионы себе?

@Etyuhibosecyu · 08.12.2018, 16:49 **[ТС]**