Python:在大型字符串中查找部分字符串匹配

我对在Python中实现自动完成感兴趣.例如,当用户键入字符串时,我想在磁盘上显示名称以该字符串开头的文件子集.

什么是一种有效的算法来查找匹配大型语料库中某些条件的字符串(比如数十万个字符串)？就像是:

matches = [s for s in allfiles if s.startswith(input)]

我希望条件灵活; 例如.只要输入中的所有字母都以相同的顺序出现在s中,而不是严格的startwith,它就是匹配.什么比我在这里展示的蛮力方法更好？

对于精确匹配,通常实现这样的方法是将您的语料库存储在trie中.我们的想法是将每个字母存储为树中的节点,链接到单词中的下一个字母.找到匹配只是走在树上,并显示当前位置的所有孩子.例如."猫","牛"和"汽车"将存储为:

  a--t
 / \ 
c   r
 \
  o--w

当你获得交流时,你从c节点开始,a然后将你带到c/a节点(子节点"t"和"r",将cat和car作为你的完成).

请注意,您还需要标记完整单词的节点来处理作为其他子串的名称(例如"car"和"cart")

要获得所需的模糊匹配,您可能需要进行一些更改.