Procurando por uma string em um fluxo de entrada

9

Eu tenho um arquivo binário grande (muitos gigabytes, então carregá-lo na memória não é uma opção) que eu quero procurar por todas as ocorrências da string "icpf".

Eu tentei usar std::search para isso, mas acabei sendo mordido pelo fato de que std::search só funciona para iteradores avançados, não para iteradores de entrada.

A biblioteca padrão fornece uma alternativa rápida para isso? Ou preciso codificar manualmente a pesquisa (ler em partes de uma vez e std::search , ou ignore tudo até um 'i' e depois verificar manualmente os próximos três caracteres)?

    
por zennehoy 22.02.2016 в 18:32
fonte

3 respostas

1
  

A biblioteca padrão fornece uma alternativa rápida para isso?

Embora a biblioteca C ++ padrão ofereça formas de pesquisar fluxos de texto, ela não oferece algoritmos comparáveis para fluxos binários.

  

Ou preciso codificar manualmente a pesquisa (ler em blocos de uma vez e std::search , ou ignorar tudo até um 'i' e depois verificar manualmente os próximos três caracteres)?

Codificar a abordagem "ignorar e pesquisar" pode ser complicado, porque é fácil codificar uma solução que ignore as entradas. Por exemplo, se você estiver procurando por "icpf" em um arquivo contendo "icpicpf" , um programa simples que processa um caractere de cada vez não encontrará o sufixo "icpf" depois de descartar o prefixo "icpi" .

Se você for codificar isso sozinho, considere implementar Knuth Algoritmo –Morris – Pratt . Existem muitas implementações disponíveis on-line e ela opera corretamente em fluxos, porque considera um caractere por vez e nunca retorna.

    
por dasblinkenlight 22.02.2016 / 18:56
fonte
1

O método mais rápido é carregar o arquivo inteiro na memória e depois pesquisar a memória.

A próxima melhor alternativa é manter o disco rígido em movimento. Talvez tenha um thread que lê pedaços de dados em um buffer e outro thread que pesquisa o buffer.

Descendo a lista, lendo grandes blocos de dados em um buffer, pesquisar o buffer é uma boa técnica, embora não tão eficiente quanto os métodos anteriores.

Você pode ler linha por linha, usando std::getline e std::string . Isso não é tão rápido quanto a leitura de bloco porque a função de entrada está procurando o caractere de nova linha (e alocando memória no std::string ).

O pior caso é provavelmente ler personagem por personagem. A sobrecarga de função é ruim para a leitura de um único caractere (geralmente a sobrecarga é a mesma para a leitura de um grande bloco de dados).

Não, não há nenhuma função de biblioteca C ++ padrão para pesquisar arquivos. Alguns sistemas operacionais têm utilitários para pesquisar arquivos; talvez você possa usar um desses.

Editar 1:
O gargalo está inserindo os dados. Depois de obter os dados em um buffer, há muitos algoritmos de pesquisa eficientes em vez da força bruta (procurando pela primeira letra, depois procurando as próximas letras, etc.).

Pesquise na internet por "algoritmo de busca de string".

    
por Thomas Matthews 22.02.2016 / 18:40
fonte
0

Eu não conheço nenhuma solução de biblioteca padrão pura, mas o kernel já implementa a pré-busca, então deve ser possível mmap() o arquivo para obter os iteradores avançados: (tratamento de erros omitido)

size_t search(int fd, size_t fileSize) {
    auto start = reinterpret_cast<char*>(
        ::mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0));
    ::madvise(start, fileSize, MADV_SEQUENTIAL);
    auto pattern = "icpf";
    auto offset = std::search(start, start+fileSize, pattern, pattern+4);
    return offset - start;
}

É um pequeno passo de fé, confiando em seu kernel para fazer o carregamento lento, pré-buscar e descartar corretamente. Por outro lado, se você puder confiar em alguém com isso, provavelmente seriam desenvolvedores do kernel.

Aviso: na verdade, eu não testei isso em um arquivo com vários gigabytes.

    
por Benno 22.02.2016 / 19:37
fonte