Сама задача: Под N-граммой понимается последовательность из N слов. При решении можно считать, что все слова пронумерованы, и работать с последовательностью из N целых чисел.

Задача обучения: Пусть имеется последовательность X = {x(i)}, где i - индекс(i = 1..T). Данный набор, как правило, называют набором обучающих данных. Необходимо вычислить и запомнить вероятности вхождения для любой подпоследовательности из N подряд идущих значений p(x(i), x(i+1), .., x(i+N)) = c(x(i), x(i+1), .., x(i+N)) / T - N, где c(x(i), x(i+1), .., x(i+N)) - количество встреч подпоследовательности x(i), x(i+1), .., x(i+N) в X. Вычисление вероятности для N-граммы: Для последовательности чисел y(i), y(i+1), .., y(i+N) необходимо вернуть вероятность ее встречи в последовательности X - p(x(i), x(i+1), .., x(i+N)). С задачей обучения всё более-менее ясно, а вот с вычислением вероятности для N-граммы не совсем. Что за числа эти y(i), y(i+1), .., y(i+N)? произвольные числа? когда числа x(i+1), .., x(i+N) в X это числа, которые должны обязательно входить в X? А что такое X - p(x(i), x(i+1), .., x(i+N))??? Когда X-множество, а p(x(i), x(i+1), .., x(i+N)) - число.И как для этого считать вероятность вхождения чисел y(i), y(i+1), .., y(i+N)?? Кто может, объясните по подробнее пожалуйста.

задан 9 Мар '13 21:42

изменен 9 Мар '13 21:43

10|600 символов нужно символов осталось
1

В постановке задачи имеется много путаницы, хотя суть вполне понятна. Я предлагаю изложить всё заново. Дана строка из $%T$% символов. Для любой строки из $%N+1$% символа, где $%N< T$%, рассматривается количество вхождений этой подстроки в заданную строку. (В тексте говорится об $%N$% подряд идущих значениях, в то время как они имеют вид $%x(i),x(i+1),\ldots,x(N)$%, то есть их на самом деле $%N+1$%.)

Например, если исходная строка имеет вид $%0110001110$%, то $%T$% равно десяти, и подстрока $%01$% имеет два вхождения, а подстрока $%11$% имеет три вхождения. Здесь $%N=1$%, и вероятности встретить рассматриваемую подстроку в "случайном" месте равны $%2/9$% и $%1/3$% соответственно. Делим мы здесь на $%T-N$%, то есть на общее число подстрок из $%N+1$% символа. (Знаменатель дроби $%T-N$% в тексте должен быть окружён скобками.)

Символы $%y(i),\ldots,y(i+N)$% означают ровно то же самое, что только что было обозначено в виде "иксов". А конструкция с "минусом" здесь означает просто тире: если его заменить на оборот "обозначаемая через", то получится осмысленная фраза.

Подсчёт вероятности осуществляется по простому алгоритму: нам известна строка и подстрока, а также числа $%N$% и $%T$%. Анализируем все вхождения подстрок данной длины (их будет $%T-N$%), сравнивая их поочерёдно с нашей подстрокой. В программе это реализуется как цикл внутри цикла. Найденное количество вхождений делим на $%T-N$%, находя вероятность.

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

ссылка

отвечен 9 Мар '13 22:14

Спасибо большое! Теперь более-менее понятно!

(9 Мар '13 22:32) rekrut
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,000

задан
9 Мар '13 21:42

показан
1347 раз

обновлен
9 Мар '13 22:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru