Построение лемматизатора: оптимизация скорости

Question

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

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

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

леммаформ: запрет

суффикс: ing

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

Мое решение:

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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