estructura de datos para coincidencia de patrones en los datos grandes

Question

Problema Antecedentes

I tiene un vocabulario finito que contiene de, digamos, 10 símbolos [A-J]. Lo que significan estos símbolos no es relevante para la pregunta. Pueden ser bases de ADN, fonemas, palabras, etc.

Un elemento es una secuencia de símbolos. En este problema, todos los artículos son de la misma longitud (digamos 6). P.ej.

A C B A D J 

Tengo una tabla grande (5M) que contiene recuentos de todos los elementos de longitud 6 muestreados de algunos datos conocidos. P.ej.

A C B A D J  55 
B C B I C F  923 
A B C D E G  478 

Dando una nueva secuencia con un símbolo desconocido, mi tarea es adivinar el símbolo. En el siguiente ejemplo, ¿el símbolo que falta es ?.

B C B ? C F 

Una solución simple para adivinar ? es mirar en mi mesa y encontrar el elemento con el recuento más grande que se ajusta al patrón de B C B ? C F

Preguntas

1. ¿Qué es una buena estructura de datos para almacenar mi tabla de elementos de frecuencia para que yo manejar el espacio-tiempo de manera razonablemente eficiente? Prefiero usar menos memoria si el cálculo en tiempo de consulta es razonable. (Voy a tener muchas de esas tablas, por lo que el número 5M es solo una aproximación.)

2. ¿Cuáles son algunos detalles de implementación que pueden marcar una gran diferencia en la velocidad de procesamiento?

cosas que he pensado:

1. Hacer una cadena de cada secuencia y usar expresiones regulares para que coincida. Advertencia: 1. O (n) es inaceptable. (2) Las expresiones regulares son lentas. (3) Las cuerdas (al menos en java) están hinchadas.

2. Deje que Lucene maneje la indexación. Desactivar tfidf puntuación. Use la búsqueda de frase. Potencialmente, use los valores de conteo para la puntuación, de modo que Lucene también se encargue de la clasificación.

3. Use el prefijo y el sufijo para indexar cada elemento.

4. Utilice db (probable en la memoria) con toda la información en una/columna separada para manejar la búsqueda.

---

Actualizaciones

1. En mi aplicación real, que va a trabajar con secuencias de longitud 5,6,7,8,9,10 almacenados por separado. Simplifiqué el problema restringiéndolo a una longitud fija. De ahí la restricción/preferencia a una solución que usa menos memoria.
2. Mi tamaño del vocabulario se puede suponer que estar bajo 20.

Answer 1

Basado en el comentario de que sólo habrá 1 desconocido que puede hacer lo siguiente:

Pero sus datos en una tabla hash. Cuando necesite buscar un patrón, genere todas las combinaciones de comodines, ya que su vocabulario es limitado, esto significaría, como máximo, buscar 20 patrones. Esto suena como un truco, pero si considera las implicaciones de rendimiento de otros métodos, es difícil de superar. La búsqueda de tablas hash es O (1), 20 búsquedas es O (1) también.

Este método no es aconsejable si el número de caracteres comodín podría aumentar, aunque todavía puede funcionar bien para 2 o 3.

Una matriz de doble trie también funcionaría y puede reducir la cantidad de espacio para almacenar sus cadenas , pero el rendimiento sufriría.

Answer 2

el fin de caracterizar de forma única una nueva secuencia, dos piezas de información son necesarios: la secuencia (string) de cinco símbolos conocidos, y la posición de el símbolo desconocido. Si su alfabeto tiene 10 símbolos, entonces no puede haber más de 10^5 = 100000 cadenas únicas de cinco símbolos.

Dependiendo de sus recursos de memoria, esto puede ser lo suficientemente pequeño como para caber en una tabla hash cuyas entradas proporcionan una estructura de búsqueda para encontrar la mejor combinación (posición, símbolo). Por ejemplo:

--------- 
| BCBCF | --> { 0: <heap of symbols partially ordered by frequency>, ... } 
--------- 

Esto debería permitir una búsqueda bastante eficiente para una nueva secuencia: concatenar los símbolos conocidos, buscar la secuencia en la tabla hash, encontrar la posición del carácter desconocido, y luego devolver el símbolo que está en la parte superior del montón correspondiente.

Si puede garantizar que la estructura de búsqueda será estable (sin nueva entrada) antes de realizar cualquier búsqueda, puede exprimir un poco más la eficiencia reemplazando cada uno de los montones indexados por posición con el símbolo único que habría estado en la cima del montón. (La estructura del montón solo es necesaria durante la fase de búsqueda si ingresa nueva información que puede cambiar las frecuencias de los símbolos.)

Answer 3

Estuve entre los "todos omitiendo lo obvio" aquí.

Simplemente use cualquier búsqueda rápida de clave/valor que esté disponible para usted. Y busca todos tus valores posibles. Es un conjunto pequeño, y no tomará mucho tiempo. Cualquier otra cosa menos que almacenar sus datos 6 veces será más lento.

Si tiene un gran vocabulario posible, entonces mi respuesta anterior sería apropiada.

---

Aquí está mi vieja (y mala) respuesta.

Me gustaría pegarlos en una base de datos con múltiples índices concatenados. ¿Cuántos dependen de ti?

Como mínimo tendría 2. Tendría un índice en (col1, col2, col3, col4, col5, col6) y (col4, col5, col6, col1, col2, col3). Esto significaría que, sin importar qué columna faltaba, habría una forma de obtener sus datos y solo mirar a través de 1/1000 de los registros. Si lo desea, podría indexar (col1, col2, col3, col4, col5, col6), (col3, col4, col5, col6, col1, col2) y (col5, col6, col1, col2, col3, col4) para limitar su búsqueda a 1/10000 de los datos. Esto usa la mitad de la memoria, pero es 10 veces más rápido. (Advertencia, no garantizaré que MySQL descubra con éxito qué índice debería usar. Espero que otras bases de datos lo hagan bien, pero no lo han probado).

Si no desea utilizar un la base de datos puede usar árboles binarios equilibrados exactamente como sugerí usar los índices anteriores. Para cualquier búsqueda dada, elija el árbol que tiene el elemento faltante lo más profundo posible. Haga una búsqueda de rango. Filtra los datos devueltos solo para las filas de interés. Esto es, de hecho, exactamente lo que una buena base de datos debería hacer arriba con esos índices.

Answer 4

El db sería una solución fácil, pero otra solución es un árbol donde cada nodo elige un carácter y la hoja contendría una matriz de posibles resultados y recuentos. Entonces solo tomaría 5 pasos en el árbol para unir una cuerda. Pero crear el árbol tomaría N * C tiempo donde N es el número de elementos y C es el número de caracteres en cada elemento. Los comodines son solo un nodo en el árbol que eliminará simultáneamente un carácter de la entrada pero mantiene intactos los resultados posibles.

Answer 5

La prueba con intenta parece ser la mejor: con el número de ocurrencia de cadena en hojas puede diseñar fácilmente la función que devolverá todas las cadenas posibles con un carácter faltante en O (log n) tiempo, y luego solo itere sobre este pequeño número de cadenas, buscando el número máximo de ocurrencias. Si usa caracteres de A a Z, habrá como máximo 26 de tales cadenas, por lo que iterar no requerirá mucho.

yo sepa, Lucene utiliza como mecanismo interno para su wildcards search, por lo que puede concatenar sus caracteres, índice con KeywordAnalyzer (omitir derivados) y luego buscar como "ACB? DJ". La única restricción aquí es que Lucene no puede manejar las búsquedas con el primer "?", Pero puede eludirlo agregando un carácter adicional al comienzo (solo haga un truco para eludir las comprobaciones Lucene) o teniendo un índice más para las palabras invertidas (aumentará el rendimiento para palabras con comodín como primer char mucho).

Y, finalmente, si primero tiene que calcular el número de ocurrencias de todos modos, puede usar algunos esquemas de aprendizaje automático como árboles de decisión para manejar todo el trabajo. Hubo casos en que los árboles de decisión se usaron para comprimir la base de datos y acelerar la búsqueda, por lo que puede hacer lo mismo. Use líneas como instancias, posición de caracteres como atributos y caracteres en sí mismos como valores de atributo. Luego ejecute algún algoritmo como C4.5 (puede usar la implementación Weka's llamada J48) con una poda mínima y una clasificación de ejecución: ¡el algoritmo hará el resto!