二进制字符串搜索 - 最小容器宽度？

我碰巧在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，二等分过程将不得不停止并切换到正则表达式/常规旧字符串匹配之类的东西。

我没有那么多，询问如何做到这一点的什么这种类型的搜索被称为 ...什么是与“窗口尺寸”分隔标准二进制搜索叫什么名字？有条件地平分数据集的内容，一旦满足条件，就会退回到某种其他形式的字符串匹配，以确保在查询中可以有效地存在结尾通配符（因此搜索“Peter”将得到“彼得杰克逊“和”彼得爱德华兹“）

希望我已经清楚我的意思。我在典型的DB场景中意识到名称可能是分开的，这仅仅是作为概念证明。

来源

2012-12-17 DeaconDesperado

在最坏的情况下，它可能是所有的彼得，不是吗？ – kdubs

事实上，在最坏的情况下（或者我应该说预定的那个？），所有的彼得斯将被提取。 – DeaconDesperado

所以看起来你必须根据你可能搜索的内容进行分类。我猜你可以做一个二进制，直到你找到一个匹配，然后做两个方向的线性搜索来找到所有其他匹配。不知道我是否称它为垃圾箱，但是你会将你的数据组织成二叉树，并且是线性的。 – kdubs

我没有穿过这种类型的双级搜索来之前，所以不知道它是否有一个知名的名字。但是，我可以提出一个如何实施的方法。

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

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

现在来比较。当比较列表元素x与搜索键k时，比较器将仅使用x[:len(k)]并忽略其余的x。因此，当搜索“彼得”时，列表中的所有彼得斯将与关键字相等。因此，bisect_left()到bisect_right()会给你包含列表中所有Peters的范围。

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

来源

2012-12-17 20:15:08 NPE

第一个比较应该仍然是一个平分，但是，对吧？因此，找到彼得的第一个实例（或者只是最初的二等分），然后使用比较器来匹配但是很多字符都与查询相关... – DeaconDesperado

@DeaconDesperado：第一种方法查找完全匹配并返回至多一个，而第二个查找前缀匹配并返回一个范围。您可以根据您的应用程序混合并匹配这些属性... – NPE

在你的二进制搜索中，你要么打一个完全匹配或者匹配的区域。
所以在你的情况下，你需要获得上下边界（hilo，就像你打电话给他们的那样），包含Peter的区域并返回所有的中间字符串。

但如果你的目标是做一些像一个字的显示接下来的话你应该考虑尝试次数，而不是BSTS

来源

2012-12-17 20:14:56 Cratylus

谢谢，我想我明白你在说什么...... hi和lo的计算必须考虑子集是否完全由好匹配组成。我明白你的意思是关于“接下来的单词”......已经使用了后缀树。 – DeaconDesperado

hi和lo的计算必须考虑子集是否完全由好匹配组成。它不必如此复杂，因为元素已经排序。所以你需要的是''low''''里面的所有元素 – Cratylus

二进制字符串搜索 - 最小容器宽度？

回答

相关问题