Algoritmo para encontrar las subcadenas más comunes en una cadena

¿Hay algún algoritmo que pueda usarse para encontrar las frases más comunes (o subcadenas) en una cadena? Por ejemplo, la siguiente cadena tendría “hello world” como su frase más común de dos letras:

"hello world this is hello world. hello world repeats three times in this string!"

En la cadena de arriba, la cadena más común (después del carácter de cadena vacía, que se repite un número infinito de veces) sería el carácter de espacio .

¿Hay alguna manera de generar una lista de subcadenas comunes en esta cadena, desde la más común a la menos común?

Esta es una tarea similar al algoritmo de Nussinov y, de hecho, incluso más sencilla, ya que no permitimos ningún espacio, inserción o falta de coincidencia en la alineación.

Para la cadena A que tiene la longitud N, defina una tabla F[-1 .. N, -1 .. N] y complete usando las siguientes reglas:

  for i = 0 to N for j = 0 to N if i != j { if A[i] == A[j] F[i,j] = F [i-1,j-1] + 1; else F[i,j] = 0; } 

Por ejemplo, para BA O BA B:

AlgChart

Esto se ejecuta en O(n^2) tiempo. Los valores más grandes en la tabla ahora apuntan a las posiciones finales de las secuencias más largas autocompatibles (i – el final de una ocurrencia, j – otra). Al principio, se supone que la matriz tiene cero inicialización. He agregado una condición para excluir la diagonal que es la autocomparación más larga pero probablemente no interesante.

Pensando más, esta tabla es simétrica sobre diagonal, por lo que es suficiente para calcular solo la mitad. Además, la matriz se inicializa en cero, por lo que la asignación de cero es redundante. Eso permanece

  for i = 0 to N for j = i + 1 to N if A[i] == A[j] F[i,j] = F [i-1,j-1] + 1; 

Más corto pero potencialmente más difícil de entender. La tabla calculada contiene todas las coincidencias, cortas y largas. Puede agregar más filtros según lo necesite.

En el siguiente paso, necesita recuperar cadenas, siguiendo desde las celdas que no son cero hacia arriba y hacia la izquierda por diagonal. Durante este paso también es trivial utilizar algunos hashmap para contar el número de coincidencias de auto-similitud para la misma cadena. Con una cadena normal y una longitud mínima normal, solo se procesará un pequeño número de celdas de la tabla a través de este mapa.

Creo que usar hashmap directamente en realidad requiere O (n ^ 3) ya que las cadenas clave al final del acceso deben ser comparadas de alguna manera por la igualdad. Esta comparación es probablemente O (n).

Pitón. Esto es algo rápido y sucio, con las estructuras de datos haciendo la mayor parte del levantamiento.

 from collections import Counter accumulator = Counter() text = 'hello world this is hello world.' for length in range(1,len(text)+1): for start in range(len(text) - length): accumulator[text[start:start+length]] += 1 

La estructura del contador es un diccionario respaldado por hash diseñado para contar cuántas veces has visto algo. Agregarlo a una clave inexistente lo creará, mientras que recuperar una clave inexistente le dará cero en lugar de un error. Entonces, todo lo que tiene que hacer es iterar sobre todas las subcadenas.

solo pseudo código, y tal vez esta no es la solución más hermosa, pero resolvería así:

 function separateWords(String incomingString) returns StringArray{ //Code } function findMax(Map map) returns String{ //Code } function mainAlgorithm(String incomingString) returns String{ StringArray sArr = separateWords(incomingString); Map map; //init with no content for(word: sArr){ Integer count = map.get(word); if(count == null){ map.put(word,1); } else { //remove if neccessary map.put(word,count++); } } return findMax(map); } 

Donde el mapa puede contener una clave, el valor se empareja como en Java HashMap.

Perl, O(n²) solución

 my $str = "hello world this is hello world. hello world repeats three times in this string!"; my @words = split(/[^az]+/i, $str); my ($display,$ix,$i,%ocur) = 10; # calculate for ($ix=0 ; $ix< =$#words ; $ix++) { for ($i=$ix ; $i<=$#words ; $i++) { $ocur{ join(':', @words[$ix .. $i]) }++; } } # display foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) { print "$_: $ocur{$_}\n"; last if !--$display; } 

muestra los 10 mejores puntajes de las cadenas secundarias más comunes (en caso de empate, primero muestre la cadena de palabras más larga). Cambia $display a 1 para tener solo el resultado.
Hay n(n+1)/2 iteraciones.

Dado que para cada subcadena de una Cadena de longitud> = 2 el texto contiene al menos una subcadena de longitud 2 al menos tantas veces, solo necesitamos investigar las subcadenas de longitud 2.

 val s = "hello world this is hello world. hello world repeats three times in this string!" val li = s.sliding (2, 1).toList // li: List[String] = List(he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " t", th, hi, is, "s ", " i", is, "s ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, d., ". ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " r", re, ep, pe, ea, at, ts, "s ", " t", th, hr, re, ee, "e ", " t", ti, im, me, es, "s ", " i", in, "n ", " t", th, hi, is, "s ", " s", st, tr, ri, in, ng, g!) val uniques = li.toSet uniques.toList.map (u => li.count (_ == u)) // res18: List[Int] = List(1, 2, 1, 1, 3, 1, 5, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 1, 3, 3, 2, 4, 1, 2, 2, 1) uniques.toList(6) res19: String = "s "