Последние несколько дней (вообще-то учитывая выходные/праздники - то недель) я изучаю тему с анализом текстов - определение языка текста, выделение значимых слов и т.д. Поиск обычно приводит так или иначе к стеммингу Портера - алгоритму, который был придуман еще в 1980 году (ага, я в том году перед первым классом Олимпиаду-80 смотрел летом по телеящику :) ); а может и раньше, а сформулирован в 80-м.. не суть важно, смысл в том, что в результате применения к слову определенных правил получаем основу слова (не корень в лингвистическом смысле), которую храним для поиска/анализа.
Как обычно все, что находится - перепечатывание из пустого в порожнее какого-то кода на php, хотя реализация есть на многих языках на сайте то-ли автора, то-ли сочувствующих ему; там же есть и текстовый документ с описанием собственно алгоритма. Там же где-то есть и реализации для разных языков, включая русский, но я пока не дошел, понять бы, как все работает для начала :)
Собственно чтобы понять я перевел себе этот текст, вдруг кому-то еще пригодится - будет лежать тут.
1. ВВЕДЕНИЕ
Автоматическое удаление суффиксов является операцией, которая особенно полезна в области информационного поиска. Обычно есть коллекция документов, каждый из которых описывается словами из названия и возможно словами в описании документа. Если проигнорировать точное взаимное расположение слов, можно допустить, что содержание документа представляется набором слов или “терминов”. Термины с одинаковым корнем будут обычно иметь аналогичное значение:
CONNECT
CONNECTED
CONNECTING
CONNECTION
CONNECTIONS
Производительность системы будет выше, если группа терминов будет упрощена в единственный термин. Это можно сделать, удалив различные суффиксы типа -ED, -ING, -ION, IONS, оставив единственный термин/слово CONNECT. Дополнительно, процесс удаления суффиксов уменьшит количество терминов в системе, уменьшит размер и сложность данных, что всегда выгодно при дальнейшем поиске.
Смысл задачи будет сильно зависеть от использования словаря стемов, списка используемых суффиксов и естественно от целей, для которых производится удаление суффиксов. Здесь принят подход без использования словаря стемов, с максимальной производительностью.
В любой программе стемминга надо иметь в виду 2 соображения: во-первых, суффиксы удаляются только лишь для улучшения производительности, а не по лингвистическим соображениям. Это означает, что не всегда очевидно, по каким признакам суффикс был удален, даже если бы можно было определить суффикс в слове автоматическими средствами.
Возможно, лучшим критерием для удаления суффикса из двух слов W1 и W2 и получения основы S было бы, если бы мы могли сказать, что нет различий между двумя заявлениями “документ о W1” и “документ о W2”. Так, если W1=`CONNECTION' и W2=`CONNECTIONS', то вполне можно обьединить их общим термином ; но если W1=`RELATE', а W2=`RELATIVITY', это выглядит неразумно (особенно если коллекция документов касается теоретической физики). Между этими двумя крайностями существует множество разных вариантов, и получая два термина W1 и W2 всегда будут приниматься какие-то решения, должны ли они быть обьединены в единый стем, точно так же, как решается - релевантен ли документ запросу при поиске.
Во-вторых с подходом, принятым здесь (использование списка суффиксов с различными правилами) успешность удаления суффиксов будет значительно меньше 100%. К примеру, если у SAND и SANDER общая основа, то скорее всего общая основа будет и у WAND и WANDER. Ошибка здесь из-за того, что -ER рассматривается как суффикс, хотя на самом деле он часть корня в слове WANDER. Точно так же удаление суффикса может полностью изменить смысл слова, делая его (удаление) бесполезным в смысле релевантности. PROBE и PROBATE к примеру имеют совсем разные значения в современном английском, но оба скорее всего сведуться к стему PROB
2. АЛГОРИТМ
Чтобы представить алгоритм очистки (стемминга) надо внести несколько определений.
“Согласная” в слове - это буква кроме A, E, I, O или U и кроме Y после согласной. Так что в слове TOY согласные T и Y, а в SYZYGY - S, Z и G. Если буква не согласная - значит она гласная.
Согласная будет обозначаться “c”, гласная как “v”. Список ccc... с длиной больше, чем 0, будет обозначен как “C”, такой же список vvv... как “V”. Следовательно, любое слово или часть слова имеет одну из 4-х форм:
CVCV ... C
CVCV ... V
VCVC ... C
VCVC ... V
Они все могут быть записаны в единственной форме
[C]VCVC ... [V]
где квадратные скобки означают произвольное содержимое. Используя (VC){m} для обозначения “VC повторяется m раз”, можем также записать
[C](VC){m}[V].
m будет называться “мерой” слова или части слова. Случай m = 0 описывает “пустое” слово. Вот несколько примеров:
m=0 TR, EE, TREE, Y, BY: TR -> cc -> [C]
m=1 TROUBLE, OATS, TREES, IVY: TROUBLE -> ccvvccv -> CVCV -> C(VC){1}V
m=2 TROUBLES, PRIVATE, OATEN, ORRERY
Правило для удаления суффикса будет иметь следующий вид:
(condition) S1 -> S2
Это означает, что если слово заканчивается на S1 и основа до S1 удовлетворяет условию, то S1 заменяется на S2. Условие как правило дается в терминах m, например:
(m > 1) EMENT ->
Здесь S1 = `EMENT' и S2 “пустое”. Применение этого правила к REPLACEMENT дает REPLAC, так как REPLAC это часть слова с m = 2.
Часть “условие” может содержать следующее:
*S - стем, который заканчивается на S (аналогично для других букв).
*v* - стем содержит гласную
*d - стем содержит удвоенную согласную (-TT, -SS).
*o - стем заканчивается на cvc, причем вторая c - не W, X или Y (-WIL, -HOP).
Также условие может содержать выражение с and, or и not, так что
(m>1 and (*S or *T))
проверяет основу с m > 1, которая заканчивается на S или T, а
(*d and not (*L or *S or *Z))
проверяет стем, который заканчивается удвоенной согласной, но не L, S или Z. Такие условия требуются редко.
Если есть несколько правил друг под другом только одно будет применено - то, у которого самое длинное соответствие для данного слова. К примеру:
SSES -> SS
IES -> I
SS -> SS
S ->
CARESSES превратится в CARESS, так как SSES является самым длинным совпадением. Соответственно CARESS -> CARESS (S1=`SS'), CARES -> CARE (S1=`S').
В правилах ниже примеры их применения, успешные или нет, выводятся справа с нижнем регистре. Алгоритм следующий:
Шаг 1a
SSES -> SS caresses -> caress
IES -> I ponies -> poni
ties -> ti
SS -> SS caress -> caress
S -> cats -> cat
Шаг 1б
(m>0) EED -> EE feed -> feed
agreed -> agree
(*v*) ED -> plastered -> plaster
bled -> bled
(*v*) ING -> motoring -> motor
sing -> sing
Если срабатывает второе или третье правила из шага 1б, можно продолжить:
AT -> ATE conflat(ed) -> conflate
BL -> BLE troubl(ed) -> trouble
IZ -> IZE siz(ed) -> size
(*d and not (*L or *S or *Z))
-> single letter
hopp(ing) -> hop
tann(ed) -> tan
fall(ing) -> fall
hiss(ing) -> hiss
fizz(ed) -> fizz
(m=1 and *o) -> E fail(ing) -> fail
fil(ing) -> file
Правило “-> single letter” вызывает удаление одной из букв из пары. -E добавляется в конец -AT, -BL и -IZ, так что суффиксы -ATE, -BLE и -IZE можно будет распознать позже. Эта E может быть удалена в шаге 4.
Шаг 1в
(*v*) Y -> I happy -> happi
sky -> sky
Шаг 1 рассматривает множественное число и прошедшее время. Следующие шаги намного проще
Шаг 2
(m>0) ATIONAL -> ATE relational -> relate
(m>0) TIONAL -> TION conditional -> condition
rational -> rational
(m>0) ENCI -> ENCE valenci -> valence
(m>0) ANCI -> ANCE hesitanci -> hesitance
(m>0) IZER -> IZE digitizer -> digitize
(m>0) ABLI -> ABLE conformabli -> conformable
(m>0) ALLI -> AL radicalli -> radical
(m>0) ENTLI -> ENT differentli -> different
(m>0) ELI -> E vileli - > vile
(m>0) OUSLI -> OUS analogousli -> analogous
(m>0) IZATION -> IZE vietnamization -> vietnamize
(m>0) ATION -> ATE predication -> predicate
(m>0) ATOR -> ATE operator -> operate
(m>0) ALISM -> AL feudalism -> feudal
(m>0) IVENESS -> IVE decisiveness -> decisive
(m>0) FULNESS -> FUL hopefulness -> hopeful
(m>0) OUSNESS -> OUS callousness -> callous
(m>0) ALITI -> AL formaliti -> formal
(m>0) IVITI -> IVE sensitiviti -> sensitive
(m>0) BILITI -> BLE sensibiliti -> sensible
Тест для строки S1 можно делать быстро, проверяя предпоследнюю букву слова, которое тестируется.
Шаг 3
(m>0) ICATE -> IC triplicate -> triplic
(m>0) ATIVE -> formative -> form
(m>0) ALIZE -> AL formalize -> formal
(m>0) ICITI -> IC electriciti -> electric
(m>0) ICAL -> IC electrical -> electric
(m>0) FUL -> hopeful -> hope
(m>0) NESS -> goodness -> good
Шаг 4
(m>1) AL -> revival -> reviv
(m>1) ANCE -> allowance -> allow
(m>1) ENCE -> inference -> infer
(m>1) ER -> airliner -> airlin
(m>1) IC -> gyroscopic -> gyroscop
(m>1) ABLE -> adjustable -> adjust
(m>1) IBLE -> defensible -> defens
(m>1) ANT -> irritant -> irrit
(m>1) EMENT -> replacement -> replac
(m>1) MENT -> adjustment -> adjust
(m>1) ENT -> dependent -> depend
(m>1 and (*S or *T)) ION -> adoption -> adopt
(m>1) OU -> homologou -> homolog
(m>1) ISM -> communism -> commun
(m>1) ATE -> activate -> activ
(m>1) ITI -> angulariti -> angular
(m>1) OUS -> homologous -> homolog
(m>1) IVE -> effective -> effect
(m>1) IZE -> bowdlerize -> bowdler
Теперь суффиксы удалены и осталось прибраться
Шаг 5а
(m>1) E -> probate -> probat
rate -> rate
(m=1 and not *o) E -> cease -> ceas
Шаг 5б
(m > 1 and *d and *L) -> single letter
controll -> control
roll -> roll
Алгоритм достаточно осторожен, чтобы не удалять суффикс, когда основа слишком короткая; нет никаких лингвистических оснований делать именно так. Значение меры m может быть использовано достаточно эффективно, чтобы помочь решить, стоит ли отбрасывать суффикс. К примеру в следующих двух списках:
list A list B
------ ------
RELATE DERIVATE
PROBATE ACTIVATE
CONFLATE DEMONSTRATE
PIRATE NECESSITATE
PRELATE RENOVATE
-ATE удален из списка B, но не из списка A. Это означает, что пары DERIVATE/DERIVE, ACTIVATE/ACTIVE, DEMONSTRATE/DEMONSTRABLE, NECESSITATE/NECESSITOUS, будут обьединены. То, что не предпринимается никаких попыток для определения префиксов, может сделать результат весьма противоречивым. Так, PRELATE не теряет -ATE, но ARCHPRELATE становится ARCHPREL. Но на практике это не имеет большого значения
Сложные суффиксы удаляются по частям в разных шагах. Так GENERALIZATIONS обрезается до GENERALIZATION (Шаг 1), затем к GENERALIZE (Шаг 2), дальше к GENERAL (Шаг 3) и затем до GENER (Шаг 4). OSCILLATORS обрезается до OSCILLATOR (Шаг 1), потом до OSCILLATE (Шаг 2), до OSCILL (Шаг 4) и в конце концов до OSCIL (Шаг 5). В словаре из 10,000 слов уменьшение размера стемов по шагам выглядит так:
------------------------------------------------
Количество слов, урезанных на шаге 1: 3597
" 2: 766
" 3: 327
" 4: 2424
" 5: 1373
Количество не обрезанных слов: 3650
Результирующий словарь стемов содержит 6370 записей, таким образом процесс стемминга уменьшил размер словаря примерно на треть.
Комментариев нет:
Отправить комментарий