N-грамм
Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии.
|
N-грамма — последовательность из n элементов[1]. С семантической точки зрения, это может быть последовательность звуков, слогов, слов или букв. На практике чаще встречается N-грамма как ряд слов, устойчивые словосочетания называют коллокацией. Последовательность из двух последовательных элементов часто называют биграмма, последовательность из трёх элементов называется триграмма. Не менее четырёх и выше элементов обозначаются как N-грамма, N заменяется на количество последовательных элементов.
Содержание
Использование N-грамм
Общее использование N-грамм
N-граммы в целом находят своё применение в широкой области наук. Они могут применяться, например, в области теоретической математики, биологии, картографии, а также в музыке. Наиболее часто использование N-грамм включает следующие области:
- извлечение данных для кластеризации серии спутниковых снимков Земли из космоса, чтобы затем решить, какие конкретные части Земли на изображении,
- поиск генетических последовательностей,
- в области генетики используются для определения того, с каких конкретных видов животных собраны образцы ДНК,
- в компьютерном сжатии,
- для индексирования данных в поисковых системах; с использованием N-грамм, как правило, индексированы данные, связанные со звуком.
Также N-граммы широко применяются в обработке естественного языка.
Использование N-грамм для нужд обработки естественного языка
В области обработки естественного языка N-граммы используется в основном для предугадывания на основе вероятностных моделей. N-граммная модель рассчитывает вероятность последнего слова N-граммы, если известны все предыдущие. При использовании этого подхода для моделирования языка предполагается, что появление каждого слова зависит только от предыдущих слов[2].
Другое применение N-грамм является выявление плагиата. Если разделить текст на несколько небольших фрагментов, представленных N-граммами, их легко сравнить друг с другом, и таким образом получить степень сходства контролируемых документов[3]. N-граммы часто успешно используются для категоризации текста и языка. Кроме того, их можно использовать для создания функций, которые позволяют получать знания из текстовых данных. Используя N-граммы, можно эффективно найти кандидатов, чтобы заменить слова с ошибками правописания.
Пример биграммной модели
Целью построения N-граммных моделей является определение вероятности употребления заданной фразы. Эту вероятность можно задать формально как вероятность возникновения последовательности слов в неком корпусе (наборе текстов). К примеру, вероятность фразы «счастье есть удовольствие без раскаяния» можно вычислить как произведение вероятностей каждого из слов этой фразы:
P = P(счастье) * P(есть|счастье) * P(удовольствие|счастье есть) * P(без|счастье есть удовольствие) * P(раскаяния|счастье есть удовольствие без)
Чтобы определить P(счастье) нужно посчитать сколько раз это слово встретилось в тексте, и поделить это значение на общее число слов. Рассчитать вероятность P(раскаяния|счастье есть удовольствие без) сложнее. Чтобы упростить эту задачу, примем, что вероятность слова в тексте зависит только от предыдущего слова. Тогда наша формула для расчета фразы примет следующий вид:
P = P(счастье) * P(есть|счастье) * P(удовольствие|есть) * P(без|удовольствие) * P(раскаяния|без)
Рассчитать условную вероятность P(есть|счастье) несложно. Для этого считаем количество пар 'счастье есть', и делим на количество в тексте слова 'счастье'.
В результате, если мы посчитаем все пары слов в некотором тексте, мы сможем вычислить вероятность произвольной фразы. Этот набор рассчитанных вероятностей и будет биграммной моделью.
Научно-исследовательские проекты Google
Исследовательские центры Google использовали N-граммные модели для широкого круга исследований и разработок. К ним относятся такие проекты, как статистический перевод с одного языка на другой, распознавание речи, исправление орфографических ошибок, извлечение информации и многое другое. Для целей этих проектов были использованы текстовые корпусы, содержащие несколько триллионов слов.
Google решила создать свой учебный корпус. Проект называется Google teracorpus и он содержит 1 024 908 267 229 слов, собранных с общедоступных веб-сайтов[4].
Методы для извлечения N-грамм
В связи с частым использованием N-грамм для решения различных задач необходим надежный и быстрый алгоритм для извлечения их из текста. Подходящий инструмент для извлечения N-грамм должен быть в состоянии работать с неограниченным размером текста, работать быстро и эффективно использовать имеющиеся ресурсы. Есть несколько методов извлечения N-грамм из текста. Эти методы основаны на разных принципах:
- Алгоритм Nagao 94 для текстов на японском[5]
- Алгоритм Лемпеля — Зива — Велча
- Суффиксный массив
- Суффиксное дерево
- Инвертированный индекс
Синтаксические N-граммы
Синтаксические N-граммы — это N-граммы, определяемые путями в деревьях синтаксических зависимостей или деревьях составляющих, а не линейной структурой текста[6][7]. Например, предложение: «Экономические новости оказывают незначительное влияние на финансовые рынки» может быть преобразовано в синтаксические N-граммы следуя древовидной структуре его отношений зависимостей: новости-экономические, влияние-незначительное, влияние-на-рынки-финансовые и другие[6].
Синтаксические N-граммы отражают синтаксическую структуру в отличие от линейных N-грамм и могут использоваться в тех же приложениях, что и линейные N-граммы, в том числе в качестве признаков в векторной модели. Применение синтаксических N-грамм дает лучшие результаты при решении определенных задач, чем использование стандартных N-грамм, например, для определения авторства[8].
См. также
Напишите отзыв о статье "N-грамм"
Примечания
- ↑ Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakia, pp. 54-65, February 2008. ISBN 978-80-227-2827-0.
- ↑ 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. — 988 p. — ISBN 9780131873216.
- ↑ Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008. ISBN 978-80-969184-8-5
- ↑ FRANZ, Alex, BRANTS, Thorsten. [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.
- ↑ 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.
- ↑ 1 2 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.
- ↑ 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.
- ↑ 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, [www.sciencedirect.com/science/article/pii/S0957417413006271 DOI 10.1016/j.eswa.2013.08.015].
Отрывок, характеризующий N-грамм
– Отчего? – не переменяя положения, сказала Наташа.– Оттого, что он молод, оттого, что он беден, оттого, что он родня… оттого, что ты и сама не любишь его.
– А почему вы знаете?
– Я знаю. Это не хорошо, мой дружок.
– А если я хочу… – сказала Наташа.
– Перестань говорить глупости, – сказала графиня.
– А если я хочу…
– Наташа, я серьезно…
Наташа не дала ей договорить, притянула к себе большую руку графини и поцеловала ее сверху, потом в ладонь, потом опять повернула и стала целовать ее в косточку верхнего сустава пальца, потом в промежуток, потом опять в косточку, шопотом приговаривая: «январь, февраль, март, апрель, май».
– Говорите, мама, что же вы молчите? Говорите, – сказала она, оглядываясь на мать, которая нежным взглядом смотрела на дочь и из за этого созерцания, казалось, забыла всё, что она хотела сказать.
– Это не годится, душа моя. Не все поймут вашу детскую связь, а видеть его таким близким с тобой может повредить тебе в глазах других молодых людей, которые к нам ездят, и, главное, напрасно мучает его. Он, может быть, нашел себе партию по себе, богатую; а теперь он с ума сходит.
– Сходит? – повторила Наташа.
– Я тебе про себя скажу. У меня был один cousin…
– Знаю – Кирилла Матвеич, да ведь он старик?
– Не всегда был старик. Но вот что, Наташа, я поговорю с Борей. Ему не надо так часто ездить…
– Отчего же не надо, коли ему хочется?
– Оттого, что я знаю, что это ничем не кончится.
– Почему вы знаете? Нет, мама, вы не говорите ему. Что за глупости! – говорила Наташа тоном человека, у которого хотят отнять его собственность.
– Ну не выйду замуж, так пускай ездит, коли ему весело и мне весело. – Наташа улыбаясь поглядела на мать.
– Не замуж, а так , – повторила она.
– Как же это, мой друг?
– Да так . Ну, очень нужно, что замуж не выйду, а… так .
– Так, так, – повторила графиня и, трясясь всем своим телом, засмеялась добрым, неожиданным старушечьим смехом.
– Полноте смеяться, перестаньте, – закричала Наташа, – всю кровать трясете. Ужасно вы на меня похожи, такая же хохотунья… Постойте… – Она схватила обе руки графини, поцеловала на одной кость мизинца – июнь, и продолжала целовать июль, август на другой руке. – Мама, а он очень влюблен? Как на ваши глаза? В вас были так влюблены? И очень мил, очень, очень мил! Только не совсем в моем вкусе – он узкий такой, как часы столовые… Вы не понимаете?…Узкий, знаете, серый, светлый…
– Что ты врешь! – сказала графиня.
Наташа продолжала:
– Неужели вы не понимаете? Николенька бы понял… Безухий – тот синий, темно синий с красным, и он четвероугольный.
– Ты и с ним кокетничаешь, – смеясь сказала графиня.
– Нет, он франмасон, я узнала. Он славный, темно синий с красным, как вам растолковать…
– Графинюшка, – послышался голос графа из за двери. – Ты не спишь? – Наташа вскочила босиком, захватила в руки туфли и убежала в свою комнату.
Она долго не могла заснуть. Она всё думала о том, что никто никак не может понять всего, что она понимает, и что в ней есть.
«Соня?» подумала она, глядя на спящую, свернувшуюся кошечку с ее огромной косой. «Нет, куда ей! Она добродетельная. Она влюбилась в Николеньку и больше ничего знать не хочет. Мама, и та не понимает. Это удивительно, как я умна и как… она мила», – продолжала она, говоря про себя в третьем лице и воображая, что это говорит про нее какой то очень умный, самый умный и самый хороший мужчина… «Всё, всё в ней есть, – продолжал этот мужчина, – умна необыкновенно, мила и потом хороша, необыкновенно хороша, ловка, – плавает, верхом ездит отлично, а голос! Можно сказать, удивительный голос!» Она пропела свою любимую музыкальную фразу из Херубиниевской оперы, бросилась на постель, засмеялась от радостной мысли, что она сейчас заснет, крикнула Дуняшу потушить свечку, и еще Дуняша не успела выйти из комнаты, как она уже перешла в другой, еще более счастливый мир сновидений, где всё было так же легко и прекрасно, как и в действительности, но только было еще лучше, потому что было по другому.
На другой день графиня, пригласив к себе Бориса, переговорила с ним, и с того дня он перестал бывать у Ростовых.
31 го декабря, накануне нового 1810 года, le reveillon [ночной ужин], был бал у Екатерининского вельможи. На бале должен был быть дипломатический корпус и государь.
На Английской набережной светился бесчисленными огнями иллюминации известный дом вельможи. У освещенного подъезда с красным сукном стояла полиция, и не одни жандармы, но полицеймейстер на подъезде и десятки офицеров полиции. Экипажи отъезжали, и всё подъезжали новые с красными лакеями и с лакеями в перьях на шляпах. Из карет выходили мужчины в мундирах, звездах и лентах; дамы в атласе и горностаях осторожно сходили по шумно откладываемым подножкам, и торопливо и беззвучно проходили по сукну подъезда.
Почти всякий раз, как подъезжал новый экипаж, в толпе пробегал шопот и снимались шапки.
– Государь?… Нет, министр… принц… посланник… Разве не видишь перья?… – говорилось из толпы. Один из толпы, одетый лучше других, казалось, знал всех, и называл по имени знатнейших вельмож того времени.
Уже одна треть гостей приехала на этот бал, а у Ростовых, долженствующих быть на этом бале, еще шли торопливые приготовления одевания.
Много было толков и приготовлений для этого бала в семействе Ростовых, много страхов, что приглашение не будет получено, платье не будет готово, и не устроится всё так, как было нужно.
Вместе с Ростовыми ехала на бал Марья Игнатьевна Перонская, приятельница и родственница графини, худая и желтая фрейлина старого двора, руководящая провинциальных Ростовых в высшем петербургском свете.
В 10 часов вечера Ростовы должны были заехать за фрейлиной к Таврическому саду; а между тем было уже без пяти минут десять, а еще барышни не были одеты.
Наташа ехала на первый большой бал в своей жизни. Она в этот день встала в 8 часов утра и целый день находилась в лихорадочной тревоге и деятельности. Все силы ее, с самого утра, были устремлены на то, чтобы они все: она, мама, Соня были одеты как нельзя лучше. Соня и графиня поручились вполне ей. На графине должно было быть масака бархатное платье, на них двух белые дымковые платья на розовых, шелковых чехлах с розанами в корсаже. Волоса должны были быть причесаны a la grecque [по гречески].
Все существенное уже было сделано: ноги, руки, шея, уши были уже особенно тщательно, по бальному, вымыты, надушены и напудрены; обуты уже были шелковые, ажурные чулки и белые атласные башмаки с бантиками; прически были почти окончены. Соня кончала одеваться, графиня тоже; но Наташа, хлопотавшая за всех, отстала. Она еще сидела перед зеркалом в накинутом на худенькие плечи пеньюаре. Соня, уже одетая, стояла посреди комнаты и, нажимая до боли маленьким пальцем, прикалывала последнюю визжавшую под булавкой ленту.
– Не так, не так, Соня, – сказала Наташа, поворачивая голову от прически и хватаясь руками за волоса, которые не поспела отпустить державшая их горничная. – Не так бант, поди сюда. – Соня присела. Наташа переколола ленту иначе.