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 слов, собранных с общедоступных веб-сайтовОшибка цитирования Отсутствует закрывающий тег </ref>

См. также

Биграммный шифр

Примечания

↑ Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakia, pp. 54-65, February 2008. ISBN 978-80-227-2827-0.
↑ URAFSKY, Daniel, MARTIN, James H. Speech And Language Processing : An Introduction To Natural Language Processing, Computational Linguistics, And Speech Recognition. 2nd edition. Upper Saddle River: Prentice Hall, 2008. 1024 s. Доступно по адресу: <http://books.google.com/books?id=fZmj5UNK8AQC&dq=Speech+and+language+processing+:an+introduction+to+natural+language+processing&printsec=frontcover&source=bl&ots=LqS8_-HLQI&sig=0hNFclP0wlsKmjUtfyShEm437ws&hl=en&ei=sjrvSZaHCImI_QbE_cjDDw&sa=X&oi=book_result&ct=result&resnum=9>. ISBN 0-13-504196-1.
↑ Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008. ISBN 978-80-969184-8-5

[1] Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakia, pp. 54-65, February 2008. ISBN 978-80-227-2827-0.

[2] URAFSKY, Daniel, MARTIN, James H. Speech And Language Processing : An Introduction To Natural Language Processing, Computational Linguistics, And Speech Recognition. 2nd edition. Upper Saddle River: Prentice Hall, 2008. 1024 s. Доступно по адресу: <http://books.google.com/books?id=fZmj5UNK8AQC&dq=Speech+and+language+processing+:an+introduction+to+natural+language+processing&printsec=frontcover&source=bl&ots=LqS8_-HLQI&sig=0hNFclP0wlsKmjUtfyShEm437ws&hl=en&ei=sjrvSZaHCImI_QbE_cjDDw&sa=X&oi=book_result&ct=result&resnum=9>. ISBN 0-13-504196-1.

[3] Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008. ISBN 978-80-969184-8-5

[1]

[2]

[3]