파일의 엔트로피를 계산하는 방법은 무엇입니까?

파일의 엔트로피를 계산하는 방법은 무엇입니까?

---

파일의 엔트로피를 계산하는 방법은 무엇입니까? (또는 그냥 많은 바이트를 말해 봅시다)
아이디어가 있지만 수학적으로 정확한지 확신 할 수 없습니다.

내 생각은 다음과 같습니다.

• 256 개 정수 (모두 0)의 배열을 만듭니다.
• 파일을 탐색하고 각 바이트
  에 대해 배열의 해당 위치를 증가시킵니다.
• 끝 : 배열의 "평균"값을 계산합니다.
• 0으로 카운터를 초기화
  하고 배열의 각 항목
  에 대해 항목의 차이를 카운터에 "평균"에 추가합니다.

글쎄, 이제 막혔어. 모든 결과가 0.0과 1.0 사이에 있도록 카운터 결과를 "투영"하는 방법은 무엇입니까? 하지만 그 아이디어는 어쨌든 일관성이 없습니다 ...

누군가가 더 좋고 간단한 솔루션을 갖기를 바랍니다.

참고 : 파일의 내용을 가정하려면 모든 것이 필요합니다 :
(일반 텍스트, 마크 업, 압축 또는 일부 바이너리, ...)

---

• 끝 : 배열의 "평균"값을 계산합니다.
• 0으로 카운터를 초기화하고 배열의 각 항목에 대해 항목의 차이를 카운터에 "평균"에 추가합니다.

함께 일부 수정하면 섀넌의 엔트로피를 얻을 수 있습니다 :

"평균"을 "엔트로피"로 변경

(float) entropy = 0
for i in the array[256]:Counts do 
  (float)p = Counts[i] / filesize
  if (p > 0) entropy = entropy - p*lg(p) // lgN is the logarithm with base 2

편집 : Wesley가 언급했듯이 0 범위에서 조정하려면 엔트로피를 8로 나누어야합니다 . . 1 (또는 대수 기수 256을 사용할 수 있습니다).

---

더 간단한 해결책 : 파일을 gzip하십시오. 파일 크기 비율을 사용합니다 : (gzipped 크기) / (원본 크기)를 임의성 (예 : 엔트로피)의 척도로 사용합니다.

이 방법은 (gzip이 "이상적인"압축기가 아니기 때문에) 엔트로피의 정확한 절대 값을 제공하지는 않지만 다른 소스의 엔트로피를 비교해야하는 경우 충분합니다.

---

바이트 모음의 정보 엔트로피를 계산하려면 tydok의 대답과 비슷한 작업을 수행해야합니다. (tydok의 답변은 비트 모음에서 작동합니다.)

다음 변수는 이미 존재한다고 가정합니다.

• byte_counts파일의 각 값이있는 바이트 수의 256 요소 목록입니다. 예를 들어 byte_counts[2]는 값이있는 바이트 수입니다 2.

• total 파일의 총 바이트 수입니다.

다음 코드를 파이썬으로 작성할 것이지만 무슨 일이 일어나고 있는지 분명해야합니다.

import math

entropy = 0

for count in byte_counts:
    # If no bytes of this value were seen in the value, it doesn't affect
    # the entropy of the file.
    if count == 0:
        continue
    # p is the probability of seeing this byte in the file, as a floating-
    # point number
    p = 1.0 * count / total
    entropy -= p * math.log(p, 256)

주목해야 할 몇 가지 사항이 있습니다.

• 확인 count == 0은 단지 최적화가 아닙니다. 이면 count == 0, p == 0및 log ( p )가 정의되지 않아 ( "음의 무한대") 오류가 발생합니다.

• 256에 대한 호출이 math.log가능하다 이산 값들의 수를 나타낸다. 8 비트로 구성된 바이트에는 256 개의 가능한 값이 있습니다.

결과 값은 0 (파일의 모든 단일 바이트가 동일 함)에서 최대 1 (바이트가 가능한 모든 바이트 값간에 균등하게 나뉩니다) 사이입니다.

---

log base 256 사용에 대한 설명

이 알고리즘은 일반적으로 log base 2를 사용하여 적용되는 것이 사실입니다. 이것은 결과 답을 비트 단위로 제공합니다. 이 경우 주어진 파일에 대해 최대 8 비트의 엔트로피가 있습니다. 직접 시도해보십시오 : byte_counts모두 1또는 2또는 의 목록을 만들어 입력의 엔트로피를 최대화하십시오 100. 파일의 바이트가 균등하게 분산되면 8 비트의 엔트로피가 있음을 알 수 있습니다.

다른 로그 밑을 사용할 수 있습니다. 사용 B 각 비트는 2의 값을 가질 수 = 2로하면, 비트 결과를 허용한다. b = 10을 사용하면 각 dit에 대해 10 개의 가능한 값 이 있으므로 결과를 dits 또는 십진수 비트 에 넣습니다 . b = 256을 사용하면 각 바이트가 256 개의 개별 값 중 하나를 가질 수 있으므로 결과가 바이트 단위로 제공됩니다.

흥미롭게도 로그 ID를 사용하면 결과 엔트로피를 단위간에 변환하는 방법을 알아낼 수 있습니다. 비트 단위로 얻은 결과는 8로 나누어 바이트 단위로 변환 할 수 있습니다. 흥미롭고 의도적 인 부작용으로 엔트로피를 0과 1 사이의 값으로 제공합니다.

요약해서 말하자면:

• 다양한 단위를 사용하여 엔트로피를 표현할 수 있습니다.
• 대부분의 사람들은 엔트로피를 비트 단위로 표현합니다 ( b = 2).
  • 바이트 모음의 경우 최대 엔트로피 8 비트를 제공합니다.
  • 질문자는 0과 1 사이의 결과를 원하므로이 결과를 의미있는 값을 위해 8로 나눕니다.
• 위의 알고리즘은 바이트 단위로 엔트로피를 계산합니다 ( b = 256).
  • 이것은 (비트 엔트로피) / 8과 같습니다.
  • 이것은 이미 0과 1 사이의 값을 제공합니다.

---

그만한 가치를 위해, 여기에 c #으로 표현 된 전통적인 (엔트로피 비트) 계산이 있습니다.

/// <summary>
/// returns bits of entropy represented in a given string, per 
/// http://en.wikipedia.org/wiki/Entropy_(information_theory) 
/// </summary>
public static double ShannonEntropy(string s)
{
    var map = new Dictionary<char, int>();
    foreach (char c in s)
    {
        if (!map.ContainsKey(c))
            map.Add(c, 1);
        else
            map[c] += 1;
    }

    double result = 0.0;
    int len = s.Length;
    foreach (var item in map)
    {
        var frequency = (double)item.Value / len;
        result -= frequency * (Math.Log(frequency) / Math.Log(2));
    }

    return result;
}

---

이것이 ent처리 할 수 있는 것 입니까? (또는 귀하의 플랫폼에서 사용할 수 없습니다.)

$ dd if=/dev/urandom of=file bs=1024 count=10
$ ent file
Entropy = 7.983185 bits per byte.
...

반대의 예로서 여기에 엔트로피가없는 파일이 있습니다.

$ dd if=/dev/zero of=file bs=1024 count=10
$ ent file
Entropy = 0.000000 bits per byte.
...

---

답변에 2 년이 늦었으니 몇 번의 찬성 투표에도 불구하고 이것을 고려해주세요.

짧은 대답 : 대부분의 사람들이 파일의 "엔트로피"를 비트 단위로 말할 때 생각하는 내용을 얻으려면 아래의 첫 번째 및 세 번째 굵은 방정식을 사용하십시오. 대부분의 사람들이 알지 못하는 그의 논문에서 13 번 언급했듯이 실제로 엔트로피 / 기호 인 Shannon의 H 엔트로피를 원한다면 첫 번째 방정식을 사용하십시오. 일부 온라인 엔트로피 계산기는 이것을 사용하지만 Shannon의 H는 "전체 엔트로피"가 아니라 "특정 엔트로피"로 많은 혼란을 야기했습니다. 정규화 된 엔트로피 / 기호 인 0과 1 사이의 답을 원하는 경우 1 차 및 2 차 방정식을 사용합니다 (비트 / 기호가 아니라 데이터가 자체 로그 기반을 선택하도록하여 데이터의 "엔트로피 특성"에 대한 진정한 통계 측정 값입니다). 2, e 또는 10을 임의로 할당하는 대신).

n 개의 고유 한 유형의 심볼을 가진 N 개의 심볼 길이의 파일 (데이터) 엔트로피 유형 에는 4 가지 가 있습니다 . 그러나 파일의 내용을 알면 파일의 상태를 알 수 있으므로 S = 0임을 명심하십시오. 정확하게 말하면, 액세스 할 수있는 많은 데이터를 생성하는 소스가있는 경우 해당 소스의 예상 미래 엔트로피 / 문자를 계산할 수 있습니다. 파일에 다음을 사용하는 경우 해당 소스에서 다른 파일의 예상 엔트로피를 추정하고 있다고 말하는 것이 더 정확합니다.

• Shannon (특정) 엔트로피 H = -1 * sum (count_i / N * log (count_i / N))
  여기서 count_i는 N에서 기호 i가 발생한 횟수입니다.
  단위는 로그가 밑이 2 인 경우 비트 / 기호, nats / 기호입니다. 자연 로그인 경우.
• Normalized specific entropy: H / log(n)
  Units are entropy/symbol. Ranges from 0 to 1. 1 means each symbol occurred equally often and near 0 is where all symbols except 1 occurred only once, and the rest of a very long file was the other symbol. The log is in the same base as the H.
• Absolute entropy S = N * H
  Units are bits if log is base 2, nats if ln()).
• Normalized absolute entropy S = N * H / log(n)
  Unit is "entropy", varies from 0 to N. The log is in the same base as the H.

Although the last one is the truest "entropy", the first one (Shannon entropy H) is what all books call "entropy" without (the needed IMHO) qualification. Most do not clarify (like Shannon did) that it is bits/symbol or entropy per symbol. Calling H "entropy" is speaking too loosely.

For files with equal frequency of each symbol: S = N * H = N. This is the case for most large files of bits. Entropy does not do any compression on the data and is thereby completely ignorant of any patterns, so 000000111111 has the same H and S as 010111101000 (6 1's and 6 0's in both cases).

Like others have said, using a standard compression routine like gzip and dividing before and after will give a better measure of the amount of pre-existing "order" in the file, but that is biased against data that fits the compression scheme better. There's no general purpose perfectly optimized compressor that we can use to define an absolute "order".

Another thing to consider: H changes if you change how you express the data. H will be different if you select different groupings of bits (bits, nibbles, bytes, or hex). So you divide by log(n) where n is the number of unique symbols in the data (2 for binary, 256 for bytes) and H will range from 0 to 1 (this is normalized intensive Shannon entropy in units of entropy per symbol). But technically if only 100 of the 256 types of bytes occur, then n=100, not 256.

H is an "intensive" entropy, i.e. it is per symbol which is analogous to specific entropy in physics which is entropy per kg or per mole. Regular "extensive" entropy of a file analogous to physics' S is S=N*H where N is the number of symbols in the file. H would be exactly analogous to a portion of an ideal gas volume. Information entropy can't simply be made exactly equal to physical entropy in a deeper sense because physical entropy allows for "ordered" as well disordered arrangements: physical entropy comes out more than a completely random entropy (such as a compressed file). One aspect of the different For an ideal gas there is a additional 5/2 factor to account for this: S = k * N * (H+5/2) where H = possible quantum states per molecule = (xp)^3/hbar * 2 * sigma^2 where x=width of the box, p=total non-directional momentum in the system (calculated from kinetic energy and mass per molecule), and sigma=0.341 in keeping with uncertainty principle giving only the number of possible states within 1 std dev.

A little math gives a shorter form of normalized extensive entropy for a file:

S=N * H / log(n) = sum(count_i*log(N/count_i))/log(n)

Units of this are "entropy" (which is not really a unit). It is normalized to be a better universal measure than the "entropy" units of N * H. But it also should not be called "entropy" without clarification because the normal historical convention is to erringly call H "entropy" (which is contrary to the clarifications made in Shannon's text).

---

There's no such thing as the entropy of a file. In information theory, the entropy is a function of a random variable, not of a fixed data set (well, technically a fixed data set does have an entropy, but that entropy would be 0 — we can regard the data as a random distribution that has only one possible outcome with probability 1).

In order to calculate the entropy, you need a random variable with which to model your file. The entropy will then be the entropy of the distribution of that random variable. This entropy will equal the number of bits of information contained in that random variable.

---

If you use information theory entropy, mind that it might make sense not to use it on bytes. Say, if your data consists of floats you should instead fit a probability distribution to those floats and calculate the entropy of that distribution.

Or, if the contents of the file is unicode characters, you should use those, etc.

---

Calculates entropy of any string of unsigned chars of size "length". This is basically a refactoring of the code found at http://rosettacode.org/wiki/Entropy. I use this for a 64 bit IV generator that creates a container of 100000000 IV's with no dupes and a average entropy of 3.9. http://www.quantifiedtechnologies.com/Programming.html

#include <string>
#include <map>
#include <algorithm>
#include <cmath>
typedef unsigned char uint8;

double Calculate(uint8 * input, int  length)
  {
  std::map<char, int> frequencies;
  for (int i = 0; i < length; ++i)
    frequencies[input[i]] ++;

  double infocontent = 0;
  for (std::pair<char, int> p : frequencies)
  {
    double freq = static_cast<double>(p.second) / length;
    infocontent += freq * log2(freq);
  }
  infocontent *= -1;
  return infocontent;
 }

---

Re: I need the whole thing to make assumptions on the file's contents: (plaintext, markup, compressed or some binary, ...)

As others have pointed out (or been confused/distracted by), I think you're actually talking about metric entropy (entropy divided by length of message). See more at Entropy (information theory) - Wikipedia.

jitter's comment linking to Scanning data for entropy anomalies is very relevant to your underlying goal. That links eventually to libdisorder (C library for measuring byte entropy). That approach would seem to give you lots more information to work with, since it shows how the metric entropy varies in different parts of the file. See e.g. this graph of how the entropy of a block of 256 consecutive bytes from a 4 MB jpg image (y axis) changes for different offsets (x axis). At the beginning and end the entropy is lower, as it part-way in, but it is about 7 bits per byte for most of the file.

Source: https://github.com/cyphunk/entropy_examples. [Note that this and other graphs are available via the novel http://nonwhiteheterosexualmalelicense.org license....]

More interesting is the analysis and similar graphs at Analysing the byte entropy of a FAT formatted disk | GL.IB.LY

Statistics like the max, min, mode, and standard deviation of the metric entropy for the whole file and/or the first and last blocks of it might be very helpful as a signature.

This book also seems relevant: Detection and Recognition of File Masquerading for E-mail and Data Security - Springer

---

Without any additional information entropy of a file is (by definition) equal to its size*8 bits. Entropy of text file is roughly size*6.6 bits, given that:

• each character is equally probable
• there are 95 printable characters in byte
• log(95)/log(2) = 6.6

Entropy of text file in English is estimated to be around 0.6 to 1.3 bits per character (as explained here).

In general you cannot talk about entropy of a given file. Entropy is a property of a set of files.

If you need an entropy (or entropy per byte, to be exact) the best way is to compress it using gzip, bz2, rar or any other strong compression, and then divide compressed size by uncompressed size. It would be a great estimate of entropy.

Calculating entropy byte by byte as Nick Dandoulakis suggested gives a very poor estimate, because it assumes every byte is independent. In text files, for example, it is much more probable to have a small letter after a letter than a whitespace or punctuation after a letter, since words typically are longer than 2 characters. So probability of next character being in a-z range is correlated with value of previous character. Don't use Nick's rough estimate for any real data, use gzip compression ratio instead.

참고URL : https://stackoverflow.com/questions/990477/how-to-calculate-the-entropy-of-a-file