Decidir si una cadena comodín coincide completamente con otra cadena comodín en un conjunto

Aquí hay un problema que me ha estado molestando por un tiempo. Digamos que una cadena es una secuencia de 1s y 0s, y una cadena comodín es una secuencia de 1, 0 y? S. Todas las cadenas y cadenas comodín tienen la misma longitud. Estos son comodines UNIX estándar; 10 ?? 1 coincide con 10011, 10111, etc. - a? coincide con un 1 o un 0 en esa posición. Si y son cadenas comodín, entonces escribimos si cada cadena que coincide con también coincide con .$v$$w$$v \leq w$$v$$w$

Los problemas : dado un conjunto de cadenas comodín, y una consulta (también una cadena comodín), ¿existe una tal que ? Y si no, ¿podemos agregar a eficiente?$S$$v$$w \in S$$v \leq w$$v$$S$

Aquí está la solución obvia (donde es el tamaño de las cadenas, es el tamaño de la palabra de RAM (generalmente 32 o 64)): revise cada elemento de la lista y pruebe la condición (que se puede hacer en 2 o 3 operaciones usando bit-twiddling). También pruebe si mantiene para cualquier elemento mientras estamos escaneando. Si falla nuestra prueba, agregue al conjunto y elimine las que marcamos.$O(\frac{k}{m}n)$$k$$m$$v \geq w$$w$$v$$v$$w$

Pero eso no es lo suficientemente rápido. Sería realmente genial si hubiera una solución o, en un mundo perfecto, una complejidad similar a un árbol de raíz ( ). También está bien que las consultas sean aproximadamente correctas : es decir, si , devuelve sí o no; pero si la condición no se cumple definitivamente devuelva no.$O(\log n)$$O(k)$$v \leq w$

Aunque esto no ayuda a la complejidad del peor de los casos, puede suponer que todos los elementos en están delimitados por una cadena comodín; es decir, existe algún tal que para todos los , .$S$$v$$w \in S$$v \geq w$

Ideas que he probado

• Las cadenas comodín forman un entramado de unión. Podríamos tener un árbol n-ary que contenga cadenas comodín; las hojas serían cadenas comodín y las ramas representarían la unión de todos los niños. Si la consulta y la unión son incomparables, entonces no tenemos que perder el tiempo tratando de comparar con todos los hijos de esa rama. Además, si realizamos una actualización y la actualización es mayor que una combinación, simplemente podemos eliminar toda la rama. Desafortunadamente, esto sigue siendo en el peor de los casos, y no siempre encontramos las "mejores" uniones que hacer al escanear a través del árbol para agregar elementos.$O(n)$
• Se podría formar un trie radix de . Sabemos que está delimitado por alguna cadena comodín; supongamos que es? 0? 0. Entonces, todas las ramas del trie solo tienen que estar en el 1er y 3er bits de las cuerdas. Si el bit actual en el que estamos bifurcando la consulta es un 1, tenemos que verificar el? y las 1 ramas; si es 0, verificamos el? y las 0 ramas; si es así, solo verificamos el? rama. Debido a que potencialmente tenemos que tomar varias ramas, esto no parece muy bueno (es difícil actualizar el trie por la misma razón). Dado que la coincidencia es una operación muy rápida, duele en comparación con la ingenua estrategia de atravesar mucho en un árbol (seguir un montón de punteros es mucho más costoso que hacer algunos OR y AND).$S$$S$

Trabajo relacionado

• En la comunidad de redes, este problema se manifiesta como "clasificación de paquetes", aquí hay una buena encuesta de los algoritmos y las estructuras de datos conocidas . Desafortunadamente, casi siempre se supone que las cadenas comodín solo coinciden con los prefijos, y la consulta es una tupla de tales cadenas. Por supuesto, siempre podemos convertir una cadena comodín general para cumplir con estos criterios: 1? 00? 1 ?? es (1,?, 0, 0,?, 1,?,?). Sin embargo, esto no sería eficiente. La otra suposición hecha es que estas tuplas están asociadas con un "color", y las consultas deberían devolver el color (no solo que coincida). Esto hace que el problema sea mucho más difícil, porque tenemos que ordenar las tuplas (o de lo contrario es ambiguo cuál de (0,?) Y (?, 1) coincide (0, 1)).

• En la comunidad de algoritmos he encontrado muchos resultados relacionados con la búsqueda de subcadenas que coinciden con "no me importa". Este es un problema considerablemente más difícil, y realmente no puedo utilizar ninguna de las técnicas.

En conclusión

¡Gracias por cualquier ayuda!

$S$$O(k)$

$S$

En cuanto a agregar cadenas a la máquina, hay un trabajo reciente sobre el cambio de un autómata de estado finito de forma incremental. Ver este artículo de Daciuk et al: "Construcción incremental de autómatas de estado finito acíclicos mínimos".

¿Esto ayuda?