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

Bugrimov

Дата 26.11.2012, 18:08 (ссылка)

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

Загрузка ...

Новичок

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

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

Доброе время суток!
Нужна помощь в вопросе нахождения энтропии текста, максимальной энтропии и избыточности текста. Кто-нибудь сталкивался с данным вопросом?

Добавлено @ 18:13
Есть следующая функция, до которой я додумался

Код


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;
    

    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(strchr(".,:;?!-\'\"", ch))    // Если в тексте встречаются знаки препинания
            ch = '.';                    // объединить в один символ '.'
        code[ch]++;    // Считает число символов каждого типа
        
    }

    for(i = 0; i < 256; i++)
        total += code[i];    // Число символов

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

    fclose(pf);
    getch();
}

Но, на сколько я понимаю, максимальная энтропия и избыточность находятся не верно. smile

Нужен совет знающих людей.

Это сообщение отредактировал(а) Bugrimov - 26.11.2012, 18:15

Dem_max

Дата 26.11.2012, 18:24 (ссылка)

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

Загрузка ...

Эксперт

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

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

А что значит энтропия текста ?

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

Американские программисты долго не могли понять, почему русские при зависании Windоws всё время повторяют "Твой зайка написал" ("Yоur bunnу wrоte")

Bugrimov

Дата 26.11.2012, 18:55 (ссылка)

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

Загрузка ...

Новичок

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

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

http://ru.wikipedia.org/wiki/%C8%ED%F4%EE%...%F0%EE%EF%E8%FF

Добавлено через 6 минут и 45 секунд
http://www.sernam.ru/book_tec.php?id=53

Dem_max

Дата 27.11.2012, 03:07 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата

разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других.

как известно гласных в словах больше, но именно согласные несут информацию в словах. Если из слова убрать все гласные буквы, то это слово мы по прежнему можем понять по согласным буквам.

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

Bugrimov

Дата 27.11.2012, 04:52 (ссылка)

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

Загрузка ...

Новичок

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

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

Есть какие-нибудь соображения по поводу кода

feodorv

Дата 27.11.2012, 07:04 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Bugrimov @ 26.11.2012, 19:08

)

max_entr = log(total)/log(2);

На вид, должно быть не log(total), а log(256) (ну, или если Вы все знаки препинания свалили в одну кучу, то логарифм меньшего числа, чем 256).

Цитата(Bugrimov @ 26.11.2012, 19:08

)

printf("\n Избыточ.: %6.3f", max_entr_p/entr_p);

Судя по учебнику, должно быть

Код


    printf("\n Избыточ.: %6.3f", 1-entr_p/max_entr_p);

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

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

Bugrimov

Дата 27.11.2012, 19:30 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата

log(256)

Но в тексте файла могут не использоваться все символы (256). Максимальная энтропия не рассчитывается от размера алфавита например текст "aaacccbbms" - размер алфавита 5, т.е. 5 символов, поправьте меня если я ошибаюсь. Как тогда должен выглядеть программный код?

feodorv

Дата 27.11.2012, 22:53 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Bugrimov @ 27.11.2012, 20:30

)

Но в тексте файла могут не использоваться все символы (256).

Могут, но Вы же их учитываете (посмотрите, как формируется total), учитываете даже пробелы, табуляцию, перенос строк, различаете строчные буквы от прописных.

Потом, если в тексте не встретилась какая-то буква алфавита, то это не значит, что её существование можно проигнорировать (как раз нет, просто она редко встречается).

Цитата(Bugrimov @ 27.11.2012, 20:30

)

Как тогда должен выглядеть программный код?

Ограничьте себя английским алфавитом или русским. Не различайте строчные и прописные буквы. Если есть необходимость в учёте знаков препинания - учитывайте. Все остальные символы игнорируйте. Соответственно вместо 256 получится 26/27 или 32/33/34 (если учитывать ё и пунктуацию) символов.

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

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

volatile

Дата 27.11.2012, 23:37 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Bugrimov @ 26.11.2012, 18:08

)

else
entropy();

Рекурсия здесь не нужна абсолютна.

По поводу энтропии. вы ее никогда точно не посчитаете.
Приблизительно её можно оценить с помощью архиватора.
Архиваторы, асимтотично стремятся к некому пределу сжатия.
У кого-то лучше получается, у кого-то хуже.
Со временем появляются новые архиваторы, которые сжимают текст еще лучше.
Но ни один архиватор никогда не сможет сжать текст ниже уровня энтропии.
А вот каков он этот предел... кто ответит? smile

Bugrimov

Дата 28.11.2012, 04:57 (ссылка)

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

Загрузка ...

Новичок

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

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

Я пытался добиться следующего:
Открыть любой текстовый файл. Рассчитать его энтропию (регистр не учитывается - строчные и прописные символы одинаковые, все знаки препинания подсчитать как один символ - любой символ), максимальную энтропию и избыточность текста. В коде рассмотрен еще один вариант - для пар символов. Я полагал, что есть определенная формула по расчету энтропии, максимальной энтропии, избыточности. С энтропией и избыточностью вроде разобрался с макс. энтропией вообще ничего не понятно. Есть у кого-нибудь образец кода.

feodorv

Дата 28.11.2012, 07:42 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Bugrimov @ 28.11.2012, 05:57

)

регистр не учитывается - строчные и прописные символы одинаковые

В коде, который Вы привели, регистр учитывается. А так же пробелы, табуляция, перевод строки и прочая.
Судя по заданию, нужно именно ограничиться каким-то языком (русским или английским), плюс пунктуация.

Цитата(Bugrimov @ 28.11.2012, 05:57

)

Есть у кого-нибудь образец кода.

А при чём здесь образец кода, когда максимальная энтропия достигается при равных вероятностях для всех букв алфавита?

Код


max_entr = log(m)/log(2);

где m - число букв алфавита (с учётом пунктуации).

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

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

Bugrimov

Дата 29.11.2012, 04:42 (ссылка)

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

Загрузка ...

Новичок

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

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

Подскажите пожалуйста как в моем куске кода можно сделать, чтобы регистр не учитывался, знаки препинания (табуляция и пробелы) считались как один символ.
Число букв алфавита m.
Для большего понимания. Например текст: фффаааяяя qqrrr (6 букв алфавита). Я верно понимаю? Или учитываются все буквы алфавита. Если например текст латинница - все буквы латинского языка, если русский - то русского.

Это сообщение отредактировал(а) Bugrimov - 29.11.2012, 04:46

feodorv

Дата 30.11.2012, 19:15 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Bugrimov @ 29.11.2012, 05:42

)

Или учитываются все буквы алфавита.

Честно говоря, для большей ясности лучше спросить у заказчика)))
Лично я бы тупо ограничился английским алфавитом, завёл бы массив из 27 позиций (26 на буквы, 1 на остальные символы) и сделал бы аналогично Вашему коду, только иначе бы вычислял индекс массива:

Код

int index, ch;

if( ch >= 'A' && ch <= 'Z' )
  index = ch - 'A';
else if( ch >= 'a' && ch <= 'z' )
  index = ch - 'a';
else
  index = 26;

code[index]++;

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

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

Bugrimov

Дата 30.11.2012, 20:21 (ссылка)

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

Загрузка ...

Новичок

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

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

Будут открываться текстовые файлы на русском или английском языке, возможно это предусмотреть как-нибудь в коде.

Цитата(Bugrimov @ 29.11.2012, 04:42

)

Для большего понимания. Например текст: фффаааяяя qqrrr (6 букв алфавита). Я верно понимаю? Или учитываются все буквы алфавита. Если например текст латинница - все буквы латинского языка, если русский - то русского.

Этот вопрос так же актуален... smile

feodorv

Дата 30.11.2012, 20:30 (ссылка)

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

Загрузка ...

Эксперт

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

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

А что по этому поводу говорит "заказчик"?

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

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

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