algorithm - usados - que es la edicion de texto
Búsqueda rápida de editor de texto (4)
¿Alguien sabe cómo los editores de textos / editores de programadores pueden hacer búsquedas tan rápidas en archivos de texto muy grandes?
¿Están indexando en carga, al comienzo del hallazgo o alguna otra técnica inteligente?
Necesito desesperadamente una implementación más rápida de lo que tengo, que es una caminata desesperadamente lenta de arriba hacia abajo del texto.
Cualquier idea es realmente apreciada.
Esto es para una implementación C #, pero es la técnica que me interesa más que el código real.
grep
Aunque no es un editor de texto en sí mismo, pero a menudo lo llaman muchos editores de texto. Tengo curiosidad si has probado el código fuente de grep? Siempre me ha parecido tremendamente rápido, incluso cuando busco archivos de gran tamaño.
Comience con el algoritmo de búsqueda de Boyer-Moore . Requiere un preprocesamiento (que es rápido) y realiza búsquedas bastante bien, especialmente cuando se buscan subcadenas largas.
No me sorprendería que la mayoría simplemente use la técnica de búsqueda básica e ingenua (escanea en busca de una coincidencia en el 1er carbón, luego prueba si el golpe sale).
Uno de los métodos que conozco que aún no se menciona, es el Knuth-Morris-Pratt-Search (KMP), pero no es tan bueno para los textos de lenguaje (se debe a una propiedad de prefijo del algoritmo), pero para cosas como el ADN coincidente Está muy, muy bien.
Otro es un hash-Search (no sé si hay un nombre oficial). Primero calcules un valor hash de tu patrón y luego creas una ventana deslizante (con el tamaño de tu patrón) y la mueves sobre tu texto para ver si los hashes coinciden. La idea aquí es elegir el hash de una manera que no tenga que calcular el hash para la ventana completa, pero actualice su hash solo con el siguiente char (y el viejo char descarta el cálculo del hash). Este algoritmo funciona muy bien, cuando tiene que buscar varias cadenas (porque acaba de calcular de antemano sus hashes para sus cadenas).