Cadeias de Caracteres

Material sobre Cadeias de Caracteres, Autômatos e Algoritmo de Força bruta

Definição e Motivação
• Cadeia de caracteres: sequência de elementos denominados caracteres. • Os caracteres são escolhidos de um conjunto denominado alfabeto.
Ex.: em uma cadeia de bits o alfabeto é {0, 1}.
• Casamento de cadeias de caracteres ou casamento de padrão: encontrar todas as ocorrências de um padrão em um texto.
• Exemplos de aplicação:
– edição de texto;
– recuperação de informação;
– estudo de sequências de DNA em biologia computacional
Notação
• Texto: arranjo T[1..n] de tamanho n;
• Padrão: arranjo P[1..m] de tamanho m _ n.
• Os elementos de P e T são escolhidos de um alfabeto finito _ de tamanho c.
Ex.: _ = {0, 1} ou _ = {a, b, . . . , z}.
• Casamento de cadeias ou casamento de padrão: dados duas cadeias P (padrão) de comprimento |P| = m e T (texto) de comprimento |T| = n, onde n _ m, deseja-se saber as ocorrências de
P em T.
Estruturas de Dados para Texto e Padrão const MAXTAMTEXTO = 1000;
MAXTAMPADRAO = 10;
MAXCHAR = 256; type TipoTexto = array[1. .MAXTAMTEXTO] of char;
TipoPadrao= array[1. .MAXTAMPADRAO] of char;
Categorias de Algoritmos
• P e T não são pré-processados:
– algoritmo sequencial, on-line e de tempo-real;
– padrão e texto não são conhecidos a priori.
– complexidade de tempo O(mn) e de espaço O(1), para pior caso.
• P pré-processado:
– algoritmo sequencial;
– padrão conhecido anteriormente permitindo seu pré-processamento. – complexidade de tempo O(n) e de espaço O(m + c), no pior caso.
– ex.: programas para edição de textos.
• P e T são pré-processados:
– algoritmo constrói índice.
– complexidade de tempo O(log n) e de espaço é O(n).
– tempo para obter o índice é grande, O(n) ou O(n log n).
– compensado por muitas operações de pesquisa no texto.
– Tipos de índices mais conhecidos:
_ Arquivos invertidos
_ Árvores trie e árvores Patricia
_ Arranjos de sufixos
Exemplos: P e T são pré-processados
• Diversos