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

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

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

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

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

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

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

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

Однако Вы могли стать близкими к произвольному доступу путем ведения внешнего списка, созданного во время сжатия, которое показывает корреспонденцию между выбранными точками в несжатом потоке данных и их местоположениями в сжатом потоке данных. Необходимо было бы, очевидно, выбрать метод, где схема перевода между исходным потоком и его сжатой версией не меняется в зависимости от местоположения в потоке (т.е. № LZ77 или LZ78; вместо этого Вы, вероятно, хотели бы пойти для Huffman или парного байтом кодирования.), Очевидно, это подверглось бы большому количеству издержек, и необходимо будет выбрать, как Вы хотели обменять между пространством памяти, необходимым для "точек закладки", и процессорное время должно было распаковать поток, начинающий в точке закладки получить данные, которые Вы на самом деле ищете на том чтении.

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

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

Никакая схема сжатия не предоставит мелкомодульный произвольный доступ по двум связанным причинам:

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

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

Что касается записи произвольного доступа... Я не могу думать ни о каком аккуратный решение: (

Я думаю, что Стивен Денн может что-то придумать. Представьте себе:

• zip-подобное сжатие последовательностей в коды
• словарь, отображающий код -> последовательность
• файл будет похож на файловую систему
  • каждая запись генерирует новый "файл" (последовательность байтов, сжатая по словарю)
  • "файловая система" отслеживает, какому "файлу" принадлежит какой байт (начало, конец)
  • каждый "файл" сжат по словарю
  • чтение работает пофайлово, распаковывая и извлекая байты по "файловой системе"
  • записи делают "файлы" недействительными, новые "файлы" добавляются взамен недействительных
• этой системе потребуется:
  • механизм дефрагментации файловой системы
  • уплотнение словаря время от времени (удаление неиспользуемых кодов)
• при правильном подходе, ведение домашнего хозяйства может быть сделано, когда никто не смотрит (время простоя) или путем создания нового файла и "переключения" в конечном итоге

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

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

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

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

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

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

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