Редактирование: N-грамма

{{стиль}}
'''N-грамма''' — последовательность из n элементов<ref>Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakia, pp. 54-65, February 2008. ISBN 978-80-227-2827-0.</ref>. С [[семантика|семантической]] точки зрения, это может быть [[последовательность]] звуков, слогов, слов или букв. На практике чаще встречается N-грамма как ряд слов, устойчивые словосочетания называют [[Коллокация (лингвистика)|коллокацией]]. Последовательность из двух последовательных элементов часто называют '''биграмма''', последовательность из трёх элементов называется '''триграмма'''. Не менее четырёх и выше элементов обозначаются как N-грамма, N заменяется на количество последовательных элементов.

== Использование N-грамм ==

=== Общее использование N-грамм ===
N-граммы в целом находят свое применение в широкой области наук. Они могут применяться, например, в области теоретической [[математика|математики]], [[биология|биологии]], [[картография|картографии]], а также в [[музыка|музыке]]. Наиболее часто использование N-грамм включает следующие области:
* извлечение [[данные|данных]] для [[кластеризация|кластеризации]] серии спутниковых снимков Земли из космоса, чтобы затем решить, какие конкретные части Земли на изображении,
* поиск [[Генетический код|генетических последовательностей]],
* в области [[генетика|генетики]] используются для определения того, с каких конкретных видов животных собраны образцы [[ДНК]],
* в компьютерном [[сжатие данных|сжатии]],
* для [[поисковый индекс|индексирования]] данных в [[поисковая система|поисковых системах]]; с использованием N-грамм, как правило, индексированы данные, связанные со звуком.
Также N-граммы широко применяются в [[Обработка естественного языка|обработке естественного языка]].

=== Использование N-грамм для нужд обработки естественного языка ===
В области обработки естественного языка N-граммы используется в основном для предугадывания на основе [[Теория вероятностей|вероятностных моделей]]. N-граммная модель рассчитывает [[вероятность]] последнего слова N-граммы, если известны все предыдущие. При использовании этого подхода для моделирования языка предполагается, что появление каждого слова зависит только от предыдущих слов<ref>{{книга
 | автор         = Jurafsky, D. and Martin, J.H.
 | заглавие      = Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition
 | издательство  = Pearson Prentice Hall
 | год           = 2009
 | allpages      = 988
 | isbn          = 9780131873216
 | ref           = Jurafsky, D. and Martin, J.H.
}}</ref>.

Другое применение N-грамм является выявление [[плагиат]]а. Если разделить текст на несколько небольших фрагментов, представленных N-граммами, их легко сравнить друг с другом, и таким образом получить степень сходства контролируемых документов<ref>Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008. ISBN 978-80-969184-8-5</ref>. N-граммы часто успешно используются для категоризации текста и языка. Кроме того, их можно использовать для создания функций, которые позволяют получать знания из текстовых данных. Используя N-граммы, можно эффективно найти кандидатов, чтобы заменить слова с ошибками правописания.

=== Пример биграммной модели ===
Целью построения N-граммных моделей является определение вероятности употребления заданной фразы. Эту вероятность можно задать формально как вероятность возникновения последовательности слов в неком [[Корпусная лингвистика|корпусе]] (наборе текстов). К примеру, вероятность фразы «счастье есть удовольствие без раскаяния» можно вычислить как произведение вероятностей каждого из слов этой фразы:

<small><pre>P = P(счастье) * P(есть|счастье) * P(удовольствие|счастье есть) * P(без|счастье есть удовольствие) * P(раскаяния|счастье есть удовольствие без)</pre></small>

Чтобы определить P(счастье) нужно посчитать сколько раз это слово встретилось в тексте, и поделить это значение на общее число слов. Рассчитать вероятность P(раскаяния|счастье есть удовольствие без) сложнее. Чтобы упростить эту задачу, примем, что вероятность слова в тексте зависит только от предыдущего слова. Тогда наша формула для расчета фразы примет следующий вид:

<small><pre>P = P(счастье) * P(есть|счастье) * P(удовольствие|есть) * P(без|удовольствие) * P(раскаяния|без)</pre></small>

Рассчитать условную вероятность P(есть|счастье) несложно. Для этого считаем количество пар 'счастье есть', и делим на количество в тексте слова 'счастье'.

В результате, если мы посчитаем все пары слов в некотором тексте, мы сможем вычислить вероятность произвольной фразы. Этот набор рассчитанных вероятностей и будет биграммной моделью.

== Научно-исследовательские проекты Google ==
Исследовательские центры [[Google]] использовали N-граммные модели для широкого круга исследований и разработок. К ним относятся такие проекты, как [[Статистический машинный перевод|статистический перевод]] с одного языка на другой, [[распознавание речи]], исправление орфографических ошибок, [[извлечение информации]] и многое другое. Для целей этих проектов были использованы текстовые корпусы, содержащие несколько триллионов слов.

Google решила создать свой учебный корпус. Проект называется Google teracorpus и он содержит 1 024 908 267 229 слов, собранных с общедоступных веб-сайтов<ref>FRANZ, Alex, BRANTS, Thorsten. [http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html Official Google Research Blog: All Our N-gram are Belong to You]. Thursday, August 03, 2006 at 8/03/2006 11:26:00 AM. Созданная база N-грамм продаётся в виде 5 DVD.</ref>.

== Методы для извлечения N-грамм ==
В связи с частым использованием N-грамм для решения различных задач необходим надежный и быстрый [[алгоритм]] для извлечения их из текста. Подходящий инструмент для извлечения N-грамм должен быть в состоянии работать с неограниченным размером текста, работать быстро и эффективно использовать имеющиеся ресурсы. Есть несколько методов извлечения N-грамм из текста. Эти методы основаны на разных принципах:
* ''Алгоритм Nagao 94'' для текстов на [[Японский язык|японском]]<ref>M. Nagao and S. Mori. A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese. In Proceedings of the 15th International Conference on Computational Linguistics (COLING 1994), Kyoto, Japan, 1994.</ref>
* [[Алгоритм Лемпеля — Зива — Велча]]
* [[Суффиксный массив]]
* [[Суффиксное дерево]]
* [[Инвертированный индекс]]

== Синтаксические N-граммы ==
Синтаксические N-граммы — это N-граммы, определяемые путями в деревьях синтаксических зависимостей или деревьях составляющих, а не линейной структурой текста<ref name="sng">Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández. Syntactic Dependency-based N-grams as Classification Features. LNAI 7630, pp. 1-11, 2012.</ref><ref>Grigori Sidorov. Syntactic Dependency Based N-grams in Rule Based Automatic English as Second Language Grammar Correction. International Journal of Computational Linguistics and Applications, Vol. 4, No. 2, pp. 169—188, 2013.</ref>. Например, предложение: «Экономические новости оказывают незначительное влияние на финансовые рынки» может быть преобразовано в синтаксические N-граммы следуя древовидной структуре его [[Грамматика зависимостей|отношений зависимостей]]: новости-экономические, влияние-незначительное, влияние-на-рынки-финансовые и другие<ref name="sng"/>.

Синтаксические N-граммы отражают синтаксическую структуру в отличие от линейных N-грамм и могут использоваться в тех же приложениях, что и линейные N-граммы, в том числе в качестве признаков в векторной модели. Применение синтаксических N-грамм дает лучшие результаты при решении определенных задач, чем использование стандартных N-грамм, например, для определения авторства<ref>Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández. Syntactic N-grams as Machine Learning Features for Natural Language Processing. Expert Systems with Applications, Vol. 41, No. 3, pp. 853—860, [http://www.sciencedirect.com/science/article/pii/S0957417413006271 DOI 10.1016/j.eswa.2013.08.015].</ref>.

== См. также ==
* [[Биграммный шифр]]

== Примечания ==
{{примечания}}

[[Категория:Информатика]]
[[Категория:Обработка естественного языка]]