Вычисление энтропии текста -- Sage

Список источников:

urls = [ "http://lib.ru/DIC/OZHEGOW/ozhegow_a_d.txt", "http://lib.ru/DIC/OZHEGOW/ozhegow_e_l.txt", "http://lib.ru/DIC/OZHEGOW/ozhegow_m_o.txt", "http://lib.ru/DIC/OZHEGOW/ozhegow_p_r.txt", "http://lib.ru/DIC/OZHEGOW/ozhegow_s_q.txt" ] # Словарь Ожегова

выбор кодировки:

import codecs decoder = codecs.getreader('cp1251')

Открытие источников:

import urllib2 files = [ decoder(urllib2.urlopen(url), errors='ignore') for url in urls ]

Хранилища структурированных данных:

letters = {} lettersc = {} words = {} totalletters = 0 totalwords = 0 prevletter = None prevword = None

Функции для добавления данных в структуры:

def inc_if_has(d,el): if d.has_key(el): d[el] = d[el] + 1 else: d[el] = 1 def inc_if_has_prev(d, el, prev): if prev == None: return if d.has_key(prev): if d[prev].has_key(el): d[prev][el] = d[prev][el] + 1 else: d[prev][el] = 1 else: d[prev] = {} d[prev][el] = 1

Считывание источников:

import re import string regexp = re.compile('['+string.punctuation+string.whitespace+string.digits+r'a-z\\]+') for file in files: for line in file: line = line.strip(); if len(line) < 1: continue; if line[0] == u'<': continue; line = line.lower() for word in regexp.split(line, re.UNICODE): for char in word: inc_if_has(letters, char) inc_if_has_prev(lettersc, char, prevletter) totalletters = totalletters + 1 prevletter = char inc_if_has(words, word) totalwords = totalwords + 1 prevword = word file.close()

Всего символов в тексте:

totalletters

Всего слов в тексте:

totalwords

Сколько раз встретился символ "й":

letters[u'й']

Сколько раз встретилось слово "текст":

words[u'текст']

Подсчёт вероятностей для символов:

letter_probs ={} for key,value in letters.iteritems(): letter_probs[key] = n(value/totalletters);

Подсчёт вероятностей для слов:

word_probs ={} for key,value in words.iteritems(): word_probs[key] = n(value/totalwords);

Вероятность того, что произвольный символ из текста, окажется буквой "а"

letter_probs[u'а']

0.0775585515171020

0.0775585515171020

Вероятность того, что произвольное слово из текста, окажется словом "ответ":

word_probs[u'ответ']

0.0000974245192947143

0.0000974245192947143

Уникальных символов:

unique_letters = len( letters ) unique_letters

Сколько раз в среднем используется каждый символ:

n(totalletters/unique_letters)

165045.705882353

165045.705882353

Уникальных слов:

unique_words = len( words ) unique_words

Сколько раз в средним используется каждое слово:

n(totalwords/unique_words)

7.91631010663269

7.91631010663269

Энтропия для алфавита из букв, т.е. сколько бит нужно на символ для кодирования текста:

entropy_letters = -sum([n(p*log(p, 2)) for p in letter_probs.values()]); entropy_letters

4.49914108954347

4.49914108954347

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

entropy_letters1 = 0 for c in letters.keys(): temp = 0 followed = sum( lettersc[c].values() ) for char in letters.keys(): if (lettersc[c].has_key(char)): p = lettersc[c][char] / followed temp = temp - n(p*log(p, 2)) entropy_letters1 = entropy_letters1 + temp * letter_probs[c] entropy_letters1

3.86169238777431

3.86169238777431

Энтропия для алфавита из уникальных слов текста, т.е. сколько бит нужно на слово для кодирования текста:

entropy_words = 0 for p in word_probs.values(): entropy_words = entropy_words - n(p*log(p, 2)) entropy_words

11.6318837673449

11.6318837673449

При средней длина слова

midwordlen = n(totalletters/totalwords) midwordlen

4.75393870388114

4.75393870388114

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

midwordlen*8

38.0315096310491

38.0315096310491

и даже меньше, чем количество бит, используя которое можно было бы закодировать слово, ограничиваясь только символами алфавита:

n(midwordlen*log(unique_letters, 2))

24.1854865055771

24.1854865055771

Вычисление энтропии текста

622 days ago by kpp