字符串的映射特性是否有助于更快地解析字符串？

Question

我正在制作一本词汇词典，它将帮助我根据语音学和字形学来查找英语单词。这本词典将帮助我找到我需要教孩子的英语单词的具体例子。

为此，我制作了一个大的Python字典，它有大约200000个单词键，其中的值是它们的语音。

为了查找单词，例如，带有最后一个-aK*e图形素的单词，其中K*将是任意数量的辅音，我可以用正则表达式解析所有的键。

然而，我认为，实际上将单词映射为在网格中编写会更聪明一些。因此，我可以“书签”所有的单词，其最后的字母是一个-e等等。因此，当我查找单词时，我可以简单地调用这些书签，并确保每次都会减少要解析的字数，就像上面的例子一样。

我的策略真的有意义吗？还是使用正则表达式来解决这个问题？

我几乎没有时间去编程，在我花宝贵的时间打字之前，我想要一些专家的建议。谢谢。

Answer 1

的确，tries使回答这些查询的速度更快、效率更高。现在还不清楚你是从单词的末尾还是从一开始就在搜索，但是如果这两者都有一点，那么你必须为这两个方向构建尝试。如果你需要在中间找到匹配物，那么两种方法都不会有帮助。

反向索引(比如那些为搜索引擎提供动力的索引)有时可以通过将单词存储为字符N克，然后存储n-克之间的连接信息来构造单词来解决这一问题。例如，“溢出”可能被分解为“some”、“rfl”和“ow”，并且在某个地方存在一些元数据，指出有一个单词将这三个n-克组合在一起。以不同的方式拆分每个单词可以引导和跟踪通配符查询，尽管我对细节有些模糊:-/

或认为，除非性能对此应用程序非常重要，否则对于这种字典大小，使用正则表达式的速度可能足够快(并且可能进一步优化)，而且非常简单。使用80k字词典进行的快速和肮脏的测试：

with open('dictionary.txt') as fin:
    words = fin.read().strip().split('\n')

import re
import time
expr = re.compile(r'a[^aeiouy]+e$', re.I)

# Of course, this extends easily to using a dictionary, too
def bench():
    start = -time.time()
    matches = [word for word in words if expr.search(word)]
    return start + time.time()

在我的电脑上，它大约需要50‘s，为了简单明了地使用正则表达式和有限的时间，我认为这是值得的。