Pencarian biner dalam file teks yang diurutkan

13

Saya memiliki file besar yang diurutkan dengan miliaran baris panjang variabel. Diberikan baris baru saya ingin tahu nomor byte yang akan didapat jika sudah dimasukkan dalam file yang diurutkan.

Contoh

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

Diberikan input 'foo' saya akan mendapatkan output 9.

Ini mudah dilakukan dengan hanya menelusuri seluruh file, tetapi karena miliaran baris panjang variabel akan lebih cepat untuk melakukan pencarian biner.

Apakah alat pengolah teks seperti itu sudah ada?

Edit:

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

text-processing search Ole Tange
sumber
berapa lama baris yang Anda cari (dalam karakter)? dan berapa banyak baris seperti itu yang perlu Anda cari?
gogoud
@ gogoud Saya tidak mencari alat terbatas, tetapi alat yang bisa digunakan pada sembarang file teks (tidak peduli panjang baris atau jumlah baris).
Ole Tange
bagi mereka yang mungkin ingin menghasilkan input raksasa seperti itu: unix.stackexchange.com/a/279098/9689
Grzegorz Wierzowiecki

Jawaban:

4

Saya tidak mengetahui beberapa alat standar melakukan ini. Namun Anda dapat menulis sendiri. Misalnya skrip ruby ​​berikut harus melakukan pekerjaan.

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

Agak sulit karena setelah pencarian Anda biasanya berada di tengah-tengah beberapa baris dan oleh karena itu perlu melakukan satu readline untuk sampai ke awal baris berikut, yang dapat Anda baca dan bandingkan dengan kunci Anda.

michas
sumber
Bisakah diubah untuk menerima -n / -r untuk memproses file yang diurutkan berdasarkan sort -rdan sort -n?
Ole Tange
Kode di atas terutama untuk menunjukkan ide. Jauh dari sempurna. (Misalnya gagal jika kunci masuk ke tempat pertama.) Jangan ragu untuk beradaptasi dengan kebutuhan Anda.
michas
5

(Ini bukan jawaban yang benar untuk pertanyaan Anda, hanya titik awal.)

Saya menggunakan sgrep ( sortir grep) dalam situasi yang sama.

Sayangnya (kita memerlukan kondisi saat ini) tidak memiliki output byte-offset; tapi saya pikir itu bisa dengan mudah ditambahkan.

Joao
sumber