Стемінг
Стемінг (англ. stemming) - це процес скорочення слова до основи шляхом відкидання допоміжних частин, таких як закінчення чи суфікс. Результати стемінгу іноді дуже схожі на визначення кореня слова, але його алгоритми базуються на інших принципах. Тому слово після обробки алгоритмом стемінгу (стематизації) може відрізнятися від морфологічного кореня слова. Стемінг застосовується в лінгвістичній морфології та в інформаційному пошуку. Багато пошукових систем використовують стемінг для об’єднання слів у яких збігаються форми після стематизації, вони вважають такі слова синонімами. Цей процес називають злиттям.
Комп’ютерна програма, що реалізує алгоритм стемінгу іноді має назву стемер.
Приклади
Під час стемінгу слова "швидко", "швидкий", "швидкі" будуть перетворені до форми "швидк". А слова "бігом", "бігаю", "бігати" взагалі до кореня слова "біг".
Історична довідка
Вперше алгоритм стемінгу був опублікований Джулі Бет Ловінс у 1968.[1] На свій час це була передова робота яка мала великий вплив на подальші дослідження у цьому напрямку.
Пізніше алгоритм стемінгу був написаний Мартіном Портером та опублікований в липні 1980 у журналі Program. Цей алгоритм набув широкого поширення та став де-факто стандартним алгоритмом стемінгу для англійської мови. Доктор Портер отримав Tony Kent Strix award у 2000 році за свою роботу над стемінгом та внесок у галузь пошуку інформації.
Існує досить багато реалізацій Портерівського алгоритму, що вільно поширюються у програмному забезпеченні, але деякі з них мають певні вади. Як результат, не всі алгоритми стемінгу видають результат, який від них очікують. Щоб зменшити подібні помилки Мартін Потер створив офіційну вільну реалізацію алгоритму у 2000 році. А наступні кілька роки присвятив побудові Snowball, спеціального середовища для написання алгоритмів стемінгу, яке призначене для вдосконалення стемінгу англійської мови та написанню алгоритмів стемінгу ще для кількох мов.
Алгоритми
Існує кілька варіантів алгоритмів стемінгу, які відрізняються своєю точністю та продуктивністю.
Пошук за таблицею
Цей алгоритм використовує принцип пошуку за таблицею в якій зібрані всі можливі варіанти слів та їх форми після стемінгу. Перевагами цього методу є простота, швидкість та зручність обробки винятків з мовних правил. До недоліків слід віднести те, що таблиця пошуку має містити в собі всі форми слів: тобто алгоритм не буде працювати з новими словами (а як відомо, "живі" мови постійно поповнюються новими словами) і розміри такої таблиці можуть бути істотними. Для мов з відносно простою морфологією, таких як англійська, розміри таблиці пошуку доволі скромні, проте у аглютинативних мовах, наприклад, турецькій, кількість варіантів слів з одним коренем може йти на сотні.
Фрагмент таблиці пошуку, на прикладі слова "безпритульний":
| Слово | Стемінг |
| безпритульна | безпритул |
| безпритульне | |
| безпритульний | |
| безпритульним | |
| безпритульними | |
| безпритульних | |
| безпритульні | |
| безпритульній | |
| безпритульнім | |
| безпритульного | |
| безпритульної | |
| безпритульному | |
| безпритульною | |
| безпритульну |
Відсічення закінчень та суфіксів
Ці алгоритми базуються на правилах, за якими можна скорочувати слово. Якщо взяти приклад з алгоритму пошуку за таблицею, то ці правила можуть мати такий вигляд:
- слово закінчується на "льна" - відсікаємо від слова "ьна";
- слово закінчується на "льне" - відсікаємо "ьне";
- слово закінчується на "льний" - відсікаємо "ьний";
- слово закінчується на "льним" - відсікаємо "ьним".
Кількість таких правил стемінгу набагато менша за таблицю з усіма словоформами, а тому алгоритм є досить компактним та продуктивним. Наведені вище 4 правила правильно обробляють наступні прикметники:
| Слово | Стемінг |
| безпритульна | безпритул |
| повільне | повіл |
| ортогональний | ортогонал |
| цивільним | цивіл |
Проте алгоритм може робити хибні висновки і спотворювати форму стемінгу. Наприклад, слово "пальне" перетвориться на "пал" замість правильної форми "пальн". Тому враховуючи особливості мови набір правил по відсіченню закінчень та суфіксів може бути досить складним. До недоліків також слід віднести обробку винятків, коли базові слова мають змінну форму. Наприклад, слова "бігом" та "біжу" повинні мати після стемінгу однаковий вигляд "біг", але простим відсіканням закінчення це не можливо зробити. Алгоритм вимушений враховувати такі ситуації - це призводить до ускладнення правил, і врешті-решт негативно впливає на ефективність.
Лематизація
Це більш комплексний підхід, що базується на визначенні основи слова шляхом лематизації. Першим кроком цього алгоритму є визначення частин мови у реченні, так званий POS tagging. На другому кроці, до слова застосовуються правила стемінгу відповідно до частини мови. Тобто слова "пальне" та "вітальне" мають проходити через різні ланцюжки правил, тому що "пальне" - іменник, а "вітальне" - прикметник. Теоретично алгоритми стемінгу, що базуються на лематизації повинні мати дуже високу якість і мінімальний відсоток помилок, але вони дуже залежні від правильності розпізнавання частин мови.
Стохастичні алгоритми
Стохастичні алгоритми базуються на ймовірності визначення основи слова. По своїй природі вони мають здатність "навчатися" і чим краща та більша база навчання, тим кращий результат їх роботи. База знань для цих алгоритмів - це набір логічних правил та таблиці пошуку. Після опрацювання слова стохастичним алгоритмом може з’явитися декілька варіантів основи слова, з яких алгоритм обере найімовірніший, на його думку, варіант.
Розглянемо приклад. Уявімо, що маємо лише одне логічне правило за яким від слова відсікаємо останні літери. База знань наведена у таблиці:
| Слово | Стемінг | Закінчення |
| особистість | особист | ість |
| спогади | спогад | и |
| дивними | дивн | ими |
У стовпці "Закінчення" наведений результат "навчання" алгоритму на базі знань, тобто якщо слова закінчуються на "ість", "и" чи "ими", то алгоритм знає що з ними робити. Для ілюстрації спробуємо виконати стемінг слова "кияни":
| Слово | Закінчується на? | Результат | Числовий результат |
| кияни | ість | ні | 0 |
| кияни | и | так | 1 |
| кияни | ими | ні | 0 |
Маємо один варінт (2-й рядок), тому слово після стемінгу - "киян". Але якщо передати цьому алгоритму слово "чуйними", то відповідь вже не однозначна:
| Слово | Закінчується на? | Результат | Числовий результат |
| чуйними | ість | ні | 0 |
| чуйними | и | так | 1 |
| чуйними | ими | так | 1 |
Перед нашим алгоритмом дилема, який варіант стемінгу обрати: "чуйним" чи "чуйн"? Ускладнення правила дозволяє розв'язати такі розбіжності: ми можемо віддавати перевагу стемінгу, який скорочує слово найбільше чи найменше.
Іноді алгоритми лематизації теж мають стохастичні властивості, коли частину мови вони визначають без урахування контексту, в якому це слово було вжито в реченні. У таких випадках перевага віддається найвірогіднішій частині мови для цього слова, і як результат - ймовірність помилок стемінгу зростає.
Гібридний підхід
При побудові гібридного алгоритму стемінгу може використовуватись комбінація алгоритмів, що наведені вище. Наприклад, алгоритм може використовувати метод відсікання закінчень та суфіксів, але на першому етапі виконувати пошук по таблиці. На відміну від пошуку по таблиці ця таблиця містить не всі словоформи, а тільки винятки з правил, які хибно обробляються алгоритмом, що відсікає закінчення.
Відсічення префіксів
Деякі стемери не обмежуються відсіченням від слова суфіксів та закінчень, а додатково намагаються позбавити слово ще й префіксу. Звичайно, не можна позбавляти всі слова префіксів, тому що після такого нерозбірливого стемінгу від слова "незалежний" утвориться "залежн", а це вже слово з протилежним змістом. Але існують слова, у яких префікс скоріше додає забарвлення ніж змінює значення слова, тому "проголошую", "наголошувати", "виголошував" цілком коректно скоротити до "голошу". Існують наукові праці, які обґрунтовують важливість таких алгоритмів стемінгу для деяких європейських мов. [2]
Пошук відповідності
Ці алгоритми використовують базу знань, що містить в собі лише основи слів. Тобто ця база знань складається з тих слів в які перетворюються звичайні слова після стемінгу. Якщо порівнювати з пошуком по таблиці, то це слова з другого стовпця. Основна мета цих алгоритмів - через систему внутрішніх правил знайти для слова найвідповіднішу форму з бази знань. Одним з таких внутрішніх правил може бути довжина збігу слова та його основи. Наприклад, у базі знань є основи "чорн" та "чорняв". Порівнюючи зі словом "чорнява" у першому випадку спільна довжина 4 ("чорнява"), а у другому - 6 ("чорнява"), тому алгоритм обере довший варіант.
Стемінг різними мовами
Якщо перші академічні роботи зі стемінгу були присвячені лише англійській, то зараз існує доволі багато реалізацій стемінгу для інших мов. Від особливостей мови залежить складність написання алгоритмів стемінгу. Так якщо стемінг англійської це доволі тривіальна задача, то стемінг для арабської чи івриту - задача на порядок складніша.
Помилки стемінгу
У алгоритмах стемінгу поширені помилки 2-х типів:
Надстемінг - це коли під час стематизації два слова скорочуються до однієї основи, хоча це не мало б статися. Недостемінг - це протилежна помилка, коли слова отримують різні основи, хоча б мали мати одну спільну. Алгоритми стемінгу намагаються мінімізувати подібні помилки, проте скорочення помилок одного типу може призвести до зростання помилок іншого.
Посилання
- Julie Beth Lovins (1968). Development of a stemming algorithm. Mechanical Translation and Computational Linguistics 11:22–31.
- Jongejan, B. and H. Dalianis. Automatic training of lemmatization rules that handle morphological changes in pre-, in- and suffixes alike. In the Proceeding of the ACL-2009, Joint conference of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, Singapore, August 2-7, 2009, pp. 145-153
- Порівняння алгоритмів стемінгу для української мови (англ.)
- Вероятностный морфологический анализатор русского и украинского языков (рос.)
- Модуль Drupal для стемінга українською Архівовано 20 серпня 2011 у Wayback Machine.
- Hardcoded stemmer for Ukrainian
- Стемінг за словником в українському аналізаторі для Lucene