Русская морфология основанная на памяти

Один из перспективных подходов в машинном обучении базируется на запоминании уже разобранных примеров и поиске похожего образца. Например, у нас уже есть коллекция расшифрованных аудиозаписей, и если появляется новый звуковой файл, мы ищем похожий образец и на его основе строим распознавание. Рассмотрим, как базируясь на этом принципе, можно построить морфологию русского языка.




В большинстве случаев словоформа образуется за счет изменения суффикса слова. При этом в простейшем случае правило, согласно которому будет определяться нормальная форма, задается тройкой (n,newsuffix,morphinfo),
где

• n - длина суффикса, который нужно отбросить;
• newsuffix - новый суффикс, добавление которого даст нормальную форму;
• morphinfo - морфологическая информация (например, падеж, род и т.д.).

Например, для слова “люди” правило будет иметь следующий вид - (4,”человек”,”существительное, мужского рода, в именительном падеже, множественного числа”). В том случае, если у слова может быть несколько нормальных словоформ (вина -> вино, вина), правило будет состоять из нескольких троек. Примеры, когда словоформа образуется еще и с помощью префикса, мы рассматривать не будем. Во основном, это касается прилагательных в превосходной степени, которые, в принципе, могут трактоваться как отдельное слово (например, “наилучший”, “наибольший”). Установив такое правило для каждого слова, мы легко можем получить нормальную словоформу.



Словарь с проекта AOT содержит около 5 миллионов словоформ, по которым строится порядка 30 тысяч правил для определения нормальной формы слова. Собственно, это и есть те самые обработанные результаты, столь необходимые для построения нашего алгоритма. При этом на первый взгляд кажется, что для нахождения нужного правила необходимо хранить все 5 миллионов словоформ. В действительности это не так.



Попробуем построить эвристику для нахождения нормальной формы слова, которая в тоже время поможет уменьшить количество хранимой информации. Для этого будем использовать следующую закономерность: чем более длинный общий суффикс имеют два слова, тем с большей вероятностью у них будет одинаковое правило для формирования нормальной формы.



Поступим следующим образом: отсортируем все словоформы в лексографическом порядке перевернутых слов. Например, для слов а, оружие, сторона, море верным будет такой порядок: а, сторона, оружие, море. Мы получаем следующую закономерность: слова, находящиеся после сортировки рядом, будут с большей вероятностью иметь одинаковое правило. Теперь удалим из нашего списка все слова, правила которых совпадают с правилом предшествующего ему слова. В нашем распоряжении останется около 500 тысяч слов, то есть мы смогли сократить объем хранимой информации в 10 раз. Таким образом, чтобы получить нормальную словоформу для какого-либо слова, нам необходимо найти наибольшее слово из оставшегося списка, не превосходящее данное и применить правило от него. Данный алгоритм будет корректно работать для всех слов из словаря и даст хорошую эвристику для незнакомых примеров. Этот подход может быть использован и для добавления поддержки русского языка в lucene.



Также для уменьшения объема занимаемой информации мы можем произвести дополнительное кодирование, при котором шесть подряд идущих букв представляются как 32-хбитный int. Таким образом, список образцов, по которым производится поиск нужного правила, представляется как двухмерный массив чисел, в котором одна строка соответствует одному слову. Для нахождения нужного образца необходимо использовать бинарный поиск. Скорость данного алгоритма составляет порядка 200 тысяч слов в секунду. Кроме того, возможны дальнейшие улучшения: например, использование префиксного дерева для хранения и поиска информации. Но это уже тема для следующего разговора.

Коммуникация расширений и веб страницы в Firefox.

Большинство расширений для firefox на целены на изменение веб страниц, убрать рекламу, добавить новый функционал. Как у разработчиков проблем с этим не возникает, до странице легко добраться из расширение. Иногда возникает обратная ситуация. Не обходимо, что после некоторых операций пользователя на странице данные были переданы в плагин. Напрямую этого сделать нельзя по причинам безопасности. Но есть способы как это можно сделать. В это статье мы рассмотрим каким образом организовать взаимодействие плагина и станице в обе стороны.

От расширения к веб-странице

Как правило после того станица загружена взаимодействие плагина со страницей сводиться к выполнению некоторого скрипта на ней. В самом простом случае можно создать нужный нам скрипт непосредственно на странице. Вот как это можно сделать для текущего странице в браузере:

var browser = gBrowser.selectedTab.linkedBrowser;
var document = browser.contentDocument;
var script = document.createElement("script");
script.type = "text/javascript";
script.innerHTML = "alert('Hello word!')";
document.body.appendChild(script);



Однако при реализации более сложного взаимодействия, могут возникнуть некоторые трудности c обработкой исключений, передачей параметров. Что бы их избежать нужно создать специальный div или другой элемент на странице, повесить на него обработчик событий отвечающий за выполнения скриптов на странице.

var element = document.getElementById("_console");
if (!element)
{
   element = document.createElement("div");
   element.setAttribute("id", "_console");
   element.setAttribute("style", "display:none");
   document.documentElement.appendChild(element);
}
element.addEventListener("runCommandEvent", function(event)
   {
      var element = event.target;
      var expr = JSON.parse(element.getAttribute("expr"));
      var data = element.getAttribute("data");
      evaluate(expr, data);
   }, true);

Что бы что, то выполнить на странице потребуется создать событие и предать необходимые данные

var document = tabBrowser.contentDocument;
var event = document.createEvent("Events");
event.initEvent("runCommandEvent", true, false);
var element = document.getElementById("_console");
element.setAttribute("expr", src);
element.setAttribute("data", JSON.strinfigy(data));
element.dispatchEvent(event);

Что бы данные корректно передались на станицу необходимо их стерилизовать в строку, из которого они потом будут восстановлены. Начиная с Firefox 3.5 это легко сделать с помощью встроенной поддержки JSON.

За исполнения скрипта отвечает функция evaluate в которой и происходит обработка исключений. Так же в контексте выполнения будет доступна переменная data c нужной информацией:

{
  try
  {
     var result = window.eval(expr);     
   }
   catch(exc)
   {
      var result = exc;
      result.source = expr;
   }
}

Этот способ предпочтителен для реализации сложного взаимодействия, тогда как в простых случаях достаточно ограничиться созданием нового скрипта на веб странице.

От страницы к расширению

Передавать что либо из веб странице в расширение удобно так же при помощи событий. Создадим обработчик для них

var browser = gBrowser.selectedTab.linkedBrowser;
var document = tabBrowser.contentDocument;
document.addEventListener("eventFromPage", eventListener, false, true);

Теперь необходимо создать событие. Данные помещаются в поле объекта document. Здесь так же проще передавать уже сереализованные данные.

var event = document.createEvent("Events");
event.initEvent("eventFromPage", true, false);
document._dataForExtension = JSON.stringify(someData);
document.dispatchEvent(event);

Следующий шаг - обработать событие и полученные данные. Если мы будем обращаться напрямую к полю _dataForExtension оно не будет доступно по соображением безопасности. Любой дом объект странице при доступе к нему из расширения обертывается в прокси. Получить доступ до полей объекта можно через wrappedJSObject. Таким образом обработчик событий получается следующим.

eventListener: function(event)
{
  var document = tabBrowser.contentDocument;
  var data = JSON.parse(document.wrappedJSObject._dataForExtension);
  callbackFromSrcipt(data);
}

Пару слов напоследок. При реализации данного подхода надо внимательно следить за тем, что бы обработчик был создан до того, как в его адрес начнут поступать события. К сожалению, это условие не всегда просто гарантировать.

Maven release plugin и svn

Вчера выкладывая новую версию русской морфологии, я наткнулся на невозможность выполнить нормально команду release:prepare. Постоянно получал ошибку

[INFO] Unable to tag SCM
Provider message:
The svn tag command failed.
Command output:
svn: Commit failed (details follow):
svn: File '/svn/tags/morphology-0.7/morph/pom.xml' already exists

Хотя файла morphology-0.7/morph/pom.xml не в svn, не у меня на диске негде не было. После нескольких десятков минут, выяснилось, что это баг в subversions, и лечится он следующим образом: после получения этой ошибки выполнить команду svn update, а затем снова mvn release:prepare.

Модификация байт-кода виртуальной машины Java

Данный пост является продолжением статьи о байт-коде виртуальной машины Java, и мы считаем, что читатель имеет представление о его структуре. Наиболее распространенной библиотекой для модификации байт-кода является фрейморк ASM от object web. На нем построено большинство высокоуровневых библиотек, в частности cglib.

Библиотека ASM имеет два варианта API. Что бы лучше представить отличие между ними, проведем следующую аналогию. Класса это некое дерево. Корень его- сам класс. Переменные, методы, подклассы это листья его листья. Инструкции - листья методов. Таким образом можно провести параллель с XML и двумя типами его парсеров. Первый вариант Core API похож на SAX парсер. Когда нужно прочитать, создать или внести изменения, делается обход дерева представления класса. Второй вариант (Tree API) работает по прицепу DOM парсера. Сначала строиться дерево представления, а затем с ним производиться необходимые манипуляции. Очевидно, что первый вариант API менее ресурсоемкий, более подходящей для внесения небольших изменений. Второй требует больше ресурсов, но и дает более гибкие возможности. Мы рассмотрим только первый вариант API.



Что бы создать класса с помощью Core API, нужно обойти дерево его представления. Рассмотрим более конкретный пример. Мы хоти профилировать следующий класс

public class Example {

    public void run(String name) {
        try {
            Thread.sleep(5);
            System.out.println("Currennt time is " + new Date(System.currentTimeMillis()));
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println(name);
    }

}

Например получать информацию о времени выполнения метода run. Для этого создадим наследника.

public class Test extends Example {

    @Override
    public void run(String name)  {
        long l = System.currentTimeMillis();
        super.run(name);
        System.out.println((System.currentTimeMillis() - l));
    }
}

А вот как можно создать его используя ASM.

ClassWriter cw = new ClassWriter(ClassWriter.COMPUTE_MAXS);
cw.visit(Opcodes.V1_5, Opcodes.ACC_PUBLIC, "org/Test", null, "org/example/Example", null);
cw.visitField(Opcodes.ACC_PRIVATE, "name", "Ljava/lang/String;",null, null).visitEnd();


MethodVisitor methodVisitor = cw.visitMethod(Opcodes.ACC_PUBLIC, "<init>", "()V", null, null);
methodVisitor.visitCode();
methodVisitor.visitVarInsn(Opcodes.ALOAD, 0);
methodVisitor.visitMethodInsn(Opcodes.INVOKESPECIAL, "org/example/Example", "<init>", "()V");
methodVisitor.visitInsn(Opcodes.RETURN);
methodVisitor.visitMaxs(1, 1);
methodVisitor.visitEnd();

methodVisitor = cw.visitMethod(Opcodes.ACC_PUBLIC, "run", "(Ljava/lang/String;)V", null, null);
methodVisitor.visitCode();
methodVisitor.visitMethodInsn(Opcodes.INVOKESTATIC, "java/lang/System", "currentTimeMillis", "()J");
methodVisitor.visitVarInsn(Opcodes.LSTORE, 2);
methodVisitor.visitVarInsn(Opcodes.ALOAD, 0);
methodVisitor.visitVarInsn(Opcodes.ALOAD, 1);
methodVisitor.visitMethodInsn(Opcodes.INVOKESPECIAL, "org/example/Example", "run", "(Ljava/lang/String;)V");
methodVisitor.visitFieldInsn(Opcodes.GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
methodVisitor.visitMethodInsn(Opcodes.INVOKESTATIC, "java/lang/System", "currentTimeMillis", "()J");
methodVisitor.visitVarInsn(Opcodes.LLOAD, 2);
methodVisitor.visitInsn(Opcodes.LSUB);
methodVisitor.visitMethodInsn(Opcodes.INVOKEVIRTUAL, "java/io/PrintStream", "println", "(J)V");
methodVisitor.visitInsn(Opcodes.RETURN);
methodVisitor.visitMaxs(5, 4);
methodVisitor.visitEnd();

cw.visitEnd();
return cw.toByteArray();

Таким образом мы получили массив байт, в котором храниться структура нового класса. Теперь нам нужно это новый класс загрузить. Для этого понадобится свой ClassLoader, так как у стандартного метод по загрузке класса имеет модификатор protected.

class MyClassLoader extends ClassLoader {

    public Class defineClass(String name, byte[] b) {
        return defineClass(name, b, 0, b.length);
    }
}

А вот как это можно сделать

MyClassLoader myClassLoader = new MyClassLoader();
Class bClass = myClassLoader.defineClass("org.Test", Generator.getBytecodeForClass());

Constructor constructor = bClass.getConstructor();
Object o = constructor.newInstance();

Example e = (Example) o;
e.run("test");

Таким образом мы можем создать утилиту для быстрого профилирования, которая с помощью reflection получает информацию и используя ее создает нужный класс. По подобному прицепу строятся библиотеки реализующие AOP.

Рассмотрим другой пример. Допустим нам нужно протестировать класс, который вызывает System.currentTimeMillis(). Для этого нам достаточно научиться заменять вызов currentTimeMillis(), на вызов другого статического метода. Действуем так: читаем класс, обходя его дерево и где нужно изменяя вызов метода.


ClassReader cr = new ClassReader("org.example.Example");
ClassWriter cw = new ClassWriter(cr, ClassWriter.COMPUTE_MAXS);

ClassVisitor cv = new ReplaceStaticMethodClassAdapter(cw);
cr.accept(cv, ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES);

return cw.toByteArray();

//----------------------------------------------------------------------------


private static class ReplaceStaticMethodClassAdapter extends ClassAdapter{


    public RepaleStaticMethodClassAdapter(ClassVisitor classVisitor) {
        super(classVisitor);
    }

    @Override
    public MethodVisitor visitMethod(int i, String s, String s1, String s2, String[] strings) {
        return new RepalceStaticMethodAdapter(super.visitMethod(i, s, s1, s2, strings));
    }

    private class RepalceStaticMethodAdapter extends MethodAdapter{
        public RepalceStaticMethodAdapter(MethodVisitor methodVisitor) {
            super(methodVisitor);
        }

        @Override
        public void visitMethodInsn(int i, String s, String s1, String s2) {
            if(i == Opcodes.INVOKESTATIC &&  "java/lang/System".equals(s) && "currentTimeMillis".equals(s1) && "()J".equals(s2)){
                super.visitMethodInsn(Opcodes.INVOKESTATIC, "org/example/Generator", "myTime", "()J");
            }  else{
                super.visitMethodInsn(i, s, s1, s2);
            }
        }
    }
}

Загрузкой модифицированного класса имеет некоторые особенности. В jvm классы определяются не только своим именем, но и еще ClassLoader который был использован при его загрузки. Класс загруженный с помощью MyClassLoader будет иметь другой тип, чем тоже класс загруженный ClassLoder по умолчанию. Таким образом вызвать метод, нам понадобится использовать reflection.

MyClassLoader myClassLoader = new MyClassLoader();
Class aClass = myClassLoader.defineClass("org.example.Example", Generator.getModifedClass());
Constructor constructor = aClass.getConstructor();
Object o = constructor.newInstance();
Method method = aClass.getMethod("run", String.class);
method.invoke(o,"test");

Можно также загрузить оба класса Test и Example c помощью MyClassLoader, и если у класса Test вызывать метод run, то у класса Example будет вызывается измененный метод.

Работающий пример можно взять отсюда.

Структура байт-кода виртуальной машины Java

Платформы java имеется две особенности. Для обеспечения кроссплатформенности программа сначала компилируется в промежуточный язык низкого уровня - байт-код. Вторая особенность загрузка исполняемых классов происходит с помощью расширяемых classloader. Это механизм обеспечивает большую гибкость и позволяет модифицировать исполняемый код при загрузки, создавать и подгружать новые классы во время выполнения программы.

Такая техника широко применяется для реализации AOP, создания тестовых фреймворков, ORM. Особенно хочется отметить terracota, продукт с красивой идеей кластеризации jvm и на всю катушку использующей модификации байт-кода. Эта заметка будет посвящена обзору структуры байт-кода, первой части этой сильной связки.

Каждому классу в java соответствует один откомпилированный файл. Это справедливо даже для подклассов или анонимным классов. Такой файл содержит информацию об имени класса, его родители, список интерфейсов которые он реализует, перечисление его полей и методов. Важно отметить, что после компиляции информации которая содержит директива import теряется и все классы именуются теперь через полный путь. Например в место String будет записано java/lang/String.

Самое интересное как будут выглядеть методы класса в байт-коде. Будем наблюдать во, что трансформируется следующий класс:

package org;

class Test {
    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;

    }
}

Метод getName будет описываться в байт-коде следующим образом.

public getName()Ljava/lang/String;
ALOAD 0
GETFIELD org/Test name
ARETURN

Начнем с заголовка. В нем содержится информация о название метода то, что метод вызывается без параметров и тип возвращаемого аргумента.

Байт-кода стеко-ориентированный язык, похожий по своей структуре на ассемблер. Что бы произвести операции с данными их сначала нужно положит на стек. Мы хотим взять поле у объект. Что бы это сделять нужно его положить в стек. В байт-коде нет имен переменных, у них есть номера. Нулевой номер у ссылки на текущий объект или у переменой this. Потом идут параметры исполняемого метода. Затем остальные переменные.

Команда ALOAD 0 кладет переменную this на стек. Что бы на стек положить тип данных, отличный от ссылки нужно воспользоваться другой командой. Для long будет LLOAD, а для doubles[] будет DALOAD.

Следующая команда GETFIELD, убирает со стека ссылку на объект и кладет примитивный тип или ссылку на поле данного объекта. У нее есть два параметра. Первый имя класса, второй имя переменной. Если же переменная статическая, то предварительно класть на стек ничего не нужно, а команду нужно заменить на GETSTATIC с теме же параметрами.

Последняя команда говорит, что метод завершен и возвращает значения типа ссылки со стека.

Сеттер имеет немного более сложную структуру.

public setName(Ljava/lang/String;)V
ALOAD 0
ALOAD 1
PUTFIELD org/Test name
RETURN

Данный метод ничего не возвращает. Первые две команды кладут на стек переменную this и параметр исполняемого метода. Затем вызывается команда PUTFIELD (PUTSTATIC для статического поля) которая установит значение поля объекта и уберет со стека последние два значения. Последняя команда выход из метода.

Добавим к нашему объект еще пару методов и посмотрим какой байт-код им соответствует.

    public void forTest(Boolean b){
        System.out.prinln(b);

    }

    public Long testMethods(Collection<Long> testInterface){
        Long a = System.curretM();

        forTest(testInterface.contains(a));    
        return a;

    }

testMethod имеет следующие представление.

INVOKESTATIC java/lang/System currentTimeMillis ()J
LSTORE 2
ALOAD 0
ALOAD 1
LLOAD 2
INVOKESTATIC java/lang/Long valueOf (J)Ljava/lang/Long;
INVOKEINTERFACE java/util/Collection contains (Ljava/lang/Object;)Z
INVOKESTATIC java/lang/Boolean valueOf (Z)Ljava/lang/Boolean;
INVOKEVIRTUAL org/Test forTest (Ljava/lang/Boolean;)V
LLOAD 2
INVOKESTATIC java/lang/Long valueOf (J)Ljava/lang/Long;
ARETURN

Первая команда вызывает статический метод у класса System. Вторая запоминает результат вызова метода currentTimeMillis в переменной со вторым номером. Затем мы кладем переменную this, параметр метода и переменную с номером 2 на стек. Преобразую переменную к типу java/lang/Long. И проверяем, что она у нас содержится в коллекции, вызывая метод у параметра исполняемого. У нас параметр интерфейс, поэтому применяется команда INVOKEINTERFACE. Для метода класса необходимо использовать INVOKEVIRTUAL. Что бы вызвать метод у объект или интерфейса необходимо, что бы на стеке лежал объект, затем параметры вызываемого метода. В результате вызова метода они заменяться на результат или просто уберутся со стека, если метод ничего возвращает. Последняя три команды кладут перемену на стек, превращают ее в объект и возвращают ее как значение метода.


Что бы завершить наш экскурс в байт-код добавим последний метод и посмотрим на циклы и условные операторы.

    public void testAriphmentics(){
       int i = -17;

        while(i < 10){
            if(i < 0){

                i = i + 7;
            }
            i  = i*13;

        }
    }

Он в байт-коде будет выглядить так

ACC_FINAL -17
ISTORE 1
Label:L1466604866
ILOAD 1
ACC_FINAL 10
IF_ICMPGE L329949514
ILOAD 1
IFGE L658705244
ILOAD 1
ACC_FINAL 7
IADD
ISTORE 1
Label:L658705244
ILOAD 1
ACC_FINAL 13
IMUL
ISTORE 1
GOTO L1466604866
Label:L329949514
RETURN

Первые две команды инициализирую переменную i (с номером 1) значением -17.

Дальше у нас начинается тело цикла. Для реализации которого потребуются метки,
команда перехода и условный оператор. В теле нашего метода аж целых три меток. Первая метка означает начало цикла. Вторая нужна для условного оператора, а последняя знаменует конец цикла. Уловный оператор имеет один параметр метку перехода. Прежде чем его вызвать сравниваемы значения должны лежать на стеке. Для сравнения с нулем используется отдельная команда. Для каждого типа есть свой оператор сравнения. Для int он IF_ICMPGE. После сравнения сравниваемы значения убираются со стека. Для арифметических действий с двумя переменным их так же как и для условного оператора нужно предварительно положить на стек. После выполнения они снимаются со стека, а на их место кладется результат.

На это краткий экскурс в байт-код закончен, некоторые вопросы такие как исключения, синхронизация не были затронуты. Я надеюсь, что имея представление о байт коде читатель без труда справиться с ними. В следующей части мы рассмотрим инструменты которые применяются для модификации байт-кода.

Гибридная реализация русской морфологии.

При создание поисковых решение одним из первых с чем приходиться сталкивать разработчику это первоначальная обработка текста. Разбивка на термины, фильтрация стоп слов. Важной операцией влияющей на качество поиска на данном этапе является приведение слов к нормальной форме. Ниже приведены основные подходы к этой проблеме.

В простейшем случаем можно воспользаватся оператором усечения (стемминг), который откидывает окончания и оставляет основную форму слова. Наиболее популярным решением для английского языка является стеммер от Snawball. Он базируется на нескольких простых правилах. Например если s является последней буквой в слове, то ее можно отбросить. Вот пример его работы для английского языка:

comments -> comment
using -> use
stemming -> stem
received -> receiv
develops -> develop.

Хотя Snawball и поддерживает русский язык, но его применение не дает достаточно качественных результатов. Вот пример двух словоформы одного и того же слова для которых усечение происходить по разному:

отзыв -> отз
отзывы -> отзыв

Другой подход - хранить все пары (слово, нормальная форма). Минусы этого здесь очевидны. Если встречается не знакомое слово, то алгоритм для него не сработает. Другой минус вытекает из того, что современный словарь русского языка содержит больше полуторамиллиона словоформ. Все их нужно хранить и быстро осуществлять поиск среди них. Можно построить конечный автомат, для сокращения объема требуемой памяти и повышения скорости работы. Алгоритм для построения такого автомата приведен в статье [1]. Реализация на С++ доступна на сайте aot.ru. Данный алгоритм довольно сложный в реализации.

Можно использовать гибридный вариант стемминга и словарного подхода. В большинстве случаях нам будет достаточно знания нескольких последних букв слова для правильного определения его нормальной формы. Таким образом мы заменим пары (слово, нормальная форма) на (окончание слова, окончание нормально формы). В качестве окончания слова будем брать 7 последних букв слова. Тем самым решилась проблема отсутствия незнакомых слов в словаре. Ясно, что данный результат будет хуже чем словарный, но гораздо лучше чем результат стеммера. Для слова не более 7 букв слов алгоритм даст точный ответ. Он так же применяется в реализации морфологии от aot.ru в качестве эвристики для незнакомых слов. Отличие реализации в том, так же строиться конечный автомат как и для слов из словаря.

Рассмотрим вопрос о его сложности и требуемого объема памяти. В русском алфавите 33 буквы плюс в нужно еще учитывать, что в словах может встречаться дефис. Таким образом одна буква в слове кодируется числом от 0 до 33 и 64-битный тип данных (например long в java) может содержать в себе информацию об 7-12 буках. Этого вполне достаточно для наших целей. Для эксперимента возьмем словарь с сайта проекта aot.ru, распространяемый по лицензии LGPL 2.0. Он нам даст 750 тысяч уникальных пар (окончание слова, окончание нормально формы). Некоторые из пар будут иметь одинаковые окончания слов для которых требуется определить нормальную форму. Будем оставлять только одну — которая чаще встречается и подходит для более распространенных слов в русском языке. Так им образом у нас останется около 690 тысяч пар. В частности для более чем 600 тысячах случаях нормальная форма будет определять однозначно.

Нетрудно подсчитать, что данные необходимы для работы алгоритма будут занимать около 10.6 мегабайт. Нужного окончания можно будет найти с помощью бинарного поиска. (нужно около найти 20 сравнений). Длясравнения в алгоритме от aot.ru размер автомата без морфологической информации около 5 мегабайт. Для реализации эвристики по концу слова нужен еще один автомат, к сожалению его размер не приведен. Таким образом размер памяти сопоставим, а данная реализация дает не значительно худший результат при меньших затратах.

Реализация данного подхода была воплощена на java, так же был сделан Analayzer русского языка
для поискового фрейморка lucene. Она распространяется под apache 2.0 лицензии.

[1] Jan Daciuk, Bruce Watson, and Richard Watson, Incremental Construction of Minimal Acyclic Finite State Automata and Transducers, proceedings of Finite State Methods in Natural Language Processing, pp. 48-56, Bilkent University, Ankara, Turkey, June 29 - July 1, 1998.