Wyszukiwanie binarne w posortowanym pliku tekstowym

13

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

Ole Tange
źródło
jak długa jest linia, której szukasz (w znakach)? i ile takich linii potrzebujesz wyszukać?
gogoud,
@gogoud Nie szukam ograniczonego narzędzia, ale takiego, które działa na dowolnym pliku tekstowym (bez względu na długość linii lub liczbę linii).
Ole Tange
dla tych, którzy mogą chcieć wygenerować tak gigantyczny wkład: unix.stackexchange.com/a/279098/9689
Grzegorz

Odpowiedzi:

4

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.

michas
źródło
Czy można to zmienić, aby zaakceptować -n / -r do przetwarzania plików posortowanych według sort -ri sort -n?
Ole Tange
Powyższy kod służy głównie do pokazania pomysłu. Jest daleki od ideału. (Na przykład nie powiedzie się, jeśli klucz trafi na pierwsze miejsce.) Możesz dostosować się do swoich potrzeb.
michas,
5

(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ć.

JJoao
źródło