Форум программистов, компьютерный форум, киберфорум
Наши страницы

Непризнанные теории, гипотезы

Войти
Регистрация
Восстановить пароль
 
 
артист
93 / 19 / 5
Регистрация: 17.09.2014
Сообщений: 1,178
Завершенные тесты: 2
#1

Как написать лучший алгоритм сжатия - Теории

28.12.2016, 20:36. Просмотров 792. Ответов 26
Метки нет (Все метки)

Проснулся сегодня в 5 часов утра, приснилось что я алгоритм сжатия данных придумал, да такой, что можно сжать любой размер до 1го байта, о как.
Странно кстати, я вообще сжатием не интересовался до этого ни разу...
Ну врубил комп, давай вспоминать чего там снилось, толком ничего не вспомнил, помню только 2 байта в 1 методом каких-то операций.
Пол утра считал, и так и так, ну никак нельзя 8 нулей||единиц засунуть в 4...

Пробовал в 4 прохода с множителем - нифига.

В итоге наморосил какой-то бред в текстовике:
Кликните здесь для просмотра всего текста
0-255 диапазон

1 200 - два байта для сжатия.

255 почему-то должно присутствовать...

200 - 1 = 199
255 - 199 = 56

255 / 1 = 255

255 / 200 =


11111111 = 256
1111111 = 127
111111 = 64
11111 = 32
1111 = 16

0000 - 0 0 и 0
0001 - 1 0 и 1
0010 - 2 0 и 2
0011 - 3 0 и 3
0100 - 4 1 и 0
0101 - 5 1 и 1
0110 - 6 1 и 2
0111 - 7 1 и 3
1000 - 8 2 и 0
1001 - 9 2 и 1
1010 - 10 2 и 2
1011 - 11 2 и 3
1100 - 12 3 и 0
1101 - 13 3 и 1
1110 - 14 3 и 2
1111 - 15 3 и 3


200 / 2 = 100 / 2 = 50 / 2 = 25 / 5 = 5 / 5 = 1
200 / 3 = 66,66666666666667
200 / 4 = 50 / 4 = 12,5
200 / 5 = 40 / 5 = 8 / 5 = 1,6
200 / 6 = 33,33333333333333
200 / 7 = 28,57142857142857
200 / 8 = 25

200 / 4 = 50
50 / 5 = 10
10 / 2 = 5
5 / 5 = 1

0001 1 * 1
00001 1 * 1
000001 1 * 1
0000001 1 * 1

0010 1 * 2
00010 2 * 1
000010 2 * 1
0000010 2 * 1

0011 1 * 2
00010 2

200 \ 2 = 100


256 - 1 = 254
128 - 254 = -127
64 - -127 = 191
32 - = -159
8
4
2

255
127.5
63,75
31,875
15,9375


11001000 = 200

200 / 255 = 0,7843137254901961 ~ 0.78

1001110 = 78

78 / 127 = 0,6141732283464567 ~ 0.61


Потом загуглил, есть 2 типа сжатия, и все работают на повторении.
1й - когда подряд идут одинаковые байты, 2й - когда в файле встречаются одинаковые байты...

Вот и верь после этого снам...

Добавлено через 6 часов 24 минуты
Да не стоило в отдельную тему, это я как пример ТСу, что не все сны сбываются...Я вообще не интересуюсь такими вещами как сжатие ))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2016, 20:36
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Как написать лучший алгоритм сжатия (Теории):

У какого архиватора лучший метод сжатия? - Программы архиваторы
Может и тупой вопрос но спрашиваю почему 100мб данных обычный способ сжимает лучше чем максимальный? и вобще что лучше сжимает рар или...

Алгоритм сжатия - Pascal
целочисленную таблицу из n-элементов переписать так, чтобы вместо одинаковых, идущих подряд элементов оставался только один. Заранее...

Алгоритм сжатия LZ - C++
Если у кого есть, поделитесь кодом, пожалуйста:-/

.NET 4.x Алгоритм сжатия Jpeg - C#
У кого ни будь есть готовый Алгоритм сжатия Jpeg? Хотя бы самый простой без задания качества итд. Причем нужен именно самостоятельно...

Алгоритм сжатия RLE - C#
Здравствуйте, очень нужна помощь в задании! Просто очень срочно, пожалуйста! Написать программу способную сохранять в файл и загружать из...

Алгоритм сжатия Хаффмана - Delphi
Мне нужно реализовать сжатие текста алгоритмом Хаффмана. Я нашел неплохой исходник, но там дерево сохраняется в текстовую переменную а...

26
gazlan
3139 / 1915 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
02.02.2017, 20:33 #16
Именно, софистика.

Ваш трехмерный мир - игра в песочнице. Мегабайт текста имеет миллион координатных осей и, в общем случае (литературный текст) порядка 200,000 степеней свободы (независимых обобщенных координат). Задачи компрессора: 1. найти эти оси и 2. "примять углы", так чтобы среднее расстояние от барицентра до вершины для всех осей было примерно одинаково (рассматривайте это как процесс многомерной шлифовки: выступы срываются, впадины засыпаются).

Сдвиг и Поворот - это упрощенная двумерная аналогия, речь идет о многомерной деформации, инвариант которой - энтропия фрактала.

Представьте, например, конденсацию пара в жидкость - тот несжимаемый объем, в который, в конечном итоге, превратится паровой фрактал, и есть энтропия.
0
артист
93 / 19 / 5
Регистрация: 17.09.2014
Сообщений: 1,178
Завершенные тесты: 2
02.02.2017, 22:18  [ТС] #17
Операционная система на 3м счислении была уже давно придумана, вроде в россии, и работала быстрее...

Если сжать хотя бы 3 байта в 2 - это уже будет круто.

Байт(всегда число) как всем тут известно имеет диапазон 0-255 и 8 бит(всегда 0 или 1).
Просто я как ни крутил, зашифровать(сжать точнее) число в само себя не получается.
Т.е. можно брать 24 бита и зашифровывать их в 16 битах.

Например 1й бит в зашифрованном виде может говорить не является ли 1 байт 0м, 2й бит - для 2го байта, 3й - для 3го.
Дальше идет некая последовательность оперирования числами, если присутствует в 3х байтах 0, то оставшиеся 13 байт применяются для 2х.
Если нет нолей тогда уже делятся на 3 байта, и каким-то образом шифруются.

Это так, приблизительная схема, как я пытался сделать.
Только я 2к1 пробовал, и понял, что это невозможно, даже не обладая средними знаниями математики.
0
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
03.02.2017, 11:28 #18
Цитата Сообщение от артист Посмотреть сообщение
Байт(всегда число) как всем тут известно имеет диапазон 0-255 и 8 бит(всегда 0 или 1).
Байт - это условность. Не на всех машинах байт = 8 бит.Из вики:
Из вики: "Однако в истории компьютерной техники существовали решения с иными размерами байта (например, 6, 32 или 36 битов)". И не только с этим количеством, были еще 7 бит.
Алгоритм упирается в принятую систему исчисления.
Если "разворачивать" число в другой системе исчисления и возвращать его обратно, то оно вернется с потерями?
Не использовать для вычислений XOR, а использовать только NOT и CNOT.
Да и для начала нужно четко определить , что такое сжатие? Что мы собираемся "сжимать"?

Добавлено через 1 минуту
Число - это по сути частично реализованная абстракция.

Добавлено через 1 час 28 минут
Null, 1,2,3,4,5,6,7,8,9, Десять(тут нет никакого перехода через 0)
0
артист
93 / 19 / 5
Регистрация: 17.09.2014
Сообщений: 1,178
Завершенные тесты: 2
03.02.2017, 18:45  [ТС] #19
Сжимать размер нулей и единиц естественно.

Можно брать хоть по 9 бит(просто диапазон будет больше, 0-510) или по 4(диапазон 0-15), главное и неизменное - это 0 и 1, а данные, это просто поток.
Просто если брать нестандартную длину, то нужно будет кроме шифровки ещё и длину данных запаковывать...
Хотя и так, если сжатие будет 4 к 3, то уже длина данных не всегда будет делиться ровно на 4...

Добавлено через 17 минут
Сам не знаю для чего нужно представлять данные в виде чисел(просто в двоичном виде уже есть алгоритмы, и они просто на повторы идут), с числами удобнее работать.
Подумал так, и в итоге получается нужно придумать иную систему, которая будет короче всё это делать.

Например вот взять те же числа, 0 записывается в виде восьми нулей(допустим байт == 8 бит).
А мог бы записываться 1м байтом, просто 0.
Так же например 3 - это 6 нулей и 2 единицы в конце, а можно записать его как 2 единицы.
Т.е. отбрасывание нулей слева.
Но в таком случае, как понять где концается одно число, и начинается другое?
Разделителем, например 2 нуля, раз нолей может быть только 1.
Много конечно таким образом не сожмёшь, да и сжатие данных может быть только 1 раз, как и с повторяющимися битами...
И скорее всего такой алгоритм тоже уже давно придуман
0
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
04.02.2017, 06:08 #20
Алгоритм скорее всего придуман. Но не обязательно.
Вопрос - как упаковать если у нас осталось 0 1 или 1 0. Пусть при этом 0 изобразим как круг а один как квадрат.
так мы выходим за рамки двоичного измерения. 0 1 будет у нас фигура квадрат в окружности, а 1 0 окружность в квадрате. Так мы вроде упаковали два в одно, без потери информации.

Добавлено через 11 минут
Но нам понадобилось для этого дополнительная информация - то что это окружность,a это квадрат.
И еще понадобилось знать окружность в квадрате или квадрат в окружности.
B в какой-то момент нам опять нужно эту информацию где-то хранить.
0
артист
93 / 19 / 5
Регистрация: 17.09.2014
Сообщений: 1,178
Завершенные тесты: 2
04.02.2017, 10:32  [ТС] #21
Не подумал, ведь есть числа, в которых есть нули и в середине, например:

10000001
01100101
01001100

Так, что с делителем неувязочка. ))

Если не трогать нули и 1цы, а работать только с числами...

Зашифровать 2 в 1м.

Взять два числа, 5 и 189.
Разница между ними 5 - 189 = -184.
Зная разницу, можно получить любое из этих чисел.

1е: 189 + (-184) = 5
2е: 5 - (-184) = 189

Но чтобы получить другое число, нужно знать одно из них.
Таким образом опять получается 2 числа, да ещё и с операциями.
____________________________________________________________

Другой вариант, умножение.
Можно записать число в виде уравнения.
Запись большого числа, 2мя маленькими числами.

Например 100, его можно представить в виде 2х целых множителей:
50 * 2
25 * 4
20 * 5
10 * 10

Все эти числа в 2м виде(в скобках длина без нолей слева):
01100100 = 100 (7)
00110010 = 50 (6)
00011001 = 25 (5)
00010100 = 20 (5)
00001010 = 10 (4)
00000101 = 5 (3)
00000100 = 4 (3)
00000010 = 2 (2)

Теперь, если сложить длину записываемых чисел(множителей), получается:
6 + 2 = 8
5 + 3 = 8
5 + 3 = 8
4 + 4 = 8

В итоге никакого уменьшения длины не получилось.
Кто знает математику получше меня, наверное подумает, что за ахинея, ведь 2я система так и работает, на умножении разрядов... ))
И по сути в 2м представлении биты просто разорвали в определенных местах.

Ну так вот, а что если ввести некие постоянные числа, на которые число будет умножаться N количество раз.
Дальше моих знаний не хватило, по сути я сейчас просто описал то, что у меня в 1м посте под спойлером...

Было бы прикольно, сидишь такой в интернете, у тебя спрашивают: смотрел такой-то фильм?
Ты: нет.
Тебе: Посмотри. 10111001. Пережатие = 120067070. Длина 980156504 байт.
Конечно распаковка заняла бы много времени(и зависела бы только от мощности пк), но зато как быстро было получено...
0
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
04.02.2017, 18:16 #22
Такая идея пришла в голову: Если передавать информацию через центр Земли, то пути интернета станут короче.
Довольно сложно реализовать радиосвязь в диапазоне сверхдлинных волн и длинных волн.
А упаковывать инфу можно амплитудной, частотной и фазовой модуляцией.
0
gazlan
3139 / 1915 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
05.02.2017, 05:48 #23
Для тех, кто в самом деле интересуется темой:
  • О цифровых сигналах и их обработке стоит почитать у Л.М. Финк ("Теория передачи дискретных сообщений", "Сигналы, помехи, ошибки").
  • Большинство алгоритмов сжатия не используют позиционную систему счисления и никакие - двоичную. В двоичном алфавите сжатие невозможно "по определению".
  • В целом, сжатие - очень частный случай компиляции (как трансформации текста по заданным правилам). Но в отличие от аннотирования, рецензирования и проч., сжатие без потерь требует существования обратной процедуры - "декомпиляции".
0
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
05.02.2017, 10:52 #24
Вот интересная статья про сжатие текстов : http://www.compression-pointers.ru/compress_169.html
Но для дальнейшего сжатия на компьютере мы упирается в представление чисел в памяти компьютера в двоичной системе исчисления.
Такие параметры как "скорость" "упаковки" и "скорость" распаковки для нас тоже важны.

Добавлено через 17 минут
Единици представления информации.
Опять деление: качественное представление и количественное представление.

Добавлено через 14 минут
Как представить единицу измерения запаха и вкуса.

Добавлено через 3 минуты
Представим единицу измерения информации как образ.
0
Ixmil
1 / 18 / 0
Регистрация: 17.06.2013
Сообщений: 587
14.02.2017, 08:47 #25
Увожаемый артист, Прочитал вашу первую надпись. (хотя "месяц" назад), Вы просто "спотыкаетесь о подробности".
Но сон вам подсказал скорей всего верно. Надо просто наплевать на точности. Весовую категорию сжатия которого вы привели - называют сжатием с потерями, где часть данных или не востановима, или в восстановленном уравнении так и остаётся иксом. В точной степени, этот способ - не достижим, (хотя и слова которыми я пользуюсь тоже далеки от точности). Возможности сжатия без потерь, я прекрасно знаю, поскольку таковых алгоритмов написал, наверно тысячи. Писал и вроде тех что у вас. Но как план конспект.


Цитата Сообщение от артист Посмотреть сообщение
Пол утра считал, и так и так, ну никак нельзя 8 нулей||единиц засунуть в 4...
Это только в рамках стандартной, и такой педантичной логики - нет. Причём в математике есть маса правил, вращающихся вокруг, этого нет.
Короче говоря можно засунуть, но не очень точно. Можно очень, не точно, можно в половину или в четверть неточно, и т.д.


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


В идеях самые ценные - которые вкусно пахнут, но где то нехватает важной шестерёнки, из за чего думается что идея непригодна. Но именно она и есть самая ценная. И лучше записывать такие идеи, а понимание , и как доделать - скорей всего придут позже.
0
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
26.02.2017, 11:40 #26
Мне мысль такая пришла в голову. Слова чем отличаются? Блондинка сказала буквами.
Ну,тогда, предположим слова [гора] [рога] они чем отличаются, только расположением букв.
Но главная мысль не в этом. Правильный ответ будет - слова отличаются смыслом. Сама по себе буква смысл не несет.
Теперь сожмем два слова гора и рога в два символа. ^ - гора. Такой же символ перевернутый рога.
Тогда китайские иероглифы дают нам наибольшую степень сжатия.
0
артист
93 / 19 / 5
Регистрация: 17.09.2014
Сообщений: 1,178
Завершенные тесты: 2
26.02.2017, 18:24  [ТС] #27
Это типа в программе вбить все слова, а передавать их короткий ид?
0
26.02.2017, 18:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2017, 18:24
Привет! Вот еще темы с ответами:

Алгоритм сжатия PPM-D - C++
Может кто рассказать о алгоритме сжатия PPM-D и как его реализовать или покидайте ссылки, литературу какую то (Гугл не предлагать, искал,...

Алгоритм сжатия Хаффмана - C#
помогите пожалуйста с данным алгоритмом, моя программа работает, вот только не сжимет, а наоборот, размер становится больше! Этот алгоритм...

Алгоритм сжатия данных - C#
Помогите пожалуйста, необходимо создать программное приложение сжатия данных алгоритмом LZ77

Алгоритм сжатия данных - C++
подскажите алгоритм сжатия данных, чтобы был не очень сложный и в то же время эффективный


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru