用有向字图快速自动完成
fast-autocomplete的Python项目详细描述
快速自动完成0.4.3
使用有向字图（dwg）和levenshtein编辑距离快速自动完成。
结果通过LFU缓存（最不常用）。
为什么
阅读此处为何构建快速自动完成功能：http://zepworks.com/posts/you autocomplete me/
这个库是在我们得出结论，elasticsearch的自动完成提示程序不够快，没有做我们需要的所有事情时编写的：
- 一旦我们切换到快速自动完成，我们的平均延迟从120ms变为30ms，因此性能和错误的提高3-4倍降为零。
- elasticsearch的autocomplete suggester不处理您输入的任何单词组合。例如，当单词
2018，Toyota Camry，Los Angeles单独输入时，Fast AutoComplete可以处理洛杉矶的2018丰田凯美瑞。而elasticsearch的autocomplete则需要将整句话输入其中，才能在autocomplete结果中显示出来。
你可能会说：
- 关于1：是的，但您正在使用缓存。回答：嘘是的，保持安静。我们也在使用C库进行Levenshtein编辑距离，因此它也得到了改进。
- 关于2：酷。回答：好的，现在我们正在交谈。
如何
在这里阅读自动完成的速度：http://zepworks.com/posts/you autocomplete me/
简而言之，快速自动完成功能的作用是：
- 用您的文字填充DWG。
- 按图形节点的字母顺序排列，直到找到包含单词的节点。
- 在图形上找到单词后继续，直到到达叶节点。
- 再次从根节点重新启动，直到它到达图形中不存在的字母。
- 根据剩余单词的数量，返回所有被卡住的子单词
- 或者运行levenshtein edit distance来查找左边的结束词，然后从那里继续。
通过这样做，它可以标记文本，例如：
2018洛杉矶丰田凯美瑞进入[2018，丰田凯美瑞，进入，洛杉矶]
并在键入时返回自动完成结果。
安装
pip安装快速自动完成功能
注意：快速自动完成仅适用于Python3.6及更新版本。
你还在用python 2吗？升级时间。
许可证
麻省理工学院< /P>
DWG
我们在这个库中使用的数据结构称为dawg。
dwg代表有向字图。下面是一个基于测试中提供的"makes_models_short.csv"的示例dwg：
用法
首先让我们从数据开始。图书馆留给你如何准备数据。
示例1
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]
单词是字典，每个单词都有上下文。例如"count"，如何显示单词，单词周围的其他上下文等等。在这个示例中，单词没有任何上下文。
例2
假设我们有一个csv，其中包含来自车辆品牌和型号的以下内容：
make,model acura,zdx alfa romeo,4c alfa romeo,4c coupe alfa romeo,giulia bmw,1 series bmw,2 series 2007,2007 2017,2017 2018,2018
我们要做的是将其转换为一本词汇词典及其上下文。
importcsvfromfast_autocomplete.miscimportread_csv_gendefget_words(path):csv_gen=read_csv_gen(path,csv_func=csv.DictReader)words={}forlineincsv_gen:make=line['make']model=line['model']ifmake!=model:local_words=[model,'{} {}'.format(make,model)]whilelocal_words:word=local_words.pop()ifwordnotinwords:words[word]={}ifmakenotinwords:words[make]={}returnwords
read_csv_gen只是一个帮助函数。你真的不需要它。关键是我们要转换hat csv发送给如下所示的词典：
>>>words=get_words('path to the csv')>>>words{'acura zdx':{},'zdx':{},'acura':{},'alfa romeo 4c':{},'4c':{},'alfa romeo':{},'alfa romeo 4c coupe':{},'4c coupe':{},'alfa romeo giulia':{},'giulia':{},'bmw 1 series':{},'1 series':{},'bmw':{},'bmw 2 series':{},'2 series':{},'2007':{},'2017':{},'2018':{}}
这是一本符合上下文的词典。我们已经决定不需要为本例中的单词设置任何上下文，因此所有上下文都是空的。不过，一般来说，你会想要一些更复杂的逻辑词周围的上下文。上下文用于将单词"keys"转换为它们的上下文，这是单词词典中键的值。
除了单词，我们通常还需要一本同义词词典。像这样：
synonyms={"alfa romeo":["alfa"],"bmw":["beemer","bimmer"],"mercedes-benz":["mercedes","benz"],"volkswagen":["vw"]}
注意同义词是可选的。也许在您的用例中，您不需要同义词。
现在，我们可以使用上面的命令初始化自动完成功能
fromfast_autocompleteimportAutoCompleteautocomplete=AutoComplete(words=words,synonyms=synonyms)
此时，autocomplete已经创建了一个结构。
现在你可以搜索了！
- word：返回自动完成结果的单词
- 最大成本：计算结果时要考虑的最大编辑距离
- 大小：要返回的最大结果数
>>>autocomplete.search(word='2018 bmw 1',max_cost=3,size=3)[['2018','bmw'],['2018','bmw 1 series']]
如果我们错按了怎么办？它仍然有效。没问题。
>>>autocomplete.search(word='2018 bmw 1a',max_cost=3,size=3)[['2018','bmw'],['2018','bmw 1 series']]
好的，我们现在搜索阿尔法：
>>>autocomplete.search(word='alfa',max_cost=3,size=3)[['alfa romeo'],['alfa romeo 4c'],['alfa romeo giulia']]
如果我们不知道alfa的发音，然后键入alpha，会怎么样？
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]0
它仍然有效！
快速自动完成确保结果有意义！
好的，让我们把单词洛杉矶添加到单词中：
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]1
到目前为止，我们还没有使用上下文。这个库留给你如何使用上下文。但基本上，如果我们给每个词一个上下文，那么上面的回答就可以很容易地翻译成上下文列表。
上下文
如果我们的字典是：
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]2
然后自动完成。单词可用于将结果映射到上下文中：
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]3
绘制
此包实际上可以在填充DWG时绘制DWG，也可以在为您填充DWG后绘制！ 下面是用"makes\u models\u short.csv"中的单词填充DWG的动画：
绘制dwg填充动画
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]4
一旦您初始化了上面的autocompletedraw类，它将填充dwg并生成动画！ 有关此代码正确设置的示例，请查看测试。实际上，dwg中的动画也是通过单元测试生成的！
注意，如果有很多单词，图形文件将很大。不必在填充DWG时绘制所有框架，只需绘制最后一个阶段：
绘制最终图形
要只绘制一个显示dwg最后阶段的图形，请使用draw mixin并运行draw_graph函数：
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]5
演示
如果您想与终端中的自动完成结果进行实时交互，可以使用演示模块：
只要向它传递一个自动完成的实例，搜索就会配置：
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]6
开发
- 复制回购协议
- 使用python 3.6或更新版本制作virtualenv
pip安装-r requirements-dev.txt
运行测试
pytest
我们试图保持代码覆盖率的高标准。目前，dwg模块的覆盖率约为99%！
释放量
我们使用bump2version对版本进行凹凸和标记。
>>>fromfast_autocompleteimportAutoComplete>>>words={'book':{},'burrito':{},'pizza':{},'pasta':{}}>>>autocomplete=AutoComplete(words=words)>>>autocomplete.search(word='b',max_cost=3,size=3)[['book'],['burrito']]>>>autocomplete.search(word='bu',max_cost=3,size=3)[['burrito']]>>>autocomplete.search(word='barrito',max_cost=3,size=3)# mis-spelling[['burrito']]7
作者
- 在Fair Financial Corp.自动完成。
- LFU缓存由Shane Wang提供
自动完成的其他方式
弹性搜索。是的，ElasticSearch通常是一个比这个库更好的自动完成解决方案。我一般说。在我们的特定用例中，我们希望自动完成比弹性搜索和处理单词组合更快。否则ElasticSearch将是完美的。贝赫场景弹性搜索采用lucene中的有限状态传感器（fst）来实现自动完成。fst比我们在快速自动完成中使用的更复杂。
如果你的自动完成应该基于一个大的文本博客返回结果（例如基于一些书籍内容），那么更好的解决方案是使用马尔可夫链和条件概率。是的，外面已经有图书馆了！https://github.com/rodricios/autocomplete看起来很棒。免责声明：我们没有实际使用它，因为它不适合我们的特定用例。
为什么是图纸
dwg代表有向字图。最初我们使用的是trie树结构。但很快，很明显一些分支需要合并回其他分支。例如beemer和bmw分支都需要在同一个节点中结束，因为它们是同义词。因此我们使用了dwg.
什么是同义词、干净同义词和部分同义词
同义词是产生相同结果的词。
- 例如
beemer和bmw都应该给您bmw alfa和alfa romeo都应该给您alfa romeo
同义词分为两组：
- 干净的同义词：这两个词共享很少或没有词。例如
beemervs.bmw - 部分同义词：两个词中的一个是另一个词的子串。例如
alfa和alfa romeo或gm与gmc
在内部，这两种同义词被区别对待，但作为库的用户，您不需要真正关心它。您只需通过定义get synonyms方法来提供同义词词典。
为什么部分同义词有一个完整的子树
问：部分同义词是指同义词是原词的一部分。例如，alfa是alfa romeo的部分同义词。
在这种情况下，在dwg中同时插入alfa和alfa romeo。阿尔法将有阿尔法4c和阿尔法罗密欧将有阿尔法罗密欧4c分支。为什么不让阿尔法分行成为阿尔法罗密欧分行，然后您将自动拥有阿尔法的所有分行
答：我们用字母表示边缘。因此alfa只能有一条边出来，那就是空格（）。该边将被转到一个节点，该节点的分支指向alfa romoe，alfa 4c等。它不能有一个指向该节点，而另一个指向alfa romeo的直系子节点。这样，当我们遍历dwg以输入alfa 4时，就可以到达正确的节点。
我让丰田陷入困境，但当我输入"玩具"时，它不会出现。
答：如果在dwg中输入带有大写字母t的toyota，则搜索词也会以大写字母t开头。我们建议您在将所有内容放入dwg之前将其小写。fast autocomplete不会自动为您执行此操作，因为它假定要将单词字典放入dwg中。在将数据放入DWG之前，您需要先清理自己的数据。
欢迎加入QQ群-->： 979659372
