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

1. 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:

1. Pesquisa no vocabulário: palavras da consulta são isoladas e pesquisadas no vocabulário
2. Recuperação das ocorrências: as listas de ocorrências das palavras encontradas no vocabulário são recuperadas.
3. 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.