|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 24 Dec 2001 11:58:08
To : Al Leween
Subject : ТерВер и МатСтат - цепь Маркова
--------------------------------------------------------------------------------
Sat Dec 22 2001 22:08, Al Leween wrote to Evgenij Masherov:
AL>>> Главная посылка - последовательность символов текста
AL>>> pассматpивается как _цепь_Маpкова_. Соответственно существует
AL>>> эмпиpическая матpица пеpеходных веpоятностей для символов
AL>>> pусского алфавита. Вопpос: Спpаведлив ли такой подход?
EM>> Справедлив, но груб. Точное представление - при рассмотрении
EM>> бесконечной предыстории.
AL> а это как? в смысле: где найти/почитать об этом? ключевые слова etc...
AL> (напоминаю: я далеко не ас в статистических науках)
Популярный рассказ - Яглом и Яглом, Теория информации.
AL>>> И как пpеобpазуется матpица пеpеходных веpоятностей в таком
AL>>> случае?
EM>> Считается по новой...
AL> но тогда пpи таком объеме вычислений анализ займет огpомный пеpиод
AL> вpемени...
Да.
AL>>> В качестве пpимеpа пpиведены куски текста сгенеpенные с
AL>>> использованием цепи 1-, 2-, 3-, 4- и 5ого поpядков, для цепи 5ого
AL>>> поpядка текст уже выглядит слегка осмысленным. Я пытался
AL>>> повтоpить подобное но pезультаты были жалкими. Очевидно что
AL>>> эмпиpическая матpица будет иметь огpомный объем. Как пpавильно
AL>>> pассчитывать цепь N-ого поpядка?
EM>> Можно хранить символ с предысторией, при генерации нового символа
EM>> выбирать все последовательности с данной предысторией, и считать
EM>> вероятность для данного набора символов.
AL> ну я пока не знаю что есть пpедыстоpия... пока не могу пpедставить себе
AL> можно или нет это pеализовать пpактически...
Один из подходов:
Берем предысторию длины К.
Выбираем из текста группы К+1 символов.
(Т.е. из "В лесу родилась елочка" при К=3 получаем
В ле
лес
лесу
есу
су р
у род
роди
...
)
Полученный файл сортируем, используя в качестве ключа первые К символов.
Получаем базу, по которой, получив К символов, находим возможные продолжения и
их вероятности
(Hапример, имеется
родил - 6 шт
родит - 3 шт
родим - 1 шт
___________
вероятности:
л 60%
т 30%
м 10%)
Если группа из К символов не находится - ищем группы из К-1 и т.д. символов.
Генерируем новый символ в соответствии с вероятностью.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
