Tengo un archivo de texto grande que necesito para buscar una cadena específica. ¿Hay una forma rápida de hacerlo sin leer línea por línea?¿Cómo se busca un archivo de texto grande para una cadena sin ir línea por línea en C#?
Este método es extremadamente lento debido al tamaño de los archivos (más de 100 MB).
Dado el tamaño de los archivos, ¿realmente le gustaría leerlos completamente en la memoria de antemano? Línea por línea es probable que sea el mejor enfoque aquí.
En todos los casos, tendrá que revisar todo el archivo.
Búsqueda Rabin-Karp string search o similar.
No necesariamente cada vez que lo busca. Si el mismo archivo se va a buscar muchas veces, probablemente tendría sentido crear un índice del archivo, por lo que solo tendría que haber una sola pasada sobre el archivo completo para permitir cualquier número de búsquedas rápidas. –
Si desea acelerar la lectura línea por línea, puede crear una aplicación basada en cola:
Un hilo lee las líneas y las pone en una fila de espera segura. Un segundo puede entonces procesar las cadenas
Tengo un archivo de texto grande que necesito para buscar una cadena específica. ¿Hay una forma rápida de hacerlo sin leer línea por línea?
La única manera de evitar buscar en todo el archivo es ordenar u organizar la entrada de antemano. Por ejemplo, si se trata de un archivo XML y necesita hacer muchas de estas búsquedas, tendría sentido analizar el archivo XML en un árbol DOM. O si esta es una lista de palabras y estás buscando todas las palabras que comienzan con las letras "aero", podría tener sentido ordenar toda la entrada primero si haces mucho de ese tipo de búsqueda en el mismo archivo .
El problema de velocidad aquí podría ser la velocidad utilizada para cargar el archivo en la memoria antes de realizar la búsqueda. Intente crear un perfil de su aplicación para ver dónde está el cuello de botella. Si está cargando el archivo, podría intentar "fragmentar" la carga del archivo para que el archivo se distribuya en pequeños fragmentos y cada fragmento tenga la búsqueda realizada en él.
Obviamente, si la parte de la cadena que se encuentra está al final del archivo, no habrá ganancia de rendimiento.
Puede almacenar una gran cantidad de datos del archivo en la memoria de una vez, hasta cualquier restricción que desee, y luego buscar la cadena.
Esto tendría el efecto de reducir el número de lecturas en el archivo y probablemente sería un método más rápido, pero sería más de memoria si configura el tamaño del búfer demasiado alto.
Debería poder leer el carácter carácter por carácter que coincide con cada carácter en la cadena de búsqueda hasta que llegue al final de la cadena de búsqueda en cuyo caso tiene una coincidencia. Si en algún momento el personaje que leyó no coincide con el personaje que está buscando, restablezca el conteo correspondiente a 0 y comience nuevamente. Por ejemplo (**** pseudocódigo/**** no probado):
byte[] lookingFor = System.Text.Encoding.UTF8.GetBytes("hello world");
int index = 0;
int position = 0;
bool matchFound = false;
using (FileStream fileStream = new FileStream(fileName, FileMode.Open))
{
while (fileStream.ReadByte() == lookingFor[index])
{
index++;
if (index == lookingFor.length)
{
matchFound = true;
position = File.position - lookingFor.length;
break;
}
}
}
Ese es uno de los muchos algoritmos que podría utilizar (aunque puede ser apagado por uno con la comprobación de longitud). Solo encontrará la primera coincidencia, por lo que probablemente desee ajustar el ciclo while en otro ciclo para encontrar varias coincidencias.
Además, una cosa a tener en cuenta acerca de la lectura del archivo línea por línea es que si la cadena deseada para hacer coincidir líneas de trazos no la va a encontrar.Si está bien, entonces puede buscar línea por línea, pero si necesita cadenas de búsqueda para abarcar líneas, querrá usar un algoritmo como el detallado anteriormente.
Por último, si está buscando la mejor velocidad, lo que parece que es, querrá migrar el código anterior para usar un StreamReader o algún otro lector de búfer.
¿Su proyecto necesita buscar diferentes archivos para la misma cadena o una cadena diferente cada vez, o buscar el mismo archivo para diferentes cadenas cada vez?
Si es el último, podría crear un índice del archivo. Pero no tiene sentido hacer esto si el archivo cambia con frecuencia, porque construir el índice será costoso.
Para indexar un archivo para búsqueda de texto completo, puede usar la biblioteca Lucene.NET.
FYI, su enlace está roto – musefan
Si sólo estás buscando una cadena específica, yo diría que la línea por línea es la mejor y más eficiente mecanismo. Por otro lado, si va a buscar varias cadenas, particularmente en varios puntos diferentes de la aplicación, es posible que desee consultar Lucene.Net para crear un índice y luego consultar el índice. Si se trata de una ejecución única (es decir, no tendrá que volver a consultar el mismo archivo más adelante), puede crear el índice en un archivo temporal que el sistema limpiará automáticamente (por lo general, el tiempo de arranque; puede eliminarlo usted mismo cuando su programa se cierra). Si necesita buscar el mismo archivo nuevamente más adelante, puede guardar el índice en una ubicación conocida y obtener un rendimiento mucho mejor la segunda vez.
Colóquelo en SQL Server 2005/2008 y use su capacidad de búsqueda de texto completo.
Aquí está mi solución que usa una secuencia para leer en un carácter a la vez. Creé una clase personalizada para buscar el valor de un carácter a la vez hasta encontrar el valor completo.
Realicé algunas pruebas con un archivo de 100 MB guardado en una unidad de red y la velocidad depende totalmente de qué tan rápido pueda leer en el archivo. Si el archivo se almacenó en un búfer en Windows, la búsqueda del archivo completo tomó menos de 3 segundos. De lo contrario, podría tomar de 7 segundos a 60 segundos, dependiendo de la velocidad de la red.
La búsqueda en sí tomó menos de un segundo si se ejecutó contra una cadena en la memoria y no había caracteres coincidentes. Si muchos de los personajes principales encontrados coinciden con la búsqueda podría tomar mucho más tiempo.
public static int FindInFile(string fileName, string value)
{ // returns complement of number of characters in file if not found
// else returns index where value found
int index = 0;
using (System.IO.StreamReader reader = new System.IO.StreamReader(fileName))
{
if (String.IsNullOrEmpty(value))
return 0;
StringSearch valueSearch = new StringSearch(value);
int readChar;
while ((readChar = reader.Read()) >= 0)
{
++index;
if (valueSearch.Found(readChar))
return index - value.Length;
}
}
return ~index;
}
public class StringSearch
{ // Call Found one character at a time until string found
private readonly string value;
private readonly List<int> indexList = new List<int>();
public StringSearch(string value)
{
this.value = value;
}
public bool Found(int nextChar)
{
for (int index = 0; index < indexList.Count;)
{
int valueIndex = indexList[index];
if (value[valueIndex] == nextChar)
{
++valueIndex;
if (valueIndex == value.Length)
{
indexList[index] = indexList[indexList.Count - 1];
indexList.RemoveAt(indexList.Count - 1);
return true;
}
else
{
indexList[index] = valueIndex;
++index;
}
}
else
{ // next char does not match
indexList[index] = indexList[indexList.Count - 1];
indexList.RemoveAt(indexList.Count - 1);
}
}
if (value[0] == nextChar)
{
if (value.Length == 1)
return true;
indexList.Add(1);
}
return false;
}
public void Reset()
{
indexList.Clear();
}
}
El método más rápido para buscar es el Boyer-Moore algorithm. Este método no requiere leer todos los bytes de los archivos, pero requiere acceso aleatorio a los bytes. Además, este método es simple en la realización.
Como ya dijo Wayne Cornish: Leer línea por línea podría ser el mejor enfoque.
Si lee, por ejemplo, todo el archivo en una cadena y luego busca con una expresión regular, podría ser más elegante, pero creará un objeto de cadena grande.
Este tipo de objetos pueden causar problemas, ya que se almacenarán en el Gran montón de objetos (LOH, para objetos de más de 85,000 bytes). Si analiza muchos de estos archivos grandes y su memoria es limitada (x86), es probable que se encuentre con problemas de fragmentación de LOH.
=> ¡Lea mejor línea por línea si analiza muchos archivos grandes!
Aquí hay una solución simple de una función leyendo carácter por carácter. Funcionó bien para mí
/// <summary>
/// Find <paramref name="toFind"/> in <paramref name="reader"/>.
/// </summary>
/// <param name="reader">The <see cref="TextReader"/> to find <paramref name="toFind"/> in.</param>
/// <param name="toFind">The string to find.</param>
/// <returns>Position within <paramref name="reader"/> where <paramref name="toFind"/> starts or -1 if not found.</returns>
/// <exception cref="ArgumentNullException">When <paramref name="reader"/> is null.</exception>
/// <exception cref="ArgumentException">When <paramref name="toFind"/> is null or empty.</exception>
public int FindString(TextReader reader, string toFind)
{
if(reader == null)
throw new ArgumentNullException("reader");
if(string.IsNullOrEmpty(toFind))
throw new ArgumentException("String to find may not be null or empty.");
int charsRead = -1;
int pos = 0;
int chr;
do
{
charsRead++;
chr = reader.Read();
pos = chr == toFind[pos] ? pos + 1 : 0;
}
while(chr >= 0 && pos < toFind.Length);
int result = chr < 0 ? -1 : charsRead - toFind.Length;
return result < 0 ? -1 : result;
}
Espero que ayude.
¿Ha perfilado su programa? –
¿Este archivo cambia a menudo o es estático? Si es estático, puede hacer un algoritmo fuera de línea e indexarlo para que pueda alcanzar rápidamente la subsección requerida del documento en tiempo de ejecución. – Polaris878
He visto tantas sugerencias de leer el archivo parte por parte en la memoria, pero ¿cómo manejaría el encasillado donde el término de búsqueda comienza en un segmento de archivo y termina en otro? Cargue segmentos superpuestos, tal vez, si este caso sucede, la siguiente parte del fragmento debe contener el término completo – ProfK