Wyszukiwanie binarne w posortowanym pliku tekstowym

Mam duży posortowany plik z miliardami linii o zmiennej długości. Biorąc pod uwagę nowy wiersz, chciałbym wiedzieć, który numer bajtu by się otrzymał, gdyby został uwzględniony w posortowanym pliku.

Przykład

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

Biorąc pod uwagę wejście „foo”, otrzymałbym wynik 9.

Łatwo to zrobić, po prostu przeglądając cały plik, ale mając miliardy linii o zmiennej długości, szybsze byłoby wyszukiwanie binarne.

Czy takie narzędzie do przetwarzania tekstu już istnieje?

Edytować:

Teraz działa: https://gitlab.com/ole.tange/tangetools/blob/master/bsearch/bsearch

Nie wiem, czy robi to jakieś standardowe narzędzie. Możesz jednak pisać własne. Na przykład poniższy skrypt ruby ​​powinien wykonać zadanie.

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

Jest to trochę trudne, ponieważ po wyszukiwaniu zwykle znajdujesz się w środku linii i dlatego musisz zrobić jedną linię odczytu, aby przejść do początku następnej linii, którą możesz odczytać i porównać z kluczem.

(To nie jest poprawna odpowiedź na twoje pytanie, tylko punkt wyjścia.)

Użyłem sgrep (posortowanego grep) w podobnej sytuacji.

Niestety (potrzebujemy obecnego stanu) nie ma wyjścia bajtowo-offsetowego; ale myślę, że można to łatwo dodać.

W oparciu o rozwiązanie Michas tutaj jest bardziej kompletny program:

https://gitlab.com/ole.tange/tangetools/blob/master/bsearch/bsearch