Algoritmos de búsqueda de subcadenas (gran haystack, aguja pequeña)

Question

Sé que ya hay varias preguntas similares aquí, pero necesito algunas recomendaciones para mi caso (no pude encontrar nada similar).

Tengo que buscar una gran cantidad de datos para una subcadena que sería aproximadamente mil millones de veces más pequeña (10 bytes en 10 mil millones de bytes). El pajar no cambia, por lo que puedo soportar una gran precomputación si es necesario. Solo necesito que la parte de búsqueda sea lo más rápida posible.

I conocer algoritmos que tienen O (n) tiempo (n = tamaño pajar, m = tamaño de la aguja), y la búsqueda ingenua toma O (n + m). Como el m en este caso particular sería muy pequeño, ¿hay algún otro algoritmo que pueda analizar?

Edit: Gracias a todos por sus sugerencias! Algo más de información - Los datos podrían considerarse bits aleatorios, por lo que no creo que sea posible ningún tipo de indexación/clasificación. Los datos que se buscarán pueden ser cualquier cosa, no palabras en inglés ni nada predecible.

Answer 1

Está buscando la estructura de datos llamada Trie o "árbol de prefijos". En resumen, esta estructura de datos codifica todos los posibles prefijos de cadena que se pueden encontrar en su corpus.

Here is a paper que busca secuencias de ADN para una subcadena pequeña, utilizando un árbol de prefijos. Me imagino que eso podría ayudarte, ya que tu caso suena similar.

Si conoce un límite definido en la longitud de la cadena de búsqueda de entrada, puede limitar el crecimiento de su Trie para que no almacene ningún prefijo más largo que esta longitud máxima. De esta forma, es posible que pueda incluir un Trie que represente todos los 10G en menos de 10G de memoria. Especialmente para datos altamente repetitivos, cualquier tipo de Trie es una representación de datos comprimida. (O bien debe ser, si se implementa correctamente). Limitar la profundidad Trie a la cadena de búsqueda de entrada máxima le permite limitar aún más el consumo de memoria.

Answer 2

Si puede pagar el espacio (¡mucho espacio!) Para crear un índice, definitivamente valdría la pena indexar trozos pequeños (por ejemplo, cuatro bloques de bytes) y almacenarlos con sus desplazamientos dentro del pajar, entonces las búsquedas de 10 bytes implican buscar los cuatro bloques de bytes para los primeros cuatro bytes del término de búsqueda y verificar los siguientes seis bytes.

Answer 3

Vale la pena mirar suffix arrays y trees. Ambos requieren precomputación y memoria significativa, pero son mejores que los índices inversos en el sentido de que puede buscar subcadenas arbitrarias en O(m) (para árboles de sufijos) y O(m + log n) (para arreglos de sufijos con la información de prefijo menos común).

Si tiene mucho de tiempo en sus manos, usted puede mirar en compressed suffix arrays y sucintas CSA que son versiones de sus datos que también son auto-indexación comprimido (es decir, los datos es también el índice, no hay índice externo). Este es realmente el mejor de todos los mundos porque no solo tiene una versión comprimida de sus datos (puede tirar los datos originales) sino que también está indexado. El problema es comprender los documentos de investigación y traducirlos al código :)

Si no necesita la coincidencia de subcadenas perfecta, sino capacidades de búsqueda generales, consulte Lucene.

Answer 4

Teniendo en cuenta que Knuth-Morris-Pratt o Boyer-Moore no lo van a hacer mejor, lo que debería considerar es la paralelización de su proceso de búsqueda.

Answer 5

de prefijo/sufijo árbol son generalmente la norma, mejor y más prudente solución para este tipo de cosas en mi opinión. No puedes equivocarte con ellos.

Pero aquí hay una idea diferente, que recurre a Bloom filters. Probablemente sepas qué son, pero por las dudas (y para otras personas que lean esta respuesta): los filtros Bloom son vectores de bits muy pequeños y muy compactos que se aproximan a la inclusión del conjunto. Si usted tiene un conjunto S y un filtro Bloom para ese conjunto B (S), entonces

x ∈ S ⇒ x ∈ B(S) 

pero el movimiento alternativo que es falso. Esto es lo que es probabilístico sobre la estructura: existe una probabilidad (quantifiable) de que el filtro Bloom devuelva un falso positivo. Pero aproximar la inclusión con el filtro Bloom es salvajemente más rápido que probarlo exactamente en el conjunto.

(Un caso sencillo utilizar: en muchas aplicaciones, se utiliza el filtro Bloom, así, como un filtro Comprobación de caché es caro, porque hay que hacer un acceso al disco duro, por lo que programas como. Squid primero verificará un pequeño filtro Bloom en la memoria, y si el filtro Bloom arroja un resultado positivo, Squid revisará el caché. Si fue falso positivo, está bien, porque Squid lo descubrirá cuando visite el caché. --- pero la ventaja es que el filtro Bloom habrá evitado que Squid tenga que verificar la memoria caché para un montón de solicitudes donde habría sido inútil.)

Los filtros Bloom se usaron con cierto éxito en la cadena buscar. Aquí hay un boceto (puedo recordar algunos de los detalles incorrectos) de esta aplicación. Un archivo de texto es una secuencia de N líneas. Está buscando una palabra compuesta de M letras (y ninguna palabra se puede extender entre dos líneas). Una fase de preprocesamiento generará un filtro ONE Bloom para cada línea, agregando cada subsecuencia de la línea al filtro Bloom; por ejemplo, para esta línea

Touching this dreaded sight, twice seene of vs, 

Y el filtro Bloom correspondiente será creado con "T", "A", "Tou" ... "o", "ou", ... "vs, "," s "," s ",", ". (Es posible que tenga esta parte incorrecta. O tal vez desee optimizar.)

Luego, cuando busque la subpalabra de tamaño M, simplemente haga una comprobación muy rápida de cada uno de los filtros Bloom, y cuando haya un golpe, examina la línea de cerca con el algoritmo KMP, por ejemplo. En la práctica, si sintoniza bien sus filtros Bloom, la compensación es notable. La búsqueda es increíblemente rápida porque eliminas todas las líneas inútiles.

Creo que a partir de este concepto podría derivar un esquema útil para su situación. En este momento, veo dos evidente adaptación:

• o bien cortar su conjunto de datos en muchos bloques de tamaño K (cada uno con su filtro Bloom, como las líneas en el ejemplo anterior);

• o utilice una especie de dicotomía en la que divide el conjunto en dos subconjuntos, cada uno con un filtro Bloom, luego cada subconjunto se divide en dos subconjuntos secundarios con su propio filtro Bloom, etc. (si va a agregue todas las subcadenas según lo sugerido con el método que describí, esta segunda idea sería un poco prohibitiva, excepto que no tiene que agregar todas las subcadenas, solo las subcadenas que varían del 1 al 10).

Ambas ideas se pueden combinar de forma ingeniosa para crear esquemas de varias capas.