Подскажите, как наиболее эффективно реализовать проверку последовательности на (псевдо)случайность, то есть узнать, она псп или содержит информацию. (по сути это нужно для определения скремблера, но сути это не меняет) Я реализовал через подсчет дисперсии частоты встречаемости битовых серий, т.е. если у каких то серий дисперсия высокая, значит можем предположить, что это не псп, но это не всегда дает 100% результат.
как то я баловался с хи-квадрат, хотя это почти тоже самое что дисперсия... Жал AVI с паролем и без оного AVI 100 метров 8-bit: 98.9% Chi^2: 84560.4689 DW/2: 0.8588 16-bit: 93.7% Chi^2: 31493.9199 DW/2: 0.9028 RAR 8-bit: 100.0% Chi^2: 442.2204 DW/2: 0.9897 16-bit: 100.0% Chi^2: 6.7374 DW/2: 0.9948 RAR с паролем 8-bit: 100.0% Chi^2: 0.9949 DW/2: 1.0002 16-bit: 100.0% Chi^2: 1.0009 DW/2: 0.9998
Прочитал, что 7z архивы имеют статистику шифровок... Проверил - и правда!, а сначала не поверил... Вряд ли это свидетельство сверхкрутого сжатия, наверное игорь павлов сознательно накладывает на свои архивы гамму - нафиг ему это нужно, негодяю?
Вообщем то, как изначально реализовал так и оставил, хотя выбрал еще один простой и эффеетивный для меня метод, это вычисление кумулятивных сумм (когда 0 соотв. -1, а 1 остается 1 ) от разных подпоследовательностей исходной последовательности и вычисление десперсии этих сумм.
Дома ничего нет ) Все на работе, в понедельник сделаю пару архивов и потестирую. Если действительно наложена гамма, то возможно найду и полином.
persicum Сжатие повышает энтропию по-определению. Если же мы можем вычислить в сжатом потоке какие-то закономерности, значит мы знаем как сжать этот поток ещё плотнее. Мне кажется, что скорее надо удивляться и не верить тому, что существуют алгоритмы сжатия, чьи статистики отличаются от статистик шифровок.
r90 Звиндеть мы все умеем, а чтобы эксперимент провести, ась? Берем самый современный супернавороченный архиватор FreeArc от Булата Заглушкина. Жмем CD Пресет Ultra-fast, размер архива 268М, Статистика 8-bit: 100.0% Chi^2: 0.9175 DW/2: 1.0000 Пресет Ultra, размер архива 221M, Статистика 8-bit: 100.0% Chi^2: 0.9937 DW/2: 1.0000 Ну и что, как качество сжатия влияет на статистику? Насчет 7z я понял, конечно никто гамму специально не накладывает, просто кодирование и шифрование это порой одно и тоже, хотя сжатие может быть и очень далеким от Шенновского предела. Имелись ввиду более изощренные тесты кроме энтропии.
persicum Информационная энтропия, если на неё пошире посмотреть, это очень растяжимое понятие. Есть шенноновское определение, а есть общее, которое гласит, что энтропия -- это мера неопределённости, непредсказуемости случайной величины. И, я должен признать, я использовал второе определение. Я знаю что это неправильно, что общепринятым является понимать под энтропией шенноновскую энтропию. Я был неправ сильно не упомянув про это, но это именно так. И что это? Можно огласить легенду этих чисел? Я -- теоретик-мечтатель в этой области, -- и я не знаю, что подразумевается под твоими 8-bit и DW/2. Под Chi^2, я думаю, подразумевается хи-квадрат, но как-бэ, для того чтобы понять, как надо трактовать 0.9937, стоит сначала узнать, как ты входные данные загонял в формулу для хи-квадрат. Байтами? Как unsigned char? Или может ты брал значение очередного unsigned char, делил его на 256.0, и использовал в формуле получающееся значение в диапазоне [0..1)? Может есть какой-то общепринятый метод, известный всем специалистам в этой области, но я, не будучи специалистом, его не знаю.
