FuzzDex

FuzzDex 是一个快速的 Python 库，用 Rust 编写。它实现了一个内存 fuzzy index，其工作方式类似于由人工输入键入的容错字典。

算法

您加载到 fuzzdex 系列的短语中——例如由一个或多个单词组成的街道名称，并带有一个数字索引，用于在相关的城市词典中识别此街道名称。

must-token然后，您可以使用 a （目前只有一个，但可以更改为使用更多）和附加来查询索引，should-tokens以读取总共 limit可能匹配的短语。

Must-token 被三元化（warszawa -> war ars rsz sza zaw awa），所有包含给定三元组的短语最初都是从索引中读取的。Trigrams 有分数，它们越常见，它们增加短语分数的次数就越少。should-token 的三元组还会改变分数（当它们匹配时为正），但不要从索引中添加额外的短语。然后按分数对短语进行排序。

过滤顶部短语以包含可选约束，并收集具有最大编辑距离 (Levenshtein) 的必须标记，直到limit收集到短语。

在内部，必须令牌搜索的结果被 LRU 缓存，因为在实践中它经常重复。应该令牌会有所不同，并且总是会重新计算。

用例

它旨在将用户提供的物理地址的一部分与从 OpenStreet 地图中提取的数据进行匹配，以查找街道和城市。

地址首先被标记化，然后它的部分与城市和街道的模糊字典相匹配。额外的约束可以将匹配的街道限制在给定的城市 - 或找到具有给定街道的城市。

首先使用三元组搜索数据（warszawa -> war ars rsz sza zaw awa），然后使用最大 Levenshtein 编辑距离进行额外过滤。

最初的解决方案使用了 Elasticsearch 数据库的模糊查询，它可以工作 - 但在我们的测试中慢了 21 倍。

例子

import fuzzdex
# Create two fuzzy indices with cities and streets.
cities = fuzzdex.FuzzDex()
# Warsaw has streets: Czerniakowska, Nowy Świat and Wawelska
cities.add_phrase("Warsaw", 1, constraints={1, 2, 3})
# Wrocław only Czerniawska
cities.add_phrase("Wrocław", 2, constraints={4})

streets = fuzzdex.FuzzDex()
# Streets with reversed constraints and own indices:
streets.add_phrase("Czerniakowska", 1, constraints={1})
streets.add_phrase("Nowy Świat", 2, constraints={1})
streets.add_phrase("Wawelska", 3, constraints={1})

streets.add_phrase("Czerniawska", 4, constraints={2})

# This recalculates trigram scores and makes index immutable:
cities.finish()
streets.finish()

# warszawa matches warsaw at editing distance 2.
cities.search("warszawa", [], max_distance=2, limit=60)
#    [{'origin': 'Warsaw', 'index': 1, 'token': 'warsaw',
#      'distance': 2, 'score': 200000.0, 'should_score': 0.0}]

# `świat` adds additional should score to the result and places it higher
# in case the limit is set:
streets.search("nowy", ["świat"], max_distance=2, constraint=1)
#    [{'origin': 'Nowy Świat', 'index': 2, 'token': 'nowy',
#      'distance': 0, 'score': 5.999, 'should_score': 7.4999}]

# Won't match with constraint 2.
streets.search("nowy", ["świat"], constraint=2)
#    []

# Quering for `czerniawska` will return `czerniakowska` (no constraints),
# but with a lower score and higher distance:
In [22]: streets.search("czerniawska", [], max_distance=2)
Out[22]:
#  [{'origin': 'Czerniawska', 'index': 4, 'token': 'czerniawska',
#   'distance': 0, 'score': 9.49995231628418, 'should_score': 0.0},
#  {'origin': 'Czerniakowska', 'index': 1, 'token': 'czerniakowska',
#   'distance': 2, 'score': 6.4999680519104, 'should_score': 0.0}]

安装、开发

当使用它发布的架构之一（x86_64，少数 Python 版本）时，您可以从 PyPI 安装 fuzzdex。

pip3 install fuzzdex

或者使用maturin在本地构建它：

pipenv install --dev
pipenv shell
maturin develop -r
pytest

您也可以使用 cargo 并直接复制或链接 .so 文件（将 libfuzzdex.so 重命名为 fuzzdex.so）：

cargo build --release
ln -s target/release/libfuzzdex.so fuzzdex.so

build.sh具有为 PyPI 构建 manylinux 包的命令。