Ache um código de Lempel-Ziv para a sequência: \{00010111000100000010011\}.

Passo 1

O enunciado pede: "Ache um código de Lempel-Ziv para a sequência \{00010111000100000010011\}".
Informações dadas e o que é pedido:
  • A sequência binária fornecida é \text{S} = \text{`}00010111000100000010011\text{'}.
  • 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 (\text{índice},\\ \text{símbolo})íí.
  • 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 0 significa prefixo vazio) e emitir o par (\text{índice do prefixo},\\ \text{símbolo seguinte})íí; (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 1.
  • Notação: para um par (i,a), i é o índice da maior frase do dicionário que casa com o prefixo da sequência atual (ou 0 se nenhuma casa) e a é o próximo símbolo (a seguir ao prefixo) que completa uma nova frase. A nova frase adicionada ao dicionário é (frase de índice i) seguida do símbolo a.
  • Exemplo mínimo para entender: se o dicionário está vazio e a sequência começa com 0, o maior prefixo é vazio (índice 0) e o próximo símbolo é 0 → emitimos (0,0) e adicionamos a frase índice 1 = 0. Depois continuamos a partir do próximo símbolo que ainda não foi codificado.
  • Importante: cada saída (i,a) consome do fluxo de entrada exatamente o comprimento da frase correspondente a i mais um símbolo (ou apenas um símbolo quando i=0).

Passo 4

Vou aplicar o algoritmo à sequência \text{S}=\text{`}00010111000100000010011\text{'}. 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 é 1.

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 0), o próximo símbolo é 0.
  • Emitimos (0,0).
  • Adicionamos ao dicionário o índice 1 com a frase \text{`0'}.
  • Consumimos 1 símbolo.

Passo 6

Passo/Frase 2:
  • Posição atual: começos no segundo símbolo; próximo trecho \text{`0...'}. O maior prefixo encontrado no dicionário é a frase de índice 1 = \text{`0'}. O símbolo logo após esse prefixo é outro 0.
  • Emitimos (1,0).
  • Adicionamos ao dicionário o índice 2 com a frase \text{`00'} (isto é, frase 1 seguida de 0).
  • Consumimos os dois símbolos correspondentes (prefixo 0 + símbolo 0).

Passo 7

Passo/Frase 3:
  • Posição atual: próximo símbolo é 1. Não há frase que comece com 1 no dicionário, então o maior prefixo é vazio (índice 0), e o próximo símbolo é 1.
  • Emitimos (0,1).
  • Adicionamos ao dicionário o índice 3 com a frase \text{`1'}.
  • Consumimos 1 símbolo.

Passo 8

Passo/Frase 4:
  • Posição atual: os próximos símbolos começam com \text{`0 1 ...'}. O maior prefixo presente no dicionário que casa é \text{`0'} (índice 1), e o símbolo que segue esse prefixo é 1.
  • Emitimos (1,1).
  • Adicionamos ao dicionário o índice 4 com a frase \text{`01'}.
  • Consumimos os dois símbolos (prefixo 0 + símbolo 1).

Passo 9

Passo/Frase 5:
  • Posição atual: os próximos símbolos começam com \text{`1 1 ...'}. O maior prefixo que casa é \text{`1'} (índice 3), o símbolo que segue é 1.
  • Emitimos (3,1).
  • Adicionamos ao dicionário o índice 5 com a frase \text{`11'}.
  • Consumimos os dois símbolos (1 + 1).

Passo 10

Passo/Frase 6:
  • Posição atual: estamos diante de uma sequência de zeros \text{`0 0 0 ...'}. Procurando o maior prefixo no dicionário: \text{`00'} (índice 2) casa com os dois zeros iniciais; tentar estender para \text{`000'} falha porque ainda não está no dicionário.
  • Assim, o maior prefixo é \text{`00'} (índice 2), e o próximo símbolo é 0.
  • Emitimos (2,0).
  • Adicionamos ao dicionário o índice 6 com a frase \text{`000'}.
  • Consumimos os três símbolos (00 + 0).

Passo 11

Passo/Frase 7:
  • Posição atual: o próximo símbolo é 1. O maior prefixo no dicionário é \text{`1'} (índice 3), e o símbolo seguinte é 0.
  • Emitimos (3,0).
  • Adicionamos ao dicionário o índice 7 com a frase \text{`10'}.
  • 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: \text{`000'} (índice 6) casa com três zeros; tentar estender para \text{`0000'} ainda não existe no dicionário.
  • Portanto usamos o prefixo índice 6 = \text{`000'} e o próximo símbolo é 0.
  • Emitimos (6,0).
  • Adicionamos ao dicionário o índice 8 com a frase \text{`0000'}.
  • 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 \text{`0 1 0 ...'}. O maior prefixo do dicionário que casa é \text{`01'} (índice 4), e o símbolo que segue esse prefixo é 0.
  • Emitimos (4,0).
  • Adicionamos ao dicionário o índice 9 com a frase \text{`010'}.
  • Consumimos os três símbolos (prefixo 01 + símbolo 0).

Passo 14

Passo/Frase 10 (final):
  • Posição atual: restam os três últimos símbolos \text{`0 1 1'}. O maior prefixo que casa é \text{`01'} (índice 4) e o símbolo que segue é 1.
  • Emitimos (4,1).
  • Adicionamos ao dicionário o índice 10 com a frase \text{`011'}.
  • 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 (i,a) corresponde a uma frase nova = (frase de índice i) concatenada com a. Listando frases criadas:
    • Índice 1: \text{`0'}
    • Índice 2: \text{`00'}
    • Índice 3: \text{`1'}
    • Índice 4: \text{`01'}
    • Índice 5: \text{`11'}
    • Índice 6: \text{`000'}
    • Índice 7: \text{`10'}
    • Índice 8: \text{`0000'}
    • Índice 9: \text{`010'}
    • Índice 10: \text{`011'}
  • Concatenando as frases na ordem obtém-se: \text{`0'}\\ \|\\ \text{`00'}\\ \|\\ \text{`1'}\\ \|\\ \text{`01'}\\ \|\\ \text{`11'}\\ \|\\ \text{`000'}\\ \|\\ \text{`10'}\\ \|\\ \text{`0000'}\\ \|\\ \text{`010'}\\ \|\\ \text{`011'}que é exatamente \text{`}00010111000100000010011\text{'}, a sequência original. Logo a codificação está correta.

Resposta

(0,0),\\ (1,0),\\ (0,1),\\ (1,1),\\ (3,1),\\ (2,0),\\ (3,0),\\ (6,0),\\ (4,0),\\ (4,1)
\begin{aligned} \text{Dicionário: } &1\mapsto \text{`0'},\quad 2\mapsto \text{`00'},\quad 3\mapsto \text{`1'},\quad 4\mapsto \text{`01'},\\\ &5\mapsto \text{`11'},\quad 6\mapsto \text{`000'},\quad 7\mapsto \text{`10'},\quad 8\mapsto \text{`0000'},\\\ &9\mapsto \text{`010'},\quad 10\mapsto \text{`011'}. \end{aligned}á

Exercícios relacionados