Каков наилучший алгоритм сжатия, допускающий произвольное чтение / запись в файл?

Я ошеломлен количеством ответов, которые подразумевают, что это невозможно.

Разве эти люди никогда не слышали о «сжатых файловых системах», которые существовали еще до того, как в 1993 году Stac Electronics подала на Microsoft судебный иск из-за технологии сжатых файловых систем?

Я слышал, что LZS и LZJB - популярные алгоритмы для людей, реализующих сжатые файловые системы, которые обязательно требуют как чтения с произвольным доступом, так и записи с произвольным доступом.

Возможно, самое простое и лучшее, что можно сделать, - это включить сжатие файловой системы для этого файла и позволить ОС разбираться с деталями. Но если вы настаиваете на том, чтобы обрабатывать его вручную, возможно, вы сможете почерпнуть несколько советов, прочитав о Прозрачное сжатие файлов NTFS.

Также посетите: «StackOverflow: форматы сжатия с хорошей поддержкой. для произвольного доступа к архивам? "

Формат razip поддерживает чтение с произвольным доступом с лучшей производительностью, чем gzip / bzip2, которые необходимо настроить для этой поддержки:

http://sourceforge.net/projects/razip/

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

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

Я думаю, что Стивен Денн мог кое-что выяснить. Представить:

• zip-подобное сжатие последовательностей в коды
• код отображения словаря -> последовательность
• file will be like a filesystem
  • each write generates a new "file" (a sequence of bytes, compressed according to dictionary)
  • "файловая система" отслеживает, какой "файл" каким байтам принадлежит (начало, конец)
  • каждый "файл" сжимается по словарю
  • читает работу пофайлово, распаковывая и извлекая байты в соответствии с "файловой системой"
  • записывает, делает "файлы" недействительными, новые "файлы" добавляются взамен недействительных
• this system will need:
  • defragmentation mechanism of filesystem
  • время от времени уплотнение словаря (удаление неиспользуемых кодов)
• сделано правильно, уборка может производиться, когда никто не смотрит (время простоя), или путем создания нового файла и "переключения" в конечном итоге

Одним из положительных эффектов будет то, что словарь будет применяться ко всему файлу. Если вы можете сэкономить циклы процессора, вы можете периодически проверять, не перекрываются ли последовательности «файловыми» границами, а затем перегруппировать их.

Эта идея предназначена для действительно случайных чтений. Если вы собираетесь читать только записи фиксированного размера, некоторые части этой идеи могут стать проще.

Я не знаю ни одного алгоритма сжатия, который допускал бы случайное чтение, не говоря уже о случайной записи. Если вам нужна такая возможность, лучше всего сжать файл по частям, а не целиком.

например,
Сначала рассмотрим случай, доступный только для чтения. Допустим, вы разбили файл на части по 8 КБ. Вы сжимаете каждый кусок и сохраняете каждый сжатый фрагмент последовательно. Вам нужно будет записать, где хранится каждый сжатый фрагмент и насколько он велик. Затем предположим, что вам нужно прочитать N байтов, начиная со смещения O. Вам нужно будет выяснить, в каком фрагменте он находится (O / 8K), распаковать этот фрагмент и захватить эти байты. Необходимые данные могут охватывать несколько фрагментов, поэтому вам придется иметь дело с этим сценарием.

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

В основном так работают сжатые файловые системы. Возможно, вам лучше включить сжатие файловой системы для ваших файлов и просто читать / записывать их в обычном режиме.

Сжатие - это устранение избыточности данных. К сожалению, маловероятно, что избыточность будет распределяться с монотонной равномерностью по всему файлу, и это почти единственный сценарий, в котором можно ожидать сжатия и мелкозернистого произвольного доступа.

Однако вы можете закрыть произвольный доступ, поддерживая внешний список, построенный во время сжатия, который показывает соответствие между выбранными точками в несжатом потоке данных и их местоположениями в сжатом потоке данных. Очевидно, вам придется выбрать метод, при котором схема трансляции между исходным потоком и его сжатой версией не зависит от местоположения в потоке (то есть без LZ77 или LZ78; вместо этого вы, вероятно, захотите пойти на Хаффмана или байтовую версию). парное кодирование.) Очевидно, это повлечет за собой большие накладные расходы, и вам придется решить, как вы хотите найти компромисс между объемом памяти, необходимым для «точек закладок», и временем процессора, необходимым для распаковки потока, начиная с закладки, чтобы получить данные, которые вы действительно ищете при чтении.

Что касается записи с произвольным доступом ... это почти невозможно. Как уже отмечалось, сжатие - это устранение избыточности данных. Если вы попытаетесь заменить данные, которые могли быть и были сжаты из-за избыточности, данными, которые не имеют такую ​​же избыточность, они просто не подходят.

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