ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Об одном способе ресурсоёмкого сжатия данных
60 сообщений из 60, показаны все 3 страниц
  все  
Об одном способе ресурсоёмкого сжатия данных
    #39578904
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Есть данные Д - битовая последовательность длины N, - которые требуется сжать, и стандартный ГПСЧ.

1. Находим битовую последовательность минимальной длины M, которая ни разу не встречается в Д. Назовём её "флаг" (Ф).

2. В цикле перебираем значения seed (s), используемые для инициации ГПСЧ: ГПСЧ(s).

3. Посредством ГПСЧ(s) генерируем случайную последовательность (СП) той же длины N.

4. Сравниваем побитово Д и СП. Все совпадающие - в Д и СП - последовательности битов, длиной больше М заменяем (в Д !) на флаг Ф. При этом следим, чтобы "на стыках" вставляемого флага и соседних исходных битов Д не возникали "паразитные флаги".

5. В результате замен получается битовая последовательность Д' длины N' (меньше N !).

6. Продолжаем перебор (цикл в п.2) до тех пор, пока не найдём значение seed, дающее удовлетворяющую нас степень сжатия К= N/N'

7. Архивный файл представляет собой структуру из трёх элементов: Ф, s, Д' .
______________________________

PS. Как вариант, в качестве флага Ф можно использовать вообще любую последовательность битов, желательно редко встречающуюся в Д, поскольку "естественные" вхождения Ф в Д нужно будет маркировать посредством, например, удвоения: Ф -> ФФ. (И потом нужно будет следить, чтобы дополнительные ФФ не возникали в процессе сжатия.)
...
Рейтинг: 0 / 0
03.01.2018, 12:36
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39578935
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
... кстати, файл, сжатый с применением одной пары параметров (Ф1, s1), можно дальше пытаться сжимать с каким то другим Ф2, подбирая какое-то другое значение s2. И так пока не надоест.
...
Рейтинг: 0 / 0
03.01.2018, 13:26
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579556
scf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
scf
Участник
Иван FXS,

Если ГПСЧ качественный, т.е. распределение битов равновероятно, оцените количество циклов для достижения нужной степени сжатия. Задачка не выглядит очень уж сложной и, я думаю, ответ вам не понравится.
...
Рейтинг: 0 / 0
05.01.2018, 10:00
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579565
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Задачу можно свести к вырожденной заменив гпсч на последовательность целых чисел.
...
Рейтинг: 0 / 0
05.01.2018, 10:35
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579571
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Это обычный алгоритм LZW, только с ошибками и случайно-генеруемым словарем :fail:
...
Рейтинг: 0 / 0
05.01.2018, 10:50
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579608
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
scf,

по секрету, этот топик вынесен в автономную тему из темы http://www.sql.ru/forum/1281135/dispersiya-dliny-arhiva -- где как раз обсуждалось сильное (желательно) сжатие с расходованием большого (в пределе - не ограниченного) количества ресурсов.
...
Рейтинг: 0 / 0
05.01.2018, 12:25
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579610
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Siemargl,

Сюрприз: словарь не нужно запихивать в архивный файл!
...
Рейтинг: 0 / 0
05.01.2018, 12:26
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579852
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Точно такое же первое впеч, как у Siemargl - типа ЛЗВ, но только словарь заменён алгоритмом. Т.е. как бы , отталкиваясь от идей ЛЗВ, строим нечто из класса "сжатие посредством алгоритма". В связи с этим (и учитывая корни этой темы) есть мнение, что 1 из 2-х: либо нужно уметь восстанавливать исходник, либо нужна воспроизводимость кодирования данной Д. Во всяк я так понимаю термин pow. В случае же ГСПЧ да ещё стандартного я сомневаюсь в воспроизводимости. По моему мнению, при одном и том же СИДЕ СП будут разные (а лень проверять).
...
Рейтинг: 0 / 0
05.01.2018, 19:12
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579867
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
exp98,

вы, наверное, полагаете, что если повторно вызвать ГПСЧ с тем же аргументом (seed-ом), то он возвратит другой результат ...
...
Рейтинг: 0 / 0
05.01.2018, 19:38
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579884
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXS, пример кода будет? Желательно со статистикой.
...
Рейтинг: 0 / 0
05.01.2018, 20:10
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579890
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T, в смысле "пример кода"?
...
Рейтинг: 0 / 0
05.01.2018, 20:30
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579962
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну чтож... пятница продолжается. Давайте порассуждаем.
Иван FXSЕсть данные Д - битовая последовательность длины N, - которые требуется сжать, и стандартный ГПСЧ.

Тезис о том что есть некая "последовательность в вакууме" меня не устраивает. Он - лукавый.
У меня возникли вопросы. На что похожа эта битовая последовательность?

1. Английский текст. Или произвольный текст.
2. Поток случайных бит наподобие /dev/urandom
3. Смесь вышеперечисленного.
4. Еще какой-то вариант

1. Находим битовую последовательность минимальной длины M, которая ни разу не встречается в Д. Назовём её "флаг" (Ф).

Я-бы предложил назвать его "escape" ('\')

2. В цикле перебираем значения seed (s), используемые для инициации ГПСЧ: ГПСЧ(s).

Нам нужно хотя-бы формально доказать что длина s в битах будет меньше чем длина random().
К примеру для встроенного в ОС линейного конгруэнтного ГПСЧ, аргумент и функция будут
по 32 бита. И функция - суть биекция.

Если мы вводим в задачу ГПСЧ более высокой или плавающей разрядности то надо
обосновать что он является ГПСЧ. Либо он НЕ-ГПСЧ. Либо не биекция. Не биекция - значит
не покрываем ОДЗ. И т.д.

3. Посредством ГПСЧ(s) генерируем случайную последовательность (СП) той же длины N.

4. Сравниваем побитово Д и СП. Все совпадающие - в Д и СП - последовательности битов, длиной больше М заменяем (в Д !) на флаг Ф. При этом следим, чтобы "на стыках" вставляемого флага и соседних исходных битов Д не возникали "паразитные флаги".

5. В результате замен получается битовая последовательность Д' длины N' (меньше N !).

Последний поинт - слабое место в рассуждениях.

Надо как-то подкрепить рассуждения. Ато получится очередной кодер Бабушкина.
...
Рейтинг: 0 / 0
06.01.2018, 00:56
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579979
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
maytonНам нужно хотя-бы формально доказать что длина s в битах будет меньше чем длина random().
нам совершенно это не нужно, поскольку пользоваться мы собираемся не "атомарным" значением, возвращаемым random-мом, а (как и написано далее) "случайной последовательность ... длины N". Для построения которой, естественно, нам придётся вызывать random последовательно некоторое количество раз.
...
Рейтинг: 0 / 0
06.01.2018, 09:31
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579981
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
... причём вся эта (псевдо-) "случайная последовательность длины N" алгоритмически порождается одним (исходным) значением seed.
...
Рейтинг: 0 / 0
06.01.2018, 09:33
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39579992
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
maytonПоследний поинт - слабое место в рассуждениях.
совершенно не слабое, поскольку мы делаем только те замены, которые укорачивают длину строки.
...
Рейтинг: 0 / 0
06.01.2018, 10:10
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580019
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А что там по первому вопросу?
...
Рейтинг: 0 / 0
06.01.2018, 12:35
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580027
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
mayton, да хоть "3. Смесь вышеперечисленного".

При том что вы ведь в курсе той, параллельной темы, и знаете, что тема возникла в контексте сжатия данных блокчейна криптовалюты (типа Биткойна)...
...
Рейтинг: 0 / 0
06.01.2018, 12:51
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580043
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXS, ok.

Нужен образец исходных данных. И ваш proof-of-concept.
...
Рейтинг: 0 / 0
06.01.2018, 14:08
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580127
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
maytonНужен образец исходных данных
как я понимаю, вот здесь https://rutracker.org/forum/viewtopic.php?t=5444025 файлы с расширением .ldb (типа 3806072.ldb) размером ~2Мб -- это блоки блокчейна в натуральном виде ...

С proof-of-concept заметно сложнее ... его нет, есть только чистая идея. В статусе гипотезы, к тому же.
...
Рейтинг: 0 / 0
06.01.2018, 18:58
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580130
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тогда предлагаю ее называть гипотезой СРСД (по названию топика).
...
Рейтинг: 0 / 0
06.01.2018, 19:08
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580543
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
exp98Точно такое же первое впеч, как у Siemargl - типа ЛЗВ, но только словарь заменён алгоритмом. Т.е. как бы , отталкиваясь от идей ЛЗВ, строим нечто из класса "сжатие посредством алгоритма". В связи с этим (и учитывая корни этой темы) есть мнение, что 1 из 2-х: либо нужно уметь восстанавливать исходник, либо нужна воспроизводимость кодирования данной Д. Во всяк я так понимаю термин pow. В случае же ГСПЧ да ещё стандартного я сомневаюсь в воспроизводимости. По моему мнению, при одном и том же СИДЕ СП будут разные (а лень проверять).не ну почему. псевдорандом же.
при одном и том же seed, генерирует одну и ту же последовательность.


это слегка модифицированный алгоритм под названием "мартышка, клацая на пишущей машинке, за очень большое время напишет войну и мир".
Дает возможность топикстартеру посетовать, что не то что алгоритм плохой, просто процессоры у нас слабые :)
...
Рейтинг: 0 / 0
08.01.2018, 14:23
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580553
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это ближе к Библиотеке Борхеса.
...
Рейтинг: 0 / 0
08.01.2018, 14:51
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580634
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
S.G."мартышка, клацая на пишущей машинке, за очень большое время напишет войну и мир" точно! Я думал об этом, но как-то не нашлось повода упомянуть это трудолюбивое животное.
...
Рейтинг: 0 / 0
08.01.2018, 18:55
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39580810
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
S.G."мартышка, клацая на пишущей машинкеа майнинговые фермы -- это разве не триллиарды кремниевых мартышек, клацающих на пишущих машинках?
...
Рейтинг: 0 / 0
09.01.2018, 08:19
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581669
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Иван FXSЕсть данные Д - битовая последовательность длины N, - которые требуется сжать, и стандартный ГПСЧ.

1. Находим битовую последовательность минимальной длины M, которая ни разу не встречается в Д. Назовём её "флаг" (Ф).

2. В цикле перебираем значения seed (s), используемые для инициации ГПСЧ: ГПСЧ(s).

3. Посредством ГПСЧ(s) генерируем случайную последовательность (СП) той же длины N.

4. Сравниваем побитово Д и СП. Все совпадающие - в Д и СП - последовательности битов, длиной больше М заменяем (в Д !) на флаг Ф. При этом следим, чтобы "на стыках" вставляемого флага и соседних исходных битов Д не возникали "паразитные флаги".

5. В результате замен получается битовая последовательность Д' длины N' (меньше N !).

6. Продолжаем перебор (цикл в п.2) до тех пор, пока не найдём значение seed, дающее удовлетворяющую нас степень сжатия К= N/N'

7. Архивный файл представляет собой структуру из трёх элементов: Ф, s, Д' .
______________________________

PS. Как вариант, в качестве флага Ф можно использовать вообще любую последовательность битов, желательно редко встречающуюся в Д, поскольку "естественные" вхождения Ф в Д нужно будет маркировать посредством, например, удвоения: Ф -> ФФ. (И потом нужно будет следить, чтобы дополнительные ФФ не возникали в процессе сжатия.)

А обратно как распаковать? Вот прямо с коротким примером можете?
Что значит "последовательности битов, длиной больше М заменяем ..."? Насколько больше? На фиксированное число битов? Если заменять последовательности произвольной длины больше М, то как вы потом исходную длину узнаете?
Вот допустим у вас на выходе Ф=101 и Д'=1011101, ну и s какой-то, как вы это распакуете? Вы же даже N не планируете сохранять.
...
Рейтинг: 0 / 0
10.01.2018, 12:48
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581686
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Barlone,

да, длину каждого заменяемого куска нужно будет вписывать в результирующий файл. Что несколько снизит степень сжатия.
...
Рейтинг: 0 / 0
10.01.2018, 13:13
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581697
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Ну вы хоть какие-то оценки пробовали делать? Вот какая вероятность найти хотя бы одну совпадающую последовательность битов длины M в двух последовательностях длины N, одна из которых случайная? Приблизительно (N-M)/(2^M). Не сожмется у вас ничего.
...
Рейтинг: 0 / 0
10.01.2018, 13:30
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581704
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Да, с первой попытки вряд ли сожмётся. Потому в заголовок и вынесено слово "ресурсоёмкий".
...
Рейтинг: 0 / 0
10.01.2018, 13:41
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581706
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Формула, которую вы написали -- это не "хотя бы одну совпадающую последовательность", а "КОНКРЕТНУЮ совпадающую последовательность (хотя бы один раз)".
...
Рейтинг: 0 / 0
10.01.2018, 13:43
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581708
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXS1. Находим битовую последовательность минимальной длины M, которая ни разу не встречается в Д. Назовём её "флаг" (Ф).

2. В цикле перебираем значения seed (s), используемые для инициации ГПСЧ: ГПСЧ(s).

3. Посредством ГПСЧ(s) генерируем случайную последовательность (СП) той же длины N.

4. Сравниваем побитово Д и СП. Все совпадающие - в Д и СП - последовательности битов, длиной больше М заменяем (в Д !) на флаг Ф. При этом следим, чтобы "на стыках" вставляемого флага и соседних исходных битов Д не возникали "паразитные флаги".

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

1. ГПСЧ старается генерить последовательность разных чисел, т.е. повторы достаточно редки. А у нас идут повторы букв и слогов.

2. ГПСЧ выдает значения из всего заданного диапазона, а в тексте используется только часть.

ИМХО таким алгоритмом лучше всего будет белый шум сжиматься.
...
Рейтинг: 0 / 0
10.01.2018, 13:46
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581714
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

дык, потому и http://www.sql.ru/forum/1282108/ob-odnom-paradokse-informacionnoy-entropii
...
Рейтинг: 0 / 0
10.01.2018, 13:51
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581725
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneНу вы хоть какие-то оценки пробовали делать? Вот какая вероятность найти хотя бы одну совпадающую последовательность битов длины M в двух последовательностях длины N, одна из которых случайная? Приблизительно (N-M)/(2^M). Не сожмется у вас ничего.
+1

Немного по-другому рассуждаю: ГСПЧ должен генерить последовательность всех возможных вариантов комбинаций по M байт или M*8 бит, Т.е. всего 2^(M*8). Таким образом для инициализации ГСПЧ потребуется значение размером M*8 бит. Плюс надо указывать размер сколько байт прочитать. В итоге имеем "архив" размером больше оригинала.

Я понимаю что могут попасться последовательности длиннее М, но это редкий случай и им можно пренебречь. Поэтому считаю что "архив" почти всегда будет размером больше оригинала.
...
Рейтинг: 0 / 0
10.01.2018, 14:08
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581739
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

не могу понять, что вы написали. Зачем вообще скакать -- в рассуждении и изложении - с битов на байты и обратно?

"ГПСЧ должен генерить" ... (псевдо-)случайную последовательность битов указанной длины. Всё, больше ничего от него не требуется.

(Да, seed нужно будет тоже записать в создаваемый архив, я знаю.)
...
Рейтинг: 0 / 0
10.01.2018, 14:23
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581749
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima T,

не могу понять, что вы написали. Зачем вообще скакать -- в рассуждении и изложении - с битов на байты и обратно?
Незачем, полет мысли так шел, но сути это не меняет :)

Иван FXS"ГПСЧ должен генерить" ... (псевдо-)случайную последовательность битов указанной длины. Всё, больше ничего от него не требуется.
Я к тому что для инициализации ГПСЧ, который может выдать нужную последовательность в M-бит, потребуется не менее M-бит. Это в лучшем случае.
...
Рейтинг: 0 / 0
10.01.2018, 14:42
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581759
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще раз, кратко, в битах:

Нам надо M бит найти. Чтобы точно нашлось последовательность должна содержать 2^M комбинаций, т.е. все комбинации из M бит.
Следовательно чтобы сохранить адрес нужной комбинации в последовательности (или инициализировать ГПСЧ) нам потребуется минимум М бит.

Вывод: ничего не сожмется.
...
Рейтинг: 0 / 0
10.01.2018, 14:52
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581761
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

вы утверждаете, что предложенный метод не позволит ни разу сжать входную строку ни на один одинёшенек битик, пока мы не переберём всё(!) множество битовых строк длины М?

Я готов принять это утверждение как гипотезу, но доказательства его пока не вижу ... (При том, что предложенный метод сжатия тоже не доказан, то есть гипотетичен ...)

Давайте начнём с того, что среди "всего множества битовых строк длины М" присутствует просто сама строка Д, и на каком шаге она нам попадётся -- непредсказуемо.
...
Рейтинг: 0 / 0
10.01.2018, 14:53
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581771
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

а, сорри, я тут точно запутался в обозначениях длин (N и М) ... но и вы, кажется, тоже: что значит, например, ваше
Dima TНам надо M бит найти?

Мы сравниваем две строки и, если находим локальное совпадение, то у него есть длина (которую я обозначил М).

У строк
"11111111111111111111111111111111" и
"00011111000000000000000000000000" - есть совдадение с М=5 начиная с 4-й позиции.
...
Рейтинг: 0 / 0
10.01.2018, 15:01
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581774
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
(ой, что-то я совсем забыл исходные обозначения ... далеко уже уехал.)
...
Рейтинг: 0 / 0
10.01.2018, 15:03
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581787
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Иван FXSДа, с первой попытки вряд ли сожмётся. Потому в заголовок и вынесено слово "ресурсоёмкий".Ну да. Если под "ресурсоемкий" понимать "за триллион лет что-нибудь найдем", тогда конечно.
...
Рейтинг: 0 / 0
10.01.2018, 15:12
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581792
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
То, что я написал сегодня*, проистекает из этой (описанной в этом топике) задачки следующим образом.

1. Нам нужно сжать строку S (длины N).

2. Мы берём псевдослучайную строку Z (той же длины N) и проверяем, не поможет ли она нам сделать это (п.1).

3. В этом топике я описал конкретный способ такого сжатия.

4. А сегодня (в *) я говорю: давайте просто перекодируем строку S через строку Z в строку R. И попробуем сжать полученную строку R каким угодно архиватором.

5. Если получилось -- бинго! Если нет -- возвращаемся в п. 2.

_____________________
* http://www.sql.ru/forum/1282108/ob-odnom-paradokse-informacionnoy-entropii
...
Рейтинг: 0 / 0
10.01.2018, 15:16
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581800
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima T,

а, сорри, я тут точно запутался в обозначениях длин (N и М) ... но и вы, кажется, тоже:
Есть такое, но я тебя понимаю :)

Иван FXSчто значит, например, ваше
Dima TНам надо M бит найти?

Мы сравниваем две строки и, если находим локальное совпадение, то у него есть длина (которую я обозначил М).

У строк
"11111111111111111111111111111111" и
"00011111000000000000000000000000" - есть совдадение с М=5 начиная с 4-й позиции.
Ты рассматриваешь редкий частный случай, когда есть совпадение. Я рассматриваю вариант что в последовательности есть все комбинации для М=5. Т.к. если они не все, то запись будет еще неэффективнее, т.к. придется использовать более короткие подстроки.


Давай чуть упростим задачу: есть строка М бит и какая-то последовательность. Без разницы откуда она берется (ГПСЧ, массив и т.д.).

Чтобы случайная строка размером М гарантированно присутствовала в последовательности, необходимо последовательность размером 2^М строк, т.к. всего возможно 2^М комбинаций по М бит.
Следовательно наша последовательность должна содержать все возможные комбинации. Для указания нужной комбинации надо переменную размером М бит.

Или другими словами: чтобы идентифицировать нужную комбинацию из М бит надо хранить М бит.
...
Рейтинг: 0 / 0
10.01.2018, 15:24
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581811
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
А то что ты думаешь что в последовательности найдется чудесное место где за искомой строкой в М бит будет стоять строка, которую ты будешь искать на следующем шаге, то тут ты сильно заблуждаешься, т.к. вероятность такого события почти нулевая.

Вывод: хоть сколько переборов делай, но в итоге "архив" будет больше исходного файла. За исключением некоторых частных случаев.
...
Рейтинг: 0 / 0
10.01.2018, 15:34
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581824
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima TДавай чуть упростим задачу это мне кажется, или вы в самом деле (пока) обсуждаете только один (служебный) пункт -- выбор "флага" (для конкретной входной строки)?

Просто я перечитал (наконец) свои собственные обозначения в задаче. М - это длина флага.
...
Рейтинг: 0 / 0
10.01.2018, 15:45
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581829
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
BarloneИван FXSДа, с первой попытки вряд ли сожмётся. Потому в заголовок и вынесено слово "ресурсоёмкий".Ну да. Если под "ресурсоемкий" понимать "за триллион лет что-нибудь найдем", тогда конечно."триллион", маловато, имхо.
всего-то 10 в степени 12 нулей.
...
Рейтинг: 0 / 0
10.01.2018, 15:49
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581842
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima TДавай чуть упростим задачу это мне кажется, или вы в самом деле (пока) обсуждаете только один (служебный) пункт -- выбор "флага" (для конкретной входной строки)?

Просто я перечитал (наконец) свои собственные обозначения в задаче. М - это длина флага.
Это только кажется. У тебя же на каждой итерации какая-то одна конкретная строка (или флаг) конкретной длины М бит.

По моим рассуждениям на каждой итерации будет записано не менее М бит. И не влияет что на разных итерациях у М разные значения.

Алгоритм не рабочий. Не будет он жать.
...
Рейтинг: 0 / 0
10.01.2018, 16:02
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581850
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima Tна каждой итерации какая-то одна конкретная ... флаг)нет, флаг выбирается один раз -- для исходной строки. Если она: "101010111001110101011111100111001111111111", то флаг "000" и точка.
...
Рейтинг: 0 / 0
10.01.2018, 16:09
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581865
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima Tна каждой итерации какая-то одна конкретная ... флаг)нет, флаг выбирается один раз -- для исходной строки. Если она: "101010111001110101011111100111001111111111", то флаг "000" и точка.
Я не совсем понял суть флага. Он для чего?

Объясняю как понял: есть ГПСЧ и данные, т.е. то что сжимаем.
В результате данные надо привести к такому виду:
Код: plaintext
seed 0 ,len 0 ,seed 1 ,len 2  ... seed K ,len K

где
seed i инициализация ГПСЧ
len i сколько бит прочитать из ГПСЧ

В итоге ищем результат, имеющий наименьшую длину. Правильно?
...
Рейтинг: 0 / 0
10.01.2018, 16:20
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581876
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Понял про флаг. Ты немного другим путем пошел.

Имеем Данные. Придумываем флаг чтобы не было внутри данных.
Подбираем: подстроку данных (М бит) и seed, так чтобы ГПСЧ(seed) выдавал эти М бит.
Заменяем подстроку на {флаг, seed, М} в том случае если они меньше M, т.е. получаем пожатые Данные.

Правильно?
...
Рейтинг: 0 / 0
10.01.2018, 16:31
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581880
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
нет.
Если исходная строка -
Код: plaintext
"10101011100111010101 1111 1001111001 1111111111 "
, то флаг "000", как и описано в п.1

Если случайная строка, внезапно, получилась
Код: plaintext
"11111111111111111111111111111111111111111111"
, то сжатая будет:
Код: plaintext
"10101011100111010101 000 100111001 000 "
(плюс отдельно нужно будет передать длины двух "флагированных" отрезков.
...
Рейтинг: 0 / 0
10.01.2018, 16:34
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581885
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima TЗаменяем подстроку на {флаг, seed, М} в том случае если они меньше M, т.е. получаем пожатые Данные.
Если так, то не найдется таких комбинаций, т.к. для хранения seed потребуется места столько же сколько занимает исходная подстрока, это я выше доказал. За исключением редких частных случаев.
...
Рейтинг: 0 / 0
10.01.2018, 16:38
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581886
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSнет.
Если исходная строка -
Код: plaintext
"10101011100111010101 1111 1001111001 1111111111 "
, то флаг "000", как и описано в п.1

Если случайная строка, внезапно, получилась
Код: plaintext
"11111111111111111111111111111111111111111111"
, то сжатая будет:
Код: plaintext
"10101011100111010101 000 100111001 000 "
(плюс отдельно нужно будет передать длины двух "флагированных" отрезков.
А где seed для инициализации ГПСЧ?
...
Рейтинг: 0 / 0
10.01.2018, 16:43
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581890
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

тоже нужно будет передавать, это уже написано - в п.7 исходного поста.
...
Рейтинг: 0 / 0
10.01.2018, 16:47
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581895
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima Tдля хранения seed потребуется места столько же сколько занимает исходная подстрока, это я выше доказал я это ваше доказательство не вкурил, извините. Что за "исходная под -строка"?
...
Рейтинг: 0 / 0
10.01.2018, 16:53
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581897
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima T,

тоже нужно будет передавать, это уже написано - в п.7 исходного поста.
В случае если повторов подстроки будет найдено 2 и более, то нахождение пожатого варианта становится более вероятно, но размер пожатого будет меньше на какие-то единицы бит.

И я придумал как эту задачу порешать за один проход всех вариантов seed :)
...
Рейтинг: 0 / 0
10.01.2018, 16:54
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581907
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima Tдля хранения seed потребуется места столько же сколько занимает исходная подстрока, это я выше доказал я это ваше доказательство не вкурил, извините. Что за "исходная под -строка"?
Например чтобы нашлось 1111 (это исходная подстрока), т.е. 4 бита ГПСЧ должен иметь минимум 2^4 вариантов seed, поэтому чтобы записать конкретное значение seed надо будет 4 бита.

Хотя для твоего алгоритма доказательство не совсем корректно, т.к. найти надо какой-нибудь один из всего множества, т.е. вероятность выше, но чувствую что не намного, осталось придумать как это обосновать.
...
Рейтинг: 0 / 0
10.01.2018, 17:06
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581912
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

"Например чтобы нашлось 1111 (это исходная подстрока)" ... в одной конкретной позиции ... "ГПСЧ должен иметь минимум 2^4 вариантов seed"

-- но нам совершенно не обязательно, чтобы нашлось именно "1111" и именно в этой позиции.
...
Рейтинг: 0 / 0
10.01.2018, 17:11
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39581927
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXS-- но нам совершенно не обязательно, чтобы нашлось именно "1111" и именно в этой позиции.
Верно, я потому и написал "доказательство не совсем корректно".

Надо отталкиваться от другого: какой макс.длины подстрока наиболее вероятно найдется? Думаю М бит, где М такое что 2^M меньше всех возможных комбинаций seed. Потому что ГПСЧ может выдать больше всего различных комбинаций по М бит.

Дальше надо посчитать как-то вероятность получения совпадения M+1 бит, M+2 и т.д. Не соображу как, но чувствую что каждый доп.бит уменьшает вероятность вдвое, т.е. сэкономить пару байт это уже достаточно редкий случай.
...
Рейтинг: 0 / 0
10.01.2018, 17:24
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39583939
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
SiemarglЭто обычный алгоритм LZW, только с ошибками и случайно-генеруемым словарем :fail:
только вы то ли не заметили, то ли решили умолчать о том, что "генерируемый словарь" означает, что словарь не класть в выходной файл (увеличивая его размер), как это делается в LZW.

("С ошибками" я не понял, поэтому отнестись не могу.)
...
Рейтинг: 0 / 0
14.01.2018, 15:18
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39583940
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Иван FXSсловарь не нужно класть в выходной файл
...
Рейтинг: 0 / 0
14.01.2018, 15:22
| Ответить | Цитировать | Написать  
Об одном способе ресурсоёмкого сжатия данных
    #39583961
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Сейчас, почти через две недели, я бы по-другому сформулировал концепцию сжатия (гипотетическую, конечно, поскольку осуществимость её не доказана). А именно, я бы заменил "флаг" (который непонятно-какой-длины) на "цепную адресацию":

Есть данные Д - битовая строка длины N, - которую требуется сжать, и стандартный ГПСЧ.

1. В цикле перебираем значения seed (s), используемые для инициации ГПСЧ: ГПСЧ(s).

2. Записываем s в начало выходного файла.

3. Посредством ГПСЧ(s) генерируем случайную последовательность (СП) той же длины N.

4. Устанавливаем "счётчик цепной адресации" в ноль: А=0.

5. Сравнивая побитово Д и СП, движемся вдоль них обеих до тех пор, пока не находим в них (по "цепному адресу" А) одинаковую подстроку (П) длиной М.

6. Если используемая нами нотация записи целых чисел позволят записать эти два числа (А и М) короче, чем М битов, то записываем их в начало выходного файла. И записываем в его конец очередную порцию несжатых битов - те, что шли до П (то есть подстроку П "выбрасываем", не пишем в выходной файл).

(6.1. Кстати, мы можем постановить, что с подстроками короче М0 связываться принципиально не следует; тогда записывать нужно не М, а разницу М-М0, что чуточку выгоднее.)

7. Если условие, описанное в п. 6, выполнено, переходим на п.4; если не выполнено -- переходим на п.5. Дальнейшее сканирование строк -- в любом случае -- продолжается с первого бита после подстроки П.

8. Дойдя до конца строки Д, оцениваем полученный вариант сжатия: если он лучше всех предыдущих, сохраняем его, если нет -- забываем. И переходим к п.1 .
...
Рейтинг: 0 / 0
14.01.2018, 16:49
| Ответить | Цитировать | Написать  
60 сообщений из 60, показаны все 3 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Об одном способе ресурсоёмкого сжатия данных
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]