Estructura de datos eficiente para la búsqueda de subcadenas?

Supongamos que tengo un conjunto de cadenas S y una cadena de consulta q. Quiero saber si algún miembro de S es una subcadena de q. (A los efectos de esta pregunta subcadena incluye la igualdad, por ejemplo, "foo" es una subcadena de "foo"). Por ejemplo asume la función que hace lo que yo quiero que se llama anySubstring:Estructura de datos eficiente para la búsqueda de subcadenas?

S = ["foo", "baz"] 
q = "foobar" 
assert anySubstring(S, q) # "foo" is a substring of "foobar" 

S = ["waldo", "baz"] 
assert not anySubstring(S, q)

¿Hay alguna fácil- implementar algoritmo para hacer esto con complejidad de tiempo sublineal en len(S)? Está bien si S tiene que procesarse primero en una estructura de datos inteligente porque voy a consultar cada S con muchas cadenas q, por lo que el costo amortizado de este preproceso podría ser razonable.

EDITAR: Para aclarar, no me importa que miembro de S es una subcadena de q, solo si al menos uno es. En otras palabras, I solo se preocupan por una respuesta booleana.

Fuente

2012-03-09 dsimcha

¿Las cadenas en S son cortas? ¿Cómo se compara la longitud de la cuerda más larga en S con la longitud de S? – aelguindy

Entonces, si la longitud de S es mucho menor que la suma de las posibles subcadenas, su mejor opción sería construir un suffix tree desde S y luego hacer una búsqueda en él. Esto es lineal con respecto a la longitud de S más la longitud resumida de las subcadenas candidatas. Por supuesto, no puede haber un algoritmo con una mayor complejidad, ya que tiene que pasar al menos por todas las entradas. Si el caso es opuesto, es decir, la longitud de s es mayor que la longitud resumida de las subcadenas, su mejor opción sería aho-corasick.

Espero que esto ayude.

Fuente

2012-03-09 15:25:43

Se ajusta al revés: consultar muchas veces con un solo 'q', pero aquí, el' S' es constante y 'q' está cambiando ... – amit

@amit Creo que Aho-Corasick hace lo que OP quiere ... Funciona muy parecido a su solución, excepto que el trie tiene transiciones de fallas que lo llevan a la posición correcta en el autómata. – aelguindy

@aelguindy: Estaba hablando solo del enfoque del árbol de sufijos, me temo que no estoy familiarizado con el algoritmo mencionado, pero leeré cómo funciona más tarde. – amit

Creo que Aho-Corasick algorithm hace lo que quiere. Creo que hay otra solución que es muy simple de implementar, es Karp-Rabin algorithm.

Fuente

2012-03-09 16:15:24 aelguindy

No puedo creer que sea la única persona que vote la respuesta correcta. – Nemo

Crea una expresión regular .*(S1|S2|...|Sn).* y crea su DFA mínimo.

Ejecute su cadena de consulta a través del DFA.

Fuente

2012-03-09 22:23:44

-1 ¿cómo esto es eficiente? –

@SaeedAmiri Si a OP no le importa en absoluto la eficacia del preprocesamiento, una vez que se crea el DFA, todas las consultas se ejecutan en tiempo lineal en la longitud de q, independientemente de cualquier aspecto de S. – aelguindy

@aelguindy, el árbol de sufijo funciona en un orden similar con menos factor constante y menos memoria, de hecho, debe convertir su DFA finalmente a algo así como trie. –

Estructura de datos eficiente para la búsqueda de subcadenas?

Respuesta

Cuestiones relacionadas