Pesquisa binária em um arquivo de texto classificado

13

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 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, basta percorrer todo o arquivo, mas, sendo bilhões de linhas de tamanhos variáveis, seria mais rápido fazer uma pesquisa binária.

Essa ferramenta de processamento de texto já existe?

Editar:

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

text-processing search Ole Tange
fonte
quanto tempo a linha que você está procurando (em caracteres)? e quantas linhas você precisa procurar?
gogoud
@ gogoud Não estou procurando uma ferramenta limitada, mas uma que funcione em qualquer arquivo de texto (não importa o comprimento da linha ou o número de linhas).
quer
para aqueles que gostariam de gerar tais entrada gigantesca: unix.stackexchange.com/a/279098/9689
Grzegorz Wierzowiecki

Respostas:

4

Não estou ciente de alguma ferramenta padrão fazer 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, após a busca, você geralmente fica 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.

michas
fonte
Pode ser alterado para aceitar -n / -r para processar arquivos classificados por sort -re sort -n?
quer
O código acima é principalmente para mostrar a ideia. Está longe de ser perfeito. (Por exemplo, falha se a chave for o primeiro lugar.) Sinta-se à vontade para se adaptar às suas necessidades.
Michas5 /
5

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

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

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

JJoao
fonte