Étendu code de Huffman

Question

J'ai ce devoir: trouver les mots de code pour les symboles dans tout alphabet donné. Il dit que je dois utiliser Huffman binaire sur des groupes de trois symboles. Qu'est-ce que ça veut dire exactement? Dois-je utiliser Huffman régulier sur [alphabet] ^ 3? Si oui, comment puis-je alors dire la différence entre les 3 symboles dans un groupe?

Answer 1

Je ne peux pas tout à fait dire, parce que votre description du problème n'est pas si détaillée, mais je suppose qu'ils veulent dire qu'au lieu de coder chaque symbole dans votre alphabet individuellement, vous êtes censé marcher chaque triple de symboles en tant que groupe.

Ainsi, par exemple, si votre alphabet se compose de a, b et c, au lieu de générer un codage pour chacun de ces individuellement, vous devez créer un encodage pour aaa, aab, aac, etc. Chacune de ces chaînes serait traité comme un symbole distinct dans l'algorithme de Huffman; vous pouvez les différencier simplement en faisant la comparaison de chaînes sur eux. Si vous avez besoin d'accepter l'entrée de longueur arbitraire, vous devrez également inclure dans vos symboles de l'alphabet qui sont des chaînes de longueur 1 ou 2. Par exemple, si vous encodez la aabacab chaîne, vous devez briser cette baisse dans le symboles aab, aca et b.

Est-ce que répondre à vos questions? Je n'étais pas sûr de ce que vous cherchez, alors s'il vous plaît ne hésitez pas à modifier votre question ou une réponse dans un commentaire si cela n'a rien éclairci.

Answer 2

Food for thought: ce que sur les chaînes plus courtes, et les permutations des "limites de bloc"? Qu'en est-1 et 2 chaînes de caractères? Comptez-vous juste à côté de 3, 6, 9, 12, ... dans votre texte les caractères d'entrée et pad alors nul des longueurs inégales à la fin?

Si les morceaux peuvent être de taille variable, alors il devient vraiment intéressant de trouver le meilleur ajustement. Je soupçonne que cela dégénère en un vendeur ambulant genre de problème, mais peut-être il y a une « théorème » pur ou tout autre outil là-bas pour ce genre de chose.

Peut-être essayer toutes les permutations de 3 caractères, sauvant le plus fréquemment utilisé, essayez de trouver un bon moyen pour les longues lacunes 1 et 2 car? Hmm, sonne comme il pourrait être vraiment lent, mais faisable en utilisant une sorte de fracture récursive et approche counquer: tirer la longue chaîne de longueur de bloc N, récursif puis dans le codage des lacunes que la longueur N - 1

.

Plus de questions que de réponses, j'ai peur.