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

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




В большинстве случаев словоформа образуется за счет изменения суффикса слова. При этом в простейшем случае правило, согласно которому будет определяться нормальная форма, задается тройкой (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);
}

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