Сборка лемматизатора: оптимизация скорости

Я строю лемматизатор на питоне. Поскольку мне нужно, чтобы он работал в реальном времени / обрабатывал довольно большой объем данных, скорость обработки имеет существенное значение. Данные: у меня есть все возможные суффиксы, связанные со всеми типами слов, с которыми они могут сочетаться. Кроме того, у меня есть лемма-формы, которые связаны как с их типами слов, так и с леммами. Программа берет слово на вход и выводит свою лемму. слово = лемма + суффикс

Например (Примечание: хотя пример приведен на английском языке, я не создаю лемматизатор для английского языка):

слово: запрещающий

лемма: запрещено

суффикс: ing

лемма: запретить

Мое решение:

Я преобразовал данные в (вложенные) словари:

suffixdict : {suffix1:[type1,type2, ... , type(n)], suffix2:[type1,type2, ... ,
type(n)]}    
lemmaformdict : {lemmaform:{type1:lemma}}

1) Найдите все возможные суффиксы и типы слов, с которыми они связаны. Если самый длинный суффикс составляет 3 символа, программа пытается сопоставить 'ing', 'ng', 'n' с ключами в суффиксе. Если ключ существует, он возвращает значение (набор типов слов).

2) Для каждого совпадающего суффикса найдите лемму из словаря. Если леммаформа существует, она возвращает типы слов.

3) Наконец, программа пытается пересечь типы слов, созданные на шагах 1) и 2), и, если пересечение было успешным, она возвращает лемму слова.

Мой вопрос: есть ли лучшее решение моей проблемы с точки зрения скорости? (Не обращая внимания на возможность хранить частые слова и леммы в словаре) Помощь очень полезна.


python nlp optimization lemmatization
person root    schedule 23.03.2012    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Это было бы прекрасным приложением для преобразователей конечного состояния. Почему? Потому что они позволяют эффективно переписывать строки (во времени, линейном в зависимости от размера ввода). Рассмотрим следующий датчик:

введите описание изображения здесь

Он принимает строку в качестве входных данных и проверяет, существует ли путь от начального состояния (здесь 0) до конечного состояния (10, 12 и 17, соответственно) с учетом последовательности входных символов. Если он достигает конечного состояния, он производит соответствующий вывод, например (запретить, инг), если вход был «запрещающим».

Однако я не знаю, есть ли у вас какой-либо опыт работы с конечными автоматами. Если нет, попробуйте - это того стоит. :) Попытки - это особый вид конечного автомата (пример преобразователя выше - это дерево) , так что они могут стать хорошим началом.

person jena    schedule 23.03.2012
comment
(Простите, д) плохое качество изображения ... Есть ли способ его улучшить? - person jena; 23.03.2012
comment
+1: Спасибо за идею. У меня нет предыдущего опыта работы с FST, но я обязательно попробую. - person root; 25.03.2012

arrow_upward
2
arrow_downward

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

Начальное состояние будет состоянием принятия, поэтому оно не сможет распознать суффикс (как в английском be). Из начального состояния переходы (), ('e', 'z', 'i'), ('e', 'd', 'a') и ('e', 'v', 'o'), например, все будут приходить в принимающие состояния, и вам не нужно беспокоиться о конфликтующих 'e' при использовании NFA.

Из начального состояния «символы» каждого слова вводятся в обратном направлении. Каждый раз, когда машина переходит в состояние принятия, оставшаяся часть слова просматривается в вашем lemmaformdict, и все результаты сохраняются. Затем обработка продолжается до тех пор, пока состояние машины не станет нулевым (а не просто непринятием).

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

От того, как вы реализуете NFA, зависит производительность. После создания NFA можно преобразовать в DFA, чтобы машина имела только одно состояние в любой момент времени, что может улучшить производительность, не усложняя конструкцию машины. С другой стороны, вы должны работать с вводом на уровне отдельного символа, что для Python может стоить вам производительности. (Но если производительность это дорого, возможно, вам стоит перейти на C ++.)

person wberry    schedule 23.03.2012