python - 构建词形还原器 : speed optimization

Question

我正在用 python 构建词形还原器。因为我需要它实时运行/处理相当大量的数据，所以处理速度 是最重要的。 数据:我有所有可能的后缀，这些后缀链接到它们可以组合的所有词类型。此外，我还有与其词型和引理相关联的引理形式。该程序将一个词作为输入并输出其引理。 词 = 词源 + 后缀

例如(注意:虽然这个例子是用英文给出的，但我并没有为英文构建词形还原器):

词:禁止

引理形式:禁止

后缀:ing

引理:禁止

我的解决方案:

我已将数据转换为(嵌套的)字典:

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

1) 找到所有可能的后缀和它们链接到的词类型。 如果最长可能的后缀是 3 个字符长，程序会尝试将 'ing'、'ng'、'n' 与 后缀。如果键存在，它会返回一个值(一组词类型)。

2) 对于每个匹配的后缀，从字典中搜索引理形式。 如果 lemmaform 存在，它返回词类型。

3) 最后，程序尝试对步骤 1) 和 2) 中生成的字型进行交集，如果交集是 成功它返回单词的引理。

我的问题:从速度的角度来看，我的问题是否有更好的解决方案？ (忽略在字典中保留常用词和词条的选项) 非常感谢帮助。

Answer 1

对于有限状态传感器来说，这将是一个绝妙的应用。为什么？因为它们允许您高效地进行字符串重写(时间与输入的大小成线性关系)。考虑以下简单的[ia]换能器:

它以一个字符串作为输入，并在给定输入字符序列的情况下检查是否存在从初始状态(此处为 0)到最终状态(分别为 10、12 和 17)的路径。如果它达到最终状态，它会产生适当的输出，例如(forbidd, ing) 如果输入是“forbidding”。

不过，我不知道您是否了解有限状态自动机。如果没有，请尝试一下 - 这将是值得的。 :) Tries是一种特殊的有限状态自动机(上面的示例转换器是一个 trie)，因此它们可能是一个好的开始。