AED3 10 07 Codificação por LZW

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2018
Para nós compactarmos uma mensagem usando LZW, seguiremos essa sequência de passos bem específica:
Inicializar o dicionário (com símbolos básicos) - nesse ponto, estamos falando de todos os símbolos que poderem aparecer na mensagem. Geralmente, evitamos adotar um conjunto muito específico ou muito amplo e trabalhamos com os 256 valores possíveis para os bytes (e não para os caracteres).
1. Repetir até o fim do texto:
2. A partir da posição atual, achar a maior string w existente no dicionário.
2.1. Escrever o índice de w na saída.
2.2. Olhar o próximo caráter a que não fez parte de w.
2.3. Escrever a sequência wa no dicionário.
2.4. Avançar para a posição de a.
Atenção: os valores citados no vídeo são as posições de uma tabela, vetor ou dicionário. A primeira cadeia de símbolos fica na posição 0, a segunda na posição 1, a terceira na posição 2 e assim em diante. O crescimento é sequencial. Se definirmos que esse dicionário terá até 1024 valores, então usaremos 10 bits para representar cada valor (210 = 1024). Se usarmos até 4096 posições na tabela, então precisaremos de 12 bits para representar cada posição. Perceba que o crescimento é exponencial, isto é, cada bit adicional dobra o tamanho da tabela e nos permite representar muito mais cadeias de símbolos.
No próximo vídeo, veremos como é feita a decodificação.

[@VictorHugoOliveiraUsori]

Atualmente a melhor aula sobre o assunto de todo o KZbin (2023-11-23). Parabéns pelo o ótimo trabalho professor Marcos!

[@shimadabr]

Explicação bem clara e lúcida. Melhor explicação até agora!

[@VictorHugoOliveiraUsori]

Só um pequeno comentário, o código 5, pulou direto para o 7. O símbolo 'ba' seria o código 6 ao invés do 7. O dicionário final corrigido fica: { 0 : 'a', 1 : 'b', 2 : 'c', 3 : 'wa', 4 : 'ab' , 5 : 'bb', 6 : 'ba', 7 : 'aw', 8 : 'wab', 9 : 'bba' } No dicionário anterior 'wa' está com aspas simples porque está representando APENAS UM SÍMBOLO no dicionário final, NÃO É UMA STRING! No vídeo, 'wa' está representado pelo binário 0100, e cada binário é apenas um símbolo =) Uma implementação desse algoritmo de compressão, em uma línguagem de programação, deve ser feita cuidadosamente, para não utilizar indevidamente uma String onde deveria ser um caracter, ou seja, 'wa' (aspas simples) e "wa" (aspas duplas) não são a mesma coisa, mesmo essa escrita sendo possível em algumas linguagens de programação como Python, ou NodeJS.

[@brennokm]

Não tem 'c' em wabbawabba e não vi nenhum par de aspas simples