Estoy buscando una estructura de datos que almacene un conjunto de cadenas sobre un conjunto de caracteres , capaz de realizar las siguientes operaciones. Denotamos como la estructura de datos que almacena el conjunto de cadenas .D ( S ) S
Add-Prefix-Set
en : dado un conjunto de cadenas (posiblemente vacías), cuyo tamaño está limitado por una constante y cuyas longitudes de cadena están delimitadas por una constante, devuelve . Tanto estas constantes delimitadores son globales: son los mismos para todas las entradas .T D ( { t s | t ∈ T , s ∈ S } ) TGet-Prefixes
en : return . Tenga en cuenta que realmente no me importa qué estructura se utiliza para este conjunto, siempre que pueda enumerar su contenido en tiempo .{ a | a s ∈ S , a ∈ Σ } O ( | Σ | )Remove-Prefixes
en : devuelve .D ( { s | a s ∈ S , a ∈ Σ } )Merge
: dado y , devuelve .D ( S ∪ T )
Ahora, realmente me gustaría hacer todas estas operaciones en tiempo , pero estoy bien con una estructura que hace todas estas operaciones en tiempo , donde es la longitud de la cadena más larga en el estructura. En el caso de la fusión, me gustaría un tiempo de ejecución , donde es para el primero y el para la segunda estructura.o ( n ) n o ( n 1 + n 2 ) n 1 n n
Un requisito adicional es que la estructura es inmutable, o al menos que las operaciones anteriores devuelven estructuras 'nuevas' de modo que los punteros a las antiguas sigan funcionando como antes.
Una nota sobre la amortización: está bien, pero hay que estar atento a la persistencia. A medida que reutilizo estructuras viejas todo el tiempo, estaré en problemas si llego al peor de los casos con un conjunto particular de operaciones en la misma estructura (ignorando las nuevas estructuras que crea).
Me gustaría usar dicha estructura en un algoritmo de análisis en el que estoy trabajando; la estructura anterior mantendría el lookahead que necesito para el algoritmo.
Ya he considerado usar un trie , pero el problema principal es que no sé cómo fusionar los intentos de manera eficiente. Si el conjunto de cadenas para Add-Prefix-Set
consta de solo cadenas de un solo carácter, entonces podría almacenar estos conjuntos en una pila, lo que le daría tiempos de ejecución para las primeras tres operaciones. Sin embargo, este enfoque tampoco funciona para la fusión.
Finalmente, tenga en cuenta que no estoy interesado en los factores: esto es constante para todo lo que me importa.
fuente
Add-Prefix-Set
o comienzas con un conjunto arbitrario de cadenas?Add-Prefix-Set
)Respuestas:
Lo pensé durante bastante tiempo, pero no encontré el problema de hacer todas sus operaciones de la manera más estúpida posible en una estructura DAG tipo trie:
Agregar conjunto de prefijos
Crear un trie de cadenas de . Conecte cada nodo de hoja a la raíz del viejo trie.T
Complejidad:O ( | TEl | )
Unir
Unir raíces de dos estructuras: hacer que todos los nodos hijos del segundo hijo raíz del primer nodo. Ahora puede tener varias aristas marcadas con el mismo carácter desde el mismo nodo.
Complejidad:O ( 1 )
Actualización perezosa de la raíz
Obtener prefijos
Lazy actualiza la raíz. Ahora encuentre todos los elementos secundarios de la raíz e informe el conjunto de letras en los bordes que van hacia ellos.
Eliminar-prefijos
Lazy actualiza la raíz. Une a todos los hijos de la raíz y establece el puntero raíz al resultado de esta unión. Lazy actualiza la nueva raíz.
Persistencia
fuente