Я хочу реализовать некоторые приложения с n-граммами (желательно на PHP).
Какой тип n-граммов более подходит для большинства целей? Уровень слова или уровень n-грамма уровня символов? Как можно реализовать n-грамматический токенизатор в PHP?
Во-первых, я хотел бы знать, что такое N-граммы. Это верно? Это как я понимаю n-граммы:
Предложение: "Я живу в Нью-Йорке".
бирамы на уровне слов (2 для n): "# I", "Я живу", "живу в", "в Нью-Йорке", "NY #"
бирамы уровня персонажа (2 для n): "#I", "I #", "#l", "li", "iv", "ve", "e #", "#i", "in", "n #", "#N", "NY", "Y #"
Когда у вас есть этот массив n-грамм-частей, вы бросаете дубликаты и добавляете счетчик для каждой части, задающей частоту:
биграмы уровня слова:
биграмы уровня персонажа:
Правильно ли это?
Кроме того, я хотел бы узнать больше о том, что вы можете сделать с n-граммами:
- Как я могу определить язык текста с помощью n-граммов?
- Можно ли выполнять машинный перевод с использованием n-граммов, даже если у вас нет двуязычного корпуса?
- Как создать спам-фильтр (спам, ветчина)? Объединить n-граммы с байесовским фильтром?
- Как я могу найти тему? Например: есть ли текст о баскетболе или собаках? Мой подход (сделайте следующее со статьей Википедии для "собак" и "баскетбола"): постройте векторы n-gram для обоих документов, нормализуйте их, вычислите расстояние Манхэттен/Евклида, чем ближе результат к 1, тем выше будет сходство
Как вы относитесь к моему приложению, особенно к последнему?
Надеюсь, ты поможешь мне. Спасибо заранее!
2 ответа
Word n-gram, как правило, будут более полезны для большинства приложений для текстового анализа, о которых вы упомянули, за возможным исключением определения языка, где нечто вроде символьных триграмм может дать лучшие результаты. Эффективно, вы бы создали вектор n-грамм для тела текста на каждом языке, который вас интересует, и затем сравните частоты триграмм в каждом корпусе с триграммами в документе, который вы классифицируете. Например, триграмма the , вероятно, появляется гораздо чаще на английском языке, чем на немецком, и обеспечит некоторый уровень статистической корреляции. После того, как у вас есть документы в формате n-gram, у вас есть выбор для многих алгоритмов для дальнейшего анализа, Baysian Filters, N Nearest Neighbor, Support Vector Machines и т.д.
Из упомянутых вами приложений машинный перевод, вероятно, самый надуманный, поскольку только n-граммы не приведут вас очень далеко по пути. Преобразование входного файла в представление n-gram - это всего лишь способ поместить данные в формат для дальнейшего анализа функций, но по мере того, как вы теряете много контекстуальной информации, это может быть не полезно для перевода.
Одна вещь, на которую следует обратить внимание, заключается в том, что недостаточно создать вектор для одного документа и вектор для другого документа, если размеры не совпадают. То есть первая запись в векторе не может быть the в одном документе и is в другом, или алгоритмы не будут работать. Вы завершите работу с такими векторами, как , так как большинство документов не будут содержать больше n-граммов, которые вас интересуют. Эта "подкладка" а также требует, чтобы вы заранее определили, какие ngrams вы будете включать в свой анализ. Часто это реализуется как двухпроходный алгоритм, чтобы сначала решить статистическую значимость различных n-граммов, чтобы решить, что сохранить. Google "feature selection" для получения дополнительной информации.
Основанные на словах n-граммы плюс поддержка векторных машин в отличном способе для определения темы, но для подготовки классификатора вам нужен большой корпус текста, предварительно классифицированный по теме "по теме" и "вне темы". Вы найдете большое количество исследовательских работ, объясняющих различные подходы к этой проблеме на сайте, например citeseerx . Я бы не рекомендовал эвклидово-дистанционный подход к этой проблеме, так как он не взвешивает отдельные n-граммы на основе статистической значимости, поэтому два документа, которые включают в себя the , a , is и of , будут считалось лучшим совпадением, чем два документа, которые включали Baysian . Удаление стоп-слов из ваших n-грамм интереса немного улучшило бы это.
Вы правильно относитесь к определению n-граммов.
Вы можете использовать n-граммы уровня слова для приложений типа поиска. Уровень n-граммов уровня символов можно использовать больше для анализа самого текста. Например, чтобы идентифицировать язык текста, я использовал бы частоты букв по сравнению с установленными частотами языка. То есть текст должен примерно соответствовать частоте появления букв на этом языке.
n-грамматический токенизатор для слов в PHP может быть выполнен с использованием strtok:
Для символов используйте split:
Затем вы можете просто разбить массив так, как вам угодно, на любое количество n-граммов.
Байесовские фильтры необходимо обучать для использования в качестве спам-фильтров, которые могут использоваться в сочетании с n-граммами. Однако вам нужно дать ему много вклада, чтобы он учился.
Ваш последний подход звучит прилично, поскольку изучает контекст страницы... это все же, однако, довольно сложно сделать, но n-граммы кажутся хорошей отправной точкой для этого.
Эти алгоритмы предназначены для поиска по заранее неизвестному тексту, и могут быть использованы, например, в текстовых редакторах, программах для просмотра документов или в веб-браузерах для поиска по странице. Они не требуют предварительной обработки текста и могут работать с непрерывным потоком данных.Линейный поиск
Простое последовательное применение заданной метрики (например, метрики Левенштейна) к словам из входного текста. При использовании метрики с ограничением, этот метод позволяет добиться оптимальной скорости работы. Но, при этом, чем больше k , тем сильнее возрастает время работы. Асимптотическая оценка времени - O(kn) .Bitap (также известный как Shift-Or или Baeza-Yates-Gonnet, и его модификация от Wu-Manber)
Алгоритм Bitap и различные его модификации наиболее часто используются для нечеткого поиска без индексации. Его вариация используется, например, в unix-утилите agrep , выполняющей функции аналогично стандартному grep , но с поддержкой ошибок в поисковом запросе и даже предоставляя ограниченные возможности для применения регулярных выражений.Впервые идею этого алгоритма предложили граждане Ricardo Baeza-Yates
и Gaston Gonnet
, опубликовав соответствующую статью в 1992 году.
Оригинальная версия алгоритма имеет дело только с заменами символов, и, фактически, вычисляет расстояние Хемминга
. Но немного позже Sun Wu
и Udi Manber
предложили модификацию этого алгоритма для вычисления расстояния Левенштейна
, т.е. привнесли поддержку вставок и удалений, и разработали на его основе первую версию утилиты agrep.
Результирующее значение
Где k
- количество ошибок, j
- индекс символа, s
x - маска символа (в маске единичные биты располагаются на позициях, соответствующих позициям данного символа в запросе).
Совпадение или несовпадение запросу определяется самым последним битом результирующего вектора R.
Высокая скорость работы этого алгоритма обеспечивается за счет битового параллелизма вычислений - за одну операцию возможно провести вычисления над 32 и более битами одновременно.
При этом тривиальная реализация поддерживает поиск слов длиной не более 32. Это ограничение обуславливается шириной стандартного типа int
(на 32-битных архитектурах). Можно использовать и типы больших размерностей, но это может в некоторой степени замедлить работу алгоритма.
Не смотря на то, что асимптотическое время работы этого алгоритма O(kn) совпадает с таковым у линейного метода, он значительно быстрее при длинных запросах и количестве ошибок k более 2.
Тестирование
Тестирование осуществлялось на тексте 3.2 млн слов, средняя длина слова - 10.Точный поиск
Время поиска: 3562 мсПоиск с использованием метрики Левенштейна
Время поиска при k=2 : 5728 мсВремя поиска при k=5 : 8385 мс
Поиск с использованием алгоритма Bitap с модификациями Wu-Manber
Время поиска при k=2 : 5499 мсВремя поиска при k=5 : 5928 мс
Очевидно, что простой перебор с использованием метрики, в отличие от алгоритма Bitap, сильно зависит от количества ошибок k .
Тем не менее, если речь заходит о поиске в неизменных текстах большого объема, то время поиска можно значительно сократить, произведя предварительную обработку такого текста, также называемую индексацией .
Алгоритмы нечеткого поиска с индексацией (Оффлайн)
Особенностью всех алгоритмов нечеткого поиска с индексацией является то, что индекс строится по словарю, составленному по исходному тексту или списку записей в какой-либо базе данных.Эти алгоритмы используют различные подходы к решению проблемы - одни из них используют сведение к точному поиску, другие используют свойства метрики для построения различных пространственных структур и так далее.
Прежде всего, на первом шаге по исходному тексту строится словарь, содержащий слова и их позиции в тексте. Также, можно подсчитывать частоты слов и словосочетаний для улучшения качества результатов поиска.
Предполагается, что индекс, как и словарь, целиком загружен в память.
Тактико-технические характеристики словаря:
- Исходный текст - 8.2 гигабайта материалов библиотеки Мошкова (lib.ru), 680 млн слов;
- Размер словаря - 65 мегабайт;
- Количество слов - 3.2 млн;
- Средняя длина слова - 9.5 символов;
- Средняя квадратичная длина слова (может быть полезна при оценке некоторых алгоритмов) - 10.0 символов;
- Алфавит - заглавные буквы А-Я, без Ё (для упрощения некоторых операций). Слова, содержащие символы не из алфавита, не включены в словарь.
Алгоритм расширения выборки
Этот алгоритм часто применяется в системах проверки орфографии (т.е. в spell-checker"ах), там, где размер словаря невелик, либо же где скорость работы не является основным критерием.Он основан на сведении задачи о нечетком поиске к задаче о точном поиске.
Из исходного запроса строится множество «ошибочных» слов, для каждого из которых затем производится точный поиск в словаре.
Время его работы сильно зависит от числа k ошибок и от размера алфавита A, и в случае использования бинарного поиска по словарю составляет:
Например, при k = 1
и слова длины 7 (например, «Крокодил») в русском алфавите множество ошибочных слов будет размером около 450, то есть будет необходимо сделать 450 запросов к словарю, что вполне приемлемо.
Но уже при k = 2
размер такого множества будет составлять более 115 тысяч вариантов, что соответствует полному перебору небольшого словаря, либо же 1 / 27 в нашем случае, и, следовательно, время работы будет достаточно велико. При этом не нужно забывать еще и о том, что для каждого из таких слов необходимо провести поиск на точное совпадение в словаре.
Особенности:
Алгоритм может быть легко модифицирован для генерации «ошибочных» вариантов по произвольным правилам, и, к тому же, не требует никакой предварительной обработки словаря, и, соответственно, дополнительной памяти.Возможные улучшения:
Можно генерировать не всё множество «ошибочных» слов, а только те из них, которые наиболее вероятно могут встретиться в реальной ситуации, например, слова с учетом распространенных орфографических ошибок или ошибок набора.Этот метод был придуман довольно давно, и является наиболее широко используемым, так как его реализация крайне проста, и он обеспечивает достаточно хорошую производительность. Алгоритм основывается на принципе:
«Если слово А совпадает со словом Б с учетом нескольких ошибок, то с большой долей вероятности у них будет хотя бы одна общая подстрока длины N».
Эти подстроки длины N и называются N-граммами.
Во время индексации слово разбивается на такие N-граммы, а затем это слово попадает в списки для каждой из этих N-грамм. Во время поиска запрос также разбивается на N-граммы, и для каждой из них производится последовательный перебор списка слов, содержащих такую подстроку.
Наиболее часто используемыми на практике являются триграммы - подстроки длины 3. Выбор большего значения N ведет к ограничению на минимальную длину слова, при которой уже возможно обнаружение ошибок.
Особенности:
Алгоритм N-грамм находит не все возможные слова с ошибками. Если взять, например, слово ВОТКА, и разложить его на триграммы: ВОТ КА → ВОТ ОТ К Т КА - то можно заметить, что они все содержат ошибку Т. Таким образом, слово «ВОДКА» найдено не будет, так как оно не содержит ни одной из этих триграмм, и не попадет в соответствующие им списки. Таким образом, чем меньше длина слова и чем больше в нем ошибок, тем выше шанс того, что оно не попадет в соответствующие N-граммам запроса списки, и не будет присутствовать в результате.Между тем, метод N-грамм оставляет полный простор для использования собственных метрик с произвольными свойствами и сложностью, но за это приходится платить - при его использовании остается необходимость в последовательном переборе около 15% словаря, что достаточно много для словарей большого объема.
Возможные улучшения:
Можно разбивать хеш-таблицы N-грамм по длине слов и по позиции N-граммы в слове (модификация 1). Как длина искомого слова и запроса не могут отличаться более чем на k , так и позиции N-граммы в слове могут различаться не более чем на k. Таким образом, необходимо будет проверить лишь таблицу, соответствующую позиции этой N-граммы в слове, а также k таблиц слева и k таблиц справа, т.е. всего 2k+1 соседних таблиц.
Можно еще немного уменьшить размер необходимого для просмотра множества, разбив таблицы по длине слова, и аналогичным образом просматривая только соседние 2k+1 таблицы (модификация 2).
Этот алгоритм описан в статье Бойцова Л.М. «Хеширование по сигнатуре». Он базируется на достаточно очевидном представлении «структуры» слова в виде битовых разрядов, используемой в качестве хеша (сигнатуры) в хеш-таблице.
При индексации такие хеши вычисляются для каждого из слов, и в таблицу заносится соответствие списка словарных слов этому хешу. Затем, во время поиска, для запроса вычисляется хеш и перебираются все соседние хеши, отличающиеся от исходного не более чем в k битах. Для каждого из таких хешей производится перебор списка соответствующих ему слов.
Процесс вычисления хеша - каждому биту хеша сопоставляется группа символов из алфавита. Бит 1 на позиции i в хеше означает, что в исходном слове присутствует символ из i-ой группы алфавита. Порядок букв в слове абсолютно никакого значения не имеет.
Удаление одного символа либо не изменит значения хеша (если в слове еще остались символы из той же группы алфавита), либо же соответствующий этой группе бит изменится в 0. При вставке, аналогичным образом либо один бит встанет в 1, либо никаких изменений не будет. При замене символов всё немного сложнее - хеш может либо вовсе остаться неизменным, либо же изменится в 1 или 2 позициях. При перестановках никаких изменений и вовсе не происходит, потому что порядок символов при построении хеша, как и было замечено ранее, не учитывается. Таким образом, для полного покрытия k ошибок нужно изменять не менее 2k бит в хеше.
Время работы, в среднем, при k «неполных» (вставки, удаления и транспозиции, а также малая часть замен) ошибках: 
Особенности:
Из того, что при замене одного символа могут изменятся сразу два бита, алгоритм, реализующий, например, искажения не более 2 битов одновременно в действительности не будет выдавать полного объема результатов из-за отсутствия значительной (зависит от отношения размера хеша к алфавиту) части слов с двумя заменами (и чем больше размер хеша, тем чаще замена символа будет приводить к искажению сразу двух бит, и тем менее полным будет результат). К тому же, этот алгоритм не позволяет проводить префиксный поиск.BK-деревья
Деревья Burkhard-Keller являются метрическими деревьями, алгоритмы построения таких деревьев основаны на свойстве метрики отвечать неравенству треугольника:Это свойство позволяет метрикам образовывать метрические пространства произвольной размерности. Такие метрические пространства не обязательно являются евклидовыми , так, например, метрики Левенштейна и Дамерау-Левенштейна образуют неевклидовы пространства. На основании этих свойств можно построить структуру данных, осуществляющую поиск в таком метрическом пространстве, которой и являются деревья Баркхарда-Келлера.
Улучшения:
Можно использовать возможность некоторых метрик вычислять расстояние с ограничением, устанавливая верхний предел, равный сумме максимального расстояния к потомкам вершины и результирующего расстояния, что позволит немного ускорить процесс:Тестирование
Тестирование осуществлялось на ноутбуке с Intel Core Duo T2500 (2GHz/667MHz FSB/2MB), 2Gb ОЗУ, ОС - Ubuntu 10.10 Desktop i686, JRE - OpenJDK 6 Update 20.
Тестирование осуществлялось с использованием расстояния Дамерау-Левенштейна и количеством ошибок k = 2 . Размер индекса указан вместе со словарем (65 Мб).
Размер индекса: 65 Мб
Время поиска: 320 мс / 330 мс
Полнота результатов: 100%
N-грамм (оригинальный)
Размер индекса: 170 МбВремя создания индекса: 32 с
Время поиска: 71 мс / 110 мс
Полнота результатов: 65%
N-грамм (модификация 1)
Размер индекса: 170 МбВремя создания индекса: 32 с
Время поиска: 39 мс / 46 мс
Полнота результатов: 63%
N-грамм (модификация 2)
Размер индекса: 170 МбВремя создания индекса: 32 с
Время поиска: 37 мс / 45 мс
Полнота результатов: 62%
Размер индекса: 85 Мб
Время создания индекса: 0.6 с
Время поиска: 55 мс
Полнота результатов: 56.5%
BK-деревья
Размер индекса: 150 МбВремя создания индекса: 120 с
Время поиска: 540 мс
Полнота результатов: 63%
Итого
Большинство алгоритмов нечеткого поиска с индексацией не являются истинно сублинейными (т.е. имеющими асимптотическое время работы O(log n) или ниже), и их скорость работы обычно напрямую зависит от N . Тем не менее, множественные улучшения и доработки позволяют добиться достаточного малого времени работы даже при весьма больших объемах словарей.Существует также еще множество разнообразных и неэффективных методов, основанных, помимо всего прочего, на адаптации различных, уже где-либо применяемых техник и приемов к данной предметной области. В числе таких методов - адаптация префиксных деревьев (Trie) к задачам нечеткого поиска , которую я оставил без внимания в виду её малой эффективности. Но есть и алгоритмы, основанные на оригинальных подходах, например, алгоритм Маасса-Новака , который хоть и имеет сублинейное асимптотическое время работы, но является крайне неэффективным из-за огромных констант, скрывающихся за такой временной оценкой, которые проявляются в виде огромного размера индекса.
Практическое использование алгоритмов нечеткого поиска в реальных поисковых системах тесно связано с фонетическими алгоритмами , алгоритмами лексического стемминга - выделения базовой части у различных словоформ одного и того же слова (например, такую функциональность предоставляют Snowball и Яндекс mystem), а также с ранжированием на основе статистической информации, либо же с использованием сложных изощренных метрик.
- Расстояние Левенштейна (с отсечением и префиксным вариантом);
- Расстояние Дамерау-Левенштейна (с отсечением и префиксным вариантом);
- Алгоритм Bitap (Shift-OR / Shift-AND с модификациями Wu-Manber);
- Алгоритм расширения выборки;
- Метод N-грамм (оригинальный и с модификациями);
- Метод хеширования по сигнатуре;
- BK-деревья.
Стоит заметить, что в процессе изучения этой темы у меня появились кое-какие собственные наработки, позволяющие на порядок сократить время поиска за счет умеренного увеличения размера индекса и некоторого ограничения в свободе выбора метрик. Но это уже совсем другая история.
Использование N-грамм
Общее использование N-грамм
- извлечение данных для кластеризации серии спутниковых снимков Земли из космоса, чтобы затем решить, какие конкретные части Земли на изображении,
- поиск генетических последовательностей,
- в области генетики используются для определения того, с каких конкретных видов животных собраны образцы ДНК ,
- в компьютерном сжатии ,
- с использованием N-грамм, как правило, индексированы данные, связанные со звуком.
Также N-граммы широко применяются в обработке естественного языка.
Использование N-грамм для нужд обработки естественного языка
В области обработки естественного языка, N-граммы используется в основном для предугадывания на основе вероятностных моделей. N-граммная модель рассчитывает вероятность последнего слова N-грамма если известны все предыдущие. При использовании этого подхода для моделирования языка предполагается, что появление каждого слова зависит только от предыдущих слов.
Другое применение N-граммов является выявление плагиата . Если разделить текст на несколько небольших фрагментов, представленных n-граммами, их легко сравнить друг с другом, и таким образом получить степень сходства контролируемых документов. N-грамм, часто успешно используется для категоризации текста и языка. Кроме того, их можно использовать для создания функций, которые позволяют получать знания из текстовых данных. Используя N-грамм можно эффективно найти кандидатов, чтобы заменить слова с ошибками правописания.
Научно-исследовательские проекты Google
Исследовательские центры Google использовали N-граммные модели для широкого круга исследований и разработок. К ним относятся такие проекты, как статистический перевод с одного языка на другой, распознавание речи, исправление орфографических ошибок, извлечение информации и многое другое. Для целей этих проектов были использованы тексты корпусов, содержащих несколько триллионов слов.
Google решила создать свой учебный корпус. Проект называется Google teracorpus и он содержит 1 024 908 267 229 слов, собраных с общедоступных веб-сайтов.
Методы для извлечения n-граммов
В связи с частым использованием N-граммов для решения различных задач, необходим надежный и быстрый алгоритм для извлечения их из текста. Подходящий инструмент для извлечения n-граммов должен быть в состоянии работать с неограниченным размером текста, работать быстро и эффективно использовать имеющиеся ресурсы. Есть несколько методов извлечения N-граммов из текста. Эти методы основаны на разных принципах:
Примечания
См. также
Wikimedia Foundation . 2010 .
- n-tv
- N-кадгерин
Смотреть что такое "N-грамм" в других словарях:
ГРАММ - (фр. gramme, от греч. gramma черта). Единица франц. веса = весу 1 кубического сантиметра дистиллированной воды = 22,5 русск. долям. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. ГРАММ единица меры веса во Франции … Словарь иностранных слов русского языка
грамм - грамм, род. мн. граммов и допустимо (в устной речи после числительных) грамм. Сто граммов (грамм). В защиту новой формы род. падежа мн. числа грамм выступил знаток русского языка писатель К. Чуковский. Вот что он писал в книге «Живой как жизнь»:… … Словарь трудностей произношения и ударения в современном русском языке
ГРАММ - ГРАММ, грамма, муж. (от греч. gramma знак, буква). Основная единица веса в метрической системе мер, равная весу 1 кубического сантиметра воды. Грамм весит около 1/400 фунта. ❖ Грамм атом (физ.) число граммов вещества, равное его атомному весу.… … Толковый словарь Ушакова
грамм-рентген - грамм рентге/н, грамм рентге/на, род. мн. грамм рентген и грамм рентгенов … Слитно. Раздельно. Через дефис.
грамм - Грамм, это простое слово можно было бы и не приводить в словаре ошибок, если бы не два обстоятельства; во первых, если хотите блеснуть абсолютно верным языком, то, придя в магазин, огорошьте продавца правильным: Взвесьте мне двести граммов (не… … Словарь ошибок русского языка
ГРАММ-ATOM - ГРАММ ATOM, количество элемента, масса которого, в граммах, равна его АТОМНОЙ МАССЕ. Его заменила единица системы СИ моль. Например, один грамм атом водорода (Н, атомная масса = 1) равен одному грамму. b>ГРАММ ЭКВИВАЛЕНТ, вес в граммах того… … Научно-технический энциклопедический словарь
ГРАММ - ГРАММ, а, род. мн. грамм и граммов, муж. Единица массы в десятичной системе мер, одна тысячная доля килограмма. Ни грамма (нет) чего (разг.) нисколько, нет совсем. У этого человека (нет) ни грамма совести. | прил. граммовый, ая, ое. Толковый… … Толковый словарь Ожегова
грамм - а; мн. род. граммов и грамм; м. [франц. gramme] Единица массы в метрической системе мер, одна тысячная доля килограмма. ◊ Ни (одного) грамма нет. Нисколько, нет совсем. В ком л. ни грамма фальши. Нет ни грамма совести у кого л. * * * грамм (франц … Энциклопедический словарь
Грамм Зеноб Теофиль - (Gramme) (1826 1901), электротехник. Родился в Бельгии, работал во Франции. Получил патент на практически пригодный электрический генератор с кольцевым якорем (1869). Основал промышленное производство электрических машин. * * * ГРАММ Зеноб… … Энциклопедический словарь
грамм-атом - количество вещества в граммах, численно равное его атомной массе. Термин не рекомендуется к употреблению. В СИ количество вещества выражают в молях. * * * ГРАММ АТОМ ГРАММ АТОМ, количество вещества в граммах, численно равное его атомной массе (см … Энциклопедический словарь
грамм-молекула - количество вещества в граммах, численно равное его молекулярной массе. Термин не рекомендуется к употреблению. В СИ количество вещества выражают в молях. * * * ГРАММ МОЛЕКУЛА ГРАММ МОЛЕКУЛА, количество вещества в граммах, численно равное его… … Энциклопедический словарь
,
Рассмотрены N -граммы как средство фиксации языковой реальности и как модельный конструкт. Разобрана связь модельных N -грамм и формальных грамматик. Обращено внимание на недостатки и противоречия, связанные с использованием вероятностных моделей .
Введение
Начнем с формального определения. Пусть задан некоторый конечный алфавит VT ={wi }, где wi –отдельный символ. Множество цепочек (строк) конечной длины, состоящих из символов алфавита VT , называется языком на алфавите VT и обозначается L(VT) . Отдельную цепочку из языка L(VT) будем называть высказыванием на этом языке. В свою очередь, N -граммой на алфавите VT называется цепочка длиной N . N -грамма может совпадать с каким-то высказыванием, быть его подстрокой или вообще не входить в L(VT) .
Приведем несколько примеров N -грамм.
3. , N -граммы русского языка. // Настоящий сборник.
4. Гланц С. Медико-биологическая статистика. Пер. с англ. под ред. и. М., 1999.
5. Дескриптивная лингвистика. Предисловие к книге Г. Глисона «Введение в дескриптивную лингвистику». М., 1959.
6. Теоретическая и прикладная лингвистика. М., 1968.
8. , Паузирование при автоматическом синтезе речи. // Теория и практика речевых исследований. М. 1999.
9. Минский М. Остроумие и логика когнитивного бессознательного. // Новое в зарубежной лингвистике. Вып. XXIII. М., 1988.
10. Слобин Д., Грин Дж. Психолингвистика. М., 1976
11. Теория вероятностей. М., 1972.
12. Фу К. Структурные методы в распознавании образов. М., 1977.
13. Харрис Т. Теория ветвящихся случайных процессов. М., 1966.
14. Brill E. et al. Beyond N -grams: Can linguistic sophistication improve language modeling?
15. Booth T. Probability Representation of Formal Languages. // IEEE Annual Symp. Switching and Automata Theory. 1969.
16. Jelinek F. Self-Organized Language Modeling for Speech Recognition. // Readings in Speech Recognition. 1989.
17. Je linek F. , Lafferty J. Computation of the probability of initial substring generation by stochastic context-free grammar. // Computational Linguistics, vol.
18. Harris Z. S. Method in Structural Linguistics. Chicago, 1951.
19. Lashley K. The problem of serial order in behavior. // Psycholinguistics: A book of readings, N. Y. 1961.
20. Schlesinger E. Sentence Structure and the Reading Process. Mouton. 1968.
21. Shieber S. Evidence against the context-freeness of natural language. // Linguistics and Philosophy, vol.
22. Sola Pool I. Trends in Content Analysis Today. // Psycholinguistics: A book of readings, N. Y. 1961
23. Stolcke A., Segal J. Precise n-gram probabilities from stochastic context-free grammars. // Proceedings of the 32th Annual Meeting of ACL. 1994.