Ache um código de Lempel-Ziv para a sequência:
.
Passo 1
O enunciado pede: "Ache um código de Lempel-Ziv para a sequência
".
Informações dadas e o que é pedido:
Informações dadas e o que é pedido:
- A sequência binária fornecida é
. - Objetivo: produzir o código de Lempel–Ziv (ou seja, a codificação Lempel–Ziv correspondente) dessa sequência, mostrando claramente os blocos (frases) e os pares de saída (índice, símbolo) usados na codificação.
Passo 2
Escolha do método Lempel–Ziv a ser usado (explicação e justificativa):
- O enunciado não especifica qual variante de Lempel–Ziv usar (há LZ77, LZ78, LZW, etc.). Pelo enunciado simples de exercício teórico e pela preferência usual em provas básicas, vou usar a variante clássica LZ78, que é a mais elementar e didática para exercícios: ela constrói um dicionário de frases novas e produz pares
. - Resumo da regra que sigo: (i) começar com dicionário vazio; (ii) varrer a sequência da esquerda para a direita, em cada passo encontrar o maior prefixo já presente no dicionário (índice
significa prefixo vazio) e emitir o par ; (iii) adicionar ao dicionário a concatenação (prefixo + símbolo seguinte) como nova frase com novo índice.
Passo 3
Descrição didática do algoritmo LZ78 (passo a passo, sem executar ainda):
- Dicionário inicial: vazio. Cada nova entrada recebe um índice inteiro começando em
. - Notação: para um par
, é o índice da maior frase do dicionário que casa com o prefixo da sequência atual (ou se nenhuma casa) e é o próximo símbolo (a seguir ao prefixo) que completa uma nova frase. A nova frase adicionada ao dicionário é (frase de índice ) seguida do símbolo . - Exemplo mínimo para entender: se o dicionário está vazio e a sequência começa com
0, o maior prefixo é vazio (índice) e o próximo símbolo é 0→ emitimose adicionamos a frase índice = 0. Depois continuamos a partir do próximo símbolo que ainda não foi codificado. - Importante: cada saída
consome do fluxo de entrada exatamente o comprimento da frase correspondente a mais um símbolo (ou apenas um símbolo quando ).
Passo 4
Vou aplicar o algoritmo à sequência
. Para facilitar o acompanhamento vou numerar os índices das posições da sequência e mostrar em cada passo a frase escolhida, o porquê (maior prefixo encontrado), o par emitido e a nova frase inserida no dicionário. Inicialmente o dicionário está vazio e o próximo índice a atribuir é
.
Passo 5
Passo/Frase 1:
- Posição atual: começo da sequência (primeiro símbolo). O maior prefixo do dicionário que casa é o vazio (índice
), o próximo símbolo é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos 1 símbolo.
Passo 6
Passo/Frase 2:
- Posição atual: começos no segundo símbolo; próximo trecho
. O maior prefixo encontrado no dicionário é a frase de índice = . O símbolo logo após esse prefixo é outro . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase (isto é, frase seguida de ). - Consumimos os dois símbolos correspondentes (prefixo
+ símbolo ).
Passo 7
Passo/Frase 3:
- Posição atual: próximo símbolo é
. Não há frase que comece com no dicionário, então o maior prefixo é vazio (índice ), e o próximo símbolo é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos 1 símbolo.
Passo 8
Passo/Frase 4:
- Posição atual: os próximos símbolos começam com
. O maior prefixo presente no dicionário que casa é (índice ), e o símbolo que segue esse prefixo é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos os dois símbolos (prefixo
0+ símbolo1).
Passo 9
Passo/Frase 5:
- Posição atual: os próximos símbolos começam com
. O maior prefixo que casa é (índice ), o símbolo que segue é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos os dois símbolos (
1+1).
Passo 10
Passo/Frase 6:
- Posição atual: estamos diante de uma sequência de zeros
. Procurando o maior prefixo no dicionário: (índice ) casa com os dois zeros iniciais; tentar estender para falha porque ainda não está no dicionário. - Assim, o maior prefixo é
(índice ), e o próximo símbolo é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos os três símbolos (
00+0).
Passo 11
Passo/Frase 7:
- Posição atual: o próximo símbolo é
. O maior prefixo no dicionário é (índice ), e o símbolo seguinte é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos os dois símbolos (
1+0).
Passo 12
Passo/Frase 8:
- Posição atual: novamente temos uma sequência longa de zeros. Procurando o maior prefixo:
(índice ) casa com três zeros; tentar estender para ainda não existe no dicionário. - Portanto usamos o prefixo índice
= e o próximo símbolo é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos quatro zeros (prefixo de 3 zeros + símbolo 0).
Passo 13
Passo/Frase 9:
- Posição atual: a sequência restante tem o trecho
. O maior prefixo do dicionário que casa é (índice ), e o símbolo que segue esse prefixo é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos os três símbolos (prefixo
01+ símbolo0).
Passo 14
Passo/Frase 10 (final):
- Posição atual: restam os três últimos símbolos
. O maior prefixo que casa é (índice ) e o símbolo que segue é . - Emitimos
. - Adicionamos ao dicionário o índice
com a frase . - Consumimos esses três símbolos e chegamos ao fim da sequência.
Passo 15
Verificação da reconstrução (para garantir que a codificação está correta):
- Cada par
corresponde a uma frase nova = (frase de índice ) concatenada com . Listando frases criadas: - Índice
: - Índice
: - Índice
: - Índice
: - Índice
: - Índice
: - Índice
: - Índice
: - Índice
: - Índice
:
- Índice
- Concatenando as frases na ordem obtém-se:
que é exatamente , a sequência original. Logo a codificação está correta.