Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279677 Tue, 26 Feb 2013 06:26:29 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279677 думаю тема закрыта]]> Serafim Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279661 Tue, 26 Feb 2013 05:29:37 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279661 Цитата Serafim @ 25.02.13, 07:36

2) Делим его на наименьший делитель из возможных (как минимум 2, как максимум - само число), допустим 2

Как его найти?
Да и к тому же очень редко когда будут попадаться "хорошие" данные, в которых будет много одинаковых чисел. Поэтому сжатием это не будет почти во всех случаях.]]> OpenGL Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279576 Mon, 25 Feb 2013 18:28:23 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279576 срач в многошуме.]]> Kray74 Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279545 Mon, 25 Feb 2013 17:02:11 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279545 Цитата AVA12 @ 25.02.13, 15:08

А твой алгоритм для каких данных предназначен?

вообще походу это не мой алгоритм, его уже реализовывал практически каждый школьник. Сегодня на работе поделился - коллега сказал, что когда в Вузе учился - делал, есть оказывается ещё некий Бабушкин (ака Попов с БолгенОС), который мол тоже такое же предложил. :crazy:]]> Serafim Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279542 Mon, 25 Feb 2013 16:56:00 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279542 http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%...%BD%D0%B8%D1%8F

Цитата

N случайная переменная с энтропией H(X) может быть сжата в более чем NH(X) битов с незначительным риском потери данных если N стремится к бесконечности, но если сжатие происходит менее в чем NH(X)) бит, то данные скорее всего будут потеряны. (MacKay 2003).»

]]> Мяут-Настоящий Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279490 Mon, 25 Feb 2013 15:08:30 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279490 AVA12 Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279457 Mon, 25 Feb 2013 13:55:51 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279457 Цитата AVA12 @ 25.02.13, 13:51

сам понимаешь, что избыточность нужно анализировать в случаях составления индексированного словаря, как это делает zip. В случае арифметического кодирования (именно этот случай энтропийного сжатия о котором я говорю в топике) - этот вариант не нужен, т.к. для всех данных будет использоваться одинаковое деление на целые и составление словаря множителей.]]> Serafim Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279453 Mon, 25 Feb 2013 13:51:07 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279453 Цитата

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

Гм, вообще-то сначала анализируют данные, которые надо сжимать, определяют, какую избыточность они содержат, а уж затем придумывают, как эту избыточность отжать. А не наоборот.]]> AVA12 Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279285 Mon, 25 Feb 2013 10:12:34 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279285
С первого раза я не соображу с ходу в каких случаях может быть выигрыш. Опять же, чисто теоретически нужно брать не наименьший делитель, а наибольший в пределах одного байта.]]> Serafim Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279215 Mon, 25 Feb 2013 09:03:45 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279215 Цитата MIF @ 25.02.13, 08:25

ИМХО: в обшем случае размер архива будет больше исходного файла.

Допустим, что разделители "x" и ";" занимают в стриктуре М бит. М не может быть меньше 2. Примем идеальное допучение М=2 (я не знаю, как такого добиться!)
Протестируем все N-битные числа.
Проанализируем делимость на 2.
Половина чисел нечетные - нет изменения в размере архиве после приложения правила "делимость на 2"
Четверть чисел простые четные. Размер оставшегося числа уменьшается на 1 бит. Размер области хранения информации о делимости на два занимарт 4 бита(1x1;). Потери = 3 бита;
1/8 чисел дважды четные. Размер оставшегося числа уменьшается на 2 битс. Размер области хранения информации о делимости на два занимарт 5 бит(10x1;). Потери = 3 бита;
1/16 чисел дважды четные. Размер оставшегося числа уменьшается на 3 битс. Размер области хранения информации о делимости на два занимарт 5 бит(11x1;). Потери = 2 бита;
1/32 чисел дважды четные. Размер оставшегося числа уменьшается на 4 битс. Размер области хранения информации о делимости на два занимарт 6 бит(100x1;). Потери = 2 бита;

Начная с "К четности" будет некоторый выйгрых в конечном размере, но процент таких чисел очень низок.

Получается что-то типа геометрической прогресси. Геометричекие прогрессий шодятся.
Если посчтать ее предел при M стремяшемся к бесконечности, то думаю , получатся небольшие потери (0.5-1.0 бита).

И чем больше простое число, тем большие будут потери .]]> MIF Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279208 Mon, 25 Feb 2013 08:53:46 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279208 Аэтерос Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279197 Mon, 25 Feb 2013 08:25:09 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279197 Улучшение алгоритма: вместо записывания 2,3,7,11 записывай порядковый номер простого числа: 1,2,3,4. Уже со второго простого числа (тройки) ето даёт выигрыш по краиней мере в один бит.
ИМХО: в обшем случае размер архива будет больше исходного файла.]]> MIF Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279194 Mon, 25 Feb 2013 08:13:39 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279194 Вопрос 2. Ты хоть знаешь что такое стек?)))) Недавно помню ты удивлялся что строка это массив байтов))))

Добавлено 25.02.13, 08:16

Цитата

2) Делим его на наименьший делитель из возможных (как минимум 2, как максимум - само число), допустим 2

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFAAAAAAAAAAAAAAAAAAAAAA124AAAAAAAAAAAAAAAAA456AAAAAAAAAAAAAAAAAAAAAAAFFFF1F25CCCCCCCCCCCCCCC5D6EEEE444EEE

Поделикося на 2..... Или на наименьший делитель....]]> treeS Обсуждаем новые идеи https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279171 Mon, 25 Feb 2013 07:36:39 +0000 Очень простой и мощный алгоритм сжатия https://forum.sources.ru/index.php?showtopic=372982&view=findpost&p=3279171 1) Имеем на руках феерической длины 16-ричное число
2) Делим его на наименьший делитель из возможных (как минимум 2, как максимум - само число), допустим 2
3) В результате получаем 2 и это же число, сокращённое в два раза
4) Записываем в "стек" 2 и проделываем ту же самую операцию для оставшихся данных
5) повторяем до тех пор, пока делимое не будет соответствовать делителю.
6) Далее получаем просто набор множителей для воссоздания исходной записи
7) Сокращаем количество одинаковых множителей с помошью простых простых арифметических операторов и разделяем операции спец символами, получаем что-то вроде такого:
2x32;3x3;4;6;37FFAC

Для воссоздания исходных данных возводим 2 в степень 32, 3 в степень 3, умножаем на 4, затем на 6 и в конце на 37FFAC.

Плюсы:
+ Можно сократить несколько гигабайт данных до килобайт в идеальном варианте
+ Довольно простой алгоритм
Минусы:
- Требует дофига оперативной памяти и времени вычесления даже на небольших объёмах елси делать в лоб

Ваши идеи? :)]]> Serafim Обсуждаем новые идеи