Энтропия (для математиков)
Вопрос, в общем, для математиков. В процессе написания одного задания встала проблема.
Дан текст, требуется найти его энтропию (в битах). Проблема в том, что надо найти энтропию первого-шестого порядка.
Реализовать "в лоб" я могу, но это не разумно, сами понимаете. Так как если энтропия первого-второго порядка считается норм, то для высчитывания энтропии 6 порядка потребуется значительное время.
Вопрос такой - есть ли какие-либо готовые формулы, которые позволяют находить энтропию n-порядка без физического перебора?? Ну или алгоритмы, которые значительно оптимизируют процесс нахождения?
Если есть готовый код, то тоже хорошо. Язык значения не имеет - разберусь спокойно в любом.
ЗЫ: в гугл не слать. Особо толкового я там ничего не нашел.
Дан текст, требуется найти его энтропию (в битах). Проблема в том, что надо найти энтропию первого-шестого порядка.
Реализовать "в лоб" я могу, но это не разумно, сами понимаете. Так как если энтропия первого-второго порядка считается норм, то для высчитывания энтропии 6 порядка потребуется значительное время.
Вопрос такой - есть ли какие-либо готовые формулы, которые позволяют находить энтропию n-порядка без физического перебора?? Ну или алгоритмы, которые значительно оптимизируют процесс нахождения?
Если есть готовый код, то тоже хорошо. Язык значения не имеет - разберусь спокойно в любом.
ЗЫ: в гугл не слать. Особо толкового я там ничего не нашел.
Такой формулы нет.Чтобы определить придётся решать "в лоб". Конечно, для энтропии 6-го порядка текста(256 символов) придётся попотеть(нехилый такой словарик получится - 256^6).Советую вам книгу Яглом "Вероятность и информация".Этот вопрос там рассмотрен достаточно хорошо.
