Estrutura de Dados: Casamento de Cadeias
- Cadeia de caracteres: sequência de elementos denominados caracteres
- O problema de casamento de cadeias (casamento de padrão) consiste em encontrar todas as ocorrências de um determinado padrão em um texto.
Categorias de Algoritmos
- Padrão e Texto não são pré-processados
Fornecido o texto e o padrão de tamanho n, não é realizado nenhum tipo de pré-processamento em nenhum dos dois. Você vai pesquisar o Texto e o Padrão no seu texto exatamente do jeito que se encontram.
- Complexidade no pior caso: O(mn) → Para cada caractere
- Algoritmo sequencial, on-line e de tempo real
- Complexidade de espaço para executar o algoritmo: O(1)
Comparo carcatere por caractere do meu texto com o carcatere do meu padrão até encontrar o padrão desejado.
Exemplo: Algoritmo força-bruta
2. Padrão é pré-processado
É a categoria mais utilizada, principalmente em editores de texto, onde apenas o padrão é processado. O texto não é pré processado porque ele está sendo construído. O padrão pré processado é pesquisado dentro do texto, evitando varrer todos os caracteres do seu texto e melhorando a complexidade de tempo
- Complexidade de tempo: O(n). → A complexidade passa a depender exclusivamente da quantidade de carcateres presentes no m texto.
- Ex: Shift-And
3. Padrão e Texto são pré-processados
É muito utilizado na recuperação de informações. Algoritmo constrói um índice para o texto (por exemplo: árvore B)
Tempo de geração do índice pode ser de O(n) ou O(n log n).
- A principal ED de indices utilizada p/ casamento de cadeias é o arquivo invertido:
Arquivo Invertido
É composto por vocabulário e ocorrências:
- Vocabulário: um conjunto das palavras distintas no texto. Para cada palavra distinta temos uma lista de posições de onde ela ocorre no texto é armazenada.
- Ocorrência: é o conjunto das listas de posições.
Uma vez fornecdio um padrão dentro do meu arquivo invertido, preciso pesquisar esse padrão no meu vocabulário. Assim que localizei, pego a lista de ocorrênicas e apresento onde a palavra se encontra.
Como verificar se a frase: tem palavras está no arquivo invertido? Como pesquisaria isso?
Resposta: Já que o arquivo invertido não trabalha com frases, pesquiso separadamente as duas palavras. Ache a lista de ocorrência dessas duas palavras, manipule as duas listas para ver se uma palavra está em seguida da outra a partir do índice.
- As ocorrências ocupam muito mais espaço do que o vocabulário → A sequência de ocorrências podem ser muito maiores e ocupando muito mais espaço do que a palavra.
- Caso todas as ocorrências não caibam na memória principal. Se eu tenho uma árvore B, guardo um link de arquivo pra memória secundária que mostre onde as ocorrências se encontram.
- Geralmente mantemos as ocorrências em um arquivo separado e as palavras em memória principal
- A previsão sobre o crescimento do tamanho do vocabulário é definida pela lei de Heaps
Etapas de Pesquisa no Arquivo Invertido:
- Pesquisa no vocabulário: palavras da consulta são isoladas e pesquisadas no vocabulário
- Recuperação das ocorrências: as listas de ocorrências das palavras encontradas no vocabulário são recuperadas.
- Manipulação das ocorrências: as listas de ocorrências são processadas para tratar frases, proximidade e/ou operações lógicas
Arquivo Invertido usando árvore TRIE:
- Texto: “Texto tem palavras. Palavras exercem fascínio.”
Casamento Exato de Cadeia
Consiste em encontrar ocorrências exatas de um padrão no texto
- Leitura dos caracteres do texto um a um no intuito de identificar uma ocorrência possível do padrão: Algoritmo força Bruta e Shift-And
- Pesquisa do padrão P em uma janela que desliza ao longo do texto T, procurando um casamento de P e T da direita pra esquerda: Algoritmos BM, BMH e BMHs
Algoritmo Força Bruta
No algoritmo acima, temos o “Tipo Texto T” de tamanho long n e o “TipoPadrao P” de tamanho long m representando o nosso texto e nosso padrão de tamanho n e m. As variáveis i, j, k são variáveis auxiliares para caminharem no padrão. O for faz a leitura dentro do texto, o i varia de 1 até o valor de (n -m +1), uma vez que a intenção é varrer o i até a posição que anteceda o número de caracteres do padrão que desejamos pesquisar. Em seguida, o k varre o texto.
Na condição do while, estamos fazendo uma comparação da posição do texto com o padrão, se os dois valores forem iguais o j e o k caminham pegando o próximo caractere do padrão e do texto. A última parte da condição é uma verificação caso o valor de j atinja a quantidade máxima de caractares, por isso temos j≤m. Se j≤m for falso é porque comparamos tudo do padrão. Assim, sairia do while e iria para o for, o i recebe o próximo caractere do texto, o k recebe 2 e reinicio o padrão.
Pior Caso: Cm = m x n. Quando temos uma quantidade pequena de caracteres no alfabeto.
Referências
Slides e vídeos de BCC203 (UFOP) — Introdução; Arquivo invertido; Algoritmo força bruta— Professor Guilherme Tavares.