VPF::Энтропия текста - Форум программистов

volatile

Дата 4.12.2012, 00:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(baldina @ 3.12.2012, 10:41

)

архиваторы используют адаптивное сжатие.

Да какое бы сжатие они не использовали, они не могут нарушить закон:
"Информация - не сжимаема"
это такой-же основополагающий закон, как и закон сохранения энергии.

Цитата(baldina @ 3.12.2012, 10:41

)

если частоты известны заранее,

да в том то и дело, что частоты не известны. И получение этих частот выходит далеко за рамки этой темы.

Ту энтропию что вы посчитаете, это не настоящая энтропия. Эта некая абстрактная, отвлеченная от реальности энтропия.
Впрочем, это видимо и нужно по заданию.
так что считайте на здоровье.
smile

Bugrimov

Дата 4.12.2012, 05:16 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 24
Регистрация: 8.11.2012

Репутация: нет
Всего: нет

Формулу эту я встречал, но практической реализации ее не видел.

Код


total = 0;
    prev = fgetc(pf);
    while((ch = fgetc(pf)) != EOF)
    {
        if (strchr(".,:!?'\"", ch))
            ch = '.';
        code_p[prev*256 + ch]++;
        prev = ch;
    }

    for(i = 0; i < 256*256; i++)
        total += code_p[i];
    
    for(i = 0; i < 256*256; i++)
        if(code_p[i])
        entr_p -= code_p[i]*log(((float)code_p[i])/total);
    entr_p /= log(2)*total*2;
    max_entr_p = log(total)/log(2.7);
    printf("\n Энтр. для пар символов: %6.3f Макс. энтропия: %6.3f Избыточ.: %6.3f", entr_p, max_entr_p, max_entr_p/entr_p);

Вот все что есть по этому поводу. Хотя уже понятно, что log(2), вместо log(2.7).
Можете что-нибудь подсказать на уже имеющемся программном коде.

Код


void entropy(void)
{
    FILE    *pf = NULL;
    char    file[SIZE];
    long    ch, i, prev, total = 0;
    int        code[256] = {0}, code_p[256*256] = {0};
    float    entr = 0, entr_p = 0, max_entr, max_entr_p;
    int        m, rusTotal = 0, engTotal = 0, punTotal = 0;
    int        lastch = EOF; 

    

    Messages(2);
    printf("\n\n");
    system("DIR /a:-d");
    
    
    printf("\n Введите имя файла: ");
    gets(file);
    pf = fopen(file, "rt");    // Открытие файла для чтения
    if(pf == NULL)
    {
        Messages(3);
        printf("\n Выбрать файл (ENTER) / Выход в меню (ESC)");
        if(getch() == 27)
            menu();
        else
            entropy();
    }
    
    while((ch = fgetc(pf)) != EOF)
    {
  
        if(isalpha(ch))
        {
            ch = tolower(ch);
            if(ch == 'ё') ch = 'е';
                code[ch]++;
    
            if(ch >= 0x80) 
                rusTotal++; 
            else 
                engTotal++;
            if(lastch != EOF) 
                code_p[256*lastch + ch]++;
        }
        else 
        {
            ch = '.'; // всё остальное
            code[ch]++;
            punTotal++;
            if(lastch != EOF) 
                code_p[256*lastch + ch]++;
        }
        lastch = ch;
    }

    fclose(pf);
    
    if(engTotal == 0 && rusTotal == 0)
         m = 26 + 1; // будем считать, что это был английский текст...
    else if(engTotal == 0)
        m = 32 + 1;
    else if(rusTotal == 0)
        m = 26 + 1;
    else 
        m = 26 + 32 + 1;
    total = rusTotal + engTotal + punTotal;

    for(i = 0; i < 256; i++)
    if(code[i])
        entr -= (float)code[i] * log((float)code[i] / (float)total);
    entr /= log(2)*total;
    max_entr = log(m)/log(2);
printf("\n Энтр. для символа: %6.3f Макс. энтропия: %6.3f", entr, max_entr);
    printf("\n Избыточ.: %6.3f", 1-entr/max_entr);
fclose(pf);
    getch();
}

feodorv

Дата 4.12.2012, 06:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Bugrimov @ 4.12.2012, 06:16

)

Можете что-нибудь подсказать на уже имеющемся программном коде.

Ну, просто возникло устойчивое чувство, что я вместо Вас делаю Вашу лабораторную работу smile

Давайте подсчитаем вероятность встречи в тексте пары символов AB:

Код


p(AB) = {вероятность символа A, если за ним следует ещё символ} * {вероятность того, что после A в тексте встретится B} = p(A) * p(B|A)

Правда, здесь есть небольшая тонкость, связанная с тем, что у последней в тексте буквы пары нет (за ней не следует никакая другая), поэтому в при учёте вероятностей букв последнюю букву в тексте мы учитывать не будем, хотя пару символов, в которую она входит, учтём. Иначе не сойдутся вероятности))) Этот факт выражается также в том, что для текста из total символов число пар символов только (total-1). Из-за этого сразу после первого этапа в программе сделаем небольшую коррекцию:

Код

.....
getch();

if( total < 2 )
{
  // дальше считать смысла нет, энтропия 0
  printf("\n Энтр. для пары символов: 0");
  return 0;
}
total--; // число пар в тексте
code[lastch]--; // последний символ в вероятностях для пар не учитывается

Подготовившись таким образом, мы можем вычислить p(A):

Код


p(A) = {число всех букв A в тексте, начинающих пару символов} / {число всех букв в тексте, начинающих пару символов} = code[A] / total

как и для первого этапа, но с учётом специфики пар, то есть ранее оговоренной тонкости.

Подсчитаем вероятность буквы B, если перед ней стояла буква A:

Код


p(B|A) = {число пар AB} / {общее число пар, где первой является A}

Если как следует подумать, то придёт понимание, что {общее число пар, где первой является A} есть просто число букв A в тексте (с учётом ранее оговоренной тонкости) (хотя в коде, если не лень и нет веры, можно подсчитать в цикле))) То есть:

Код


p(B|A) = {число пар AB} / {число всех букв A в тексте} = code_p[A*256+B] / code[A]

Итого:

Код


p(AB) = ({число всех букв A в тексте, начинающих пару символов} / {число всех букв в тексте, начинающих пару символов}) * 
            ({число пар AB} / {число всех букв A в тексте, начинающих пару символов}) = 
    {число пар AB} / {число всех букв в тексте, начинающих пару символов}

А с учётом того, что {число всех букв в тексте, начинающих пару символов} есть просто-напросто {общее число пар символов в тексте}, получаем невероятный, умопомрачительный результат

Код


p(AB) = (число пар AB) / (общее число пар символов в тексте) = code_p[A*256+B] / total

Осталось всё это подставить в

Цитата(feodorv @ 3.12.2012, 11:16

)

ent2 = - sum(i:total) sum(j:total) p(ij) * log( p(ij) )

и получить готовый результат.

Мне безумно хочется получить от Вас значение для максимальной энтропии пар. Оно интересно и весьма поучительно.

Добавлено через 4 минуты и 10 секунд
У Вас в коде файл два раза закрывается:

Цитата(Bugrimov @ 4.12.2012, 06:16

)

fclose(pf);
...
fclose(pf);

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 6.12.2012, 09:36 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(feodorv @ 4.12.2012, 07:16

)

Мне безумно хочется получить от Вас значение для максимальной энтропии пар. Оно интересно и весьма поучительно.

Чувствую, даже попыток вычислить искомое не будет smile

А жаль. Всё вычисляется элементарно...

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »