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

User Tag List

Страница 3 из 4 ПерваяПервая 1234 ПоследняяПоследняя
Показано с 21 по 30 из 36

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

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

    По умолчанию

    Цитата Сообщение от HardWareMan Посмотреть сообщение
    К сожалению, только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.
    в принципе можно ужать фаил в одну хеш суму 2К
    а потом бруталфорсом перебирать все возможные варианты файла

    так же можно сохранить указатель какой по счету файл с такой хеш суммой соответствует исходному

    только этот файл должен быть с контролем ошибок

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

    но это из разряда первую половину вечности файл пакуем
    вторую распаковываем....

    - - - Добавлено - - -

    Цитата Сообщение от HardWareMan Посмотреть сообщение
    только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.
    вот только путь к нужной книге будет занимать больше места чем сама книга...

    - - - Добавлено - - -

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

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

    По умолчанию

    Цитата Сообщение от NEO SPECTRUMAN Посмотреть сообщение
    один из них будет соответствовать тому что мы запаковали
    Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных (пусть даже текста, ибо не факт, что ему можно будеть объяснить, что "Сильмариллион" это осмысленный текст), как компьютер узнает, какой именно текст мы запаковали?
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

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

    По умолчанию

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных (пусть даже текста, ибо не факт, что ему можно будеть объяснить, что "Сильмариллион" это осмысленный текст), как компьютер узнает, какой именно текст мы запаковали?
    дык кодирование с контролем ошибок
    контрольные суммы на каждые 256 байт например
    номер файла с такой же хеш суммой по счету (скорей всего будет гигантских размеров)
    ИИ (в далеком будещем например)


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

    - - - Добавлено - - -

    Цитата Сообщение от NEO SPECTRUMAN Посмотреть сообщение
    Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных
    проблема не так проверить осмысленность данных
    а перебрать все возможные комбинации байтов файла (ну или не все можно и как то оптимизировать)

    при самых простых контрольных суммах на это уйдет неимоверное количество времени

    но оно хорошо дружит с многопоточностью!!!

    - - - Добавлено - - -

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    какой именно текст мы запаковали?
    наверное придется перебирать ручками
    а оно ли это
    наверное это не сильно далеко уходит от "библиотеки" которую упомянул HardWareMan

    понадобится еще целая куча места чтобы описать как отличить нужный файл
    Последний раз редактировалось NEO SPECTRUMAN; 15.08.2017 в 21:16.

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

    По умолчанию

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    Вроде нет. Она определяется вероятностью повторов.
    Энтропия вычисляется на основании вероятностей/частот символов. Простая энтропия - независимыми вероятностями символов, условная - вероятностями с учётом предшествующих символов.

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

    Повторы - это повторяющиеся цепочки символов, я так понимаю? Жмутся не только повторяющиеся цепочки, но и отдельные символы с разной частотой появления. Cуществуют и другие специфические "артефакты" входного потока, поддающиеся сжатию.

    Это и есть перебор: добавили словарь одного размера, посчитали энтропию, добавили второй, опять посчитали и т.д. пока не нашли идеальный размер словаря для конкретных данных.
    Можно просмотреть весь поток/файл полностью, выявить все повторяющиеся цепочки, построить словарь - расширение алфавита, размером с количество входных символов + количество выделенных повторяющихся цепочек. Далее считаем энтропию. Никакого перебора.
    Последний раз редактировалось Spectramine; 15.08.2017 в 21:23.

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

    По умолчанию

    Цитата Сообщение от NEO SPECTRUMAN Посмотреть сообщение
    наверное придется перебирать ручками
    Тогда уж сжимать книгу в код ISBN, а при распаковке брать её с полки и сканировать ручным сканером и распознавать OCR...

    Думацо можно уже прекращать постить тут всякий бред.
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

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

    По умолчанию

    Цитата Сообщение от CodeMaster Посмотреть сообщение
    Думацо можно уже прекращать постить тут всякий бред.
    на основе этого бреда
    мну вспомнил
    один свой старый алгоритм по сжатию (с нимоверно долгой распаковкой)
    и внезапно почти придумал еще один новый (который может даже будет что то жать но явно не в 2к любой файл...)

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

    По умолчанию

    Цитата Сообщение от weiv Посмотреть сообщение
    Повторы - это повторяющиеся цепочки символов, я так понимаю?
    Повторы это повторы, хоть символы, хоть цепочки которые идут подряд.

    Цитата Сообщение от weiv Посмотреть сообщение
    Например, для текста важна зависимость вероятности текущего символа от предыдущего
    Какие зависимости для энтропийного сжатия?

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

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

    По умолчанию

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


    Какие зависимости для энтропийного сжатия?
    Для сжатия с фиксированными частотами символов, зависимостью можно считать общую таблицу частот символов. По оси X - номер символа, по оси Y - его частота. Зависимость, заданная таблично, плюс сумма частот символов =1, то есть частоты взаимозависимы.
    Также для энтропийного сжатия используются зависимости частот символов от N-го количества предыдущих символов (условная энтропия).


    Чего так архиваторы не делают?
    Если размер буфера >= размера файла, они так и делают. В остальном - видимо, ограничения на объем используемой памяти/время архивации поджимают.

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

    По умолчанию

    А где нибудь применяется упаковка с потерями
    а потом отдельная упаковка разницы с оригиналом?

    так чтоб в итоге получалось без потерь

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

    По умолчанию

    Цитата Сообщение от weiv Посмотреть сообщение
    Если размер буфера >= размера файла, они так и делают.
    Появится время, проверю на практике.

    Цитата Сообщение от NEO SPECTRUMAN Посмотреть сообщение
    так чтоб в итоге получалось без потерь
    Практически уверен, что коэффициент сжатия будет меньше, а время больше.
    "Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.

Страница 3 из 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

Ваши права

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