КОМПЬЮТЕРНАЯ ПРОГРАММА ДЛЯ СЖАТИЯ ФАЙЛОВ НЕЗАВИСИМО ОТ ИХ ТИПА 0. Вступительные замечания      Эта идея реализована мною лет 20 тому назад, когда я работал ещё на 286 компьютере, в ДОС-е, и используя транслятор Паскаля с 1986 года, если не ошибаюсь. И программа работала, и ещё работает у меня, но раз все стали использовать какой-то Winzip то и я в конце концов перешёл к ней. Но я написал её, с одной стороны чтобы использовать лучше дискеты, мои файлы не помещались и нужно было их разбивать на части, а с другой стороны чтобы испробовать своё хеширование, потому что в этом трансляторе нельзя было уделять больше чем 48 КВ на все переменные, а мне был нужен один массив в худшем случае из 64 КВ, лучше вдвое больше, и ещё кажется столько для других массивов. То есть это было для меня вызовом, но не только это. Я решил использовать одну, прямо таки антинаучную идею, делать сжатие не анализируя тип файла (их ведь много, и всё время появляются новые, я не собирался их изучать, да и конкурировать фирменные продукты), а сжимая файл да того размера который ... сам Бог (или естество файла) позволяет при кодировании знаков!      Я разъясню это дальше, но пока хочу добавить, что не смотря на все возможные трудности с хешированием (я думаю что дефинировал этот основной массив порядка нескольких КВ, т.е. хотя бы раз в десять меньше действительно нужного) программа работала довольно-таки хорошо, для текстовых файлов давала около 45% (а Winzip давал где-то 55%) сжатия, а для некоторых других где изображения даже до 15% основного файла. Что не хорошо, однако, это то что она работает ужасающе медленно, потому что делает несколько итерации, считает всё байт за байтом, сравнивает их, формирует массивы, потом обрабатывает эти массивы с информацией о целом файле, и если файл порядка 100 - 200 КВ (как было в начале в ДОС-е) то всё шло в считанные секунды, но если файл, скажем, 2 МВ, то тогда уходил иногда и битый ... час (зависимость от размера файла наверное экспоненциальная, ни в коем случае не линейная). Так что я, кажется, информировал, то ли офис IBM-а, то ли ещё какой-то фирмы, но решил, что хватит -- программа моя, она работает, но я не собираюсь распространять её дальше, ибо теперь все файлы растут очень сильно, и если это видео информация, то кто знает сколько времени программа будет работать.      Это всё так, однако ... Видите ли, у меня часто имеется "однако", особенно при нетрадиционных подходах. Так здесь дело в том, что если не хеширование, если я мог бы уделить целый МВ на переменные, а то и больше, сделать виртуальные массивы для файлов (скажем по пару МВ), и читать блочно в них, то это могло бы спокойно снизить время на целый порядок, если и не больше. Но дело этим не кончается, потому что выходной файл у меня получался как бы ... после мясорубки, я менял сами байты, формировал свои новые "байты" (или слова, правильнее говоря), и это могло бы дать очень хорошее шифрование! А ведь люди всё ещё ищут всякие возможности для лучшего шифрования, оказывается это так для обеспечения секюрити банковских операций, где применялись сверх-большие простые числа (скажем, из несколько сот а то и тысяч цифр, где нахождение их простых множителей довольно трудоёмкая (time consuming) операция, но проверка почти что тривиальная (путём умножения, хотя и не обычного, а целочисленного с неограниченным числом чисел).      Так что, видите ли, я думаю что в моей "сумасшедшей" идеи всё ещё есть "хлеб" (как говорят болгары) и лучше изложить её в общих чертах, свести её до знания всех кто интересуется, чем уносить её с собой в могилу. Да только я специально не буду смотреть на точную реализацию, а рассказывать по памяти. Это и сохранить некоторые ноухау за мной, но если программу нужно будет делать в новой программной среде, то её, всё равно, придётся переписывать (т.е. писать) заново. А и такой метод изложения сухих профессиональных вещей сделает их общедоступными, как и полагается на литературном сайте. Ну, этого достаточно в качестве вступления. 1. Моя идея сжатия файла до допустимого самим его характером      Всё началось с того, что я заметил, что в одном файле используются далеко не все возможные символы. Скажем, если это текстовой файл на латинице, то обычно остаются около 50 возможных знаков, и даже если на кириллице (в ДОС-е, разумеется, где таблица из 256 знаков, а и в первых Windows-ах) тоже остаются 10-20 знаков; только .exe файлы используют почти на 100 процентов все возможные знаки. Эти знаки можно использовать. Как? Ну, кодированием последовательностей знаков, и то наиболее часто используемых таких! Это всегда составляет мой нулевой пасс (проход). Но это, очевидно, капля в море, это так, чтобы не оставлять ничего неиспользованного. Дальше я просто расширяю размер байтов и делаю свои "байты", из 10 битов, или из 12 (или больше, но эксперименты показали, что 16 битовые "байты" имеют слишком большие размеры, чтобы можно было сэкономить что-то их использованием). Если новые байты у меня из 10 битов, то если первые два бита "00", то это старые знаки, и остаются ещё три варианта, т.е. три знаковых таблиц для кодирования! Это уже кое-что. Теперь остаётся только для каждого конкретного файла находить что ещё добавлять, какие новые символы формировать, и добавлять по одной такой таблице при каждом проходе, анализируя последовательности из старых и новых символов. Но уже видите, что байты смещаются, и не известно что каждый действительный байт означает, так что повторение каких-то байтов не означает действительное повторение символов, здесь вещи перемешаны.      Так, а что добавлять? Ну, то что нужно для каждого файла, то что встречается чаще всего в нём, грубо говоря. По идее я хотел проводить анализ всех возможных последовательностей символов, хотя бы в разумных границах, т.е. сначала из двухбайтовых последовательностей (что не означает разделить файл на пары байтов, а на всех возможных таких последовательностей, т.е. n и n+1, n+1 и n+2, и так далее если нужно), потом из трёх байтов, потом из четырёх, а может быть и из пяти. Потом как-то взвешивать количество встречаний в зависимости от длины, и выбирать наиболее встречаемые последовательности, которые и закодировать добавляя новые символы для них, но один такой символ уже будет означать два (или больше) исходных символов. Понимаете в чём может быть экономия, и почему она зависит от самого файла, не только от его типа, а от конкретного файла? И действительно, при хешировании я вставлял промежуточные печати максимального повторения и сначала они были, кажется, несколько тысяч (если не заблуждаюсь, потому что это будет при условии, что я использую двухбайтовые целые числа как счётчики, а то может использовал однобайтовые), и под конец новой знаковой таблицы они раз в десять меньше.      Скоро, однако, я решил, что это излишне сложно, и так я увеличу время на пару порядков (!), так что оставил только двухбайтовые последовательности, но зато наличие нескольких проходов обязательно, так что при трёх проходов, если в файле часто встречаются, скажем, последовательности шпаций, то в конечном итоге я буду заменять 2^3 = 8 таких шпаций одним новым символом. Кроме того, с каким-то приближением, замена двух непосредственно последовательных символов несколько раз должна быть эквивалентной замене группы из нескольких (4-5) символов. Поэтому число проходов нужно, не годится если я в одном пассе добавил все возможные символы.      Так, а как, всё таки, анализировать последовательности? Обычным подсчётом числа встречаний, разумеется, так что по идее, если хотим обойтись без хеширования вообще, нужно поддерживать массив размерности 2*newbytelength, что в наиболее использованном мною варианте (потому что эксперименты показали, что так лучше) из 10 битов, дало бы размерность в 20 битов, т.е. 1 МВ да и по 2 байта для integer-ов, это 2 МВ. Размерность новых "байтов" должна быть использована и для старых байтов, чтобы можно было при втором проходе использовать, наравне со старыми байтами, и новые, удлинённые "байты", представляющие двухбайтовые последовательности. В этом случае выходит что моё хеширование, в действительности (я ведь сказал, что специально не хочу смотреть как было в самом деле), использовало меньше одного процента реальных массивов, и поэтому у меня и время такое ошеломляющее, да и экономия не такая уж большая (т.е. если начало файла не является достаточно представительным для всего файла то хеш-таблица очень скоро заполняется и дальше даже если появляются более часто встречаемые комбинации они просто пропускаться, нет места для размещения их счётчиков).      Потом, даже если и можно задать массивы размерностью пары МВ, это вряд ли стоит делать, ибо эти массивы должны быть всё время в ОП, иначе ничего не сэкономим в смысле времени, да нужны и виртуальные массивы для самых файлов (порции их, какие-то буферы), потому что они просматриваются досконально, байт за байтом, да и то в новых границах и размеров байтов Так что какое-то хеширование может всегда быть нужным, но так, где-то одна четверть возможных комбинации, а не до смешного малые порции. 2. Формирование новых файлов      Когда накоплена статистика для количества встречаний всех последовательностей из двух новых байтов, то тогда этот массив упорядочивается и выделяются первые 256 пар из него, в порядке уменьшения использования. Если не ошибаюсь, я не упорядочиваю весь массив, а ищу 256 раз ту пару, которая встречается больше всех других (поиск максимального значения поля счётчика) и записываю её во временную табличку новых символов. Когда известно что на что нужно менять я ещё раз прохожу по всему файлу, и читая все "байты" я заменяю их новыми или нет, и переписываю в новый вариант файла, только что впереди всего этого я кладу саму таблицу новых символов, и пару других показателей, как номер цикла. Я ухитряюсь использовать только два файла, чередуя их, и читаю из одного и записываю в другой, а потом, при следующем проходе, наоборот. Ну, и нужно обратить особое внимание на дополнение нового файла до целого числа байтов (обычными нулями), чтобы не произошла ошибка при чтении новых небайтовых "байтов". Хранятся, разумеется и таблицы для всех i-1 итераций (то ли после текущей, то ли в конце файла), но любая итерация работает с "байтами" новой длины. Возможность кончать хоть одной итерацией раньше нет смысла предусматривать, так как место для новой таблице предусмотрено. Таким образом после выполнения данной итерации, файлы меняются местами, нулируются массивы, читается заново только что записанный файл, отделяется его таблица в начале, переписывается в нужное время в новый файл, а та основная часть файла без таблиц заново анализируется на частоту встречания двух последовательных новых "байтов", так же как и в предыдущей итерации, потом снова формируется новая таблица, перекодируется файл, и записывается.      Именно информация в начале каждой итерации файла, содержащая последнюю таблицу из 256 новых знаков, используется при расшифровывании (декодировании) файла, декодирующей программой, которая работает значительно быстрее, ибо она только читает порцию из битов, и, или заменяет их новой последовательностью, или оставляет их такими же. Так что время работы и не такой уж существенный фактор, так как при расшифровывании (или растягивании) файла работа проходит довольно быстро. Но так как здесь добавляются всегда 256 новых знаков, и так как номер итерации определяет их первых битов, то записываются только пары старых символов (из предыдущей итерации), а не каким новым символом точно заменять (это лишнее).      Если, однако, эти таблицы записывать на отдельный файл, то их можно использовать для шифровании файла, на что остановимся в следующем пункте. 3. Вариант шифрованного сжатия      Так как без таблиц новых символов и сам чёрт, как говорится, не сможет ничего понять в файле, то ясно, что если их высылать отдельно можно сохранить секретность сжатого файла. Однако я имею в виду не такую секретность, где одна программа (дешифрирующая) может, всё таки, расшифровать разные файлы (имея файлы с ихними новыми таблицами), а новые персональные шифры для каждого потребителя! Это элементарно сделать если перед записи таблицы проводить простую замену (swapping) нескольких пар байтов. Так как байтов 256 или 2 шестнадцатеричных цифры то запись, скажем 6FA7 будет означать что 111-й элемент таблицы (пара символов, из нужного числа битов, для данной итерации) нужно заменить (или заменён) на 167 её элемент. Это действительный шифр, так что дешифрирующую программу можно сделать универсальной и таблиц символов ни к чему записывать на отдельные файлы, но эти замены, для каждой итерации нужно посылать секретно, не по имейле, а в отдельном конверте, что-то такое. Тогда декодирующая и декомпрессирующая программа должна просто спрашивать низы шестнадцатеричных чисел, примерно по четыре пары на итерацию или 12 таких четвёрок цифр как чуть выше, и когда человек введёт их (или скопирует из какого-то файла на его компьютере), то тогда всё будет в порядке, а если не введёт, то будет считаться что нет никаких замен и тогда получится битовый фарш, как сказал в начале.      Возможностей для замен, по идее, и для 10-битовых "байтов" и трёх итераций, даже не 3*256 а на много больше, так можно выполнять несколько замен с участием одного из байтов, что будет результировать в циклические замены. Генерирование шифров случайным образом (скажем, сделав программу, которая запускается и всё время генерирует случайные шестнадцатеричные числа, пока кто-то не нажмёт нужную кнопку) даст возможность обеспечить абсолютную уникальность этих шифров. Единственный минус такого метода будет то, что и запомнить эти последовательности довольно-таки трудно и нужно смотреть куда-то, что значит что шифр может быть обнаружен. Но ведь это всегда так с шифрами, не так ли? Я не занимался такими вещами, да думаю что так. Другой вариант это работа с текущим кодом из какой-то книги, если установить некоторый метод конвертирования букв (из любого алфавита) в шестнадцатеричные числа, что не так уж и сложно (скажем, остатки деления по модулю 16, самое простое -- то что будут некоторые повторения, как сказал, не имеет значения). И если это видео файлы, то тогда компрессия может получиться на десятичный порядок, и больше, и время декодирования, при современных компьютерах, будет не существенным.      Однако -- это моё любимое слово, хотя бы в этом материале -- если уже знаковые таблицы стали двухбайтовыми (я не но сто процентов уверен в этом, но "нутром чувствую" что это так), а и для видео информации тоже давно используются слова длиннее байта, то тогда возможен и другой альтернативный метод работы, на чём остановимся в следующем пункте. 4. Кодирование в новых знаковых таблицах      Сначала я хочу отметить здесь то, что если таблицы уже двухбайтовые, то тогда даже и при классическом варианте стоит ещё на нулевом пассе провести свопинг байтов через двухбайтовое слово, т.е. так, чтобы байты чередовались: I II, II I, I II, II I, ... . Таким образом, как я подозреваю, массивное сжатие получится в I-х байтов, а сами таблицы будут во II-х байтах. Это может привести к чувствительно большей компрессии файлов, а если они не двухбайтовые (что иногда может случиться, я ведь говорю о всяких возможных типов файлов), то это не помешает, просто сравнивание будет проводиться через байт. Я лично давно думаю испробовать это в моей программе, но всё руки не доходят -- с тех пор как стал публиковаться по Интеренете, да и переводиться, нет времени на программистскую работу (тем более с трансляторами с 86 года прошлого века).      Однако в этом пункте я имею в виду, то, что раз таблицы такие расширенные, то тогда нет никакой надобности в расширении слов (хотя бы для текстовых файлов, но подозреваю и что для видео, ибо при кодировании цвета в 24 битах выходит, что слова даже и трёхбайтовые), тогда они просто очень слабо использованы и может случиться что останется место для тысячи и больше новых символов! Как это установить? Ну, нужно просто работать двухбайтовыми словами, и весь анализ проводить на уровне двух байтов, что повлечёт за собой необходимость в обязательном хешировании, и работе со словами в два раза длиннее. Это сразу повысить размерность задачи, но, как сказал, это может быть и не будет нужно, если использовать простой трюк с разменой байтов через слово. Тут нужно поэкспериментировать.      И всё зависит от величины файла. Если они по МВ-у и больше, и видео файлы, то хотя соседние пункты и будут очень похожие, всё же, при большом файле будут использованы все возможные цвета. Но может быть для аудио файлов будет вовсе не так много вариантов? Главное по моему это выбрать один универсальный метод чтобы его можно было применят во всех случаях с довольно хорошим результатом, не искать перфекции; тогда и шифрование будет иметь смысл. В конце концов можно поставить некоторый лимит (например из 1-го, или из 10-ти МВ) и каждый файл обрабатывать на таких порциях, и кодировать отдельно, хотя и сохранять в одном файле.      Ну, варианты имеются, и программу можно модифицировать, но главное что я подаю вполне работающую, и то неплохо, идею, имеется прецедент. Только что я лично не собираюсь переустанавливать мою писательскую и переводческую деятельность, так что тратить много времени на программистские эксперименты не собираюсь. Если какой-то фирме взбредёт в голову, что я буду им нужен, то пусть переведут мне сначала 2,000 евро, только для реализованной идеи, а там дальше подумаем.      12.2014