N грама іноді також Q грама в обчислювальній лінгвістиці та теорії ймовірностей послідовність з n елементів із певної ви

N-грама (іноді також Q-грама) — в обчислювальній лінгвістиці та теорії ймовірностей: послідовність з n елементів із певної вибірки тексту або мовлення. Елементами можуть бути фонеми, склади, букви, слова залежно від застосування. N-грами зазвичай отримуються з тексового або ^[en]. Якщо елементи — слова, то N-грами також називають шинґли (англ. shingles, ймовірно від шиндель, ґонт, бо послідовні N-грами в тексті перекриваються як покриття даху).

Використовуючи латинські числівникові префікси N-грама розміру 1 називається «уніграмою», розміру 2 «біграма» (чи «диграма»); розміру 3 — «триграма». Також використовуються звичайні числівники, «чотири-грама» і т. ін. В обчислювальній біології полімер чи олігомер відомого розміру називають ^[en]ом, а не N-грамою і конкретні грецькі числівникові префікси, такі як «мономер», «димер», «тример».

Використання N-грам

Загальне використання N-грам

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

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

Також N-грами широко застосовуються в обробці природної мови.

Використання N-грам для потреб обробки природної мови

В області обробки природної мови, N-грами використовується в основному для передбачення на основі імовірнісних моделей. N-грамна модель розраховує ймовірність останнього слова N-грами, якщо відомі всі попередні. При використанні цього підходу для моделювання мови передбачається, що поява кожного слова залежить тільки від попередніх слів.

Інше застосування N-грам є виявлення плагіату. Якщо розділити текст на кілька невеликих фрагментів, представлених N-грамами, їх легко порівняти один з одним, і таким чином отримати ступінь подібності контрольованих документів. N-грами часто успішно використовуються для категоризації тексту та мови. Крім того, їх можна використовувати для створення функцій, які дозволяють отримувати знання з текстових даних. Використовуючи 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 слів, зібраних із загальнодоступних вебсайтів.

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

У зв'язку з частим використанням N-грам для вирішення різних завдань необхідний надійний і швидкий алгоритм для вилучення їх з тексту. Відповідний інструмент для вилучення N-грам повинен бути в змозі працювати з необмеженим по розміру текстом, працювати швидко й ефективно використовувати наявні ресурси. Є кілька методів вилучення N-грам з тексту. Ці методи засновані на різних принципах:

Алгоритм Nagao 94 для текстів на японському
Алгоритм Лемпеля — Зіва — Велча
Суфіксне дерево
Інвертований індекс

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

Синтаксичні N-грами — це N-грами, що визначаються шляхами в деревах синтаксичних залежностей або деревах складових, а не лінійною структурою тексту. Наприклад, речення: «Економічні новини мають незначний вплив на фінансові ринки» може бути перетворено в синтаксичні N-грами слідуючи деревоподібній структурі його відносин залежностей: новини-економічні, вплив-незначний, вплив-на-ринки-фінансові та інші.

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

Компроміс зсуву та дисперсії

Аби обрати значення n в N-грамній моделі, необхідно знайти компроміс між стабільністю оцінки і її доречністю. Це означає що триграми є частим вибором для великого навчального корпусу (мільйони слів), а біграми часто використовуються з меншими.

Методи згладжування

Є завдання балансування ваги між нечастими грамами (наприклад, якщо власне ім'я зустрінеться один раз у навчальних даних) та частими грамами. Крім того, елементи які не з'являлись у навчальних даних отримають ймовірність 0,0 без згладжування. Для незнайомих, але правдоподібних даних з вибірки, можна ввести ^[en].

На практиці, необхідно згладити розподіл ймовірності додавши ненульові ймовірності для слів чи N-грамів які ще не зустрічались. Причиною є те що моделі які напряму виводяться з частот N-грамів мають серйозні проблеми при зіткненні з раніше небаченими N-грамами — проблему нульової частоти. Використовуються різноманітні методи згладжування, від простого «додати один» (Лапласового) згладжування (присвоїти частоту 1 N-грамам які не зустрічалися, див ^[en]) до складніших, таких як ^[en] або ^[en]. Деякі з цих методів аналогічні присвоєнню апріорного розподілу до ймовірностей N-грамів і використання баєсового висновування для обчислення апостеріорних імовірностей N-грамів, але складніші методи виводять не таким чином, а через незалежні міркування.

Лінійна інтерполяція (використання зваженого середнього уніграми, біграми і триграми)
^[en]
^[en]
^[en]
^[en]

Пропуск-грама

У галузі обчислювальної лінгвістики, особливо у моделюванні мови, пропуск-грами (англ. skip-grams) є узагальненням N-грамів, у якій компоненти (зазвичай слова) не обов'язково мають бути сусідами у тексті що обробляється, між ними можуть залишатися пропуски. Пропуск-грами є одним зі способів розв'язати проблему розрідженості даних до якої схильний звичайний N-грамний аналіз. В галузі комп'ютерної безпеки, пропуск-грами виявилися стійкішими до атак ніж N-грами.

Формально, N-грама — це підпослідовності довжини $n$ сусідніх елементів деякої послідовності токенів $w 1 \dots w n$ . Тоді $k$ -пропуск- $n$ -грама це підпослідовність довжини $n$ елементів які з'являються один від одного на відстані не більшій ніж $k$ .

Наприклад, у тексті:

the rain in Spain falls mainly on the plain

множина 1-пропуск-2-грамів включає всі біграми (2-грами), і на додачу послідовності

the in, rain Spain, in falls, Spain mainly, falls on, mainly the, and on plain.

Див. також

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

Примітки

Broder, Andrei Z.; Glassman, Steven C.; Manasse, Mark S.; Zweig, Geoffrey (1997). Syntactic clustering of the web. Computer Networks and ISDN Systems. 29 (8): 1157—1166. doi:10.1016/s0169-7552(97)00031-7.
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. — .
Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008.
FRANZ, Alex, BRANTS, Thorsten.
Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández.
Grigori Sidorov.
Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández.
Huang, Xuedong; Alleva, Fileno; Hon, Hsiao-wuen; Hwang, Mei-yuh; Rosenfeld, Ronald (1 січня 1992). The SPHINX-II Speech Recognition System: An Overview. Computer Speech & Language. 7 (2): 137—148. CiteSeerX 10.1.1.45.1629. doi:10.1006/csla.1993.1007.
David Guthrie та ін. (2006). (PDF). Архів оригіналу (PDF) за 17 травня 2017. Процитовано 27 квітня 2014.
Jonathan Oliver та ін. (2021). Designing the Elements of a Fuzzy Hashing Scheme (PDF). (PDF) оригіналу за 14 квітня 2021. Процитовано 14 квітня 2021.

Це незавершена стаття з інформатики.
Ви можете проєкту, виправивши або дописавши її.

[1] Broder, Andrei Z.; Glassman, Steven C.; Manasse, Mark S.; Zweig, Geoffrey (1997). Syntactic clustering of the web. Computer Networks and ISDN Systems. 29 (8): 1157—1166. doi:10.1016/s0169-7552(97)00031-7.

[2] 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. — .

[3] Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008.

[4] FRANZ, Alex, BRANTS, Thorsten.

[sng-5] Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández.

[6] Grigori Sidorov.

[7] Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández.

[8] Huang, Xuedong; Alleva, Fileno; Hon, Hsiao-wuen; Hwang, Mei-yuh; Rosenfeld, Ronald (1 січня 1992). The SPHINX-II Speech Recognition System: An Overview. Computer Speech & Language. 7 (2): 137—148. CiteSeerX 10.1.1.45.1629. doi:10.1006/csla.1993.1007.

[9] David Guthrie та ін. (2006). (PDF). Архів оригіналу (PDF) за 17 травня 2017. Процитовано 27 квітня 2014.

[10] Jonathan Oliver та ін. (2021). Designing the Elements of a Fuzzy Hashing Scheme (PDF). (PDF) оригіналу за 14 квітня 2021. Процитовано 14 квітня 2021.