N-граммы

 

 

 

gramma

 

...грамма — (gramma, письменный знак, черта, написание, линия) составная часть сложных слов, означающая: «запись, графическое изображение» (радиограмма, картограмма, кардиограмма, диаграмма, монограмма, фонограмма и т.п.).

 

 

Грамматология

 

Жак Деррида («Сущность и грамма»):

  • то, что бытийствует, – есть и, значит, не может не быть; время, которое течет, – изменяется, и, следовательно, должно представлять собой невозможное сочетание бытия и небытия

Грамматология:

  • (языкознание) изучает соотношения между буквами алфавита и звуками речи.

  • (философия) исследовует взаимовлияние письменности и культуры.

kmp рекомендует книгу Ж. Деррида «De la Grammatologie»
в русском переводе: «Нечто, относящееся к грамматологии» («О грамматологии»)

 

Жак Деррида («О грамматологии»):

Что может представлять собой наука о письменности, если прежде чем стать объектом науки, письменность является условием науки:

  • сама идея науки появилась в определенную эру письменности;

  • идея науки была определена и сформулирована как проект, располагающийся и реализующийся в языке и письме;

  • наука о письменности появилась в определенный период истории (в 18 в.) на основе сложившейся системы взаимоотношений устной речи и описания;

Прежде чем быть объектом истории — истории как исторической науки, — письменность открывает само поле истории — как развертывания истории.

Жак Деррида («О грамматологии»):

  • Понятие письма шире понятия языка и объемлет его. Слово "письмо" относится не только к системе записи, которая здесь вторична, но и к самой сути и содержанию всех видов деятельности. Именно в этом смысле современный биолог говорит о письме и о про-грамме ("пред-письме") по поводу простейших информационных процессов в живой клетке.

  • Наконец, и все поле кибернетического программирования тоже выступает как поле письма. Далее, если предположить, что кибернетическая теория способна искоренить в себе все те метафизические понятия, посредством которых прежде противопоставлялись машина и человек (включая такие, как душа, жизнь, ценность, выбор, память), то и тогда она должна сохранить - во всяком случае, пока не обнаружится ее собственная историко-метафизическая принадлежность — понятие письма, следа, граммы или графемы.

  • Прежде чем предстать как нечто человеческое (со всеми отличительными признаками, которые всегда приписывались человеку, и всей соответствующей системой значений) или нечто не-человеческое, грамма или графема обозначали  простой элемент  (стихия или же неразложимый атом) прото-синтеза (archi-synthese) как такового, который не поддается определению внутри системы метафизических противоположностей и, следовательно, не может быть назван опытом вообще, а тем самым и (перво)началом смысла вообще.

 

 

 

От слова к n-грамме

Слово - основная единица языка и речи...
Слово  многогранно, многоуровнево, многоаспектно...
Слово  считается понятием неопределенным и априорным...

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

Слово у человека, n-граммы для машин...

 

 

N-грамма (строгая дефиниция)

Пусть задан некоторый конечный алфавит V = {wi}, где wi — символ.

Языком L(V) называют множество цепочек конечной длины из символов wi.

Высказыванием называют произвольную цепочку  из языка L(V).

N-граммой на алфавите V называют произвольную цепочку из языка L(V) длиной N

 

Вероятностный подход:

Пусть известны вероятности p(wk|wk−N , wk−N+1...wk−1), т.е. вероятности того, что текущее (при разборе цепочки) слово – это wk, а N предыдущими словами были wk−N , wk−N+1...wk−1.

Тогда вероятность некоторой цепочки beg w1...wT end, где beg и end – специальные символы начала и конца строки (цепочки), можно вычислить как p(beg w1...wT end) = p(w1|beg)p(w2|w1)...p(wT |w1...wT −1)p(end|w1...wT )

 

 

N-грамма (просто и ясно)

N-грамма — последовательность из n элементов (слогов, слов, букв, фраз).

Униграмма - один элемент (вырожденный случай n-граммы)

Биграмма - последовательность из двух элементов

Триграмма - последовательность из трёх элементов.

На практике чаще встречается N-грамма как грамматически допустимых описаний N подряд стоящих слов.

 

Частотные N-граммы называют коллокациями
http://opencorpora.org/?page=downloads

Слово ... слово ... унигармма

 

 

Теория N-грамм

N-граммы (как объект теоретического анализа!) изучены недостаточно, в том числе их формальные математические свойства.

Модель N-грамм не является объяснительной и не входит ни в какую другую объяснительную модель.

N-граммы можно рассматривать как

  •  средство фиксации языковой реальности

  • модель, основанную на формальной грамматике Хомского.

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

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

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

 

 

Применение N-грамм

N-граммы очень широко применяются в обработке естественного языка, а также в математикебиоинформатике, генетике, картографии, музыке, акустике, компьютерном сжатии  и др.

В области обработки естественного языка N-граммы наиболее часто применяются:

  • для предугадывания на основе вероятностных моделей.

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

Модель N-граммы описывается марковской цепью (N–1)-го порядка.

Задача оценивания статистических параметров N-граммы сводится к задачам по марковским цепям, а оценкой вероятности N-граммы служит частота ее встречаемости.

  • для выявление плагиата. Если разделить текст на несколько небольших фрагментов, представленных N-граммами, их легко сравнить друг с другом, и таким образом получить степень сходства контролируемых документов.

  • для категоризации текста и языка.

  • для извлечения знаний из текстовых данных.

  • для автоматической проверки правописания (поиска кандидатов на замену слов с ошибками правописания)

  • для нечеткого поиска по тексту

  • для атрибуции (в частности, авторства) текста

  • для создания языковых моделей в системах синтеза и распознавания речи

  • для реализации машинного перевода.

N-граммные модели лежат в основе языквых исследований и разработок Google (машинный перевод, распознавание речи, исправление орфографических ошибок, извлечение информации и др.). Для целей этих проектов были использованы текстовые корпусы, содержащие триллионы слов.

 

 

Биграммная модель вероятности заданной фразы

Вероятность употребления заданной фразы можно описать формально как вероятность возникновения последовательности слов в неком корпусе (наборе текстов).

Например:

  • вероятность фразы «счастье есть лабораторные без ошибок» можно вычислить как произведение вероятностей каждого из слов этой фразы:

P = P(счастье) * P(есть|счастье) * P(лабораторные|счастье есть) * P(без|счастье есть  лабораторные) * P(ошибок|счастье есть лабораторные без)

Чтобы определить P(счастье) нужно посчитать сколько раз это слово встретилось в тексте, и поделить это значение на общее число слов.

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

P = P(счастье) * P(есть|счастье) * P(лабораторные|есть) * P(без|лабораторные) * P(ошибок|без)

Чтобы рассчитать условную вероятность P(есть|счастье) считаем количество пар 'счастье есть', и делим на количество в тексте слова 'счастье'.

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

Этот набор рассчитанных вероятностей и будет биграммной моделью.

 

 

N-граммный метод нечеткого поиска по тексту

N-граммный метод нечеткого поиска по тексту:

  • широко используем,

  • очень прост,

  • высокоэффективен.

Идея метода:

  • Если слово А совпадает со словом Б с учетом возможных ошибок, вероятно у них будут общие N-граммы (подстроки длины N)

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

 

Наиболее часто используемыми на практике являются триграммы — подстроки длины 3.

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

Метод N-грамм находит не все возможные слова с ошибками:

  • Слово ВОТКА → ВОТ ОТК ТКА все триграммы содержат ошибку Т и слово «ВОДКА» найдено не будет, так как оно не содержит ни одной из этих триграмм, и не попадет в соответствующие им списки. Таким образом, чем меньше длина слова и чем больше в нем ошибок, тем выше шанс того, что оно не попадет в соответствующие N-граммам запроса списки, и не будет присутствовать в результате.

Возможные улучшения:

  • Можно разбивать хеш-таблицы N-грамм по длине слов и по позиции N-граммы в слове. Как длина искомого слова и запроса не могут отличаться более чем на k, так и позиции N-граммы в слове могут различаться не более чем на k и необходимо будет проверить лишь таблицу, соответствующую позиции этой N-граммы в слове, а также k таблиц слева и k таблиц справа, т.е. всего 2k+1 соседних таблиц.

 

  • Можно уменьшить размер необходимого для просмотра множества, разбив таблицы по длине слова и просматривая только соседние 2k+1 таблицы

 

 

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

В связи с частым использованием N-грамм для решения различных задачразработаны стандартные алгоритмы  извлечения их из текста, основанные на разных принципах:

  • Алгоритм Лемпеля — Зива — Велча

  • Суффиксный массив

  • Суффиксное дерево

  • Инвертированный индекс

  • Алгоритм Nagao 94 (для текстов на японском)

 

 

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

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

Например, предложение:

Несвоевременное выполнение лабораторных работ оказывает значительное влияние на экзаменационную отметку

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

  • сообщение-предупредительное,

  • сообщение-образовательное,

  • влияние-значительное,

  • влияние-на-экзаменационную отметку и другие.

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

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

 

 

Google Ngram Viewer

Google Ngram Viewer (Google Books Ngram Viewer) — поисковый онлайн-сервис компании Google, позволяющий строить графики частотности языковых единиц на основе печатных источников, опубликованных с 16 века и собранных в сервис Google Books.

Графики изменений частоты встречаемости n-грамм:

  • По вертикальной оси графика, который строит система, откладывается относительная частота встречаемости заданной N-граммы в данном году, выраженная в процентах.

  • На горизонтальной оси показаны годы, входящие в заданный пользователем временной интервал.

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

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

Область запроса на построение графика включает:

  • Graph these case-sensitive comma separated phrases – построить графики для этих словоформ с учетом регистра, разделять запятыми Ngram (окно запроса на построение графика);

  • case-insensitive – при установке флажка в окне система не различает заглавные и строчные буквы;

  • between and – между …. и… (окно указания временного периода, вводится год начала исследования и конца исследования);

  • from the corpus – из корпуса (выбрать из выпадающего меню);

  • with smoothing – со сглаживанием (выбрать из выпадающего меню);

  • search lots of books – искать в массивах книг (кнопка команды на поиск и построение графика).

Кроме построения графиков, система представляет ссылки к текстам, найденным по запросам. Как правило, это библиографические описания книг и фрагменты текстов с выделением в них цветом заданных N-грамм. В некоторых случаях доступен полный текст книги в графическом формате.

Имеется возможность при формулировке условий поиска задавать распознавание заглавных и строчных букв (case sensitive), или игнорировать различие между ними (case insensitive).

Система не поддерживает грамматической нормализации лексики, иначе говоря, осуществляет поиск лексических единиц (слов и словосочетаний) только в заданной форме (поиск словоформ) и строит графики частоты встречаемости словоформ и словосочетаний.

Сглаживание.

При построении графиков динамики частоты употребления слов используется так называемое «сглаживание» (smoothing). Тенденция в динамике встречаемости N-грамм (тренд) более отчетливо прослеживается при скользящем усреднении данных. Если значение сглаживания равно 1, то это означает, что для некоторого года, например для 1950, к значению относительной частоты искомого слова за этот год прибавляется значение за предыдущий год (т. е. 1949) и последующий год (т. е. 1951), после чего полученная сумма делится на три.

В окне «Smoothing» пользовательского интерфейса по умолчанию указано значение сглаживания 3. Это означает, что высчитывается среднее значение из семи чисел – относительная частота употреблений слова в данном году и для трех предыдущих и трех последующих лет. При нулевом сглаживании в графике учитывается относительная частота встречаемости N-граммы за каждый год.

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

При активизации ссылки Embed Chart (встроить график) раскрывается окно, в котором находится ссылка на команду построения данного графика. Ссылка может быть скопирована и встроена в любой HTML-текст или в пустой текстовый файл с последующим присвоением ему имени с расширением .html. Таким образом, график будет доступен в любой гипертекстовой системе, и функция определения координат останется активной.

В системе применяется набор пользовательских тэгов для модификации условий построения графиков.

Тэги частей речи Тэги этой группы могут применяться изолированно (_NOUN_), в этом случае по- казывается частота употребления данной части речи, а также могут присоединяться к какому либо знаменательному слову.

1. Тэг _NOUN_, Часть речи Существи- тельное, Действие: находит только существительное или субстантивированное прилагательное. Напр. «больной» ср. «Больной находится в тяжелом состоянии» и «Больной ребенок» Нотация: больной_NOUN (Все тэги частей речи вводятся заглавными бук- вами без пробелов)

2. Тэг _ADJ_ Часть речи Прилагательное Действие: находит только прилагательные.

3. Тэг _VERB_ Часть речи Глагол Действие: находит только глаголы.

4. Тэг _ADV_ Часть речи Наречие Дей- ствие: находит только наречия

5. Тэг _PRON_ Часть речи Местоимение Действие: находит только местоимения

6. Тэг _DET_ Часть речи Артикль Действие: Этот тэг позволяет игнорировать вид артикля Нотация: До и после подчерка должны быть пробелы (eat _DET_ sandwich). Число элементов N граммы не должно быть более трех

7. Тэг _ADP_ Часть речи Предлог или постлог Действие: находит только предлоги

8. Тэг _NUM_ Часть речи Числительное Действие: находит только числительные

9. Тэг_CONJ_Часть речи Союз Действие: находит только союзы

10. Тэг _PRT_ Часть речи Частица Действие: находит только частицы.

11. Тэг _INF (Inflections) строит кри- вые для всех форм словоизменительной парадигмы данного слова. Данная функция работает не всегда корректно, по крайней мере, для русского языка.

Тэг «подстановочный знак» * (wildcard). Ввод его через пробел после N-граммы или до неё  позволяет стро- ить график встречаемости десяти наиболее частотных сочетаний N-граммы и слова следующего за нею или ей предшествующего.

Можно использовать также синтаксический тэг, тэги позиции слов в предложении, тэг выбора корпуса

Операции над графиками

Суммирование (сложение) графиков. Операция позволяет суммировать значения каждой точки двух или более графиков. Для осуществления операции поисковые слова вводятся в окно через знак +, например: лошадь + лошади +лошадей.

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

Умножение графиков. Операция позволяет умножать на n значения всех точек графика. Операция умножения позволяет сделать сопоставимым поведение кривых, значения которых отличаются на несколько порядков. Слова в поисковое окно вводятся следующим образом: слово знак «*» множитель, например, лемматизация*100.

Деление графиков. Делить значение каждой точки графика на значение точки другого графика, имеющий ту же координату горизонтальной оси. Операция позволяет установить, во сколько раз один термин встречается чаще другого.Слова в поисковое окно вводятся следующим образом: слово – делимое, знак «/», слово – делитель, например сапоги/валенки. Операцию деления нельзя использовать по тому же типу, что операцию умножения. Выражение Время/100 означает, что система покажет, во сколько раз в текстах БД слово «время» встречается чаще (реже) чем цифра 100, а не уменьшит результат в сто раз. Это делает невозможной операцию вычисления средней встречаемости нескольких терминов

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

Можно осуществлять поиск на основе специализированных корпусов текстов (корпус британской беллетристики).

https://books.google.com/ngrams

 

 

НКРЯ: поиск по n-граммам

Поиск в НКРЯ можно вести по словосочетаниям с неснятой омонимией основного корпуса из 2, 3, 4 и 5 слов:

  • биграммам

  • триграммам

  • 4-граммам

  • 5-граммам

Поиск может быть осуществлен:

  • по точным формам и по леммам,

  • с учетом грамматических признаков и пунктуации или без.

см. справка: http://www.ruscorpora.ru/help-ngrams.html

Можно получить частотное распределение популярных словоформ и словосочетаний (основной корпус):

При подсчёте не учитываются знаки препинания и регистр. Приводятся результаты, встречающиеся не менее чемя в 100 документах. 

 

 

 

N-граммный метод классификации

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

При использовании фрагментов постоянной длины возможно установить максимальное количество фрагментов (N-грамм) для данного языка.

Так, например, для русского языка при алфавите в 30 букв количество N-грамм при N=3 равно 27000. Однако, как показывает практика, в реальных текстах реализуется не более 25-30 процентов N-грамм от общего допустимого их числа, т.е. для русского языка их не более 7000.

Метод основан на использовании вероятности появления цепочки букв N-го порядка (N-грамм) в анализируемых текстах.

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

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

По предложенному методу был проведен эксперимент классификации (отбора) документов на отечественной документальной базе данных ВИНИТИ "Коррозия" общим объемом около 10 тысяч документов. В документах обрабатывались поля: заглавие, ключевые слова и рефераты. В качестве N-грамм использовались триграммы. В качестве экзаменационной выборки использовался массив документов базы данных "Химия" объемом более 30 тысяч документов. В результате анализа экспериментальных данных были полученны: полнота - 90 процентов и точность 70 процентов.

Отбор (классификация) документов с использованием предложенного метода является хорошей альтернативой использованию традиционных методов отбора (поиска) при формулировании поисковых запросов с помощью булевой логики.

 

 

N-граммный метод выявления орфографических ошибок

 

Автоматическое обнаружение орфографических ошибок в текстах документов использует следующие подходы:

  • N-граммный, основанный на использовании допустимых буквенных сочетаний;

  • словарный, основанный на использовании эталонных и частотных словарей.

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

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

Поэтому, на наш взгляд, несмотря на немного худшие характеристики методов (судя по опубликованным данным), основанных на использовании N-грамм, по сравнению со словарными методами, эти методы более предпочтительны ввиду их большей мобильности для малых ЭВМ.

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

На основе данного метода разработана диалоговая система обнаружения орфографических ошибок в текстах документов, функционирующая в рамках АСНТИ СО РАН.

Система предлагает пользователю одну из следующих возможностей:

  • заменить (отредактировать) неправильное слово на правильное и обучиться на нем;

  • оставить слово без изменений (новое слово) с обучением системы на нем;

  • оставить слово без изменений (аббревиатура, фамилия автора и др.) без обучения.

Степень обнаружения ошибок - 90%.

 

 

Рекомендуемая литература

 

http://cognitive.ru/assets/docs/scienwork/sbornic2/samoilov.doc

http://www.dialog-21.ru/media/1354/150.pdf

http://szelenin.blogspot.com.by/2014/12/n-gram.html

 

 

kmp