|
Сама задача: Под 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 
rekrut |
|
В постановке задачи имеется много путаницы, хотя суть вполне понятна. Я предлагаю изложить всё заново. Дана строка из $%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 
falcao Спасибо большое! Теперь более-менее понятно!
(9 Мар '13 22:32)
rekrut
|