构建一个词形还原器：速度优化

Question

我在使用Python编写一个词形还原器。由于需要实现实时运行/处理大量数据，因此处理速度至关重要。 数据：我拥有所有可能的后缀，这些后缀与它们可以结合的所有词类相连。此外，我还有与它们的词类和词元形式相关联的词元表格。该程序以单词作为输入并输出其词元形式。 单词=词元表格+后缀

例如（注意：虽然例子是用英语给出的，但我不是在编写英语的词形还原器）：

单词：forbidding

词元表格：forbidd

后缀：ing

词元：forbid

我的解决方案：

我已将数据转换为（嵌套）字典：

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

1) 找到所有可能的后缀以及它们连接到的单词类型。如果最长可能的后缀长度为 3 个字符，则程序会尝试将 'ing'、'ng' 和 'n' 与 suffixdict 中的键进行匹配。如果存在该键，则返回一个值（一组单词类型）。

2) 对于每个匹配的后缀，在字典中搜索 lemmaform。如果 lemmaform 存在，则返回单词类型。

3) 最后，程序尝试交集步骤 1 和步骤 2 生成的单词类型，如果交集成功，则返回单词的词源。

我的问题是：从速度的角度来看，是否有更好的解决方案？（不考虑在字典中保留常见的单词和词源选项）非常感谢您的帮助。

- root

Answer 1

这将是有限状态转换器的绝佳应用。为什么？因为它们可以让您高效地进行字符串重写（时间复杂度与输入大小成线性关系）。考虑以下示例转换器：

它接受一个字符串作为输入，并检查是否存在从初始状态（此处为0）到终态（分别为10、12和17）的路径，给定输入字符序列。如果到达终态，则生成相应的输出，例如（禁止，ing），如果输入是“forbidding”。我不知道你是否有任何有限状态自动机的背景，如果没有，请尝试一下-这将是值得的努力。:) Tries 是一种特殊的有限状态自动机（上面的样本转换器是一个trie），因此它们可能是一个很好的开始。

- jena

---

对不起，这张图片的质量很差... 有没有办法可以提升一下？ - jena

+1：谢谢你的建议。我之前没有使用过FST，但我一定会尝试一下。 - root

Answer 2

考虑使用一个覆盖所有识别后缀的非确定性trie自动机，但是要倒序分析单词。非确定性意味着机器可以同时处于多个状态，并且整个机器在任何一个接受状态时都是接受状态。

初始状态将是一个接受状态，因此它可以识别没有后缀的单词（例如英语中的 be）。从初始状态开始，转换()，('e'，'z'，'i')，('e'，'d'，'a')和('e'，'v'，'o')等都会到达接受状态，而使用NFA时不必担心冲突的'e'。

从初始状态开始，每个单词的“字符”都是倒序输入的。每当机器进入一个接受状态时，剩余部分的单词将在您的lemmaformdict中查找，并保留所有结果。然后继续处理，直到机器的状态为null（不仅仅是非接受状态）。

在那一点上，沿途指示的词形总选择次数导致了从上下文中移除的该单词的可能解释（而这应该始终是一个很小的数字）。

如何实现NFA将决定性能。 NFA可以转换为DFA一旦构建完成，因此该机器在任何给定时间只有一个状态，这可能有助于提高性能而不会使机器的构造复杂化。 不利的一面是，您必须在单个字符级别上处理输入，这可能会影响Python的性能。（但如果性能非常宝贵，也许你应该转到C ++。）

- wberry