ds.algorithms – Decidir si una cadena comodín coincide completamente con otra cadena comodín en un conjunto

Pregunta:

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

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

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

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

Aunque esto no ayuda a la complejidad del peor de los casos, puede asumir que todos los elementos en $ S $ están delimitados por una cadena comodín; es decir, existen algunos $ v $ tales que para todos los $ w \ en S $, $ v \ geq w $.

Ideas que he probado

  • Las cadenas de caracteres comodín forman un semirretículo de unión. Podríamos tener un árbol n-ario que contenga cadenas de caracteres comodín; las hojas serían cadenas de caracteres comodín y las ramas representarían la unión de todos los hijos. Si la consulta y la combinación son incomparables, entonces no tenemos que perder el tiempo tratando de comparar con todos los hijos de esa rama. Además, si hacemos una actualización, y resulta que la actualización es mayor que una combinación, simplemente podemos eliminar toda la rama. Desafortunadamente, esto sigue siendo $ O (n) $ en el peor de los casos, y no siempre encontramos las "mejores" combinaciones para realizar cuando escaneamos el árbol para agregar elementos.
  • Se podría formar una raíz trie de $ S $. Sabemos que $ S $ está acotado por alguna cadena comodín; suponga que es? 0? 0. Entonces, todas las ramas del trie solo tienen que estar en el primer y tercer bits de las cadenas. Si el bit actual en el que nos estamos ramificando de la consulta es un 1, tenemos que marcar el? y las 1 ramas; si es 0, comprobamos el? y las 0 ramas; si es ?, solo marcamos 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 el emparejamiento es una operación muy, muy rápida, duele en comparación con la estrategia ingenua de atravesar mucho en un árbol (seguir un montón de punteros es mucho más costoso que hacer algunos OR y AND).

Trabajo relacionado

  • En la comunidad de redes, este problema se manifiesta como "clasificación de paquetes", aquí hay un buen estudio de los algoritmos y estructuras de datos conocidos . Desafortunadamente, casi siempre se asume que las cadenas comodín solo coinciden con prefijos, y la consulta es una tupla de dichas 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 que se hace es que estas tuplas están asociadas con un "color", y la consulta debe 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 con (0, 1)).

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

En conclusión

¡Gracias por cualquier ayuda!

Respuesta:

¿Qué tal usar un autómata de estado finito? El lenguaje $ S $ es finito y, por tanto, regular. Incluso después de las transformaciones a continuación, seguirá siendo regular. Entonces, después de los pasos habituales para convertir la expresión regular en un autómata determinista de estado finito, tendrá un reconocedor de lo que desea que opere en $ O (k) $ tiempo. Con suerte, esta idea seguirá siendo viable si hay errores en lo que se propone a continuación.

La arruga es cómo tratar con el operador comodín:?. Un comodín en una cadena comodín coincide con un 0 o un 1 en una cadena de prueba. Pero dado que estamos tratando de reconocer cadenas comodín, un comodín en una cadena comodín coincide con 0, 1 o? en otra cadena comodín. Este conjunto sigue siendo regular, por lo que transformamos cada aparición de? a la expresión regular (0 | 1 |?) donde la barra vertical es el operador de alternancia habitual. Entonces, si todo su conjunto $ S $ es {10 ?? 1, 0? 1? 0}, la expresión regular resultante será (10 (0 | 1 |?) (0 | 1 |?) 1 | 0 (0 | 1 |?) 1 (0 | 1 |?) 0)

En cuanto a agregar cadenas a la máquina, hay algunos trabajos recientes para cambiar un autómata de estado finito de forma incremental. Consulte este artículo de Daciuk et al: "Construcción incremental de autómatas de estado finito acíclicos mínimos".

¿Esto ayuda?

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım