在已排序的文本文件中进行二分查找

Question

我有一个包含数十亿行可变长度的大排序文件。给定一个新行，我想知道如果它已包含在排序文件中，它将获得哪个字节数。

例子

a\n
c\n
d\n
f\n
g\n

给定输入 'foo' 我会得到输出 9。

这很容易通过简单地遍历整个文件来完成，但是由于数十亿行的可变长度，进行二分搜索会更快。

这样的文本处理工具是否已经存在？

编辑：

现在可以了：https : //gitlab.com/ole.tange/tangetools/blob/master/2search

Answer 1

（这不是您问题的正确答案，只是一个起点。）

我在类似的情况下使用了sgrep（排序的 grep）。

不幸的是（我们需要当前状态）它没有字节偏移量输出；但我认为它可以很容易地添加。

Answer 2

我不知道有什么标准工具可以做到这一点。不过你可以自己写。例如，下面的 ruby​​ 脚本应该可以完成这项工作。

file, key = ARGV.shift, ARGV.shift
min, max = 0, File.size(file)

File.open(file) do |f|
  while max-min>1 do
    middle = (max+min)/2
    f.seek middle
    f.readline
    if f.eof? or f.readline>=key
      max = middle
    else
      min = middle
    end
  end
  f.seek max
  f.readline
  p f.pos+1
end

这有点棘手，因为在查找之后，您通常位于某行的中间，因此需要执行一个 readline 才能到达下一行的开头，您可以读取该行并将其与您的密钥进行比较。