¿Cuál es la mejor manera de hacer una búsqueda en un archivo grande?
https://stackoverflow.com/questions/1212255
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy buscando aplicar una búsqueda KMP (o similar) a un archivo grande (> 4GB).
Sin embargo, espero que esto me dé problemas. No puedo copiarlo todo a la memoria porque no hay suficiente espacio allí.
Mi pregunta es, ¿cuál es la mejor manera de hacer esta búsqueda? ¿Debo simplemente crear un ARCHIVO * y hacer la búsqueda directamente en el archivo, debo copiar bloques (digamos 4k) a la memoria y buscarlos, o algo completamente diferente?
Solución
Si está utilizando una plataforma que lo admite, puede usar mmap (). La paginación del archivo también es una posibilidad, pero recuerde mantener el búfer lo más grande posible para reducir la sobrecarga de E / S y tener cuidado entre los límites de dos páginas (suponga que una cadena coincide, pero está dividida por el límite de la página)
Alternativamente, le sugiero que cree un índice de algún tipo y use el índice para restringir la búsqueda. La búsqueda de KMP no es particularmente eficiente. Por supuesto, esto depende de la naturaleza de su archivo, cómo se crea, etc.
Otros consejos
Para el acceso a archivos, recomendaría usar un archivo de memoria asignada para evitar la copia de datos. Es trivial en máquinas Unix. Es posible que deba dividir la asignación de archivos en bloques más pequeños si no se puede asignar en un bloque. Puedo proporcionarle un código si está interesado.
Para la búsqueda, recomendaría usar el Boyer Más algoritmo de búsqueda .
La búsqueda directa en el archivo sería muy lenta, el uso del almacenamiento en búfer proporcionará un rendimiento mucho mejor. Pero tenga en cuenta que su búfer debe ser más grande de lo que busca ( SearchLength ), por supuesto, y debe actualizar el búfer cuando sean bytes SearchLength antes de que finalice. / p>
El mejor enfoque es leerlo en bloques y buscarlo. Debe hacer que el tamaño del bloque sea un parámetro, para que pueda experimentar con lo que ofrece el mejor rendimiento.
Sin embargo, generalmente es más eficiente intentar indexar el archivo de alguna manera para que no tenga que buscar linealmente en todo el archivo. Por ejemplo, KMP es un algoritmo de búsqueda de cadenas: ¿está buscando las ocurrencias de una palabra? Luego puede crear una tabla hash (en el disco) de las palabras y su ubicación en el archivo y tener una búsqueda muy eficiente.
