☰

ソートされたテキストファイルのバイナリ検索

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

（これはあなたの質問に対する正解ではなく、ただの始点です。）

使ったスグレフ（ソートされた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

私は非常に大きなソートログファイルから特定の日付以降のすべての履歴を抽出したいことがよくあります。直線的な方法で日付を見つけるためにファイル全体を読み取るのに時間がかかりすぎます。

10年以上前に急いで修正しました。バラよりこれを簡単に実行できる2つの新しいオプションがあります。

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

ログファイルがソートされていると仮定すると、特定のlook -b -a -n日付（またはその日付に最も近い行）に対して非常に高速なバイナリ検索を実行し、その時点からファイルの終わりまですべてのレコードを出力できます。

明らかに、過去10年以上にわたって私よりも上手な人がいるでしょう。そうですか？

関連情報