Tengo un archivo grande que contiene una cadena en cada línea. Me gustaría poder determinar rápidamente si hay una cadena en el archivo. Idealmente, esto se haría utilizando un algoritmo de corte binario.
Algunos Google revelaron el look
comando con la -b
bandera que promete localizar y generar todas las cadenas que comienzan con un prefijo dado usando un algoritmo de búsqueda binario. Desafortunadamente, no parece funcionar correctamente y devuelve resultados nulos para las cadenas que sé que están en el archivo (se devuelven correctamente mediante la grep
búsqueda equivalente ).
¿Alguien sabe de otra utilidad o estrategia para buscar este archivo de manera eficiente?
look
comando funcione correctamente, porque la apariencia parece ignorar la configuración regional y solo usa C como la ordenación codificada, también abrí un error debido a este comportamiento confuso: bugzilla.kernel.org/show_bug.cgi?id=198011look -b
falló para mí con un errorFile too large
. Creo que está tratando de leer todo en la memoria.Respuestas:
Hay una diferencia esencial entre
grep
ylook
:A menos que se indique explícitamente lo contrario,
grep
encontrará patrones incluso en algún lugar dentro de las líneas. Paralook
los estados de la página de manual:No estoy usando
look
muy a menudo, pero funcionó bien en un ejemplo trivial que acabo de probar.fuente
egrep "^TEST" sortedlist.txt | wc -l
, obtengo 41,289 resultados. Sin embargo, loslook
comandos equivalenteslook -b TEST sortedlist.txt | wc -l
solo arrojan resultados de 1995. Casi me pregunto si hay un errorlook
.look
está usando diferentes configuraciones de clasificación que el programa que usó para ordenar el archivo.Tal vez una pequeña respuesta tardía:
Sgrep te ayudará.
Sgrep (grep ordenado) busca en los archivos de entrada ordenados las líneas que coinciden con una clave de búsqueda y genera las líneas coincidentes. Al buscar archivos grandes, sgrep es mucho más rápido que el grep tradicional de Unix, pero con restricciones significativas.
Puede descargar la fuente aquí: https://sourceforge.net/projects/sgrep/?source=typ_redirect
y los documentos aquí: http://sgrep.sourceforge.net/
De otra manera:
No sé qué tan grande es el archivo. Quizás deberías intentarlo en paralelo:
/programming/9066609/fastest-possible-grep
Siempre hago grep con archivos de tamaño> 100 GB, funciona bien.
fuente
sudo apt-get install sgrep
para obtener sgrep, el sgrep en los repositorios de buntu no es realmente este sgrep, no estoy seguro de que sea lo mismo.Puede trocear el archivo en pedazos y luego grep solo la pieza que desea:
entonces la búsqueda se vería así:
Esto hace dos cosas:
fuente
sgrep podría funcionar para usted:
La página del proyecto http://sgrep.sourceforge.net/ dice:
Sin embargo, para la inserción, creo que no hay mejor solución que usar una base de datos: /programming/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/ 33859372 # 33859372
fuente
sgrep
los repositorios de Ubuntu es en realidad este sgrep , que está diseñado para "buscar un archivo para un patrón estructurado" y no tiene nada que ver con la búsqueda binaria.Si lo desea realmente rápido (O (1) rápido), puede crear un conjunto de hash para investigar. No pude encontrar una implementación que me permitiera almacenar un hash precompilado en un archivo y probarlo sin tener que leer todo el archivo en la memoria, así que hice el mío .
Construya el conjunto de hash (
-b
/--build
):Pruebe el conjunto de hash (
-p
/--probe
):... o con una cadena para buscar en la entrada estándar:
Puede silenciar la salida de
--probe
con la opción-q
/--quiet
si solo está interesado en el estado de salida:Para obtener más opciones, consulte la descripción de uso accesible a través de la opción
-h
/--help
o elREADME
archivo adjunto .fuente