компрессия данных - > метод арифметического кодирования

я про этот метод https://neerc.ifmo.ru/wiki/index.php?title=Арифметическое_кодирование
1. Не подскажите как сохраняют дробные числа в заархивированом файле?
2. Как я понял для этого метода пользуются длинной арифметикой а не FPU ? это так ?
3. Как я понял этот метод довольно новый ... а есть ли исходники его реализациии?
Всем спасибо!

 

Как это нету. По вашей же ссылки есть примеры на Python. Они чем вас не устраивают?

 

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

 

f13nd! А почему вы сказали что этот метод преимушественно для текстовых файлов?

А какие методы сохранения чисел переменной длинны вобще бывают?

 

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

Либо кодировать количество разрядов в отдельном поле (как в библиотеке nn_ для rsa), либо использовать запрещенные состояния (например запрещены четыре нуля подряд и за тремя нулями обязательно должна следовать единица, которая отбрасывается при декодировании. таким образом четыре нуля подряд - конец поля).

 

Разобрался я с арифметическим кодированием ...
Даже на git залил https://github.com/VVVaSoft/WindowsFormsACC
сжимает он практически также как и метод Хафмена ... чесно говоря я от него ожидал большего ...
А знает ктонибудь методы сжатия которые жмут лучше чем словарные и PPM ? Подскажите пожалуйста.

 

Алгоритмы Лемпеля-Зива (LZ): Семейство алгоритмов, таких как LZ77 и LZ78, используют словари для кодирования повторяющихся последовательностей данных. Они часто применяются в архиваторах и сжатии текстов.

 

Теоретически там что то типа неподвижной точки есть для всякого отображения, поэтому сжатие зависит от данных, что подвергаются сжатию
Я думал над следующим: пусть любые данные есть натуральное число, тогда можно разложить его в произведение простых, и закодировать натуральным числом, если n-составное и индексом простого (в ряду простых) если n-простое
Тогда, имея множество простых (какого-то размера), можно будет восстановить архив
Имеем неподвижную точку: f(N\P) = n
То есть в этой неподвижной точке сжатия нет
Ну это такой, наиболее общий подход

 

9999*8888=88871112, 4+4=8 разрядов к 8
444*9999999=4439999556 3+7=11 разрядов к 10
А где в этом всём сжатие?

 

А причем тут разряды?
Речь вообще не о разрядах

 

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

 

Предположим, что вам надо сжать данные 0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0x7F или в виде QWORD 0x7FFFFFFF00000000. У меня 3 вопроса: Представьте разложение этого числа по вашему способу? Какой объем займет запись его после сжатия? Сколько на это потребуется времени (на сжатие и восстановление по отдельности)?

 

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

--- Сообщение объединено, 6 фев 2025 ---

0x7FFFFFFF00000000 = 9 223 372 032 559 808 512, оно составное, так что тут так и останется 0x7FFFFFFF00000000 и +1 бит на то чтобы указать, что это число составное

--- Сообщение объединено, 6 фев 2025 ---

Там вопрос спорный, равенство P и NP - задача тысячелетия

 

Вы же сами хотели разбивать его на простые и записывать. Да число составное. Вот его разбиение: 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2147483647
Но я даже не хочу представлять сколько времени у меня уйдет на современном ПК найти индекс последнего множителя.

 

Это необходимо для разархивирования, знать индексы простых чисел в множестве простых
Но имея таблицу с такими индексами это одно обращение к памяти

--- Сообщение объединено, 6 фев 2025 ---

Тут разложение искать не нужно, тут достаточно теста на простоту, который принадлежит классу не более P

--- Сообщение объединено, 6 фев 2025 ---

На сжатии нужно знать простое ли это число <=P сложность, на восстановление тестировать на простоту не нужно, т.к мы прямо указываем простое оно или составное, но нужно знать индекс простого числа в множестве простых, поэтому, не имея их, придется протестировать все числа до целевого на простоту

--- Сообщение объединено, 6 фев 2025 ---

А зачем вам это? Вы чего? Решили написать такое?

 

Вам и для этого понадобится таблица с простыми числами. И если брать только диапазон в 32 бита, то это уже более 100 млн значений. При наличии такой таблицы ваша задача проверки на простоту тоже существенно ускоряется т.к. вам не нужно при проверке N искать его предыдущие простые и количество делений сокращается. Эта же таблица вам понадобится при нахождении индексов при восстановлении.

Но вот даже хранение такой таблицы для 32-бит будет занимать неоправданно много места.

Нет. Я вам хотел показать две вещи. 1) Числа могут быть простыми во всем диапазоне натуральных т.е. вам понадобится бесконечная таблица чисел для нахождения их индексов.
2) При разбиении вы получите более одного одинакового простого сомножителя. Поэтому записать индексы придется для всех этих чисел, а это займет много больше места чем обычное представление исходного числа (намного более избыточное).

 

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

 

А это разве не ваше утверждение:

Т.е. это я вам привел пример 64-битного числа требующего разложения. Но реальные данные могут оказаться длиннее и простые сомножители соответственно много больше. А для них еще и индексы вам могут понадобиться, если проверка покажет, что оно простое (т.к. простые числа встречаются на всем диапазоне натуральных чисел). И еще одна проблема. Как вы будете кодировать 0.

т.е. вам может встретиться случай: 0x00010000 или 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00

 

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

 

Можно, но не найти его индекс.