Стемінг (англ. stemming) - це процес скорочення слова до основи шляхом відкидання допоміжних частин, таких як закінчення чи суфікс. Результати стемінгу іноді дуже схожі на визначення кореня слова, але його алгоритми базуються на інших принципах. Тому слово після обробки алгоритмом стемінгу (стематизації) може відрізнятися від морфологічного кореня слова. Стемінг застосовується в лінгвістичній морфології та в інформаційному пошуку. Багато пошукових систем використовують стемінг для об’єднання слів у яких збігаються форми після стематизації, вони вважають такі слова синонімами. Цей процес називають злиттям.

Комп’ютерна програма, що реалізує алгоритм стемінгу іноді має назву стемер.

Під час стемінгу слова "швидко", "швидкий", "швидкі" будуть перетворені до форми "швидк". А слова "бігом", "бігаю", "бігати" взагалі до кореня слова "біг".

Вперше алгоритм стемінгу був опублікований Джулі Бет Ловінс^[en] у 1968.^[1] На свій час це була передова робота яка мала великий вплив на подальші дослідження у цьому напрямку.

Пізніше алгоритм стемінгу був написаний Мартіном Портером^[en] та опублікований в липні 1980 у журналі Program. Цей алгоритм набув широкого поширення та став де-факто стандартним алгоритмом стемінгу для англійської мови. Доктор Портер отримав Tony Kent Strix award^[en] у 2000 році за свою роботу над стемінгом та внесок у галузь пошуку інформації.

Існує досить багато реалізацій Портерівського алгоритму, що вільно поширюються у програмному забезпеченні, але деякі з них мають певні вади. Як результат, не всі алгоритми стемінгу видають результат, який від них очікують. Щоб зменшити подібні помилки Мартін Потер створив офіційну вільну реалізацію [Архівовано 14 травня 2012 у Wayback Machine.] алгоритму у 2000 році. А наступні кілька роки присвятив побудові Snowball^[en], спеціального середовища для написання алгоритмів стемінгу, яке призначене для вдосконалення стемінгу англійської мови та написанню алгоритмів стемінгу ще для кількох мов.

Існує кілька варіантів алгоритмів стемінгу, які відрізняються своєю точністю та продуктивністю.

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

Фрагмент таблиці пошуку, на прикладі слова "безпритульний":

Ці алгоритми базуються на правилах, за якими можна скорочувати слово. Якщо взяти приклад з алгоритму пошуку за таблицею, то ці правила можуть мати такий вигляд:

• слово закінчується на "льна" - відсікаємо від слова "ьна";
• слово закінчується на "льне" - відсікаємо "ьне";
• слово закінчується на "льний" - відсікаємо "ьний";
• слово закінчується на "льним" - відсікаємо "ьним".

Кількість таких правил стемінгу набагато менша за таблицю з усіма словоформами, а тому алгоритм є досить компактним та продуктивним. Наведені вище 4 правила правильно обробляють наступні прикметники:

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

Це більш комплексний підхід, що базується на визначенні основи слова шляхом лематизації. Першим кроком цього алгоритму є визначення частин мови у реченні, так званий POS tagging. На другому кроці, до слова застосовуються правила стемінгу відповідно до частини мови. Тобто слова "пальне" та "вітальне" мають проходити через різні ланцюжки правил, тому що "пальне" - іменник, а "вітальне" - прикметник. Теоретично алгоритми стемінгу, що базуються на лематизації повинні мати дуже високу якість і мінімальний відсоток помилок, але вони дуже залежні від правильності розпізнавання частин мови.

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

Розглянемо приклад. Уявімо, що маємо лише одне логічне правило за яким від слова відсікаємо останні літери. База знань наведена у таблиці:

У стовпці "Закінчення" наведений результат "навчання" алгоритму на базі знань, тобто якщо слова закінчуються на "ість", "и" чи "ими", то алгоритм знає що з ними робити. Для ілюстрації спробуємо виконати стемінг слова "кияни":

Маємо один варінт (2-й рядок), тому слово після стемінгу - "киян". Але якщо передати цьому алгоритму слово "чуйними", то відповідь вже не однозначна:

Перед нашим алгоритмом дилема, який варіант стемінгу обрати: "чуйним" чи "чуйн"? Ускладнення правила дозволяє розв'язати такі розбіжності: ми можемо віддавати перевагу стемінгу, який скорочує слово найбільше чи найменше.

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

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

Деякі стемери не обмежуються відсіченням від слова суфіксів та закінчень, а додатково намагаються позбавити слово ще й префіксу. Звичайно, не можна позбавляти всі слова префіксів, тому що після такого нерозбірливого стемінгу від слова "незалежний" утвориться "залежн", а це вже слово з протилежним змістом. Але існують слова, у яких префікс скоріше додає забарвлення ніж змінює значення слова, тому "проголошую", "наголошувати", "виголошував" цілком коректно скоротити до "голошу". Існують наукові праці, які обґрунтовують важливість таких алгоритмів стемінгу для деяких європейських мов. ^[2]

Ці алгоритми використовують базу знань, що містить в собі лише основи слів. Тобто ця база знань складається з тих слів в які перетворюються звичайні слова після стемінгу. Якщо порівнювати з пошуком по таблиці, то це слова з другого стовпця. Основна мета цих алгоритмів - через систему внутрішніх правил знайти для слова найвідповіднішу форму з бази знань. Одним з таких внутрішніх правил може бути довжина збігу слова та його основи. Наприклад, у базі знань є основи "чорн" та "чорняв". Порівнюючи зі словом "чорнява" у першому випадку спільна довжина 4 ("чорнява"), а у другому - 6 ("чорнява"), тому алгоритм обере довший варіант.

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

Існують варіанти стемінгу для української мови^{[3][4][5][6][7]}.

У алгоритмах стемінгу поширені помилки 2-х типів:

• надстемінг (англ. overstemming)
• недостемінг (англ. understemming)

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