Важная информация

User Tag List

Страница 2 из 4 ПерваяПервая 1234 ПоследняяПоследняя
Показано с 11 по 20 из 36

Тема: Существует ли идеальное сжатие без потери данных?

  1. #11
    Guru Аватар для CodeMaster
    Регистрация
    26.04.2009
    Адрес
    г. Воронеж
    Сообщений
    6,210
    Спасибо Благодарностей отдано 
    131
    Спасибо Благодарностей получено 
    210
    Поблагодарили
    181 сообщений
    Mentioned
    6 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от NEO SPECTRUMAN Посмотреть сообщение
    для каждого типа файла/конкретного файла идеальным будет свое сжатие
    Та это всё понятно. Вот например берём мы Войну и Мир в txt пакуем алгоритмом PPM (будем считать, что он лучший для текста) на выходе мы получим единственно возможный файл с упакованными данными минимального размера независимо от вычислительных возможностей? Другими словами, если нам дан конкретный набор данных и известен его тип, можно математически высчитать его минимальный размер в упакованном виде?

    Цитата Сообщение от nlo_j77 Посмотреть сообщение
    P.S. Похоже на ахинею, но могу обосновать
    Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)
    Последний раз редактировалось CodeMaster; 13.08.2017 в 22:13.
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

  2. #12
    Member Аватар для nlo_j77
    Регистрация
    03.08.2008
    Адрес
    Томск
    Сообщений
    108
    Спасибо Благодарностей отдано 
    2
    Спасибо Благодарностей получено 
    14
    Поблагодарили
    7 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от NEO SPECTRUMAN Посмотреть сообщение
    но как ни старайся в один бит
    больше чем 1 бит данных ты не запихнешь...
    Одного бита вполне хватит для маркера изменённых данных.

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)
    Чтобы упаковать, надо не теоретически доказать, а написать пакер... - за него мне платить точно никто не будет (да и не нужен он никому, ибо больно медленно будет паковать/распаковывать)... - мне работа пока важнее

  3. #13
    Guru Аватар для CodeMaster
    Регистрация
    26.04.2009
    Адрес
    г. Воронеж
    Сообщений
    6,210
    Спасибо Благодарностей отдано 
    131
    Спасибо Благодарностей получено 
    210
    Поблагодарили
    181 сообщений
    Mentioned
    6 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от nlo_j77 Посмотреть сообщение
    Чтобы упаковать, надо не теоретически доказать, а написать пакер...
    Мне пакер не нужен, мне теоретическое обоснование гораздо интереснее.

    Цитата Сообщение от nlo_j77 Посмотреть сообщение
    да и не нужен он никому, ибо больно медленно будет паковать/распаковывать
    Это всё относительно.
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

  4. #14
    Member Аватар для nlo_j77
    Регистрация
    03.08.2008
    Адрес
    Томск
    Сообщений
    108
    Спасибо Благодарностей отдано 
    2
    Спасибо Благодарностей получено 
    14
    Поблагодарили
    7 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Ну смотри - допустим мы преобразуем 8-ми битные данные в 7-ми и добавляем один бит маркера - дальше некоторые байты изменяем (допустим меняем на 0) и помечаем маркером в итоге получается пакующаяся последовательность (до этого ищем что и как изменить чтобы последовательность паковалась), пакуем и получаем опять последовательность (в теории упакованную процентов на 5-10, опять преобразуем данные в 7 бит с добавлением маркера... - в итоге получим нулевую последовательность с двумя словарями распаковки и данными, которые при паковке-преобразовании не будут менять своего размера - который, чисто в теории равен около 512 байт

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

    P.S. немного поясню - у нас непакующаяся последовательность 512 байт, а мы пакуем 513 - после, как минимум 512 проходов, её раздует до намного большего размера, а потом ещё за 512 проходов она упакуется в 512 байт (немного грубо, но смысл передаёт)
    Последний раз редактировалось nlo_j77; 14.08.2017 в 22:43.

  5. #15
    Banned
    Регистрация
    22.05.2011
    Адрес
    г. Дзержинск, Украина
    Сообщений
    6,841
    Спасибо Благодарностей отдано 
    483
    Спасибо Благодарностей получено 
    656
    Поблагодарили
    511 сообщений
    Mentioned
    10 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от nlo_j77 Посмотреть сообщение
    чисто в теории равен около 512 байт
    8 битами как ни старайся можно описать 256 разнообразных уникальных файлов
    как ни старайся ты не упакуешь больше
    это же относится ко всему остальному
    в один бит не вместишь 2Кб рандомных значений...

  6. #16
    Veteran
    Регистрация
    07.10.2006
    Сообщений
    1,640
    Спасибо Благодарностей отдано 
    241
    Спасибо Благодарностей получено 
    249
    Поблагодарили
    155 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    Та это всё понятно. Вот например берём мы Войну и Мир в txt пакуем алгоритмом PPM (будем считать, что он лучший для текста) на выходе мы получим единственно возможный файл с упакованными данными минимального размера независимо от вычислительных возможностей? Другими словами, если нам дан конкретный набор данных и известен его тип, можно математически высчитать его минимальный размер в упакованном виде?



    Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)
    Существует такое понятие, как информационная энтропия. Энтропия сообщения определяет предел сжатия. Так что насчет "всё можно упаковать в 2 кб" - это из области вечных двигателей.

  7. #16
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  8. #17
    Guru Аватар для CodeMaster
    Регистрация
    26.04.2009
    Адрес
    г. Воронеж
    Сообщений
    6,210
    Спасибо Благодарностей отдано 
    131
    Спасибо Благодарностей получено 
    210
    Поблагодарили
    181 сообщений
    Mentioned
    6 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от weiv Посмотреть сообщение
    Так что насчет "всё можно упаковать в 2 кб" - это из области вечных двигателей.
    Это не ко мне обращение.

    Цитата Сообщение от weiv Посмотреть сообщение
    Существует такое понятие, как информационная энтропия. Энтропия сообщения определяет предел сжатия.
    Мне интересен не предел как таковой, а математическое обоснование этого предела. Насколько я понял, вот как раз для энтропийных алгоритмов сжатия можно математически высчитать максимальный коэф сжатия, а для словарных нет, там только методом перебора можно подобрать максимальное сжатие.
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

  9. #18
    Veteran
    Регистрация
    07.10.2006
    Сообщений
    1,640
    Спасибо Благодарностей отдано 
    241
    Спасибо Благодарностей получено 
    249
    Поблагодарили
    155 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    Мне интересен не предел как таковой, а математическое обоснование этого предела. Насколько я понял, вот как раз для энтропийных алгоритмов сжатия можно математически высчитать максимальный коэф сжатия, а для словарных нет, там только методом перебора можно подобрать максимальное сжатие.
    Насколько я понимаю, энтропия сообщения определяется зависимостями символов сообщения. Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга, тем более точно рассчитывается энтропия.

    Словарные методы сжатия кодируют преобразованный алфавит входного потока, дополненный символами повторяющихся цепочек (либо символами длин и смещений). Добавьте эти символы к входному алфавиту, рассчитывайте энтропию с учетом этих символов и - вуаля, можно вычислить энтропию для словарных методов сжатия.
    Последний раз редактировалось Spectramine; 15.08.2017 в 13:25.

  10. #19
    Guru Аватар для HardWareMan
    Регистрация
    26.02.2011
    Адрес
    г. Павлодар, Казахстан
    Сообщений
    4,395
    Спасибо Благодарностей отдано 
    304
    Спасибо Благодарностей получено 
    594
    Поблагодарили
    440 сообщений
    Mentioned
    10 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Вы слышали про вавилонскую библиотеку? К сожалению, только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.

  11. #20
    Guru Аватар для CodeMaster
    Регистрация
    26.04.2009
    Адрес
    г. Воронеж
    Сообщений
    6,210
    Спасибо Благодарностей отдано 
    131
    Спасибо Благодарностей получено 
    210
    Поблагодарили
    181 сообщений
    Mentioned
    6 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от weiv Посмотреть сообщение
    Насколько я понимаю, энтропия сообщения определяется зависимостями символов сообщения.
    Вроде нет. Она определяется вероятностью повторов.

    Цитата Сообщение от weiv Посмотреть сообщение
    Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга
    Не знаю как с зависимостью, но количество повторов в данных, вроде бы, вычисляется однозначно.

    Цитата Сообщение от weiv Посмотреть сообщение
    Добавьте эти символы к входному алфавиту, рассчитывайте энтропию с учетом этих символов и - вуаля, можно вычислить энтропию для словарных методов сжатия.
    Это и есть перебор: добавили словарь одного размера, посчитали энтропию, добавили второй, опять посчитали и т.д. пока не нашли идеальный размер словаря для конкретных данных.

    Цитата Сообщение от HardWareMan Посмотреть сообщение
    Вы слышали про вавилонскую библиотеку?
    А как это относится к данной теме?
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

Страница 2 из 4 ПерваяПервая 1234 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Архивирование, сжатие, упаковка.
    от GriV в разделе Программирование
    Ответов: 30
    Последнее: 22.07.2019, 17:25
  2. RLE сжатие (покритикуйте)
    от Vladson в разделе Программирование
    Ответов: 12
    Последнее: 16.03.2008, 12:29
  3. Ответов: 18
    Последнее: 18.06.2006, 16:50

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •