Encuentra la subcadena de prefijo que ofrece la mejor compresión

Question

Problema :

Dada una lista de cadenas, encuentre la subcadena que, si se resta del principio de todas las cadenas donde coincide y se reemplaza por un byte de escape, proporciona la longitud total más corta.

Ejemplo :

" foo " , " tonto " , "bar"

El resultado es: '' foo '' como la cadena base con las cadenas " \ 0 " , " \ 0l " , " bar " y una longitud total de 9 bytes " \ 0 " es el byte de escape. La suma de la longitud de las cadenas originales es 10, por lo que en este caso solo guardamos un byte.

Un algoritmo ingenuo se vería así:

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

Eso nos dará la respuesta, pero es algo así como O ((n * m) ^ 2), que es demasiado caro.

Answer 1

Usa un bosque de árboles de prefijos (trie) ...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

entonces, podemos encontrar el mejor resultado, y garantizarlo, maximizando (profundidad * frecuencia) que será reemplazado con su personaje de escape. Puede optimizar la búsqueda haciendo una búsqueda de profundidad de rama y límite para el máximo.

De la complejidad: O (C), como se menciona en el comentario, para construirlo y para encontrar el óptimo, depende. Si ordena la frecuencia de los primeros elementos (O (A), donde A es el tamaño del alfabeto de los idiomas), podrá cortar más ramas y tener una buena probabilidad de obtener un tiempo sub-lineal.

Creo que esto está claro, no voy a escribirlo, ¿qué es esto una tarea? ;)

Answer 2

Intentaría comenzar ordenando la lista. Luego, simplemente pasa de una cadena a otra comparando el primer carácter con el primer carácter de la siguiente cadena. Una vez que tengas una coincidencia, mirarías el próximo personaje. Debería idear una forma de rastrear el mejor resultado hasta ahora.

Answer 3

Bueno, el primer paso sería ordenar la lista. Luego, pase por la lista, comparando cada elemento con el anterior, haciendo un seguimiento de las ejecuciones más largas de 2 caracteres, 3 caracteres, 4 caracteres, etc. Luego, la figura muestra los 20 prefijos de 3 caracteres mejor que los 15 prefijos de 4 caracteres.