5

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

例如（注意：虽然示例是用英语给出的，但我并没有为英语构建词形还原器）：

词语： 禁止

引理形式：禁止

后缀：ing

引理：禁止

我的解决方案：

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

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

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

2）对于每个匹配的后缀，从字典中搜索引理形式。如果 lemmaform 存在，则返回 wordtypes。

3) 最后，程序尝试与步骤 1) 和 2) 中产生的词型相交，如果相交成功，则返回该词的引理。

我的问题：从速度的角度来看，我的问题是否有更好的解决方案？（忽略在字典中保留常用词和引理的选项）帮助很大。

4

2 回答 2

6

这将是有限状态传感器的一个很好的应用。为什么？因为它们允许您有效地进行字符串重写（在时间上与输入的大小成线性关系）。考虑以下简单的换能器：

在此处输入图像描述

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

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

于 2012-03-23T17:49:00.633 回答
2

考虑使用一个非确定性的 trie 自动机，涵盖所有已识别的后缀，但向后分析单词。非确定性意味着机器可以同时处于多个状态，并且如果这些状态中的任何一个处于接受状态，则整个机器都处于接受状态。

初始状态将是一个接受状态，因此它不能识别任何后缀（如英语中的be）。从初始状态开始，transitions , 和()example('e', 'z', 'i')都会到达接受状态，使用 NFA 时您不必担心 s 冲突。('e', 'd', 'a')('e', 'v', 'o')'e'

从初始状态开始，每个单词的“字符”都被反向输入。每次机器进入接受状态时，都会在 your 中查找单词的剩余部分lemmaformdict并保留所有结果。然后继续处理，直到机器的状态为空（不仅仅是不接受）。

在这一点上，沿途指示的所有引理选择导致从上下文中删除的单词的可能解释（并且应该始终是一个小数字）。

实施 NFA 的具体方式将决定性能。NFA 可以在构建后转换为 DFA，因此机器在任何给定时间都只有一个状态，这样可以提高性能而不会使机器的构造复杂化。不利的一面是，您必须在单个字符级别上处理输入，这对于 Python 可能会降低性能。（但如果性能如此珍贵，也许你应该切换到 C++。）

于 2012-03-23T19:39:43.920 回答