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

Question

我在名为数据的列表中只有几个文件名。我想读取文件的内容并检查文件中是否出现给定文本（示例 - 橙色）。我的文件名按顺序附加到列表中，即如果给定文本 "orange"，出现在文件 pi.txt（索引 2）中，它也会出现在索引 2 之后的所有文件中，当然我想获取文本 "orange" 首先出现的索引或文件名。

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

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

仅当您的文件已按您使用的搜索键排序时，对文件进行二进制搜索才有效，这意味着文件 X[n+1] 的数据在字典序上不得小于文件 X[n]。在这种情况下，您必须手动检查每个文件，直到您检查完所有文件……或者像这样构建一个字典文件：

'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 ), 不过-或者将它们放在单独的字典文件中，例如，如果字母太多的话，则将它们放在单独的字典文件中)。然后，确定文件名的索引（它在第一行中的位置）是否在单词的行中表示。

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

Answer 2

我觉得 if 条件有点多，你可以设法得到这样的预期结果：

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 3

您的二分查找并不是真正在寻找相等性，因此可以稍微简化一下：

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)。

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

search text using binary search in python

python

binary-search