Программирование: кодирование диапазонов частот
Обнаружил ситуацию, когда файл размером 1 мегабайт из одних пробелов сжимается моим алгоритмом в 100 килобайт, а должен сжиматься в несколько байт.
Трассировал алгоритм, чтобы понять и устранить причину.
Суть проблемы:
В расчёте вероятностей используется целочисленная арифметика, числовой диапазон делится на части для каждого символа, величина частей пропорциональна частотам символов. (Затем эти полученные части диапазона эффективно упаковываются специальным алгоритмом, который называется rangecoder. Здесь он не рассматривается.) При больших значениях счётчиков символов диапазон оказывается меньше, чем сумма счётчиков частот, и его нельзя поделить на части, не используя большое количество операций деления и умножения.
Три способа решения:
1) Расширить исходный диапазон на время вычислений. Это устранит проблемы потери точности вычислений. В конце вычислений привести его обратно в исходный диапазон.
2) Сильнее ограничить диапазон счётчиков частот, масштабировать их сумму при переполнении. Это так же устранит проблемы потери точности вычислений. У этого решения есть плюсы и минусы, о которых я здесь не упоминаю.
3) Использовать пару операций умножения / деления на всех этапах вычисления диапазонов. Очень хороший метод, но очень затратный по времени выполнения.
Собираюсь применить первые два.
Эти решения позволяют уменьшить потери сжатия в некоторых частных случаях, которые могут встречаться и при сжатии обычных файлов.
Upd: Простейшая проверка показала, что даже при грубом применении решения 1) и 2) исходный файл в 100 мегабайт, состоящий из одних пробелов, сжимается в 13 байт вместо прошлых 100 килобайт. Улучшение в несколько тысяч раз.
Трассировал алгоритм, чтобы понять и устранить причину.
Суть проблемы:
В расчёте вероятностей используется целочисленная арифметика, числовой диапазон делится на части для каждого символа, величина частей пропорциональна частотам символов. (Затем эти полученные части диапазона эффективно упаковываются специальным алгоритмом, который называется rangecoder. Здесь он не рассматривается.) При больших значениях счётчиков символов диапазон оказывается меньше, чем сумма счётчиков частот, и его нельзя поделить на части, не используя большое количество операций деления и умножения.
Три способа решения:
1) Расширить исходный диапазон на время вычислений. Это устранит проблемы потери точности вычислений. В конце вычислений привести его обратно в исходный диапазон.
2) Сильнее ограничить диапазон счётчиков частот, масштабировать их сумму при переполнении. Это так же устранит проблемы потери точности вычислений. У этого решения есть плюсы и минусы, о которых я здесь не упоминаю.
3) Использовать пару операций умножения / деления на всех этапах вычисления диапазонов. Очень хороший метод, но очень затратный по времени выполнения.
Собираюсь применить первые два.
Эти решения позволяют уменьшить потери сжатия в некоторых частных случаях, которые могут встречаться и при сжатии обычных файлов.
Upd: Простейшая проверка показала, что даже при грубом применении решения 1) и 2) исходный файл в 100 мегабайт, состоящий из одних пробелов, сжимается в 13 байт вместо прошлых 100 килобайт. Улучшение в несколько тысяч раз.