二进制字符串搜索 - 最小箱宽？

Question

我碰巧在Python中构建二进制搜索,但问题一般与二进制搜索结构有关.

让我们假设我有大约一千名符合条件的候选人,我正在使用二分搜索进行搜索,执行将分类数据集二等分的经典方法,并重复此过程以缩小符合条件的集合以进行迭代.候选人只是名字串,(第一种格式,例如"彼得杰克逊")我最初按字母顺序对集合进行排序,然后使用以下内容进行二分:

hi = len(names)
lo = 0
while lo < hi:
  mid = (lo+hi)//2
  midval = names[mid].lower()
  if midval < query.lower():
    lo = mid+1
  elif midval > query.lower():
    hi=mid
  else:
    return midval
return None

此代码改编自此处:https://stackoverflow.com/a/212413/215608

这就是事情,上面的过程假设一个完全匹配或根本没有结果.如果查询仅仅是为了"彼得",但是有几个不同姓氏的彼此怎么办？为了归还所有彼得斯,人们必须确保二等分的"箱子"从未如此小到符合条件的结果.二分过程必须停止并放弃像正则表达式/常规旧字符串匹配才能返回所有Peters.

我不是在问这个如何实现这一点,因为这种类型的搜索被称为什么...什么是二进制搜索,带有"bin size"的分隔标准？有条件地将数据集一分为二的东西,一旦满足条件,就会回退到其他形式的字符串匹配,以确保查询上可以有效地存在结束通配符(因此搜索"Peter"将获得" Peter Jacksons"和"Peter Edwards")

希望我清楚我的意思.我意识到在典型的DB场景中,名称可能是分开的,这只是作为概念证明.

Answer 1

我以前没有遇到过这种类型的两阶段搜索，所以不知道它是否有一个众所周知的名字。不过，我可以提出一种实现方法。

假设您已经运行了第一阶段，但没有找到匹配项。

您可以使用一对二分搜索和一个特殊的比较器来执行第二阶段。二分搜索将使用与bisect_left和bisect_right相同的原理。您将无法直接使用这些函数，因为您需要一个特殊的比较器，但您可以使用它们作为实现的基础。

现在到比较器。当将列表元素x与搜索键进行比较时k，比较器将仅使用x[:len(k)]并忽略其余元素x。因此，当搜索“Peter”时，列表中的所有 Peter 都将与该键进行比较。因此，bisect_left()tobisect_right()将为您提供包含列表中所有 Peters 的范围。

所有这些都可以通过比较来完成O(log n)。