Trouvez la sous-chaîne de préfixe qui donne la meilleure compression

Question

Problème:

À partir d'une liste de chaînes, recherchez la sous-chaîne qui, si elle est soustraite au début de toutes les chaînes où elle correspond, et remplacée par un octet d'échappement, donne la longueur totale la plus courte.

Exemple:

"foo" , "imbécile" , "bar"

Le résultat est le suivant: "foo" en tant que chaîne de base avec les chaînes "\ 0" , "\ 0l" , "bar" et une longueur totale de 9 octets. " \ 0 " est l'octet d'échappement. La somme de la longueur des chaînes d'origine est de 10, nous n'avons donc enregistré qu'un seul octet.

Un algorithme naïf ressemblerait à ceci:

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

Cela nous donnera la réponse, mais c'est quelque chose comme O ((n * m) ^ 2), qui est trop cher.

Answer 1

Utilisez une forêt de préfixes (trie) ...

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

alors, nous pouvons trouver le meilleur résultat et le garantir en maximisant (profondeur * fréquence) qui sera remplacé par votre caractère d'échappement. Vous pouvez optimiser la recherche en effectuant d'abord une recherche de branche et de profondeur liée.

Sur la complexité: O (C), comme mentionné dans le commentaire, pour le construire et pour trouver l’optimum, cela dépend. Si vous commandez la fréquence des premiers éléments (O (A) - où A est la taille de l'alphabet des langues), vous pourrez alors découper plus de branches et avoir de bonnes chances d'obtenir un temps sub-linéaire.

Je pense que cela est clair, je ne vais pas l'écrire - en quoi consiste un devoir? ;)

Answer 2

Je voudrais commencer par trier la liste. Ensuite, vous passez simplement de chaîne en chaîne en comparant le premier caractère au premier caractère de la chaîne suivante. Une fois que vous avez une correspondance, vous examinerez le prochain personnage. Vous auriez besoin de trouver un moyen de suivre le meilleur résultat jusqu'à présent.

Answer 3

Eh bien, la première étape serait de trier la liste. Ensuite, on parcourt la liste, en comparant chaque élément avec le précédent, en gardant une trace des plus longues exécutions à 2, 3, 4 caractères, etc. La figure représente les 20 préfixes à 3 caractères meilleurs que les 15 préfixes à 4 caractères.