Энтропия файловой системы что это
Обновлено: 06.07.2024
Рассмотрим схему [math]\mathcal_m[/math] c [math]m[/math] исходами и вероятностями [math]\[/math] и схему [math]\mathcal_k[/math] с [math]k[/math] исходами и вероятностями [math]\[/math] .
Образуем комбинированную схему c [math]m + k - 1[/math] исходами следующим образом:
Выбирается случайным образом один из исходов схемы [math]\mathcal_m[/math] , и если произошел [math]m[/math] -й исход, выбирается случайно один из исходов схемы [math]\mathcal_k[/math] , а остальные [math]m - 1[/math] исходов схемы [math]\mathcal_m[/math] считаются окончательными.
В этой комбинированной схеме [math]\mathcal[/math] мы получаем исходы [math]1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)[/math] с вероятностями [math]p_1, p_2, \dots, p_, p_mq_1, p_mq_2, \dots, p_mq_k[/math]
Легко видеть, что [math]H(\mathcal) = H(\mathcal_m) + p_mH(\mathcal_k)[/math] .
Потребуем выполнения этого свойства для любой меры неопределенности. [math]\lhd[/math]
Для доказательства формулы вычисления энтропии сначала докажем лемму.
[math]g(n) = H(\dfrac<1>, \dfrac<1>, \dots, \dfrac<1>) = -k \log_2 \dfrac<1> = k \log_2n[/math]Будем рассматривать для [math]k=1[/math] (бит).
Рассмотрим функцию [math]g(mn)[/math] :
[math]g(mn)=g(m)+ \sum\limits_^ \dfrac g(n) = g(m)+g(n)[/math]
Пусть: [math]g(2)=1 \quad[/math] , тогда [math]g(2^t)=t[/math] и [math] \quad g(n^t)=t \cdot g(n)[/math]
Рассмотрим такое [math] i [/math] , что [math]2^i \leqslant n^t \lt 2^[/math]
Можно заметить, что если [math] i=[ \log_2 n^t ] [/math] , то неравенство останется верным.
По предыдущим рассуждениям получаем, что:
[math]g(2^i) \leqslant g(n^t) \lt g(2^)[/math] [math] i \leqslant t \cdot g(n) \lt i+1 \quad \quad [/math]
Делим неравенство на [math]t[/math] :
[math]H(p_1, p_2, \dots, p_n) = -k \sum\limits_Теперь рассмотрим функцию [math]H(\dfrac, \dfrac, \dots, \dfrac)[/math]
Приведем дроби внутри функции к одному знаменателю, получаем: [math] H(\dfrac, \dfrac, \dots, \dfrac) = H(\dfrac, \dfrac, \dots, \dfrac)[/math]
Далее по свойству энтропии и доказанной лемме:
Рассмотрим вероятностное пространство — честная монета. Найдем для нее энтропию:
[math]H(X) = -\sum\limits_^ p_i \log_2p_i = -\sum\limits_^ \cdot \log_2 \dfrac> = -\sum\limits_^ \cdot (-1)> = 1[/math]
Это означает что после броска честной монеты мы получим информацию в размере [math]1[/math] бит, уменьшив степень неопределенности вдвое.
[math]H(X) = -\sum\limits_^ p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 \lt 1 [/math]
[math]0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n [/math]1) Докажем первую часть неравенства:
Так как [math] p_i\in[0,\;1][/math] , тогда [math]\log_2\dfrac \geqslant 0 [/math] . Таким образом [math] H(p_1, p_2, \dots, p_n) = \sum\limits_^ p_i\log_2 \dfrac \geqslant 0 [/math]
2) Докажем вторую часть неравенства:
[math] f(x)=\log_2x [/math] — выпуклая вверх функция, [math] p_1,p_2,\ldots,p_n\gt 0[/math] и [math] \sum \limits_^ p_i = 1 [/math] , тогда для нее выполняется неравенство Йенсена: [math] \sum\limits_^ p_i f(\dfrac) \leqslant f(\sum\limits_^ (p_i \cdot\dfrac)) [/math]
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
[math]H(A|B)= - \sum\limits_^p(b_i)\sum\limits_^ p(a_j|b_i)\log_2p(a_j|b_i) [/math]
[math] H(A \cap B) = -\sum\limits_^ \sum\limits_^ p(a_j \cap b_i)\log_2p(a_j \cap b_i) [/math]
По формуле условной вероятности [math] p(a_j|b_i)=\dfrac
[math] H(A|B)=-\sum\limits_^p(b_i)\sum\limits_^ p(a_j|b_i)\log_2p(a_j|b_i) [/math] [math]= - \sum\limits_^p(b_i) \sum\limits_^ \dfrac
[math] = H(A \cap B) +\sum\limits_^ \log_2p(b_i)\sum\limits_^ p(a_j \cap b_i) = H(A \cap B) +\sum\limits_^ \log_2p(b_i)p(b_i) = [/math] [math]H(A \cap B) - H(B) [/math]
Энтропия. Пожалуй, это одно из самых сложных для понимания понятий, с которым вы можете встретиться в курсе физики, по крайней мере если говорить о физике классической. Мало кто из выпускников физических факультетов может объяснить, что это такое. Большинство проблем с пониманием энтропии, однако, можно снять, если понять одну вещь. Энтропия качественно отличается от других термодинамических величин: таких как давление, объём или внутренняя энергия, потому что является свойством не системы, а того, как мы эту систему рассматриваем. К сожалению в курсе термодинамики её обычно рассматривают наравне с другими термодинамическими функциями, что усугубляет непонимание.
Энтропия — это то, как много информации вам не известно о системе
Например, если вы спросите меня, где я живу, и я отвечу: в России, то моя энтропия для вас будет высока, всё-таки Россия большая страна. Если же я назову вам свой почтовый индекс: 603081, то моя энтропия для вас понизится, поскольку вы получите больше информации.
Почтовый индекс содержит шесть цифр, то есть я дал вам шесть символов информации. Энтропия вашего знания обо мне понизилась приблизительно на 6 символов. (На самом деле, не совсем, потому что некоторые индексы отвечают большему количеству адресов, а некоторые — меньшему, но мы этим пренебрежём).
Или рассмотрим другой пример. Пусть у меня есть десять игральных костей (шестигранных), и выбросив их, я вам сообщаю, что их сумма равна 30. Зная только это, вы не можете сказать, какие конкретно цифры на каждой из костей — вам не хватает информации. Эти конкретные цифры на костях в статистической физике называют микросостояниями, а общую сумму (30 в нашем случае) — макросостоянием. Существует 2 930 455 микросостояний, которые отвечают сумме равной 30. Так что энтропия этого макросостояния равна приблизительно 6,5 символам (половинка появляется из-за того, что при нумерации микросостояний по порядку в седьмом разряде вам доступны не все цифры, а только 0, 1 и 2).
А что если бы я вам сказал, что сумма равна 59? Для этого макросостояния существует всего 10 возможных микросостояний, так что его энтропия равна всего лишь одному символу. Как видите, разные макросостояния имеют разные энтропии.
Пусть теперь я вам скажу, что сумма первых пяти костей 13, а сумма остальных пяти — 17, так что общая сумма снова 30. У вас, однако, в этом случае имеется больше информации, поэтому энтропия системы для вас должна упасть. И, действительно, 13 на пяти костях можно получить 420-ю разными способами, а 17 — 780-ю, то есть полное число микросостояний составит всего лишь 420х780 = 327 600. Энтропия такой системы приблизительно на один символ меньше, чем в первом примере.
Мы измеряем энтропию как количество символов, необходимых для записи числа микросостояний. Математически это количество определяется как логарифм, поэтому обозначив энтропию символом S, а число микросостояний символом Ω, мы можем записать:
Это есть ничто иное как формула Больцмана (с точностью до множителя k, который зависит от выбранных единиц измерения) для энтропии. Если макросостоянию отвечают одно микросостояние, его энтропия по этой формуле равна нулю. Если у вас есть две системы, то полная энтропия равна сумме энтропий каждой из этих систем, потому что log(AB) = log A + log B.
Из приведённого выше описания становится понятно, почему не следует думать об энтропии как о собственном свойстве системы. У системы есть опеделённые внутренняя энергия, импульс, заряд, но у неё нет определённой энтропии: энтропия десяти костей зависит от того, известна вам только их полная сумма, или также и частные суммы пятёрок костей.
Другими словами, энтропия — это то, как мы описываем систему. И это делает её сильно отличной от других величин, с которыми принято работать в физике.
Классической системой, которую рассматривают в физике, является газ, находящийся в сосуде под поршнем. Микросостояние газа — это положение и импульс (скорость) каждой его молекулы. Это эквивалентно тому, что вы знаете значение, выпавшее на каждой кости в рассмотренном раньше примере. Макросостояние газа описывается такими величинами как давление, плотность, объём, химический состав. Это как сумма значений, выпавших на костях.
Величины, описывающие макросостояние, могут быть связаны друг с другом через так называемое «уравнение состояния». Именно наличие этой связи позволяет, не зная микросостояний, предсказывать, что будет с нашей системой, если начать её нагревать или перемещать поршень. Для идеального газа уравнение состояния имеет простой вид:
хотя вы, скорее всего, лучше знакомы с уравнением Клапейрона — Менделеева pV = νRT — это то же самое уравнение, только с добавлением пары констант, чтобы вас запутать. Чем больше микросостояний отвечают данному макросостоянию, то есть чем больше частиц входят в состав нашей системы, тем лучше уравнение состояния её описывают. Для газа характерные значения числа частиц равны числу Авогадро, то есть составляют порядка 10 23 .
Величины типа давления, температуры и плотности называются усреднёнными, поскольку являются усреднённым проявлением постоянно сменяющих друг друга микросостояний, отвечающих данному макросостоянию (или, вернее, близким к нему макросостояниям). Чтобы узнать в каком микросостоянии находится система, нам надо очень много информации — мы должны знать положение и скорость каждой частицы. Количество этой информации и называется энтропией.
Как меняется энтропия с изменением макросостояния? Это легко понять. Например, если мы немного нагреем газ, то скорость его частиц возрастёт, следовательно, возрастёт и степень нашего незнания об этой скорости, то есть энтропия вырастет. Или, если мы увеличим объём газа, отведя поршень, увеличится степень нашего незнания положения частиц, и энтропия также вырастет.
Если мы рассмотрим вместо газа какое-нибудь твёрдое тело, особенно с упорядоченной структурой, как в кристаллах, например, кусок металла, то его энтропия будет невелика. Почему? Потому что зная положение одного атома в такой структуре, вы знаете и положение всех остальных (они же выстроены в правильную кристаллическую структуру), скорости же атомов невелики, потому что они не могут улететь далеко от своего положения и лишь немного колеблются вокруг положения равновесия.
Если кусок металла находится в поле тяготения (например, поднят над поверхностью Земли), то потенциальная энергия каждого атома в металле приблизительно равна потенциальной энергии других атомов, и связанная с этой энергией энтропия низка. Это отличает потенциальную энергию от кинетической, которая для теплового движения может сильно меняться от атома к атому.
Если кусок металла, поднятый на некоторую высоту, отпустить, то его потенциальная энергия будет переходить в кинетическую энергию, но энтропия возрастать практически не будет, потому что все атомы будут двигаться приблизительно одинаково. Но когда кусок упадёт на землю, во время удара атомы металла получат случайное направление движения, и энтропия резко увеличится. Кинетическая энергия направленного движения перейдёт в кинетическую энергию теплового движения. Перед ударом мы приблизительно знали, как движется каждый атом, теперь мы эту информацию потеряли.
Второй закон термодинамики утверждает, что энтропия (замкнутой системы) никогда не уменьшается. Мы теперь можем понять, почему: потому что невозможно внезапно получить больше информации о микросостояниях. Как только вы потеряли некую информацию о микросостоянии (как во время удара куска металла об землю), вы не можете вернуть её назад.
Давайте вернёмся обратно к игральным костям. Вспомним, что макросостояние с суммой 59 имеет очень низкую энтропию, но и получить его не так-то просто. Если бросать кости раз за разом, то будут выпадать те суммы (макросостояния), которым отвечает большее количество микросостояний, то есть будут реализовываться макросостояния с большой энтропией. Самой большой энтропией обладает сумма 35, и именно она и будет выпадать чаще других. Именно об этом и говорит второй закон термодинамики. Любое случайное (неконтролируемое) взаимодействие приводит к росту энтропии, по крайней мере до тех пор, пока она не достигнет своего максимума.
И ещё один пример, чтобы закрепить сказанное. Пусть у нас имеется контейнер, в котором находятся два газа, разделённых расположенной посередине контейнера перегородкой. Назовём молекулы одного газа синими, а другого — красными.
Если открыть перегородку, газы начнут перемешиваться, потому что число микросостояний, в которых газы перемешаны, намного больше, чем микросостояний, в которых они разделены, и все микросостояния, естественно, равновероятны. Когда мы открыли перегородку, для каждой молекулы мы потеряли информацию о том, с какой стороны перегородки она теперь находится. Если молекул было N, то утеряно N бит информации (биты и символы, в данном контексте, это, фактически, одно и тоже, и отличаются только неким постоянным множителем).
Ну и напоследок рассмотрим решение в рамках нашей парадигмы знаменитого парадокса демона Максвелла. Напомню, что он заключается в следующем. Пусть у нас есть перемешанные газы из синих и красных молекул. Поставим обратно перегородку, проделав в ней небольшое отверстие, в которое посадим воображаемого демона. Его задача — пропускать слева направо только красных, и справа налево только синих. Очевидно, что через некоторое время газы снова будут разделены: все синие молекулы окажутся слева от перегородки, а все красные — справа.
Получается, что наш демон понизил энтропию системы. С демоном ничего не случилось, то есть его энтропия не изменилась, а система у нас была закрытой. Получается, что мы нашли пример, когда второй закон термодинамики не выполняется! Как такое оказалось возможно?
Решается этот парадокс, однако, очень просто. Ведь энтропия — это свойство не системы, а нашего знания об этой системе. Мы с вами знаем о системе мало, поэтому нам и кажется, что её энтропия уменьшается. Но наш демон знает о системе очень много — чтобы разделять молекулы, он должен знать положение и скорость каждой из них (по крайней мере на подлёте к нему). Если он знает о молекулах всё, то с его точки зрения энтропия системы, фактически, равна нулю — у него просто нет недостающей информации о ней. В этом случае энтропия системы как была равна нулю, так и осталась равной нулю, и второй закон термодинамики нигде не нарушился.
Но даже если демон не знает всей информации о микросостоянии системы, ему, как минимум, надо знать цвет подлетающей к нему молекулы, чтобы понять, пропускать её или нет. И если общее число молекул равно N, то демон должен обладать N бит информации о системе — но именно столько информации мы и потеряли, когда открыли перегородку. То есть количество потерянной информации в точности равно количеству информации, которую необходимо получить о системе, чтобы вернуть её в исходное состояние — и это звучит вполне логично, и опять же не противоречит второму закону термодинамики.
Любой компьютерный файл, как известно, состоит из байтов. Байт может принимать значения от 0 до 255. Информационная энтропия – это статистический параметр, который показывает вероятность встречаемости определённых байтов в файле.
Визуально оценить степень энтропии можно с помощью гистограммы – распределения вероятности повторов одинаковых байтов в файле. По энтропии файла можно предположить, какого типа файл перед нами, видя только его гистограмму.
Для демонстрации возьмём три файла разных типов и сравним их гистограммы.
Гистограмма текстового файла
Первый пусть будет текстовый файл (*.TXT). Его гистограмма показана на рисунке:
Гистограмма текстового файла
Текстовый файл содержит только текст. Каждый символ текста кодируется определёнными байтами в соответствии с таблицей кодировки. Хотя видов кодировок достаточно большое количество, представленный файл – в кодировке ASCII, поэтому на первой гистограмме заняты лишь некоторые области, а больше числа 127 значений нет вовсе (127 – предельный код символа в таблице ASCII). Видно, что некоторые из символов (букв или цифр) в файле встречаются чаще, некоторые – реже. Больше всего в текстовом файле пробелов, отсюда и высокий пик на значении байта 3210.
Гистограмма PDF файла
Следующий файл будет формата PDF:
Гистограмма файла PDF
Этот файл имеет все возможные байты, так как формат PDF кодируется не так, как текстовые файлы. Он хранит много служебной информации: форматирование, шрифты, изображения и т.д. Но по его гистограмме видно, что некоторые из байтов встречаются с примерно равной вероятностью, в то время как другие – намного чаще остальных. Отсюда и множественные острые всплески на гистограмме, и в целом она имеет довольно «рваный» вид, хотя и занимает всю доступную ширину.
Гистограмма архива 7Z
И последний файл – заархивированный в формат 7Z:
Гистограмма файла 7Z
Гистограмма архива 7Z имеет две основные особенности: во-первых, все байты встречаются в заархивированном файле с более-менее равной вероятностью (достаточно ровный верхний край), а во-вторых, практически отсутствует свободное пространство над гистограммой, что говорит о почти полном отсутствии избыточности такого файла. Отсюда можно сделать вывод, что алгоритм архиватора каким-то особым образом «перемешивает» байты файла, чтобы добиться их максимально равномерного распределения.
Таким образом, энтропия в информатике, как и в физике – это мера неупорядоченности системы, в данном случае – неупорядоченности распределения байтов в файле. Энтропия позволяет судить о степени сжатия файла и – косвенно – о его типе.
Программа визуализации энтропии файлов
Как вычислить энтропию файла? (или скажем просто куча байт)
У меня есть идея, но я не уверен, что она математически верна.
моя идея заключается в следующем:
- создайте массив из 256 целых чисел (все нули).
- пройти через файл и для каждого из его байтов,
увеличить соответствующую позицию в массиве. - в конце: вычислить "среднее" значение матрица.
- инициализировать счетчик с нуля,
и для каждой записи массива:
добавить разницу записи к" среднему " прилавку.
- В конце: вычислить "среднее" значение для массива.
- инициализировать счетчик с нуля, и для каждой записи массива: добавьте разницу записи в "среднее" на счетчик.
С некоторые модификации вы можете получить энтропию Шеннона:
переименовать "среднее" в "энтропия"
Edit: Как упоминал Уэсли, мы должны разделить энтропию на 8 для того, чтобы настроить его в диапазоне 0 . . 1 (или, альтернативно, мы можем использовать основание логарифма, 256).
чтобы вычислить информационную энтропию коллекции байтов, вам нужно будет сделать что-то похожее на ответ tydok. (ответ тайдока работает над коллекцией битов.)
предполагается, что уже существуют следующие переменные:
byte_counts - это 256-элементный список количества байтов с каждым значением в вашем файле. Например, byte_counts[2] - это количество байтов, имеющих значение 2 .
total - это общее количество байтов в файле.
я напишу следующий код на Python, но должно быть очевидно, что происходит.
есть несколько вещей, которые важно отметить.
проверка count == 0 - это не просто оптимизация. Если count == 0 , потом p == 0 , и log (p) будет неопределенным ("отрицательная бесконечность"), вызывая ошибку.
на 256 in вызов math.log обозначает количество дискретных значений, которые можно. Байт состоит из восьми битов будет иметь 256 возможных значений.
результирующее значение будет находиться между 0 (каждый байт в файле одинаковый) до 1 (байты равномерно разделены между всеми возможными значениями байта).
объяснение использования базы журналов 256
это правда, что этот алгоритм обычно применяется с помощью логарифма по основанию 2. Это дает результирующий ответ в битах. В таком случае, у вас есть максимум 8 бит энтропии для какого-либо файла. Попробуйте сами: максимизируйте энтропию ввода, сделав byte_counts список всех 1 или 2 или 100 . Когда байты файла равномерно распределены, вы обнаружите, что энтропия составляет 8 бит.
можно использовать другие основания логарифма. Используя b=2 позволяет результат в битах, так как каждый бит может иметь 2 ценности. Используя b=10 ставит результат в dits, или десятичные разряды, так как для каждого dit есть 10 возможных значений. Используя b=256 выдаст результат в байтах, так как каждый байт может принимать одно из 256 дискретных значений.
интересно, что используя идентификаторы журнала, вы можете выяснить, как преобразовать полученную энтропию между единицами. Любой результат, полученный в единицах бит, может быть преобразован в единицы байтов путем деления на 8. Как интересный, умышленное побочный эффект, это дает энтропию как значение между 0 и 1.
- вы можете использовать различные единицы для выражения энтропии
- большинство людей выражают энтропию в битах (b=2)
- для коллекции байтов это дает максимальную энтропию 8 бит
- так как спрашивающий хочет результат между 0 и 1, разделите этот результат на 8 для значимого значение
- это эквивалентно (энтропия в битах) / 8
- это уже дает значение между 0 и 1
более простое решение: gzip файл. Используйте соотношение размеров файлов: (размер gzipped)/(размер оригинала) в качестве меры случайности (т. е. энтропии).
этот метод не дает вам точного абсолютного значения энтропии (потому что gzip не является "идеальным" компрессором), но это достаточно хорошо, если вам нужно сравнить энтропию разных источников.
это ent справится? (Или, возможно, его нет на вашей платформе.)
в качестве встречного примера, вот файл без энтропии.
энтропии файла не существует. В теории информации энтропия является функцией случайная величина, не фиксированного набора данных (ну, технически фиксированный набор данных имеет энтропию, но эта энтропия будет равна 0 - мы можем рассматривать данные как случайное распределение, которое имеет только один возможный результат с вероятностью 1).
чтобы вычислить энтропию, вам нужна случайная величина, с помощью которой можно моделировать файл. Тогда энтропия будет энтропия распределения этой случайной величины. Эта энтропия будет равна числу битов информации, содержащейся в этой случайной переменной.
Я на два года опоздал с ответом, поэтому, пожалуйста, подумайте об этом, несмотря на несколько голосов.
короткий ответ: используйте мои 1-е и 3-е смелые уравнения ниже, чтобы получить то, о чем думает большинство людей, когда они говорят "энтропия" файла в битах. Используйте только 1-е уравнение, если вы хотите, чтобы энтропия Шеннона H, которая на самом деле является энтропией/символом, как он заявил 13 раз в своей статье, о которой большинство людей не знают. Некоторые онлайн-калькуляторы энтропии используют этот, но H Шеннона "специфическая энтропия", а не" полная энтропия", которая вызвала столько путаницы. Используйте 1-е и 2-е уравнения, если вы хотите получить ответ между 0 и 1, который нормализуется энтропией/символом (это не бит/символ, а истинная статистическая мера "энтропийной природы" данных, позволяя данным выбирать свою собственную базу журналов вместо произвольного назначения 2, e или 10).
здесь 4 типа энтропии файлов (данных) из n символов из N уникальных типов символов. Но имейте в виду что, зная содержимое файла, вы знаете его состояние и, следовательно, S=0. Точнее, если у вас есть источник, который генерирует много данных, к которым у вас есть доступ, вы можете вычислить ожидаемую будущую энтропию/характер этого источника. Если вы используете следующее для файла, точнее сказать, что он оценивает ожидаемую энтропию других файлов из этого источника.
- Шеннон (специфические) энтропия H = -1 * sum (count_i / N * log (count_i / N))
где count_i-количество раз, когда символ I встречался в N.
Единицы измерения-это биты/символ, если log-база 2, nats / символ, если natural log. - нормированная удельная энтропия: H / log (n)
Единицы измерения-энтропия / символ. Колеблется от 0 до 1. 1 означает, что каждый символ встречается одинаково часто, а около 0 все символы, кроме 1, встречаются только один раз, а остальная часть очень длинного файла является другим символом. Журнал находится в той же базе, что и Х. - абсолютная энтропия S = N * H
Единицы-это биты, если log является базой 2, nats, если ln ()). - нормализованная абсолютная энтропия S = N * H / log (n)
Единица измерения - "энтропия", варьируется от 0 до N. журнал находится в той же базе, что и H.
хотя последняя является истинной "энтропией", первая (энтропия Шеннона H) - это то, что все книги называют" энтропией " без (необходимой имхо) квалификации. Большинство не уточняют (например Шеннон сделал), что это бит / символ или энтропия на символ. Называть H "энтропией" - это слишком вольно.
для файлов с одинаковой частотой каждого символа: S = N * H = N. Это относится к большинству больших файлов битов. Энтропия не делает никакого сжатия данных и, таким образом, полностью игнорирует любые шаблоны, поэтому 000000111111 имеет те же H и S, что и 010111101000 (6 1 и 6 0 в обоих случаях).
Как говорили другие, используя стандартную процедуру сжатия как gzip и разделение до и после даст лучшую меру количества ранее существующего "порядка" в файле, но это предвзято по отношению к данным, которые лучше подходят для схемы сжатия. Там нет общего назначения идеально оптимизированный компрессор, который мы можем использовать для определения абсолютного "порядка".
еще одна вещь, которую следует учитывать: H изменяется, если вы измените способ выражения данных. H будет отличаться, если вы выберете разные группы битов (биты, кусочки, байты или шестнадцатеричные). Так что вы делите ПО log (n) где n - количество уникальных символов в данных (2 для двоичного кода, 256 для байтов) и H будет варьироваться от 0 до 1 (это нормализованная интенсивная энтропия Шеннона в единицах энтропии на символ). Но технически, если происходит только 100 из 256 типов байтов, то n=100, а не 256.
H - "интенсивная" энтропия, т. е. это per символ, который аналогичен удельная энтропия в физике, которая является энтропией на кг или на моль. Регулярные " обширные" энтропия файла, аналогичного физике, равна S=N * H, где N - количество символов в файле. H будет точно аналогичен части идеального объема газа. Информационная энтропия не может быть просто равна физической энтропии в более глубоком смысле, потому что физическая энтропия допускает "упорядоченные", а также неупорядоченные расположения: физическая энтропия выходит больше, чем полностью случайная энтропия (например, сжатый файл). Один аспект отличается для идеального газа там является дополнительным фактором 5/2 для учета этого: S = k * N * (H+5/2), где H = возможные квантовые состояния на молекулу = (xp)^3/hbar * 2 * sigma^2, где x=ширина коробки, p=общий ненаправленный импульс в системе (рассчитанный из кинетической энергии и массы на молекулу), и sigma=0.341 в соответствии с принципом неопределенности, дающим только количество возможных состояний в пределах 1 std dev.
небольшая математика дает более короткую форму нормализованной обширной энтропии для файл:
С=Н * сек / журнал(N) = сумма(count_i*лог(Н/count_i))/журнал(N)
единицы этого - "энтропия" (которая на самом деле не является единицей). Он нормализован, чтобы быть лучшей универсальной мерой, чем" энтропия "единиц N * H. Но его также не следует называть" энтропией "без разъяснения, потому что нормальная историческая конвенция ошибочно называет H" энтропией " (что противоречит разъяснениям, сделанным в тексте Шеннона).
Если вы используете энтропию теории информации, имейте в виду, что может иметь смысл не использовать ее на байтах. Скажем, если ваши данные состоят из поплавков, вы должны вместо этого подогнать распределение вероятности к этим поплавкам и вычислить энтропию этого распределения.
или, если содержимое файла символов Unicode, вы должны использовать их и т. д.
комментарий джиттера, ссылающийся на сканирование данных на энтропию аномалии очень важно для вашей основной цели. Это в конечном итоге связывается с libdisorder (библиотека C для измерения энтропии байтов). Этот подход, похоже, даст вам больше информации для работы, так как он показывает, как метрическая энтропия изменяется в разных частях файла. См., например, этот график того, как энтропия блока из 256 последовательных байтов из изображения jpg 4 MB (ось y) изменяется для разных смещений (ось x). В начале и в конце энтропия ниже, как это частично, но это около 7 бит на байт для большей части файла.
более интересным является анализ и аналогичные графики в анализ энтропии байтов диска в формате FAT | GL.ИБ.LY
статистика, такая как max, min, mode и стандартное отклонение метрической энтропии для всего файла и/или первого и последнего блоков, может быть очень полезна в качестве подписи.
без дополнительной информации энтропия файла (по определению) равна его размеру*8 бит. Энтропия текстового файла примерно равна размеру * 6.6 бит, учитывая, что:
- каждый символ одинаково вероятен
- в byte
- log (95) / log(2) = 6.6
энтропия текстового файла на английском языке оценивается примерно в 0,6-1,3 бит на символ (как объяснено здесь).
In вообще нельзя говорить об энтропии данного файла. Энтропия является свойством a файлы.
Если вам нужна энтропия (или энтропия на байт, если быть точным), лучший способ-сжать ее с помощью gzip, bz2, rar или любого другого сильного сжатия, а затем разделить сжатый размер на несжатый размер. Это была бы отличная оценка энтропии.
вычисление энтропии байт за байтом, как предложил Ник Дандулакис, дает очень плохую оценку, потому что предполагает каждый байт независим. В текстовых файлах, например, гораздо более вероятно иметь маленькую букву после буквы, чем пробел или пунктуацию после буквы, поскольку слова обычно длиннее 2 символов. Таким образом, вероятность нахождения следующего символа в диапазоне a-z коррелирует со значением предыдущего символа. Не используйте приблизительную оценку Ника для любых реальных данных, вместо этого используйте коэффициент сжатия gzip.
Читайте также: