Сжатие данных с использованием простых чисел

22

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

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

Мой вопрос:

  • Действительно ли это осуществимо, как предполагают авторы? Согласно статье, их результаты очень эффективны и всегда сжимают данные до меньшего размера. Разве размер словаря не будет огромным?
  • Разве это не может быть использовано для повторного повторного сжатия сжатых данных с использованием того же алгоритма? Очевидно и было продемонстрировано, что такие методы (когда сжатые данные повторно сжимаются столько раз, сколько возможно, резко уменьшая размер файла) невозможны; действительно, не было бы биекции между набором всех случайных данных и сжатых данных. Так почему же это кажется возможным?
  • Даже если техника еще не совершенна, она, очевидно, может быть оптимизирована и значительно улучшена. Почему это не более широко известно / изучено? Если эти утверждения и экспериментальные результаты действительно верны, разве это не может революционизировать компьютерные технологии?
Klangen
источник
5
Как вы заметили, газета предъявляет действительно серьезные требования. Всегда очень подозрительно относитесь к таким заявлениям, особенно если статья публикуется в странном месте (удивительные статьи «революционизирующие вычисления» должны появиться в уважаемых известных местах, верно?).
Юхо
2
невозможно «всегда сжимать случайные данные», например, на основе теории сложности Колмогорова . и опровержение похоже на то, как вы набросали. не уверен, что это неверное толкование бумаги или оригинала. почему вы не подчеркиваете, где эта конкретная претензия приходит?
августа
6
«Не может ли это быть использовано для повторного повторного сжатия сжатых данных с использованием того же алгоритма?» - Да. Любой алгоритм, который утверждает, что может сжимать все произвольные данные, может быть рекурсивно применен к его собственному выходу, так что любые данные сжимаются до 0 битов. Таким образом, это требование невозможно.
Йорг Миттаг
1
@ JörgWMittag У меня есть алгоритм, который позволяет многократно сжимать файл до небольшого количества бит, но он крайне непрактичен. Также работает только с файлами, начинающимися с 1 бита: обрабатывать весь файл как большое двоичное число, уменьшать его, а затем отбрасывать начальные 0. Чтобы распаковать, увеличьте его, добавив начальную 1, если необходимо.
user253751
3
Примечание для себя: не беспокойтесь о том, чтобы отправлять какие-либо статьи в любые журналы Elsevier - никогда.
500 - Внутренняя ошибка сервера

Ответы:

34

всегда сжимать случайные наборы данных более чем на 50%

Это невозможно. Вы не можете сжать случайные данные, вам нужна некоторая структура, чтобы воспользоваться преимуществами. Сжатие должно быть обратимым, поэтому вы не можете сжать все на 50%, потому что строк длины гораздо меньше, чем строк длины n .N/2N

Есть несколько основных проблем с бумагой:

  • Они используют 10 тестовых файлов без каких-либо указаний на их содержание. Действительно ли данные случайны? Как они были созданы?

  • Они утверждают, что достигли коэффициентов сжатия не менее 50%, в то время как их тестовые данные показывают, что они достигают не более 50%.

Этот алгоритм определяет стратегию без потерь, которая использует простые числа, присутствующие в десятичной системе счисления

  • Какая? Простые числа являются простыми числами независимо от основания.

  • Проблема № 1 с декомпрессией: первичная факторизация - сложная проблема, как они делают это эффективно?

  • Выпуск № 2 с декомпрессией ( это кикера ): они умножают простые числа вместе, но при этом вы теряете какую - либо информацию о заказе, так как . Я не думаю, что это возможно, чтобы распаковать вообще, используя их технику.25знак равно10знак равно52

Я не думаю, что эта статья очень хорошая.

Том ван дер Занден
источник
Из того, что я понял, они хранят порядок строк с одинаковой кратностью в словаре. Но в случайных наборах данных это не должно генерировать огромный словарь, учитывая, что есть много 4-байтовых строк с кратностью 1 (или равной кратностью)?
Кланген
@Pickle В их примере строка «@THE» имеет кратность 2. Я не вижу, как они могут восстановить, в каких двух местах слово «the» должно идти.
Том ван дер Занден
1
Ах я вижу. Хорошее наблюдение. Действительно, это серьезная проблема. Как эта статья была принята для публикации в журнале? Разве не должно быть более строгого рецензирования?
Кланген
4
@ Рассол Да, там должно быть более строгое рецензирование. Это не всегда так, хотя иногда неопытным / ленивым / некомпетентным организаторам конференции не удается вовремя найти рецензентов. Существует множество случаев, когда принимаются статьи, содержащие случайно сгенерированные тарабарщины, и в одном журнале даже была опубликована статья под заголовком «Убери меня из своего гребаного списка рассылки» .
Том ван дер Занден
Хахаха, это потрясающе. Но грустный в то же время.
Кланген
15

Я собираюсь обратиться к Тому ван дер Зандену, который, кажется, прочитал статью и обнаружил слабость в методе. Хотя я не читал статью подробно, исходя из аннотации и таблицы результатов, это кажется правдоподобным утверждением.

Они утверждают, что постоянный коэффициент сжатия 50% для текстовых файлов (не «всех файлов»), который, как они отмечают, примерно такой же, как LZW, и примерно на 10% хуже, чем (предположительно нулевого порядка) кодирования Хаффмана. Сжатие текстовых файлов на 50% несложно достичь, используя достаточно простые методы; это бакалавриат во многих курсах по информатике.

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

Веб-сайт конференции претендует на соотношение сторон 1: 4, что заставляет задуматься, что они отвергли.

Псевдоним
источник
12

Ты спрашиваешь:

  • Действительно ли это осуществимо, как предполагают авторы? Согласно статье, их результаты очень эффективны и всегда сжимают данные до меньшего размера. Разве размер словаря не будет огромным?

Да, конечно. Даже для их подобранного вручную примера («БЫСТРЫЙ СЕРЕБРЯНЫЙ ФОКС ПЕРЕРЫВАЕТСЯ НА ЛЕНОЧНУЮ СОБАКУ») они не достигают сжатия, поскольку словарь содержит каждую 4-байтовую подстроку текста (минус 4 байта за одно повторение) ") ... и" сжатая "версия текста должна включать в себя весь словарь и всю эту хрень с простыми числами.

  • Разве это не может быть использовано для повторного повторного сжатия сжатых данных с использованием того же алгоритма? Очевидно и было продемонстрировано, что такие методы (когда сжатые данные повторно сжимаются столько раз, сколько возможно, резко уменьшая размер файла) невозможны; действительно, не было бы биекции между набором всех случайных данных и сжатых данных. Так почему же это кажется возможным?

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

Другими словами: после того, как вы сжали все ваши файлы .wav в .mp3, вы не получите никакого улучшения в размере файлов, сжав их. Если ваш MP3-компрессор справился со своей работой, не останется никаких шаблонов для использования ZIP-компрессором.

(То же самое относится и к шифрованию: если я возьму файл с нулями и зашифрую его в соответствии с моим выбранным алгоритмом шифрования, полученный файл лучше не сжимать , иначе мой алгоритм шифрования пропускает «образец» в свой вывод!)

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

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

Как уже отмечал Том ван дер Занден, «алгоритм сжатия» Чакраборти, Кар и Гуше имеет недостатки в том, что он не только не обеспечивает какой-либо степени сжатия, но и необратим (в математическом выражении «не биективно»): множество текстов, которые все «сжимаются» в одно и то же изображение, потому что их алгоритм в основном является умножением, а умножение - коммутативным.

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

Каталог файлов на один уровень выше размещенного вами URL-адреса содержит 139 «документов» такого же качества, все из которых, очевидно, приняты в «Труды Международной конференции по новейшим исследованиям в области вычислительной техники, информации, связи и приложений». Похоже, это фиктивная конференция обычного типа. Цель таких конференций - позволить мошенническим ученым требовать «публикации в журнале», а также позволить недобросовестным организаторам заработать кучу денег. (Для получения дополнительной информации о поддельных конференциях, ознакомьтесь с этой веткой reddit или различными сообщениями StackExchange по этой теме .) В каждой области существуют фиктивные конференции . Просто научитесь доверять своим инстинктам и не верьте всему, что вы читаете в «процессе конференции», и у вас все получится.

Quuxplusone
источник
Спасибо за ясное объяснение, почему эта статья просто дерьмо, и скажите, как вообще возможно, что она была написана в первую очередь и что ей удалось пройти любой тип рецензирования.
Вааб
Спасибо за ваш краткий ответ. Это действительно грустно, когда вы даже не можете доверять записям в журнале, чтобы они хотя бы были рассмотрены коллегой. Это действительно проливает много света на тот факт, что нужно быть бдительным даже при чтении «предполагаемых» публикаций в научных журналах. Можно было бы подумать, что такие статьи подлежат не только «рецензированию», но и минимальному «анализу», как это принято в таких областях. Я надеюсь, что это станет откровением для многих людей.
Кланген
Сегодня я узнал, что существуют по крайней мере два патента США на подобные «алгоритмы бесконечного сжатия». См. Gailly.net/05533051.html
Quuxplusone
5

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

J.-E. Штырь
источник
8
Даже не существует алгоритма, который может сжимать случайные наборы данных всегда более чем на 0,0000001%.
Дэвид Ричерби
1

Методы сжатия, которые восстанавливаются, в общем, находят образец и повторно выражают его в упрощенной форме. Некоторые очень умные, некоторые очень простые. В какой-то момент нет шаблона. Процесс (ы) «сварили» набор данных до самого простого уникального шаблона. Любые попытки сжатия с этого момента приводят к увеличению объема данных или снижению уникальности. В схемах сжатия магических чисел всегда есть недостаток, или слабость руки, или потеря. будьте осторожны с любым процессом, который утверждает, что делает последнюю версию WinZip или RAR.

SkipBerne
источник
2
sss
1
@DavidRicherby, то сжатие пустой строки создает больший набор данных, как утверждает SkipBerne. Тем не менее, я думаю, что его ответ должен прояснить, что он ссылается на повторное сжатие предыдущего вывода, используя тот же алгоритм .
Анхель
2
@ Анхель СкипБерне утверждает, что существуют строки, которые не могут быть сжаты никаким алгоритмом (« любая попытка сжатия с этого момента», я подчеркиваю). Это неверно по той причине, которую я привожу: для каждой строки существует алгоритм, который сжимает эту строку.
Дэвид Ричерби
Как я понимаю, SkipBerne утверждает, что для каждого алгоритма сжатия есть строка, которую нельзя сжать. Что является правдой. Конечно, эта несжимаемая строка будет разной для разных алгоритмов.
Хосе Антонио восстановил Монику
@DavidRicherby Вы теряете квантификаторы - достаточно ясно, что SkipBerne написал, что (для любого метода сжатия есть точка, после которой нет сжатия), а не та (есть точка, после которой для любого метода сжатия есть без сжатия). Этот ответ на самом деле правильный, но ничего не добавляет к старым, лучше написанным ответам.
Жиль "ТАК - перестань быть злым"