Порядок сортировки данных на диске часто влияет на эффективность последовательного сжатия в ситуациях, когда данные, естественно, следует рассматривать как неупорядоченные.
Для надуманного примера предположим, что вам нужно сжать большой текстовый файл (> 5 ГБ), содержащие миллионы строк с чрезвычайно избыточными значениями с низким количеством элементов.
SomeModerateLengthString
SomeModerateLengthString
SomeModerateLengthString
[...100 thousand repetitions...]
AnotherDifferentString
AnotherDifferentString
[...30 thousand repetitions...]
AThirdStringQuiteDifferentFromTheOthers
AThirdStringQuiteDifferentFromTheOthers
[...75 thousand repetitions...]
[...more repetitions like above, for several hundred more strings]
Очевидно, что это будет довольно хорошо сжиматься с помощью gzip, lzma или любого последовательного файлового компрессора.Вы можете тривиально запустить кодирование длины с помощью сценария оболочки.
Если вы получите строки этого файла, отсортированные в случайном порядке, сжатие страдает.Сами строки строк могут быть сжаты словарём, но большая часть памяти тратится на сохранение точного (несжимаемо случайного) порядка строк, даже когда этот порядок совершенно не имеет значения.
Здесь решение состоит в том, чтоочевидно: отсортировать файл перед сжатием.Но в реальной жизни трудно найти самый эффективный порядок сортировки.Избыточные данные, приведенные выше, могут быть вторым столбцом в CSV, где первый представляет собой 5-значное целое число с большим количеством элементов, возможно.
Существуют ли какие-либо алгоритмы сжатия, которые игнорируют требование о том, что сжатые записи должны быть возвращены втот же заказ получен, и оптимизировать, используя эту гибкость?
Если нет, есть ли какие-нибудь хорошие стратегии для оптимизации упорядочения / разделения неупорядоченных данных в интересах последовательных компрессоров?Я представляю, что цель состоит в том, чтобы объединить записи с малым расстоянием редактирования Левенштейна вместе в одни и те же порции файла, но я не уверен.