N-грамма

N-Грамма — последовательность, состоящая из n элементов, которые могут быть звуками, слогами, словами или буквами, в зависимости от контекста. Чаще всего N-грамма - это последовательность слов, устойчивые сочетания которых называются словосочетаниями.

Последовательность из двух элементов называется биграммой, а последовательность из трёх элементов называется триграммой. Последовательность, состоящая из четырёх или более элементов, называется N-граммой, где N - количество элементов.

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

Общее использование N-грамм

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

• извлечение данных для кластеризации серии спутниковых снимков Земли из космоса, чтобы затем решить, какие конкретные части Земли на изображении,
• поиск генетических последовательностей,
• в области генетики используются для определения того, с каких конкретных видов животных собраны образцы ДНК,
• в компьютерном сжатии,
• для индексирования данных в поисковых системах; с использованием N-грамм, как правило, индексированы данные, связанные со звуком.

Также N-граммы широко применяются в обработке естественного языка.

Использование N-грамм для нужд обработки естественного языка

В области обработки естественного языка N-граммы используется в основном для предугадывания на основе вероятностных моделей. N-граммная модель рассчитывает вероятность последнего слова N-граммы, если известны все предыдущие. При использовании этого подхода для моделирования языка предполагается, что появление каждого слова зависит только от предыдущих слов^[1].

Другим применением N-грамм является выявление плагиата. Если разделить текст на несколько небольших фрагментов, представленных N-граммами, их легко сравнить друг с другом и таким образом получить степень сходства анализируемых документов^[2]. 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 слов, собранных с общедоступных веб-сайтов^[3].

Методы для извлечения N-грамм

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

• Алгоритм Nagao 94 для текстов на японском^[4]
• Алгоритм Лемпеля — Зива — Велча
• Суффиксный массив
• Суффиксное дерево
• Инвертированный индекс

Синтаксические N-граммы

Синтаксические N-граммы представляют собой последовательности элементов, определяемые на основе структуры синтаксических зависимостей или составляющих, а не линейной последовательности слов в тексте^[5][6].

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

Частотность n-грамм в текстах на русском языке

Частотность n-грамм в текстах на русском языке можно найти напр. здесь: https://www.wolosz.hu/russian_n-grams.html^[7]

См. также

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