Qual é a melhor maneira de fazer uma pesquisa em um arquivo grande?

Question

Eu estou olhando para aplicar um KMP (ou similar) procurar a um arquivo grande (> 4GB).

Eu estou esperando isso para me dar problemas though.I não pode copiar tudo para a memória, porque não há espaço suficiente lá.

A minha pergunta é, qual é a melhor maneira de ir sobre como fazer esta pesquisa? Devo simplesmente criar um FILE * e fazer a pesquisa diretamente no arquivo, eu deveria copiar blocos (dizem 4k) a memória e procurar aqueles, ou qualquer outra coisa completamente?

Answer 1

Se você estiver usando uma plataforma que suporta, você pode usar mmap (). Paginação do arquivo também é uma possibilidade, mas lembre-se de manter o tampão tão grande quanto possível para reduzir o IO cima, e ter cuidado entre os limites de duas páginas (suponha que uma string é correspondente, mas é dividida pela fronteira da página)

Como alternativa, sugiro que você construa um índice de algum tipo, e usar o índice para restringir a pesquisa. Pesquisa KMP não é particularmente eficiente. Isto, obviamente, depende da natureza do seu arquivo, como ele é criado, etc.

Answer 2

Para o acesso ao arquivo que eu recomendaria a memória uso arquivo mapeado para evitar copiar os dados. É trivial em máquinas Unix. Você pode ter que dividir o mapeamento de arquivo em blocos menores, se não puder ser alocado em um bloco. Eu posso fornecer algum código se você estiver interessado.

Para a busca Eu recomendaria utilizando o href="http://www-igm.univ-mlv.fr/~lecroq/string/node14.html" rel="nofollow noreferrer"> Boyer Mais algoritmo de busca .

Answer 3

Como pesquisar diretamente no arquivo seria muito lenta, usando o buffer vai dar um desempenho muito melhor. Mas note que o buffer tem que ser maior do que o que você procura (SearchLength), é claro, e você tem que atualizar o buffer quando sendo SearchLength bytes antes do seu final.

Answer 4

Melhor abordagem é lê-la em blocos e pesquisar isso. Você deve fazer o tamanho do bloco um parâmetro, para que você possa experimentar o que dá o melhor desempenho.

No entanto, ele geralmente é mais eficiente para tentar indexar o arquivo de alguma forma, para que você não tem que procurar de forma linear ao longo de todo o arquivo. Por exemplo, KMP é um algoritmo de busca string - você está apenas à procura de occuences de uma palavra? Então você pode apenas criar uma tabela hash (no disco) das palavras e sua localização no arquivo e tem de busca muito eficiente.