Return 具有 python 中多个特征的输入查询的最佳匹配

Question

我有以下物品：

[
    { "id":"item1", "age": 1, "color": 'fff', "rate": 3 },
    { "id":"item2", "age": 2, "color": '000', "rate": 4 },
    { "id":"item3", "age": 3, "color": 'eee', "rate": 5 },
    { "id":"item4", "color": 'bbb', "rate": 5 }
]

现在，我希望用户搜索想要的项目：{"age": 1, "color": '000', "rate":5} 甚至 {"age": 3, "color": 'abc'}

我想为此查询找到最佳匹配项。我怎么做？我不是在寻找确切的答案。虽然，我有兴趣将其实现为后端服务，所以 Python 应该没问题。我只是不确定如何解决这个问题。我需要查看某种匹配算法或模糊搜索吗？

UPDATE: 数据很大（百万条），每个条有50-100个键，但有些条可能没有全部。此外，用户查询可能不包含所有键。

Answer 1

您的数据集有多大？

对于小型数据集，您可以在 O(n*m) 时间内完成此操作（列表中有 n 个项目，字典中有 m 个键），只需在比较相同键的值后获取最匹配的项目，跟踪匹配数。

search_item = {"age": 1, "color": '000', "rate": 5}
mx = -float('inf')
for item in lst:
    curr = sum(search_item[k]==item[k] for k in item)
    if curr > mx:
        match = item
        mx = curr
print(match)

搜索条件可能不是简单的键值匹配。您可以定义它！

对于非常大的数据集，您可以从列表中构造一个 k-d tree 并将搜索时间减少到 O(log(n)) 以防万一您将重复使用 list/tree 搜索多个项目。

您应该将十六进制颜色转换为数字类型，这样您就有了一个跨维度的同质 int 类型并且比较更容易，因为比较 int 比模糊字符串匹配简单得多。

例如颜色ffb比eee更接近fff：

>>> int('fff', 16)
4095
>>> int('ffb', 16)
4091
>>> int('eee', 16)
3822

Answer 2

我假设您想要 data 的元素最匹配，而不是所有字典中每个键的最佳匹配。

这可以让你开始：

>>> data = [
...     { "id":"item1", "age": 1, "color": 'fff', "rate": 3 },
...     { "id":"item2", "age": 2, "color": '000', "rate": 4 },
...     { "id":"item3", "age": 3, "color": 'eee', "rate": 5 }
... ]
>>> user_input = {"age": 1, "color": 'fff', "rate":5}
>>>
>>> criterion = lambda d: len(user_input.items() & d.items())
>>> max(data, key=criterion)
{'id': 'item1', 'age': 1, 'color': 'fff', 'rate': 3}

调用 max returns data 的唯一元素，此处有两个匹配项。

如果你想要更复杂的模糊匹配而不只是计算直接命中，例如 'ffe' 比 'abc' 更接近 'fff' 那么你需要

为与某些键关联的每种类型的值定义一个距离度量
使用这些指标来实施更复杂的 criterion。

对于字符串，请考虑 Levenshtein distance 和 abs(x - y) 数字类型。

Return 具有 python 中多个特征的输入查询的最佳匹配

Return best matches for the input query having several features in python

python

matching

fuzzy-search