Wednesday, December 15, 2010

Стеммер Портера для русского языка

Выделение основы слова это одна из задач, часто возникающая в процессе обработки текста. В школе нас конечно учили это делать, кто-нибудь помнит как? Я нет. К тому же, русский язык обладает особой сложностью и если в английском достаточно сделать несколько простых преобразований (вроде удаления ing-ового окончания) и мы уже с высокой степенью достоверности получаем требуемую основу. В русском языке эта задача намного сложней. В идеале, она решается путем составления больших морфологических словарей. Но это не путь ленивого программиста, словари надо поддерживать, ведь язык постоянно меняется, надо отдельно обрабатывать ошибки и опечатки. Путь ленивого программиста другой, специально для них, Мартин Портер в 1980 году изобрел алгоритм стемминга.

Главный плюс стеммера Портера заключается в том, что он не использует никаких словарей и выделение основы осуществляется путем преобразования слова согласно определенным правилам. В интернете полно реализаций этого алгоритма, в том числе и для Java, но, к сожалению, мне не удалось найти реализацию которая прошла бы тест самого Портера (внимание, большой документ) и в то же время сохраняла краткость и лаконичность. Поэтому, пришлось писать велосипед основываясь на PHP версии взятой здесь

Нет смысла переписывать описание алгоритма, оно, пусть и на английском, детально изложено на сайте самого Мартина Портера

Исходники на Java:
import java.util.regex.Matcher;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Porter {

    private static final Pattern PERFECTIVEGROUND = Pattern.compile("((ив|ивши|ившись|ыв|ывши|ывшись)|((?<=[ая])(в|вши|вшись)))$");

    private static final Pattern REFLEXIVE = Pattern.compile("(с[яь])$");

    private static final Pattern ADJECTIVE = Pattern.compile("(ее|ие|ые|ое|ими|ыми|ей|ий|ый|ой|ем|им|ым|ом|его|ого|ему|ому|их|ых|ую|юю|ая|яя|ою|ею)$");

    private static final Pattern PARTICIPLE = Pattern.compile("((ивш|ывш|ующ)|((?<=[ая])(ем|нн|вш|ющ|щ)))$");

    private static final Pattern VERB = Pattern.compile("((ила|ыла|ена|ейте|уйте|ите|или|ыли|ей|уй|ил|ыл|им|ым|ен|ило|ыло|ено|ят|ует|уют|ит|ыт|ены|ить|ыть|ишь|ую|ю)|((?<=[ая])(ла|на|ете|йте|ли|й|л|ем|н|ло|но|ет|ют|ны|ть|ешь|нно)))$");

    private static final Pattern NOUN = Pattern.compile("(а|ев|ов|ие|ье|е|иями|ями|ами|еи|ии|и|ией|ей|ой|ий|й|иям|ям|ием|ем|ам|ом|о|у|ах|иях|ях|ы|ь|ию|ью|ю|ия|ья|я)$");

    private static final Pattern RVRE = Pattern.compile("^(.*?[аеиоуыэюя])(.*)$");

    private static final Pattern DERIVATIONAL = Pattern.compile(".*[^аеиоуыэюя]+[аеиоуыэюя].*ость?$");

    private static final Pattern DER = Pattern.compile("ость?$");

    private static final Pattern SUPERLATIVE = Pattern.compile("(ейше|ейш)$");

    private static final Pattern I = Pattern.compile("и$");
    private static final Pattern P = Pattern.compile("ь$");
    private static final Pattern NN = Pattern.compile("нн$");

    public String stem(String word) {
        word = word.toLowerCase();
        word = word.replace('ё', 'е');
        Matcher m = RVRE.matcher(word);
        if (m.matches()) {
            String pre = m.group(1);
            String rv = m.group(2);
            String temp = PERFECTIVEGROUND.matcher(rv).replaceFirst("");
            if (temp.equals(rv)) {
                rv = REFLEXIVE.matcher(rv).replaceFirst("");
                temp = ADJECTIVE.matcher(rv).replaceFirst("");
                if (!temp.equals(rv)) {
                    rv = temp;
                    rv = PARTICIPLE.matcher(rv).replaceFirst("");
                } else {
                    temp = VERB.matcher(rv).replaceFirst("");
                    if (temp.equals(rv)) {
                        rv = NOUN.matcher(rv).replaceFirst("");
                    } else {
                        rv = temp;
                    }
                }

            } else {
                rv = temp;
            }

            rv = I.matcher(rv).replaceFirst("");

            if (DERIVATIONAL.matcher(rv).matches()) {
                rv = DER.matcher(rv).replaceFirst("");
            }

            temp = P.matcher(rv).replaceFirst("");
            if (temp.equals(rv)) {
                rv = SUPERLATIVE.matcher(rv).replaceFirst("");
                rv = NN.matcher(rv).replaceFirst("н");
            }else{
                rv = temp;
            }
            word = pre + rv;

        }

        return word;
    }

}


Для желающих протестировать, волшебная кнопка:



17 comments:

  1. Добрый день!

    Тест "самого Портера" проходит?

    ReplyDelete
  2. Добрый!

    Да, проходит.

    ReplyDelete
  3. Спасибо, очень помог алгоритм)

    ReplyDelete
  4. А разве алгоритм Стеммер Портера не должен и приставки убирать?

    ReplyDelete
  5. К сожалению, стеммер Портера удаляет только окончания и суффиксы. Приставки это совсем другая тема.

    ReplyDelete
  6. Хмм... Я ввел слово "корреляция" и в качестве результата мне выдало "корреляц", хотя неизменяемая часть слова тут "коррел".
    Пример:
    - корреляция
    - коррелирует

    ReplyDelete
  7. Это не единственное ограничение, не стоит ожидать от такого простого алгоритма 100% правильного выделения основы слова для такого сложного языка как русский.

    ReplyDelete
  8. а если б еще работал - цены б ему не было )))))))))))

    ReplyDelete
  9. а вот чтоб работал, нечего код на пхп бездумно тырить, регулярки поправь, а то хрен тебе оно на java заработает.

    ReplyDelete
  10. Спасибо и вам, Анонимус, за содержательный комментарий. К сожалению стремление blogger.com эскейпить энтити в HTML тэгах не всегда позволяют выкладывать работающий код.

    ReplyDelete
  11. длинношеее)

    ReplyDelete
  12. Добрый день,

    А не подскажешь, существуют ли какие-то более продвинутые алгоритмы выделения основы слов для русского языка?

    ReplyDelete
  13. Да, и еще вопрос по самому алгоритму. А зачем он сначала первый слог отрезает?

    ReplyDelete
  14. Чо то он и суффиксы не убирает.

    ReplyDelete
  15. Вы читать умеете? Выделяет основу слова. Основа слова - это приставки, корни, суффиксы; слово без окончания.

    ReplyDelete
  16. Если вдруг кому пригодится, вот на python реализацию портировал: https://gist.github.com/Kein1945/9111512

    ReplyDelete
  17. А я портировал на C++: http://manunich.blogspot.ru/2016/01/c-cpp.html

    ReplyDelete