使用有向词图实现的快速自动完成

导航

验证详情

这些详细信息已由PyPI 验证
维护者
来自gravatar.com的seperman的头像 seperman

未验证详情

这些详细信息尚未由PyPI 验证
项目链接
元数据
分类

项目描述

Fast Autocomplete 0.9.0

zepworks.com

使用有向词图（DWG）和Levenshtein编辑距离实现快速自动完成。

结果通过LFU（最少使用）进行缓存。

为什么

在此处了解为什么构建了fast-autocomplete： http://zepworks.com/posts/you-autocomplete-me/

我们得出结论，Elasticsearch的自动完成建议器不够快，而且没有做我们需要的所有事情，因此编写了这个库。

  1. 一旦我们切换到Fast Autocomplete，我们的平均延迟从120ms降低到30ms，性能提高了3-4倍，错误降到了零。
  2. Elasticsearch的自动完成建议器无法处理您输入的任何单词组合。例如，Fast Autocomplete可以处理当单独将“2018”，“Toyota Camry”，“Los Angeles”这些词输入时的情况，“2018 Toyota Camry in Los Angeles”。而Elasticsearch的自动完成需要将整个句子输入才能在自动完成结果中显示。

您可能会说

  1. 关于#1：是的，但是您正在使用缓存。回答：嘘，保持安静。我们也在使用C库进行Levenshtein编辑距离，这也提高了性能。
  2. 关于#2：不错。回答：好吧，我们现在在谈论了。

如何

在此处了解fast-autocomplete是如何工作的： http://zepworks.com/posts/you-autocomplete-me/

简而言之，fast Autocomplete所做的操作是

  1. 用您的单词填充DWG。
  2. 按字母顺序跟随图节点，直到找到包含单词的节点。
  3. 在找到图上的单词后继续，直到达到叶子节点。
  4. 从根节点重新开始，直到遇到图上不存在的字母。
  5. 根据剩余的单词部分，返回从它卡住的地方开始的所有子单词。
  6. 或者运行Levenshtein编辑距离，找到与剩余部分最接近的单词，并从这里继续。

通过这种方式，它可以标记如

2018丰田凯美瑞在洛杉矶成为 [2018, 丰田凯美瑞, 在, 洛杉矶]

并在输入时返回自动完成结果。

安装

pip install fast-autocomplete

注意：快速自动完成仅适用于Python 3.6及更高版本。

你还在使用Python 2吗？是时候升级了。

许可证

MIT

DWG

在这个库中我们使用的数据结构称为Dawg。

DWG代表有向单词图。下面是一个基于测试中提供的"makes_models_short.csv"的DWG示例。

dwg

dwg

用法

首先，让我们从你的数据开始。这个库将如何准备数据留给你。如果你想直接进入工厂函数，让你在最简单和最常见的情况下使用库，请跳过所有这些并跳转到排序示例。

示例 1

>>> from fast_autocomplete import AutoComplete
>>> 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

想象我们有一个包含以下内容的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

我们想要做的是将其转换为单词和它们上下文的字典。

import csv
from fast_autocomplete.misc import read_csv_gen


def get_words(path):

    csv_gen = read_csv_gen(path, csv_func=csv.DictReader)

    words = {}

    for line in csv_gen:
        make = line['make']
        model = line['model']
        if make != model:
            local_words = [model, '{} {}'.format(make, model)]
            while local_words:
                word = local_words.pop()
                if word not in words:
                    words[word] = {}
        if make not in words:
            words[make] = {}
    return words

read_csv_gen只是一个辅助函数。你实际上并不需要它。整个目的是将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': {}}

这是一个单词到它们上下文的字典。我们决定在这个例子中我们不希望单词有任何上下文，所以所有上下文都是空的。然而，通常你会在单词周围使用一些上下文，以便在更复杂的逻辑中使用。上下文用于将单词“键”转换为它们的上下文，即单词字典中的键的值。

除了单词，我们通常还想要一个同义词字典。例如：

synonyms = {
    "alfa romeo": ["alfa"],
    "bmw": ["beemer", "bimmer"],
    "mercedes-benz": ["mercedes", "benz"],
    "volkswagen": ["vw"]
}

请注意，同义词是可选的。也许在你的用例中，你不需要同义词。

现在我们可以使用上述内容来初始化自动完成

from fast_autocomplete import AutoComplete

autocomplete = AutoComplete(words=words, synonyms=synonyms)

此时，自动完成已创建了一个dwg结构。

现在你可以搜索了！

  • word：返回自动完成结果的单词
  • max_cost：计算结果时考虑的最大Levenshtein编辑距离
  • size：要返回的最大结果数
>>> autocomplete.search(word='2018 bmw 1', max_cost=3, size=3)
[['2018', 'bmw'], ['2018', 'bmw 1 series']]

如果我们不小心按了一个b怎么办？它仍然有效。没问题。

>>> autocomplete.search(word='2018 bmw 1a', max_cost=3, size=3)
[['2018', 'bmw'], ['2018', 'bmw 1 series']]

现在让我们搜索Alfa

>>> autocomplete.search(word='alfa', max_cost=3, size=3)
[['alfa romeo'], ['alfa romeo 4c'], ['alfa romeo giulia']]

如果我们不知道如何发音Alfa，我们输入alpha怎么办？

>>> autocomplete.search(word='alpha', max_cost=3, size=3)
[['alfa romeo'], ['alfa romeo 4c'], ['alfa romeo giulia']]

它仍然有效！

Fast-Autocomplete确保结果是有意义的！

现在让我们在单词中添加洛杉矶

>>> words['los angeles'] = {}
>>> words['in'] = {}
>>> autocomplete.search(word='2007 alfa in los', max_cost=3, size=3)
[['2007', 'alfa romeo', 'in'], ['2007', 'alfa romeo', 'in', 'los angeles']]

到目前为止，我们还没有使用上下文。这个库将如何使用上下文留给你。但基本上，如果我们给每个单词一个上下文，那么上述响应就可以很容易地转换为上下文列表。

上下文

如果我们的单词字典是

words = {
 'in': {},
 'alfa romeo': {'type': 'make'},
 '2007': {'type': 'year'},
 'los angeles': {'type': 'location'},
}

那么可以使用autocomplete.words将结果映射到它们的上下文

[['2007', 'alfa romeo', 'in'], ['2007', 'alfa romeo', 'in', 'los angeles']]

converted to contexts:

[[{'year': '2007'}, {'make': alfa romeo'}], [{'year': '2007'}, {'make': alfa romeo'}, {'location': 'los angeles'}]]

排序

使用Fast Autocomplete的人中，大多数人都想控制结果的排序方式。如果你不控制它，结果将根据自动完成找到匹配条件节点在图中的顺序进行排序。

排序最简单的方法是为每个项目提供一个计数。Fast AutoComplete将使用计数来排序部分匹配的项目。

例如

  1. 创建一个json文件，它是一个单词到它们上下文的字典。

文件格式需要是

{
    word: [
        context,
        display value,
        count
    ]
}

示例包含在 sample_words.json 中

{
  "acura rlx": [
    {
      "model": "rlx",
      "make": "acura"
    },
    "Acura RLX",
    3132
  ],
  "rlx": [
    {
      "model": "rlx",
      "make": "acura"
    },
    "Acura RLX",
    3132
  ],
  "acura": [
    {
      "make": "acura"
    },
    "Acura",
    130123
  ],
  ...
}

你可能想知道为什么是这个格式。这是因为在JSON文件变得非常大且键变得重复时，可以节省空间。这就是为什么我们使用一个预定义键顺序的列表。对于目前的使用案例，如果你想将上下文和显示值设置为None，你可以这样做。我们很快就会开源其他工厂函数，这些函数将充分利用上下文中的键。

  1. 通过工厂函数启动自动补全
from fast_autocomplete import autocomplete_factory

content_files = {
    'words': {
        'filepath': path/to/sample_words.json,
        'compress': True  # means compress the graph data in memory
    }
}

autocomplete = autocomplete_factory(content_files=content_files)
  1. 你可以使用自动补全，并且结果会按计数排序！
>>> autocomplete.search(word='acu')
[['acura'], ['acura mdx'], ['acura rdx']]
  1. 我们如何使用上下文和显示值呢？

这是个好问题。你需要扩展AutoComplete类来使用这些项目。我将撰写一篇关于此的博客文章。

下面是一个没有扩展的简单示例

>>> autocomplete.words['acura']
WordValue(context={'make': 'acura'}, display='Acura', count=130123, original_key=None)
>>> autocomplete.words['acura'].display
Acura

通过更新计数来更改排序

默认情况下，Fast Autocomplete使用项目的“计数”来对结果中的项目进行排序。将计数视为Fast自动补全的“指南”，以便它可以完善其结果。根据Fast自动补全是否找到与用户查询完全匹配的结果，将使用计数来完善结果。你可以在自动补全对象中实时更新计数。

例如，在 汽车品牌和型号的样本csv 中我们

make,model,count
Toyota,Aurion,6094
Toyota,Avalon,8803
Toyota,Avensis,1630
Toyota,Auris,4025
Toyota,Aygo,2115

如果我们使用自动补全进行搜索

>>> auto_complete = AutoComplete(words=WIKIPEDIA_WORDS, synonyms=SYNONYMS, full_stop_words=['bmw', 'alfa romeo'])
>>> autocomplete.search(word='toyota a')
[['toyota'], ['toyota avalon'], ['toyota aurion'], ['toyota auris']]

然而，正如你所注意到的，toyota aygo 的计数为 2115，因此它没有进入前3个结果。

我们可以使用 update_count_of_word 将 toyota aygo 的计数设置为更高的数字，以在结果中提升它。

update_count_of_word 可以通过直接设置单词的计数或通过偏移其当前值来更改计数。

>>> auto_complete = AutoComplete(words=WIKIPEDIA_WORDS, synonyms=SYNONYMS, full_stop_words=['bmw', 'alfa romeo'])
>>> auto_complete.update_count_of_word(word='toyota aygo', count=10000)
10000

现在如果我们搜索

>>> autocomplete.search(word='toyota a')
[['toyota'], ['toyota aygo'], ['toyota avalon'], ['toyota aurion']]

我们可以检查一个节点的计数

>>> autocomplete.get_count_of_word('toyota aygo')
10000

现在让我们使用偏移量来偏移不同节点的当前计数

>>> auto_complete.update_count_of_word(word='toyota aurion', offset=-6000)
94

当我们搜索时，toyota aurion 已不再出现在前3个结果中！

>>> autocomplete.search(word='toyota a')
[['toyota'], ['toyota aygo'], ['toyota avalon'], ['toyota auris']]

Unicode

默认情况下，此包仅接受ASCII小写字母，a-z。但是，你可以通过 valid_chars_for_string（字符串）和 valid_chars_for_integer（数字）传递你希望接受的字符。例如，在这里我们告诉自动补全考虑波斯字母字符作为字符串字符。

AutoComplete(
    words=SHORT_WORDS_UNICODE,
    valid_chars_for_string='اآبپتثجچحخدذرزژسشصضطظعغفقکگلمنوهی')

如果你想在ASCII字母之外传递其他字符，例如标点符号，你需要设置 valid_chars_for_string 变量以包含你需要的所有字符。例如，以下代码块设置了ASCII字母a-z以及点和撇号

valid_chars = ".'"
valid_chars += string.ascii_lowercase
AutoComplete(
    words=WORDS_WITH_PUNCTUATION,
    valid_chars_for_string=valid_chars)

绘图

实际上，这个包可以在填充dwg时或填充完成后绘制dwg！以下是使用来自 "makes_models_short.csv" 的单词填充dwg的动画

dwg填充动画

from fast_autocomplete import AutoComplete, DrawGraphMixin


class AutoCompleteDraw(DrawGraphMixin, AutoComplete):
    DRAW_POPULATION_ANIMATION = True
    DRAW_POPULATION_ANIMATION_PATH = 'animation/short_.svg'
    DRAW_POPULATION_ANIMATION_FILENO_PADDING = 6


autocomplete = AutoCompleteDraw(words=words, synonyms=synonyms)

只要你初始化了上面的AutoCompleteDraw类，它就会填充dwg并生成动画！要查看此代码的正确设置示例，请查看测试。实际上，dwg 中的动画也是通过单元测试以相同的方式生成的！

请注意，如果你有很多单词，图文件会很大。而不是在dwg被填充时绘制所有帧，你只需绘制最终阶段

绘制最终图

要绘制仅显示dwg最终阶段的单个图，请使用draw mixin并运行draw_graph函数

from fast_autocomplete import AutoComplete, DrawGraphMixin


class AutoCompleteDraw(DrawGraphMixin, AutoComplete):
    pass

autocomplete = AutoCompleteDraw(words=words, synonyms=synonyms)
autocomplete.draw_graph('path to file')

演示

如果你想在终端中与自动补全结果进行实时交互，可以使用演示模块

只需传递自动补全实例和搜索配置即可

from fast_autocomplete import demo

demo(autocomplete, max_cost=3, size=5)

开发

  1. 克隆存储库
  2. 使用Python 3.6或更高版本创建虚拟环境
  3. pip install -r requirements-dev.txt

运行测试

pytest

我们试图保持代码覆盖率的标准很高。目前，dwg 模块的覆盖率约为99%！

版本

我们使用 bump2version 来升级版本并打标签。

git checkout master && git pull
bump2version {patch|minor|major}
git push && git push --tags

作者

其他实现自动完成的方法

  1. Elasticsearch。是的，Elasticsearch 通常比这个库提供更好的自动完成解决方案。我说的是通常。在我们的特定用例中，我们希望自动完成比 Elasticsearch 更快，并且能够处理组合词。否则 Elasticsearch 将是完美的。在幕后，Elasticsearch 在 Lucene 中使用有限状态转换器 (FST) 来实现自动完成。FST 比我们在 fast-autocomplete 中使用的要复杂。

  2. 如果你的自动完成应该基于大量文本（例如基于某些书籍内容）的结果返回，那么更好的解决方案是使用马尔可夫链和条件概率。是的，已经有一个库可以做到这一点！ https://github.com/rodricios/autocomplete 并且看起来非常好。免责声明：我们没有实际使用它，因为它不适合我们的特定用例。

常见问题解答

为什么是 DWG

DWG 代表有向单词图。最初我们使用 Trie-Tree 结构。但很快就很明显，一些分支需要合并到其他分支。例如 beemer 和 bmw 分支都需要以相同的节点结束，因为它们是同义词。因此我们使用了 DWG。

什么是同义词、干净的同义词和部分同义词

同义词是应该产生相同结果的表达。

  • 例如 beemer 和 bmw 都应该给出 bmw。
  • alfa 和 alfa romeo 都应该给出 alfa romeo。

同义词被分为两组

  1. 干净的同义词：两个词共享很少或没有词。例如 beemer 与 bmw。
  2. 部分同义词：两个词中的一个词是另一个词的子串。例如 alfa 和 alfa romeo 或 gm 与 gmc。

内部这两种类型的同义词被不同地处理，但作为库的用户，你不需要真正关心这一点。你只需要通过定义 get_synonyms 方法提供同义词字典。

为什么你有部分同义词的整个子树

问题：部分同义词意味着同义词是原始词的一部分。例如 alfa 是 alfa romeo 的部分同义词。在这种情况下，你需要将 alfa 和 alfa romeo 都插入到 dwg 中。 alfa 将有 alfa 4c 和 alpha romeo 将有 alfa romeo 4c 分支。为什么不能只将 alfa 分支设置为 alfa romeo，然后你将自动拥有所有 alfa romeo 的子分支。

答案：我们使用字母作为边。因此 alfa 只能有一个来自它的边，即空格 ( )。这条边将指向一个有子分支到 alfa romoe、alfa 4c 等 的节点。不能有 指向那个节点，另一个 指向 alfa romeo 的直接子节点。这样当我们遍历 dwg 以获取 alfa 4 的输入时，我们可以到达正确的节点。

我将丰田放入 Dawg，但当我输入 toy 时，它没有出现。

答案：如果你以大写 T 将 Toyota 放入 dwg，它期望搜索词以大写 T 开头。我们建议在将它们放入 dwg 之前将所有内容转换为小写。Fast-autocomplete 不会自动为你做这件事，因为它假设 words 字典是你想放入 dwg 中的内容。这取决于你自己在将数据放入 dwg 之前对其进行清理。

项目详细信息

验证详情

这些详细信息已由PyPI 验证
维护者
来自gravatar.com的seperman的头像 seperman

未验证详情

这些详细信息尚未由PyPI 验证
项目链接
元数据
分类

版本历史 发布通知 | RSS 源

本版本

0.9.0

0.7.2

0.7.1

0.7.0

0.6.0

0.5.0

0.4.6

0.4.5

0.4.4

0.4.3

0.4.2

0.4.1

0.4.0

0.3.0

0.2.9

0.2.8

0.2.7

0.2.5

0.2.4

0.2.3

0.2.2

0.2.1

0.2.0

0.1.7

0.1.5

0.1.4

0.1.3

0.1.2

0.1.1

0.1.0

下载文件

下载适用于您平台的文件。如果您不确定选择哪个，请了解更多关于安装包的信息。

源分布

fast-autocomplete-0.9.0.tar.gz (27.9 kB 查看哈希值)

上传时间 源

构建分布

fast_autocomplete-0.9.0-py3-none-any.whl (23.4 kB 查看哈希值)

上传时间 Python 3

由以下支持