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

Question

Problème:

Étant donné une liste de chaînes, trouver la sous-chaîne qui, si elle soustrait depuis le début de toutes les chaînes où il correspond et remplacé par un octet d'échappement, donne la longueur totale la plus courte.

Exemple:

"foo", "fool", "bar"

Le résultat est le suivant: "toto" que la chaîne de base avec les cordes "\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 10, donc dans ce cas, nous avons seulement enregistré un 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 il est quelque chose comme O ((n * m)^2), ce qui est trop cher.

Answer 1

Utiliser une forêt d'arbres préfixe (TRIE) ...

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

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

Sur la complexité: O (C), comme mentionné dans le commentaire, pour le construire, et pour trouver l'optimal, 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 découper plus de branches et avoir de bonnes chances d'obtenir un temps sub-linéaire.

Je pense que c'est clair, je ne vais pas l'écrire - qu'est-ce que c'est un devoir? ;)

Answer 2

Je voudrais essayer de commencer en triant la liste. Ensuite, vous allez 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 un match, vous regardez le char suivant. 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 passe à travers la liste, en comparant chaque élément avec le précédent, en gardant la trace des plus longs 2 caractères, 3 caractères, 4 caractères, etc. Alors, les 20 préfixes de 3 caractères sont mieux représentés que les 15 préfixes de 4 caractères.