Расчет энтропии

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]

Страница 1 из 1 1
Модератор форума: Anton93

Расчет энтропии (Delphi)

Расчет энтропии

Волк-1024

Дата: Понедельник, 09.07.2012, 00:52 | Сообщение # 1

Авторитетный

Зарегистрирован: 24.07.2011

Группа: Модераторы

Сообщений: 469

Статус: Offline

В общем я когда-то перерыл и перелопатил весь инет и так и не нашёл толковой информации по этой теме, особенно на Delphi. sad

И тут я, значит, брожу по гуглу и ищу инфу по одной теме и случайно тыкаю не на ту ссылку. И попадаю на известный блог: http://www.manhunter.ru/assembler/ И что я вижу! "Расчет энтропии на Ассемблере" и думаю: "Там, наверное, килотонны кода". Открываю и охреневаю от компактности кода. Дальше я быстро принимаюсь переписывать его на Delphi. Благо моих скромных познаний асма на это хватило. biggrin

Вот по этой формуле ведётся расчёт (Хотя я в математике дуб-дубом) biggrin

А вот и сам код:

Код

function CalcMemoryEntropy(const Memory: Pointer; Size: Cardinal): Extended;
var
    Prob, Log2: Extended;
    I, Sum, Chr: Integer;
    Code: array[0..255] of Byte;
begin
    Result:=0;
    if (Memory=nil)or(Size=0) then
       Exit
    else
    begin
       for I:=0 to(Length(Code)-1) do
          Code[I]:=0;
       I:=0;
       Sum:=0;
       while (Cardinal(I)<Size) do
       begin
          Chr:=(Cardinal(PChar(Memory)[I]));
          Inc(Code[Chr]);
          Inc(Sum);
          Inc(I);
       end;
       Log2:=Math.Log2(2.0);
       for I:=0 to(Length(Code)-1) do
       begin
          if (Code[I]>0) then
          begin
             Prob:=Code[I]/Sum;                    // P(i) = SUM(i)/total
             Result:=(Result-(Prob*(Math.Log2(Prob))/Log2));   // H(i) = -P(i)*log2(P(i))
          end;
       end;
    end;
end;

Как видим, код получился достаточно простым.

Вот расчет для строки:

Код

function CalcStringEntropy(Str: string): Extended;
begin
Result:=CalcMemoryEntropy(PChar(Str), (Length(Str)));
end;

И примеры:

Без округлений энтропии:

Код

MessageBox(0, PChar(FloatToStr(CalcStringEntropy('123456789'))), nil, 0);

И с округлением до двух чисел после запятой:

Код

MessageBox(0, PChar(FormatFloat('#.##', CalcStringEntropy('123456789'))), nil, 0);

В первом случае результат будет: 3.169925000144231, а во втором 3.17.

Для чего это нужно и кому это надо? Это пригодится, например, для определения пакованности файла (как это делает PeID или DiE) и т.д.

P.S. Для вычисления энтропии файла достаточно немного изменить код.
P.S.S. Информация по теме: Wikipedia

biggrin

-------------------------------------------------------------
Забыл сказать. Для работы требуется модуль Math.

Сообщение отредактировал Волк-1024 - Понедельник, 09.07.2012, 23:57

Волк-1024

Дата: Пятница, 21.09.2012, 14:52 | Сообщение # 2

Авторитетный

Зарегистрирован: 24.07.2011

Группа: Модераторы

Сообщений: 469

Статус: Offline

Недавно снова затронул эту тему, поэтому решил немного изменить код:

Code

function CalculateMemoryEntropy(const Data: Pointer; Size: Cardinal): Extended;
var
    Prob, Log2: Extended;
    I, Sum, Chr: Cardinal;
    Code: array[0..255] of Cardinal;
begin
    Result:=0;
    if not(Assigned(Data))or(Integer(Size)<=0) then
       Exit
    else
    begin
       I:=0;
       Sum:=0;
       ZeroMemory(@Code, (Length(Code))*(SizeOf(DWORD))); // 256*4
       while (I<Size) do
       begin
          Chr:=(Cardinal(PChar(Data)[I]));
          Inc(Code[Chr]);
          Inc(Sum);
          Inc(I);
       end;
       Log2:=Math.Log2(2.0);
       for I:=0 to(Length(Code)-1) do
       begin
          Prob:=Code[I]/Sum; // P(i) = SUM(i)/total
          if (Prob>0)and(Code[I]>0) then
             Result:=(Result-(Prob*(Math.Log2(Prob))/Log2)); // H(i) = -P(i)*log2(P(i))
             //Result:=(Result+(Abs(Prob*(Math.Log2(Prob)*Log2)))); // Можно и так. Результат один и тот же.
       end;
    end;
end;

Теперь им можно вычислять и энтропию файла. Указатель на буфер с файлом пихать в Data, а его размер в Size. smile

Сообщение отредактировал Волк-1024 - Пятница, 21.09.2012, 15:20

anuar_ast

Дата: Четверг, 24.11.2016, 15:30 | Сообщение # 3

Новичок

Зарегистрирован: 24.11.2016

Группа: Пользователи

Сообщений: 1

Статус: Offline

как можно сделать чтобы с текстового файла читал текст и вычитывал энтропию текста?

B64D919B

Дата: Вторник, 05.06.2018, 00:23 | Сообщение # 4

Новичок

Зарегистрирован: 05.06.2018

Группа: Пользователи

Сообщений: 1

Статус: Offline

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

Код

function CalcEntropyForBuffer(Buffer: Pointer; BufferSize: NativeUInt): Double;
const
    DbLog: Double = 1.4426950408889634073599246810023;
var
    Entries: array [0 .. 255] of NativeUInt;
    i: NativeUInt;
    Temp: Double;
begin
    Result := 0.00;
    ZeroMemory(@Entries, SizeOf(Entries));
    for i := 0 to (BufferSize - 1) do
  inc(Entries[PByte(NativeUInt(Buffer) + i)^]);
    for i := 0 to 255 do
    begin
  Temp := Entries[i] / BufferSize;
  if (Temp > 0) then
   Result := Result + Temp * (Ln(Temp) * DbLog);
    end;
end;

Замечание на всякий случай - этот код считает энтропию файлов/данных до ~4 Гб. Если надо больше, сами знаете, что и на что заменить.

Сообщение отредактировал B64D919B - Вторник, 05.06.2018, 00:28

Расчет энтропии (Delphi)

Страница 1 из 1
1