Resumo: Retornamos aos fundamentos dos códigos de Huffman, justificamos, com base em elementos da teoria de informação, sua praticidade, limitações e apontamos as vantagens e desvantagens de considerarmos suas versões condicionais. Utilizamos cadeias de Markov para compor classes de condicionamento para códigos de Huffman e evidenciamos que, apesar dessa estratégia permitir uma redução no comprimento esperado por elemento da mensagem, exige a comunicação de um grande número de parâmetros para estabelecer o modelo empregado. Reintroduzimos o conceito e resultados associados a modelos markovianos de partição. Essa família de modelos organiza o espaço de estados associado a uma cadeia de Markov em partes baseadas em suas funções de probabilidade de transição. Estabelecemos a aliança entre códigos condicionais e tais modelos a fim de construir uma metodologia com potencial de reduzir o número de parâmetros a serem comunicados durante o processo de codificação de mensagens, provocando uma representação binária mais compacta. Além disso, estabelecemos uma nova classe de processos markovianos: as cadeias de Markov com interstício. Esse delineamento possibilita a inclusão de um passado distante e relevante na modelagem do processo estocástico, cujo manejo apropriado permite a redefinição dos modelos de partição e a construção de uma família ainda mais flexível: os G3M (modelos markovianos mínimos com interstício). Mostramos como utilizar os G3M para uma modelagem eficiente do genoma da Covid-19, para codificação de matrizes e para compressão de imagens com perda de qualidade Ver menos

Abstract: We come back to the roots of the Huffman codes and, based on elements of information theory, we justify its practicality and limitations, as well the benefits and drawbacks of its conditional forms. We design conditioning classes to Huffman codes based on Markov chains and point out that this strategy allows a reduction on the message average length per symbol, but demands the transmission of a large set of parameters to establish the selected model. We reintroduce the concept of partition Markov models and their related results. This family of models arranges the state space of a Markov chain in sets (parts) based on its transition probability functions. We establish the alliance between conditional encoding and such models for the purpose of deriving a methodology with the potential to lessen the number of parameters to be communicated during the encoding process, which yields a shorter binary representation. Furthermore, we establish a new class of Markovian processes: the Markov chain with a gap. This design allows that a faraway, but relevant, past to be included during the modeling of the stochastic process, whose proper handling leads to a redefinition of the partition models and the characterization of an even more flexible family: the G3M (minimal Markovian models with a gap). We show how to make use of the G3M to efficiently model the Covid-19 genome, and also how to integrate it to matrix encoding processes and lossy image compression Ver menos