Каков наилучший алгоритм сжатия, который позволяет случайное чтение / запись в файл?
Каков наилучший алгоритм сжатия, который позволяет случайное чтение / запись в файл?
Я знаю, что о любых адаптивных алгоритмах сжатия не может быть и речи.
И я знаю, что кодирование Хаффмана не может быть и речи.
У кого-нибудь есть лучший алгоритм сжатия, который позволил бы случайное чтение / запись?
Я думаю, что вы можете использовать любой алгоритм сжатия, если вы пишете его в блоках, но в идеале я не хотел бы распаковывать целый блок за раз. Но если у вас есть предложения по простому способу сделать это и как узнать границы блоков, пожалуйста, дайте мне знать. Если это является частью вашего решения, пожалуйста, дайте мне знать, что вы делаете, когда данные, которые вы хотите прочитать, выходят за границы блока?
В контексте ваших ответов, пожалуйста, предположите, что размер рассматриваемого файла составляет 100 ГБ, и иногда я захочу прочитать первые 10 байтов, а иногда я захочу прочитать последние 19 байтов, а иногда я захочу прочитать 17 байты в середине.,
7 ответов
Я ошеломлен количеством ответов, которые подразумевают, что такая вещь невозможна.
Разве эти люди никогда не слышали о "сжатых файловых системах", которые существовали с тех пор, как в 1993 году Stac Electronics подала в суд на Microsoft за технологию сжатых файловых систем?
Я слышал, что LZS и LZJB - популярные алгоритмы для людей, реализующих сжатые файловые системы, которые обязательно требуют как чтения с произвольным доступом, так и записи с произвольным доступом.
Возможно, самое простое и лучшее, что нужно сделать, - включить сжатие файловой системы для этого файла и позволить ОС разобраться с деталями. Но если вы настаиваете на том, чтобы обрабатывать его вручную, возможно, вы можете получить некоторые советы, прочитав о прозрачном сжатии файлов NTFS.
Также проверьте: "Stackru: форматы сжатия с хорошей поддержкой произвольного доступа в архивах?"
Формат razip поддерживает чтение с произвольным доступом с большей производительностью, чем gzip/bzip2, которые необходимо настроить для этой поддержки:
Схема сжатия на основе словаря, в которой код каждой записи словаря кодируется с одинаковым размером, даст возможность начинать чтение с любого кратного размера кода, а операции записи и обновления просты, если коды не используют их контекст / соседи.
Если кодирование включает способ различения начала и конца кодов, вам не нужно, чтобы коды были одинаковой длины, и вы можете начать чтение в любом месте в середине файла. Этот метод более полезен, если вы читаете из неизвестной позиции в потоке.
Я думаю, что Стивен Денн может быть на что-то здесь. Представить:
- zip-подобное сжатие последовательностей в коды
- код отображения словаря -> последовательность
- файл будет похож на файловую систему
- каждая запись генерирует новый "файл" (последовательность байтов, сжатых по словарю)
- "файловая система" отслеживает, какой "файл" принадлежит каким байтам (начало, конец)
- каждый "файл" сжимается по словарю
- читает работу по файлу, распаковывая и извлекая байты в соответствии с "файловой системой"
- записи делают "файлы" недействительными, новые "файлы" добавляются для замены недействительных
- эта система потребует:
- механизм дефрагментации файловой системы
- время от времени сжатие словаря (удаление неиспользуемых кодов)
- сделано правильно, ведение домашнего хозяйства может быть сделано, когда никто не смотрит (простой) или путем создания нового файла и "переключения" в конце концов
Одним положительным эффектом будет то, что словарь будет применяться ко всему файлу. Если вы можете сэкономить циклы ЦП, вы можете периодически проверять последовательности, перекрывающие "файловые" границы, а затем перегруппировать их.
Эта идея для действительно случайного чтения. Если вы когда-либо будете читать записи фиксированного размера, некоторые части этой идеи могут стать проще.
Я не знаю ни одного алгоритма сжатия, который бы допускал случайное чтение, не говоря уже о случайных записях. Если вам нужна такая способность, лучше всего сжать файл кусками, а не в целом.
например
Сначала мы рассмотрим случай только для чтения. Допустим, вы разбили свой файл на 8K кусков. Вы сжимаете каждый фрагмент и сохраняете каждый сжатый фрагмент последовательно. Вам нужно будет записать, где хранится каждый сжатый блок и насколько он велик. Затем, скажем, вам нужно прочитать N байтов, начиная со смещения O. Вам нужно будет выяснить, в каком блоке он находится (O / 8K), распаковать этот блок и захватить эти байты. Данные, которые вам нужны, могут охватывать несколько фрагментов, поэтому вам придется иметь дело с этим сценарием.
Вещи усложняются, когда вы хотите иметь возможность записи в сжатый файл. Вам приходится иметь дело с сжатыми кусками, которые становятся все больше и меньше. Возможно, вам понадобится добавить некоторые дополнительные отступы к каждому чанку на случай, если он расширяется (он все еще остается без сжатия, но разные данные будут сжиматься до разных размеров). Вам может даже понадобиться переместить фрагменты, если сжатые данные слишком велики, чтобы уместиться в исходное пространство, которое им было дано.
Это в основном то, как работают сжатые файловые системы. Возможно, вам лучше включить сжатие файловой системы для ваших файлов и просто читать / записывать их в обычном режиме.
Сжатие - это удаление избыточности из данных. К сожалению, маловероятно, что избыточность будет распределена с монотонной равномерностью по всему файлу, и это единственный сценарий, в котором можно ожидать сжатие и детальный произвольный доступ.
Однако вы можете приблизиться к произвольному доступу, поддерживая внешний список, созданный во время сжатия, который показывает соответствие между выбранными точками в несжатом потоке данных и их расположением в сжатом потоке данных. Очевидно, вам придется выбрать метод, в котором схема трансляции между исходным потоком и его сжатой версией не зависит от местоположения в потоке (т.е. без LZ77 или LZ78; вместо этого вы, вероятно, захотите перейти к Хаффману или байту. парное кодирование.) Очевидно, что это повлечет за собой много накладных расходов, и вам нужно будет решить, каким образом вы хотите обменяться между пространством хранения, необходимым для "точек закладки", и временем процессора, необходимым для распаковки потока, начиная с отметка закладки, чтобы получить данные, которые вы на самом деле ищете на этом чтении.
Что касается записи с произвольным доступом... это почти невозможно. Как уже отмечалось, сжатие заключается в удалении избыточности из данных. Если вы попытаетесь заменить данные, которые могли быть и были сжаты, потому что они были избыточными, на данные, которые не имеют такой же избыточности, они просто не подойдут.
Однако, в зависимости от того, сколько записи с произвольным доступом вы собираетесь делать, вы можете смоделировать ее, поддерживая разреженную матрицу, представляющую все данные, записанные в файл после сжатия. При всех чтениях вы проверяете матрицу, чтобы увидеть, читали ли вы область, в которую вы записали после сжатия. Если нет, то вы перейдете к сжатому файлу для данных.
Отсутствие схемы сжатия позволит детализировать произвольный доступ по двум связанным причинам:
- Вы не можете точно знать, насколько глубоко в сжатом файле находится желаемый фрагмент данных, поэтому
- нет никакого способа узнать, где начинается символ (в какой позиции бита для Хаффмана, хуже для арифметического кодирования).
Я могу только предложить обрабатывать файл как широковещательный поток и вставлять частые маркеры синхронизации / положения с очевидными накладными расходами (метки синхронизации не только сами занимают место, но и усложняют кодирование, поскольку должны избегать "случайных" меток синхронизации!). В качестве альтернативы, чтобы избежать поиска, похожего на бинарный поиск (с оптимизацией, с помощью которой вы можете лучше угадать, с чего начать, чем с середины), вы можете включить "оглавление" в начало или конец файла.
Что касается записи с произвольным доступом... Я не могу придумать ни одного изящного решения:(