Búsqueda binaria en un archivo de texto ordenado

13

Tengo un gran archivo ordenado con miles de millones de líneas de longitudes variables. Dada una nueva línea, me gustaría saber qué número de byte obtendría si se hubiera incluido en el archivo ordenado.

Ejemplo

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

Dada la entrada 'foo' obtendría la salida 9.

Esto es fácil de hacer simplemente revisando todo el archivo, pero siendo miles de millones de líneas de longitudes variables, sería más rápido hacer una búsqueda binaria.

¿Ya existe una herramienta de procesamiento de texto?

Editar:

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

text-processing search Ole Tange
fuente
¿Cuánto dura la línea que está buscando (en caracteres)? ¿Y cuántas líneas necesita buscar?
gogoud
@gogoud No estoy buscando una herramienta limitada, sino una que funcione en cualquier archivo de texto (sin importar la longitud de la línea o el número de líneas).
Ole Tange
Para aquellos que quieran generar una entrada tan gigantesca: unix.stackexchange.com/a/279098/9689
Grzegorz Wierzowiecki

Respuestas:

4

No conozco alguna herramienta estándar que haga esto. Sin embargo, puedes escribir el tuyo. Por ejemplo, el siguiente script ruby ​​debería hacer el trabajo.

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

Es un poco complicado porque después de la búsqueda, generalmente estás en el medio de una línea y, por lo tanto, necesitas hacer una línea de lectura para llegar al comienzo de la siguiente línea, que puedes leer y comparar con tu clave.

michas
fuente
¿Se puede modificar para aceptar -n / -r para procesar archivos ordenados por sort -ry sort -n?
Ole Tange
El código anterior es principalmente para mostrar la idea. Está lejos de ser perfecto. (Por ejemplo, falla si la clave va al primer lugar). Siéntase libre de adaptarse a sus necesidades.
michas
5

(Esta no es una respuesta correcta a su pregunta, solo un punto de partida).

Solía sgrep (grep ordenada) en una situación similar.

Desafortunadamente (necesitamos el estado actual) no tiene una salida de byte-offset; pero creo que podría agregarse fácilmente.

JJoao
fuente