Pesquisa binária em um arquivo de texto ordenado

Question

Eu tenho um grande arquivo classificado com bilhões de linhas de comprimentos variáveis. Dada uma nova linha, eu gostaria de saber qual número de bytes ele obteria se tivesse sido incluído no arquivo classificado.

Exemplo

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

Dada a entrada 'foo' eu obteria a saída 9.

Isso é fácil, simplesmente passando por todo o arquivo, mas sendo bilhões de linhas de comprimentos variáveis, seria mais rápido fazer uma pesquisa binária.

Essa ferramenta de processamento de texto já existe?

Editar:

Agora: link

    

Answer 1

Não estou ciente de alguma ferramenta padrão que faz isso. No entanto, você pode escrever o seu próprio. Por exemplo, o seguinte script Ruby deve fazer o trabalho.

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

É um pouco complicado, porque depois da busca você está geralmente no meio de alguma linha e, portanto, precisa fazer uma linha de leitura para chegar ao início da linha seguinte, que você pode ler e comparar com a sua chave.

    

Answer 2

(Esta não é uma resposta correta para sua pergunta, apenas um ponto de partida.)

Eu usei sgrep (grep ordenado) em uma situação semelhante.

Infelizmente (precisamos do estado atual) ele não possui uma saída de deslocamento de byte; mas acho que poderia ser facilmente adicionado.

    

Answer 3

Com base na solução Michas, aqui está um programa mais completo:

link