N-грама

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

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

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

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

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

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

Інше застосування N-грам є виявлення плагіату. Якщо розділити текст на кілька невеликих фрагментів, представлених N-грамами, їх легко порівняти один з одним, і таким чином отримати ступінь подібності контрольованих документів^[3]. N-грами часто успішно використовуються для категоризації тексту та мови. Крім того, їх можна використовувати для створення функцій, які дозволяють отримувати знання з текстових даних. Використовуючи N-грами, можна ефективно знайти кандидатів, щоб замінити слова з помилками правопису.

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

P = P (щастя) * P (є | щастя) * P (задоволення | щастя є) * P (без | щастя є задоволення) * P (каяття | щастя є задоволення без) 

Розрахувати ймовірність P (щастя) справа нехитра: потрібно всього лише порахувати скільки разів це слово зустрілося в тексті і поділити це значення на загальне число слів. Але розрахувати ймовірність P (каяття | щастя є задоволення без) уже не так просто. На щастя, ми можемо спростити цю задачу. Приймемо, що ймовірність слова в тексті залежить тільки від попереднього слова. Тоді наша формула для розрахунку фрази прийме наступний вигляд:

P = P (щастя) * P (є | щастя) * P (задоволення | є) * P (без | задоволення) * P (каяття | без) 

Вже простіше. Розрахувати умовну ймовірність P (є | щастя) не складно. Для цього рахуємо кількість пар «щастя є» і ділимо на кількість в тексті слова «щастя».

У результаті, якщо ми порахуємо всі пари слів в деякому тексті, ми зможемо обчислити імовірність довільної фрази. Цей набір розрахованих ймовірностей і буде біграмною моделлю.

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

Google вирішила створити свій навчальний корпус. Проєкт називається Google teracorpus і він містить 1 024 908 267 229 слів, зібраних із загальнодоступних вебсайтів^[4].

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

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

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

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

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

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

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

• Лінійна інтерполяція (використання зваженого середнього уніграми, біграми і триграми)
• дисконтування Гуда-Тюринга^[en]
• дисконтування Віттена-Белла
• Згладжування Лідстоуна^[en]
• моделі відступання^[en]
• Згладжування Кнесера-Нея^[en]

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

Формально, N-грама — це підпослідовності довжини n сусідніх елементів деякої послідовності токенів w₁ … 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.

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

В іншому мовному розділі є повніша стаття n-gram(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.

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