Получение энтропии большого файла

Question

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

Answer 1

В соответствии с просьбой в другом месте на этой странице приведена unsafe версия piedar's answer. Моя версия ниже, также включает в себя следующие изменения:

• Corrected логарифм быть основание 2 (вместо 256) для того, чтобы быть совместимыми с Shannon's формулировкой entropy как минимальное количество битов, требуемых для описания состояния системы. Действительно вызова Entropy(new byte[] { 0, 1, 2, ... 255 }) теперь дает ожидаемый ответ 8,0, Entropy(new byte[] { 88, 79, 79, 88 }) возвращает 1,0, Entropy(new byte[] { 4, 15, 20, 166 }) возвращает 2,0 и т.д.
• Увеличение точности с плавающей запятой извлекая знаменателя из цикла, чтобы уменьшить опустошение.
• Это извлечение цикла также влечет за собой вырождение Entropy(new byte[0]) -i.e., энтропия ничего-теперь возвращает NaN (вместо 0.000). Этот указ, в то время как not overtly defensible, делает, полезно отличить исключительный сомнительный случай от более информативных 0.000 таких результатов, как Entropy(new byte[] { 123 }), Entropy(new byte[] { 0xff, 0xff, 0xff }) и другие.
• Специфическое поведение для чтения файла было удалено, так что функция ниже работает с любыми данными information.
• Признавая семенные вклады Шеннона, измените имя переменной на 'H'.

public static unsafe Double Entropy(byte[] data) 
{ 
    int* rgi = stackalloc int[0x100], pi = rgi + 0x100; 

    for (int i = data.Length; --i >= 0;) 
     rgi[data[i]]++; 

    Double H = 0.0, cb = data.Length; 
    while (--pi >= rgi) 
     if (*pi > 0) 
      H += *pi * Math.Log(*pi/cb, 2.0); 

    return -H/cb; 
} 

Answer 2

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

Answer 3

Это будет выглядеть примерно так.

static double CalculateEntropy(FileInfo file) 
{ 
    int range = byte.MaxValue + 1; // 0 -> 256 
    byte[] values = File.ReadAllBytes(file.FullName); 

    long[] counts = new long[range]; 
    foreach (byte value in values) 
    { 
     counts[value]++; 
    } 

    double entropy = 0; 
    foreach (long count in counts) 
    { 
     if (count != 0) 
     { 
      double probability = (double)count/values.LongLength; 
      entropy -= probability * Math.Log(probability, range); 
     } 
    } 
    return entropy; 
} 

Вы могли бы вычислить характер энтропию, а не байты энтропию путем замены в File.ReadAllText() и замене byte с char. Я сомневаюсь, что вы найдете более быстрое решение, использующее Linq, но попытаться сделать хорошую головоломку.