Capítulo 6: Strings em Algoritmos

Entrada:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Saída: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Entrada:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Saída: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Entrada:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Saída: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

     (raiz)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

Texto:    "abacadabrabracabracadabrabrabracad"
Padrão: "abracadabra"
Saída:  [13]

Texto:    "abacadabrabrAqui está a tradução em português deste arquivo markdown. Para o código, não traduzi o código, apenas os comentários.

"acabracadabrabrabracad"
Padrão: "abracadabra"
Saída: [13]

O algoritmo KMP tem um tempo de execução de O(n + m), tornando-o muito mais eficiente do que a abordagem de força bruta para textos e padrões grandes.

### Algoritmo de Boyer-Moore

O algoritmo de Boyer-Moore é outro algoritmo eficiente de pesquisa de substring que funciona preprocessando a string do padrão. Ao contrário do KMP, que inicia as comparações do início do padrão, o Boyer-Moore começa do final e trabalha para trás.

A ideia-chave por trás do Boyer-Moore é usar duas funções pré-computadas: a função "bom sufixo" e a função "caractere ruim". Essas funções nos permitem pular à frente no texto quando encontramos uma incompatibilidade, semelhante ao KMP.

Aqui está um exemplo do algoritmo de Boyer-Moore:

O Boyer-Moore tem um tempo de execução no melhor caso de O(n/m) e um tempo de execução no pior caso de O(n * m), mas na prática, muitas vezes é o algoritmo de pesquisa de substring mais rápido para alfabetos grandes.

## Expressões Regulares

Expressões regulares são uma ferramenta poderosa para descrever padrões em strings. Elas fornecem uma notação concisa e flexível para correspondência, pesquisa e manipulação de texto.

Uma expressão regular é uma sequência de caracteres que define um padrão de pesquisa. A forma mais simples de uma expressão regular é uma string literal, como "hello", que corresponde exatamente à string "hello". No entanto, as expressões regulares também incluem caracteres e construções especiais que permitem padrões mais complexos:

- `.` (ponto) corresponde a qualquer caractere único.
- `*` (asterisco) corresponde a zero ou mais ocorrências do caractere ou grupo anterior.
- `+` (mais) corresponde a uma ou mais ocorrências do caractere ou grupo anterior.
- `?` (ponto de interrogação) corresponde a zero ou uma ocorrência do caractere ou grupo anterior.
- `^` (circunflexo) corresponde ao início de uma linha.
- `$` (cifrão) corresponde ao final de uma linha.
- `[]` (colchetes) definem uma classe de caracteres, correspondendo a qualquer caractere único dentro dos colchetes.Aqui está a tradução em português deste arquivo markdown. Para o código, não traduzi o código, apenas os comentários.

Aqui estão alguns exemplos de expressões regulares e os padrões que elas correspondem:

- `a.b` corresponde a qualquer string de três caracteres que começa com "a" e termina com "b", como "acb", "a5b" ou "a b".
- `a*b` corresponde a qualquer string que consiste em zero ou mais caracteres "a" seguidos por um único "b", como "b", "ab", "aab" ou "aaab".
- `a+b` corresponde a qualquer string que consiste em um ou mais caracteres "a" seguidos por um único "b", como "ab", "aab" ou "aaab", mas não "b".
- `a?b` corresponde a "ab" ou "b".
- `^a` corresponde a qualquer string que começa com "a".
- `a$` corresponde a qualquer string que termina com "a".
- `[aeiou]` corresponde a qualquer caractere vogal.

Expressões regulares são suportadas por muitas linguagens de programação e ferramentas, incluindo Java, Python e utilitários Unix como grep e sed. Elas são amplamente usadas para tarefas como validação de dados, processamento de texto e análise de logs.

## Compressão de Dados

Compressão de dados é o processo de codificar informações usando menos bits do que a representação original. Isso é útil para reduzir os requisitos de armazenamento e os tempos de transmissão. Existem dois tipos principais de compressão: sem perdas e com perdas. A compressão sem perdas permite que os dados originais sejam perfeitamente reconstruídos a partir dos dados comprimidos, enquanto a compressão com perdas permite alguma perda de informações em troca de taxas de compressão maiores.

### Codificação por Comprimento de Sequência

A codificação por comprimento de sequência (RLE) é uma técnica simples de compressão sem perdas que substitui sequências repetidas de símbolos idênticos (sequências) por uma única instância do símbolo e uma contagem do número de vezes que ele é repetido.

Aqui está um exemplo de RLE:

A RLE é eficaz para dados com muitas sequências longas, como imagens gráficas simples. No entanto, ela pode realmente aumentar o tamanho dos dados se houver poucas ou nenhuma sequência.

### Codificação de Huffman

A codificação de Huffman é um algoritmo de compressão sem perdas que atribui códigos de tamanho variável a símbolos com base em sua freAqui está a tradução em português deste arquivo Markdown. Para o código, não traduzi o código, apenas os comentários.

# Codificação de Huffman

A codificação de Huffman é um algoritmo de compressão de dados sem perdas que se baseia na frequência dos símbolos na entrada de dados. Símbolos mais frequentes são atribuídos códigos mais curtos, enquanto símbolos menos frequentes são atribuídos códigos mais longos.

O algoritmo funciona construindo uma árvore binária, chamada de árvore de Huffman, de baixo para cima. Cada nó folha representa um símbolo e sua frequência, enquanto cada nó interno representa a soma das frequências de seus filhos. A árvore é construída repetidamente mesclando os dois nós com as menores frequências até que reste apenas um nó.

Uma vez construída a árvore, o código de cada símbolo é determinado pelo caminho da raiz até o nó folha correspondente, sendo que um ramo à esquerda representa um "0" e um ramo à direita representa um "1".

Aqui está um exemplo de codificação de Huffman:

Neste exemplo, "A" recebe o código "00", "B" recebe "01", "C" recebe "10", "D" recebe "110" e "E" recebe "111". A saída comprimida é obtida substituindo cada símbolo da entrada pelo seu código correspondente.

A codificação de Huffman é um código de prefixo ótimo, o que significa que nenhum código é prefixo de outro código. Isso permite a decodificação não ambígua dos dados comprimidos. A codificação de Huffman é amplamente utilizada em vários formatos de arquivo e ferramentas de compressão, como JPEG, MP3 e ZIP.

### Compressão LZW

A compressão Lempel-Ziv-Welch (LZW) é um algoritmo de compressão de dados baseado em dicionário que constrói um dicionário (ou codebook) de strings durante a compressão. O LZW é amplamente utilizado em utilitários de compressão de arquivos e foi usado no formato de imagem GIF.

A ideia-chave por trás do LZW é substituir strings de caracteres por códigos únicos. Ele lê a string de entrada caractere por caractere e codifica a string em uma representação compacta, substituindo cada código de tamanho fixo por um código de tamanho variável. Quanto maior a string, mais espaço é economizado ao codificá-la como um único número.

Aqui está umAqui está a tradução em português do arquivo markdown, com os comentários do código traduzidos:

Descrição passo a passo de como funciona a compressão LZW:

1. Inicialize o dicionário para conter todas as strings de um único caractere.
2. Encontre a string mais longa W no dicionário que corresponda à entrada atual.
3. Emita o índice do dicionário para W na saída e remova W da entrada.
4. Adicione W seguido do próximo símbolo na entrada ao dicionário.
5. Vá para a Etapa 2.

Vamos considerar um exemplo. Suponha que queiramos comprimir a string "ABABABABA" usando LZW.

1. Inicialize o dicionário para conter "A" e "B".
2. A correspondência mais longa é "A". Emita seu índice (0) e remova-o da entrada. O dicionário agora contém "A", "B" e "AB".
3. A correspondência mais longa é "B". Emita seu índice (1) e remova-o da entrada. O dicionário agora contém "A", "B", "AB" e "BA".
4. A correspondência mais longa é "AB". Emita seu índice (2) e remova-o da entrada. O dicionário agora contém "A", "B", "AB", "BA" e "ABA".
5. A correspondência mais longa é "ABA". Emita seu índice (4) e remova-o da entrada. O dicionário agora contém "A", "B", "AB", "BA", "ABA" e "ABAB".
6. A correspondência mais longa é "BA". Emita seu índice (3). A entrada agora está vazia.

A representação comprimida de "ABABABABA" é, portanto, a sequência de índices [1], o que requer menos bits para representar do que a representação ASCII original.

A descompressão funciona de maneira semelhante, mas em ordem inversa:

1. Inicialize o dicionário para conter todas as strings de um único caractere.
2. Leia um código X da entrada.
3. Emita a string para X do dicionário.
4. Se o código anterior existir, adicione a string anterior concatenada com o primeiro caractere da string para X ao dicionário.
5. Vá para a Etapa 2.

A compressão LZW é simples e rápida, tornando-a uma boa escolha para muitas aplicações. No entanto, ela possui algumas limitações. O tamanho do dicionário pode crescer bastante, consumindo uma quantidade significativa de memória. Além disso, o dicionário é redefinido após cada bloco de entrada, o que pode reduzir a taxa de compressão para arquivos pequenos.

Apesar dessas limitaçõesAqui está a tradução em português deste arquivo markdown. Para o código, não traduzi o código, apenas os comentários.

## Conclusão

Neste capítulo, exploramos vários algoritmos importantes de processamento de strings, incluindo ordenação de strings, tries, pesquisa de substrings, expressões regulares e compressão de dados. Esses algoritmos formam a base para muitas aplicações do mundo real e são ferramentas essenciais para qualquer programador que trabalhe com dados textuais.

Começamos discutindo a ordenação de strings, que são algoritmos de ordenação otimizados que aproveitam as propriedades especiais das strings. Contagem por índice de chave, ordenação radix LSD e ordenação radix MSD fornecem métodos eficientes para ordenar strings com base em seus caracteres individuais.

Em seguida, examinamos as tries, uma estrutura de dados em árvore para armazenar e recuperar strings. As tries permitem correspondência de prefixos rápida e são comumente usadas em aplicações como autocompletar e tabelas de roteamento IP.

Algoritmos de pesquisa de substrings, como os algoritmos de Knuth-Morris-Pratt e Boyer-Moore, nos permitem pesquisar eficientemente padrões em strings maiores. Esses algoritmos têm inúmeras aplicações em edição de texto, biologia computacional e recuperação de informações.

As expressões regulares fornecem uma maneira poderosa e flexível de descrever padrões de strings. Discutimos a sintaxe básica das expressões regulares e como elas podem ser usadas para correspondência de padrões e manipulação de strings em várias linguagens de programação e ferramentas.

Finalmente, exploramos algoritmos de compressão de dados, que reduzem o tamanho dos dados explorando a redundância e os padrões dentro da entrada. Abordamos a codificação de comprimento de sequência, a codificação de Huffman e a compressão de Lempel-Ziv-Welch, cada uma com suas próprias forças e aplicações.

Entender esses algoritmos e estruturas de dados de processamento de strings é crucial para qualquer pessoa que trabalhe com dados textuais. À medida que a quantidade de dados não estruturados continua a crescer, a capacidade de manipular, pesquisar e compactar eficientemente esses dados se torna cada vez mais importante.Aqui está a tradução em português do arquivo Markdown fornecido:

# Manipulação de Strings em Python

As strings se tornarão cada vez mais valiosas. Ao dominar as técnicas abordadas neste capítulo, você estará bem equipado para enfrentar uma ampla gama de desafios de processamento de strings em seus próprios projetos e aplicações.

```python
# Exemplo 1: Concatenação de strings
first_name = "John"
last_name = "Doe"
full_name = first_name + " " + last_name
print(full_name)  # Output: John Doe

# Exemplo 2: Fatiamento de strings
message = "Hello, World!"
print(message[0:5])  # Output: Hello
print(message[7:12])  # Output: World

# Exemplo 3: Formatação de strings
age = 30
template = "Meu nome é {} e eu tenho {} anos."
output = template.format(full_name, age)
print(output)  # Output: Meu nome é John Doe e eu tenho 30 anos.

# Exemplo 4: Substituição de caracteres
text = "O rato roeu a roupa do rei."
new_text = text.replace("rato", "gato")
print(new_text)  # Output: O gato roeu a roupa do rei.