☰

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

tag-icon • tag-icon text-processing search
在已排序的文本文件中进行二分查找

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

例子

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

给定输入“foo”，我将得到输出 9。

只需遍历整个文件就可以很容易地做到这一点，但是由于有数十亿行的可变长度，因此进行二分搜索会更快。

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

编辑：

现在是这样：https://gitlab.com/ole.tange/tangetools/blob/master/2search

答案1

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

我用了sgrep(sorted grep) 在类似的情况下。

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

答案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 才能到达下一行的开头，您可以读取该行并将其与您的密钥进行比较。

答案3

基于 Michas 解决方案，这里是一个更完整的程序：

https://gitlab.com/ole.tange/tangetools/-/tree/master/2search

答案4

我经常想从一个非常大的排序日志文件中提取给定日期之后的所有记录。读取整个文件以线性方式查找日期花费的时间太长。

十几年前我匆匆修改过看有两个新选项可以让这一切变得简单：

-a: print all lines after the target line
-n: print nearest match if target is not found

假设日志文件已排序，则look -b -a -n可以对给定日期（或最接近该日期的行）进行非常快速的二分搜索，然后输出从该点到文件末尾的所有记录。

在过去的十几年里，肯定有人比我做得更好吧？

相关内容