在python中使用二进制搜索搜索文本

Question

我在一个名为data的列表中没有几个文件名。我想读取文件的内容，并检查给定的文本(例如橙色)是否出现在文件中。我的文件名按顺序被追加到列表中，即如果给定文本“橙色”，出现在文件pi.txt (索引2)中，它也将出现在索引2之后的所有文件中，而且我还想得到首先出现文本“橙色”的索引或文件名。

我在一个列表中有上千个文件，因此我想使用二进制搜索。

data = ['ae.txt', 'ac.txt', 'pi.txt', 'ad.txt', 'mm.txt', 'ab.txt']
target = "orange"

def binary_search(a, x):
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2

        if not x in open(a[mid]).read():
            lo = mid + 1
        elif x in open(a[mid]).read():
            hi = mid
        elif mid > 0 and x in open(a[mid-1]).read():
            hi = mid
        else:
            return mid

    return -1

print(binary_search(data, target))



$ cat ae.txt
papaya
guava

$ cat ac.txt 
mango
durian
papaya
guava

$ cat pi.txt 
orange
papaya
guava

$ cat ad.txt 
orange
papaya
guava

$ cat mm.txt 
orange
papaya
guava

$ cat ab.txt 
orange
papaya
guava

Answer 1

我认为有太多的条件，你可以设法得到预期的结果如下：

data = ['ae.txt', 'ac.txt', 'pi.txt', 'ad.txt', 'mm.txt', 'ab.txt']
target = "orange"

def binary_search(a, x):
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2
        print(mid)
        if not x in open(a[mid]).read():
            lo = mid + 1

        elif x in open(a[mid]).read():
            hi = mid
        if lo == hi:
            return lo

        print("low : {}; high : {}".format(lo,hi))

    return -1
index = binary_search(data, target)
print("The index where we first found the word orange is {}, the file name is {}".format(index,data[index]))

The index where we first found the word orange is 2, the file name is pi.txt

Answer 2

二进制搜索实际上并不是在寻找等式，因此可以简化一点：

def binary_search(files, string):
    lo,hi  = 0,len(files)-1
    while hi>=lo:
        mid     = (hi+lo)//2
        if string in open(files[mid]).read(): 
            hi = mid-1
        else: 
            lo = mid+1
    return lo

由于没有等式检查，hi和lo将到达停止条件(hi>=lo)，在该条件下，lo将位于第一次匹配的索引上，如果没有匹配，则在len(files)处。

Answer 3

只有当您的文件已经按照您正在使用的搜索键进行排序时，才能对文件进行二进制搜索，这意味着Xn+1文件的数据在字典上不能比Xn文件小。在这种情况下，你必须手动检查每一个文件，直到你仔细检查所有的文件.或者构建这样的字典文件：

'ae.txt', 'ac.txt', 'pi.txt', 'ad.txt', 'mm.txt', 'ab.txt'
durian 1
guava 0-5
mango 1
orange 2-5
papaya 0-5

第一行表示包含的文件，并通过定位给它们索引(例如，“ae.txt”位于0位置)。其他行表示包含每个单词的文件索引。

从这里，您可以读取文件名的第一行，通过二进制搜索在行中找到要查找的单词(不过，您可能应该找到一种方法来读取O(1)中的特定行-或者将它们放在单独的字典文件中，例如，如果单个字母太多)。然后，确定文件名的索引(它在第一行中的位置)是否在单词的行中表示。

编写编写初始文件并相应地更新它的代码似乎很简单，但如果您愿意，我可以帮助您。