Algoritmos de Varredura Linear e Busca de Padrões
Davi D. Pinheiro, Luiz A. C. B. Silva
Centro de Informática (CIn) - Universidade Federal de Pernambuco (UFPE)
Recife, PE - Brasil
{ddp,lacbs}@cin.ufpe.br
Abstract. This article has the objective of showing the importance of
algorithms in the broad range of applications on Computer Science. It will be
covered sweep line algorithms to solve geometric problems e pattern search
algorithms for solutions in string processing.
Resumo. Este artigo tem como objeto mostrar a importância de algoritmos
para as mais diversas aplicações em Ciências da Computação. São abordados
algoritmos de varredura linear para solução de problemas geométricas e
algoritmos de busca de padrões para soluções de processamento de cadeias de
caracteres.
1. A Importância em Conhecer Algoritmos
Algoritmos são como receitas para completar uma tarefa bem definida. Um pedaço de
código que calcula os termos da sequencia de Fibonacci é uma implementação de um
algoritmo em particular. Mesmo uma simples função de adicionar dois números é um
algoritmo, mesmo que simples.
Alguns algoritmos, como aqueles que computam a sequencia de Fibonacci, são
intuitivos e devem ser inicialmente imersos no nosso pensamento lógico e capacidade
de resolução de problemas. No entanto, para a maioria de nós, algoritmos complexos
são mais estudados para que possamos utiliza-los como blocos para um mais eficiente
desenvolvimento na lógica de resolver problemas no futuro.
É impressionante como muitos algoritmos complexos são usados pelas pessoas
todos os dias quando elas checam os e-mails ou escutam música nos seus computadores.
Esse artigo vai introduzir algumas ideias básicas relacionadas à análise de algoritmos, e
como coloca-los em práticas com alguns aprofundamentos e exemplos de importantes
tópicos: verrudura linear e busca de padrões.
1.1. Análise de Complexidade Computacional
Um dos mais importantes aspectos de um algoritmo é o quão rápido ele é. Às vezes é
fácil desenvolver um algoritmo para resolver um problema, mas se o algoritmo for
muito lento devemos parar e pensar em uma ideia mais sofisticada. Já que a velocidade
exata de execução de um algoritmo depende de onde o algoritmo é rodado, assim como
detalhes específicos de sua implementação, cientistas da computação tipicamente falam
sobre tempo de execução relativo ao tamanho da entrada.
Por exemplo, se a entrada consiste de N inteiros, um algoritmo pode ter um
tempo de execução proporcional a N², representado como O(N²). Isso significa que se
uma implementação do algoritmo for executada em um computador com entrada de
tamanho B, levará aproximadamente C*N² segundos, onde C é uma constante que não
muda com o tamanho da entrada.
No entanto, o tempo de execução de vários algoritmos complexos pode variar de
acordo com outros fatores além do tamanho da entrada. Por exemplo, um algoritmo de
ordenação vai rodar muito mais rápido se receber como entrada um conjunto de inteiros
ordenados, ao invés de recebê-los em ordem aleatória. Como resultado sobre o tempo de
execução de um algoritmo, existe o pior-caso e o caso-médio.
O tempo de execução do pior-caso é quanto tempo demoraria para o algoritmo
rodar caso lhe fosse dado como entrada o caso mais insidioso de todas as possíveis
entradas. O tempo de execução do caso-médio é a média do tempo que o algoritmo
levaria para rodar todas as possíveis entradas. Dos dois, o pior caso é normalmente
considerado como patamar para avaliação do tempo de execução de um determinado
algoritmo.
O processo para determinar o pior-caso e o caso-médio não é simples, já que
normalmente é impossível rodar todas as possíveis entradas para um determinado
algoritmo. No entanto existem vários estudos focados em estimar o pior-caso e o casomédio da forma mais aproximada possível.
Tabela 1. Tempo aproximado de execução para algoritmos com N = 100
Complexidade
Tempo esperado
O(Log(N))
10 segundos
O(N)
10 segundos
O(N*Log(N))
10 segundos
-7
-6
-5
2
10 segundos
6
3 minutos
O(2 )
N
10
O(N!)
10
O(N )
O(N )
-4
14
142
anos
anos
2. Varredura Linear
Nesse capítulo será explorado algoritmos mais avançados que podem ser
desenvolvidos a partir de ferramentas básicas de geometria. Eles são baseados em uma
ideia simples porem poderosa de linha de varredura: Uma linha vertical que é
conceitualmente “varrida” pelo plano. Na prática, não podemos considerar todos os
pontos então vamos considerar apenas alguns pontos discretos.
A seguir será utilizado as definições de distância Euclidiana e distância de
Manhattan. A distância Euclidiana é a normal, a distância comumente utilizada obtida
através do teorema de Pitágoras. A distância de Manhattan entre os pontos (x1,y1) e
(x2, y2) é a distância que deve ser percorrida enquanto se movimenta apenas
verticalmente ou horizontalmente, portanto |x1 – x2| + |y1 – y2|. É chamada de distância
de Manhattan porque as ruas de Manhattan são distribuídas em forma de grade, logo a
distância de Manhattan é a distância que deve ser percorrida pela estrada (também
conhecida como “distância de taxi”, ou mais formalmente a métrica L1).
2.1. Par de Pontos Mais Próximo
Dado um conjunto de pontos, encontrar o par mais próximo (em qualquer uma
das métricas). Claro que esse problema pode ser resolvido em O(N²) considerando todos
os possível pares de pontos, mas com linha de varredura pode reduzir para O(N log N).
Suponha que os pontos de 1 a N-1 foram processados (ordenados em X) and que
a distância mais próxima encontrada até agora foi h. Agora devemos processar o ponto
N e encontrar um ponto mais perto dele do que h. Mantemos um conjunto de todos os
pontos que já foram processados o qual a coordenada X está dentro da distância de h do
ponto N, como mostrado no retângulo cinza claro. Assim que cada ponto for
processado, ele é adicionado ao conjunto, e quando movemos para o próximo ponto ou
quando h é diminuído, os pontos são removidos do conjunto. O conjunto é ordenado
pela coordenada y. Uma árvore binária balanceada é apropriada para isso, permitindo o
fator log N.
Figura 1. Passo do algoritmo para achar o par de pontos mais próximos.
Para procurar por pontos mais perto que h do ponto N, devemos considerar
apenas os pontos no conjunto, e apenas os que tem coordenada y no intervalo yn – h a
yn + h (os pontos no retângulo cinza escuro). Esse intervalo pode ser extraído do
conjunto ordenado em O(log N), mas o mais importante o número de elemento é em
O(1) (o máximo exato depende da métrica usada), porque a separação entre dois pontos
quaisquer no conjunto é de pelo menos h. A busca para cada ponto requer O(log N),
dando um total de O(N log N).
2.2. Interseção de Segmento de Retas
Vamos considerar o problema de retornar todas as intersecções em um conjunto de
segmentos de reta horizontais e verticais. Já que as linhas horizontais não possuem
coordenadas no eixo X, temos que abandonar a ideia de ordenar os objetos pelo X. Em
vez disso, temos a ideia de um evento: começo de uma linha horizontal, fim de uma
linha horizontal, e uma linha vertical. Assim que a linha de varredura se movimento,
vamos manter um conjunto ativo de linhas horizontais cortadas pela linha de varredura,
ordenadas pelo valor de Y (as linhas vermelhas na figura).
Figura 2. Passo do algoritmo para achar interseção de segmentos verticais e
horizontais.
Para processar qualquer evento horizontal, simplesmente adicionamos ou
removemos um elemento do conjunto. Novamente, podemos usar uma árvore binária
balanceada para garantir tempo O(log N) nessas operações. Assim que atingirmos uma
linha vertical, uma busca em intervalo pode dar imediatamente todas as linhas
horizontais que a linha corta. Se segmentos horizontais ou verticais podem se coincidir
é necessário uma checagem adicional, e devemos considerar se as linhas com finais
coincidentes estão sendo consideradas na intersecção, mas isso não afeta a
complexidade computacional.
Se as intersecções forem necessárias, o algoritmo levaria O(N log N + l) para
todas as l intersecções. Aumentando a estruturada da arvore binaria (especificamente,
guardando o tamanho de cada sub-árvore na raiz dessa sub-árvore), é possível contar as
intersecções em tempo O(N log N).
No caso mais geral, linhas não precisam ser horizontais nem verticais, então
linhas no conjunto ativo mudam de lugar quando elas intersectam. Ao invés de ter todos
os eventos pré-ordenados, devemos utilizar uma fila de prioridades e dinamicamente
adicionar ou remover os eventos de intersecção. Em qualquer momento, a lista de
prioridade contém eventos para os pontos finais dos segmentos de reta, mas também
para os pontos de intersecção de elementos adjacentes do conjunto ativo (dado que ele
estarão no futuro). Já que existem O(N + l) eventos que devem ser alcançados, e é
necessário O(log N) para atualizar o conjunto ativo e a lista de prioridades, esse
algoritmo leva O(N log N + l log N). A figura abaixo mostra os eventos futuros na fila
de prioridade (pontos azuis). Note que nem todas as futuras intersecções estão na fila,
porque uma das linhas não está ativa ainda, ou porque as duas linhas ainda não
adjacentes na lista ativa.
Figura 3. Passo do algoritmo para achar interseção de segmentos quaisquer.
2.3. Área de União de Retângulos
Dado um conjunto de retângulos alinhados pelos eixos, qual a área da união de
todos eles? Assim como o problema de intersecção de linhas, podemos resolvê-lo
lidando com eventos e conjuntos ativos. Cada retângulo tem dois eventos: aresta direita
e aresta esquerda. Quando passamos pela aresta da esquerda, o retângulo é adicionado
ao conjunto ativo. Quando cruzamos a aresta da direita ele é removido do conjunto
ativo.
Figura 4. Passo do algoritmo mostrando linha de varredura cortando
retâgunlos.
Sabemos agora quais retângulos estão sendo cortados pela linha de varredura
(vermelha na imagem), mas o que queremos saber é o tamanho da linha de varredura
que é cortada (o tamanho da linha azul forte). Multiplicando isso pelo tamanho da
distância horizontal dos eventos fornece a área varrida entre os dois eventos.
Podemos determinar o tamanho do corte rodando o mesmo algoritmo em um
loop interno, mas rodado por 90 graus. Ignore os triangulo inativos, e considere uma
linha de varredura horizontal que move de cima para baixo. Os eventos agora são
arestas horizonteis nos triângulos ativos, e toda vez que cruzamos um, simplesmente
incrementos ou decrementamos um contador que diz quantos triângulos se sobrepõem
no ponto atual. O tamanho do corte aumenta enquanto o contador é diferente de zero.
Claro que não o aumentamos continuamente, apenas quando movemos de um evento
par ao outro.
Com as estruturas de dados corretas, isso pode ser implementado em O(N²). De
fato o loop interno pode ser substituído por uma manipulação de uma árvore binaria
para reduzir o tempo total para O(N log N), contudo isso é mais um problema de
estruturas de dados do que de geometria. O algoritmo também pode ser adaptado para
responder a problemas similares, como o perímetro total da união de todos os retângulos
ou o número máximo de retângulos que se sobrepõem em algum ponto.
2.4. Fecho Convexo de Pontos 2D
O fecho convexo de um conjunto de pontos é o menor polígono convexo que
cerca todo o conjunto, e tem um número de aplicações práticas. Um método eficiente
que é comumente usado é o Graham Scan, que requer uma ordenação por ângulos. Isso
não é tão fácil quanto parece, já que computar os ângulos é custoso e introduz
problemas de precisão. Um simples no entanto igualmente eficiente algoritmo é o
algoritmo de Andrew, e requer apenas ordenação em X para a linha de varredura.
O algoritmo de Andrew divide o fecho conexo em duas partes, o fecho superior
e o inferior. Usualmente eles se encontram nos pontos finais, mas se mais de um ponto
possui uma coordenada X minimal ou maximal, então eles são juntos por um segmento
vertical de reta. A seguir será descrito como construir o fecho superior. O fecho inferior
pode ser construído de forma similar, e de fato pode ser feito no mesmo loop.
Para construir o fecho superior, começamos com o ponto de coordenada X
mínima, em caso empate o com máximo Y. Após isso, pontos são adicionados em
ordem da coordenada X (sempre desempatando pelo maior Y quando múltiplos pontos
tem o mesmo X). Claro, as vezes isso pode causar com que o fecho seja côncavo ao
invés de convexo:
Figura 5. Passo do algoritmo para achar fecho convexo.
O caminho preto mostra o fecho atual. Após adicionar o ponto 7, devemos
checar se o último triângulo (5,6,7) é convexo. Nesse caso não é, então deletamos o
penúltimo ponto, nesse caso o 6. O processo é repetido até o triângulo conexo ser
encontrado. Nesse caso também examinamos (4,5,7) e deletamos 5 antes de examinar
(1,4,7) e perceber que é convexo, antes de proceder para o próximo ponto. Isso é
essencialmente o mesmo procedimento que é usado no Graham scan, mas procedendo
em ordem da coordenada X ao invés da ordem do ângulo feito com o ponto inicial. Isso
faz parecer com que o processo seja O(N²). O algoritmo de um modo geral é O(N log
N), porque os pontos devem inicialmente serem ordenados pela coordenada X.
2.5. Árvore de Peso Mínimo no Espaço de Manhattan
Podemos criar algoritmos ainda mais poderosos combinando linha de varredura
com um algoritmo de dividir para conquistar. Um exemplo é computar a árvore
geradora mínima de um conjunto de pontos, onde a distância entre qualquer par de
pontos é a distância de Manhattan. Isso é essencialmente o algoritmos descrito por
Guibas e Stolfi.
Primeiro quebramos o problema em um problema mais simples. Algoritmos
padrões de AGM para grafos gerais (Como o algoritmo de Prim) podem computar a
AGM em O ((E+N) log N) onde E são as arestas. Se pudermos se aproveitar de
propriedades geométricas para reduzir o número de arestas a O(N), então a
complexidade será O (N log N). De fato podemos considerar, para cada ponto P, apenas
os vizinhos mais próximos em cada um dos 8 octantes do plano (como na figura
abaixo). A figura mostra a situação em apenas um dos octantes, o Oeste-Noroeste. Q é o
vizinho mais próximo (onde a linha pontilhada indica pontos com a mesma distância de
Manhattan que Q), e R é algum ponto nesse octante. Se PR for uma aresta em uma
árvore geradora, então ela pode ser removida e substituída tanto por PQ ou QR para
produzir uma árvore geradora melhor, porque a forma do octante garante que |QR| <=
|PR|. Logo, nós é necessário considerar PR quando estiver construindo a árvore
geradora.
Figura 6. Exemplo de dois pontos pertencente ao mesmo octante.
Isso reduz o problema a encontrar o vizinho mais próximo em cada octante.
Iremos apenas considerar o octante mostrado, todos os outros não são diferentes e
podem ser cálculos pela mesma simetria. Deve estar claro que neste octante, encontrar o
vizinho mais próximo é equivalente a encontrar o ponto com o maior valor de x – y,
sujeito a um valor máximo em x + y e valor mínimo em y, e é desta forma que o
problema será considerado.
Agora imagine por um momento que o valor mínimo em y não existe.
Nesse caso podemos resolver o problema para todo P facilmente: varrer pelos pontos
em ordem crescente de x + y, e Q será o ponto com o maior valor de x - y dos quais
foram vistos até agora. É aí que o princípio de dividir para conquistar entra:
particionamos o conjunto de pontos em duas metades com uma linha horizontal, e
recursivamente resolvemos o problema para cada metade. Para pontos P na metade de
cima, nada mais precisa ser feito, porque pontos na metade de baixo não podem jogar Q
para seu P. Para a metade de baixo, temos que considerar que por ignorar a metade de
cima até agora podemos ter perdido alguns pontos mais próximos. Contudo, podemos
pegar esses pontos de uma maneira similar como antes: percorrer por todos os pontos
em ordem de x + y, mantendo informações do melhor ponto na parte de cima (maior x –
y), e para cada ponto na metade de baixo, checar se esse melhor ponto de cima é melhor
que o vizinho atual.
Até agora foi assumido que qualquer conjunto de pontos pode ser eficientemente
particionado em Y e também percorrido na ordem de x + y sem se preocupar em como
isso deve ser feito. De fato, um dos aspectos mais incríveis dessa classe de algoritmos
envolvendo dividir para conquistar com varredura linear é que é essencialmente a
mesma estrutura que um merge sort, ao ponto que um merge sort por x + y pode ser
feito por um algoritmo de forma que cada subconjunto é ordenado em x + y apenas
quando isso é necessário (os pontos inicialmente são todos ordenados por Y). Isso dá
um algoritmo em tempo O (N log N).
A ideia de encontrar o ponto mais próximo em uma pedaço de ângulo
também pode ser usado para resolver a AGM euclidiana, porem o tempo de execução O
(N log N) não é mais garantido no pior caso, porque a distância não é mais uma equação
linear. É possível computar a AGM euclidiana em O (N log N), porque é um
subconjunto da triangulação de Delaunay.
3. Busca de Padrões
O problema de busca de padrões consiste em encontrar todas ou algumas ocorrências de
um conjunto de strings em outra string. Algoritmos voltados para esse problema são de
enorme importância em diversos campos da computação.
Exemplos mais comuns são mecanismos de buscas em documentos ou páginas
web e procura de sequências de DNA. Geralmente se trabalha com um volume de dados
muito grande, e por isso se deseja um algoritmo eficiente.
3.1. Definições
Uma string S é uma sequência finita de símbolos, chamados de caracteres, que
pertencem a um conjunto Σ, chamado de alfabeto. S geralmente é representada como
S0 S1 S2 …Sn-1 , onde n é o tamanho, quando S tem tamanho zero, diz-se que uma string é
vazia e é representada pelo símbolo ϵ.
Uma substring T de S é uma sequência contínua de elementos de S.
Representada como Sk Sk+1 Sk+2 …Sk+m-1 , com tamanho m e condição 0 ≤ k ≤ k+m ≤ n,
sendo k o índice de início e k+m o índice final, que não é incluído em T. Como a
sequência é contínua em [k,k+m), ela pode ser representada como um par ordenado (l,r),
onde 0 ≤ l ≤ r ≤ n, l representa o índice inicial e r o índice final, se l = r, a substring é
vazia. Uma substring também é uma string.
Uma substring (l,r) com l = 0, é dita prefixo, com r = n, é dita sufixo. Observa-se
que há (n+1)*n/2 substrings (distintas ou não), sendo n+1 delas prefixos, e n+1 sufixos
(como cada prefixo e sufixo tem tamanho diferente, eles são distintos). Quando a
substring é diferente da string geradora, ela é dita própria.
Diz-se que uma ocorrência de U em S é uma substring T de S tal que T = U.
Uma string é igual à outra se todos os seus caracteres são os mesmo e estão na mesma
ordem. Uma ocorrência pode ser representada pelo índice inicial do prefixo, pois já se
conhece o tamanho de U, e por isso o índice final.
3.2. Algoritmo ingênuo
A forma mais fácil de verificar as ocorrências de uma string U (de tamanho m) em S (de
tamanho n) é simplesmente comparar todas as substring de S com U, visto que U tem
um tamanho bem definido, basta verificar apenas as substring de S que têm o mesmo
tamanho, reduzindo o custo para n-m+1 comparações.
Cada comparação, feito do modo mais ingênuo tem custo linear (m), logo o
custo total é (n-m+1)*m operações, assintoticamente, O(nm). O pseudocódigo abaixo
mostra o algoritmo:
1 Igual(T,S):
2
Para cada índice x de T:
3
Se T[x] /= S[x]: Retorne falso
4
Retorne verdade
5 Ocorrências(S, U):
6
saída = {}
7
m = tamanho de U
8
Para cada prefixo (x,x+m) T de S:
9
Se T = S: saída += x
10
Retorne saída
3.3. K.M.P.
O algoritmo ingênuo pode ser reescrito em uma única função dessa forma:
1 Ocorrências(S, U):
2
saída = {}
3
n = tamanho de S
4
m = tamanho de U
5
Para x de 0 a n-1:
6
x` = x
7
Para y de 0 a m-1:
8
Se S[x`] /= T[y]: Quebre o loop de y
9
x` = x` + 1
10
Se o loop terminou sem quebra: saída += x
11
Retorne saída
O problema desse algoritmo é que os índices y e x` sempre são reiniciado para
cada x. O algoritmo de Knuth–Morris–Pratt (K.M.P.), criado em 1974, tenta resolver
esse problema aproveitando as comparações já realizadas antes. Seus autores são
Donald Knuth, James Morris e Vaughan Pratt.
Define-se a função de falha F, que mapeia cada prefixo (0,y) de U no maior
prefixo (0,F(y)) dele próprio de forma que (0,F(y)) seja um sufixo próprio de (0,y).
Dessa forma, se a comparação de uma substring (x,x` = x+y-1) de S foi realizada com
sucesso até o prefixo (0,y-1) de U, mas o caracter de U de índice y-1 causaria falha, o
sufixo dessa substring (x+y-1-F(y-1), x+y-1) de S realizará a comparação com sucesso
até (0,F(y-1)) de U.
Como os sufixos de (0,y-1) de U são mesmos de (x,x+y-1) de S, F(y-1) também
representará o maior prefixo da substring atual de S. O índice 0 é uma exceção, já que ϵ
não tem nenhum sufixo próprio, e por isso não tem sua função de falha bem definida,
todos os outros prefixos tem pelo menos ϵ como sufixo próprio.
Podemos assim reescrever o algoritmo do seguinte modo, observa-se que não é
mais explicitado o x atual (início da substring de S), apenas o x` (final), em todo passo,
x = x`-y:
1 Ocorrências(S, U):
2
saída = {}
3
n = tamanho de S
4
m = tamanho de U
5
y=0
6
F = funçãoFalha(U)
7
Para x` de 0 a n-1:
8
Enquanto S[x] /= T[y] e y /= 0:
9
y = F[y]
10
Se S[x] = T[y]: y = y+1
11
Se y = m: saída += x-m
12
Retorne saída
Observa-se que o índice x` é apenas incrementado (e nunca decrementado) e que
apesar de y também poder ser decrementado quando usada a função de falha, ele só é
incrementado quando x` também o é. Também é possível perceber que a quantidade de
operações realizadas no algoritmo é limitada pela quantidade de incrementos e
decrementos de x` e y. Já que x` é incrementado no máximo n vezes, y também é
incrementado no máximo n vezes, e para que y sempre seja maior ou igual a zero, ele
também deve ser decrementado no máximo n vezes. Logo o algoritmo realiza 3n
operações, assintoticamente O(n).
A função de falha de um prefixo (0,y) pode ser calculada com base em algum
sufixo de (0,y-1), como se quer o maior deles, primeiramente se investiga o sufixo
(0,F(y-1)), o caractere de índice F(y-1) não for igual ao caracter de índice y-1, o
processo pode ser repetido recursivamente para (0,F(y-1)). O código a seguir mostra
esse cálculo:
1 FunçãoFalha(U):
2
F inicialmente indefinido
3
m = tamanho de U
4
F = funçãoFalha(U)
5
Para y de 1 a m:
6
y` = y-1
7
Enquanto y` /= 0 e U[F(y`)] /= U[y-1]:
8
y` = F(y`)
9
Se y` /= 0: F(y) = F(y`) + 1
10
Senão: F(y) = 0
11
Retorne F
Novamente, observa-se que a quantidade de operações é limitada pela
quantidade de incrementos e decrementos dos índices: y e y`. y é incrementado no
máximo m vezes, e como é acessado logo no início do loop o valor F(y-1), que era o
valor de F(y) no final da iteração anterior, o y` pode ser “conservado”, logo ele é
decrementado no máximo m vezes, pois só é incrementado quando y também o é
(mesmo raciocínio usado anteriormente). Logo a complexidade desse cálculo é O(m).
A complexidade total do algoritmo K.M.P. é O(m+n).
3.3. Árvore de Prefixos
Também chamada de trie, uma árvore de prefixos é uma estrutura organizada em forma
de árvore, seu objetivo é representar um conjunto (dicionário) de strings. Suas folhas
representam prefixos e cada aresta representa uma letra, a letra adicionada a um prefixo
(pai) para que se gere outro (filho). Um nó é dito final quando o prefixo que ele
representa é uma string do dicionário, toda folha é um nó final.
Seja m a soma dos tamanhos de cada string do dicionário, haverá no máximo
m+1 nós na árvore (um para o prefixo vazio e o restante para cada prefixo de cada
string). E no máximo m arestas (o número de aresta em uma árvore é igual ao número
de nós menos um). Dessa forma, o espaço utilizado para armazenar a árvore é
assintoticamente igual ao espaço usado para armazenar as strings.
A figura abaixo é um exemplo da árvore usada com o dicionário {“casa”,
“carro”, “cor”, “coral”, “cerca” e “a”}, nós laranjas são nós finais. O conteúdo dos nós é
implícito: gerado pelo caminho da raiz (ϵ) até o nó.
Figura 7. Trie com as palavras "A", "CARRO", "CERCA", “COR” e "CORAL".
ϵ
C
A
CA
CE
CO
CAR
CER
COR
CARR
CERC
CORA
CARRO
CERCA
CORAL
Com essa estrutura, é possível realizar uma busca (também) ingênua mais
otimizada que uma busca ingênua que itera sobre todos os padrões:
1 Ocorrências(S,L):
2
T = montar Trie a parti da lista L
3
n = tamanho de S
4
saída = {}
5
Para x de 0 a n:
6
x`= x
7
v = raiz de T
8
Enquanto v não for final e x` < n:
9
Se há aresta Sx` partindo de v:
10
v = filho de v pela aresta Sx`
11
Senão:
12
Quebre o loop
13
Incremente x`
14
Se v é final:
15
Adicione a ocorrência à saída
16
Retorne saída
3.4. Aho-Corasick
O algoritmo de Aho-Corarisk, criado por Alfred Aho e Margaret Corasick em 1975 –
um ano depois do K.M.P., generaliza o algoritmo anterior para que possa ser trabalhado
em um conjunto de palavras (e não apenas uma).
Como a função de falha deve estar definida para todos os prefixos do prefixo
atual (que se quer calcular), esse cálculo deve ser executado através de uma BFS, dessa
forma, a função para os menores prefixos é calculada antes dos maiores. O
pseudocódigo a seguir mostra a adaptação da FunçãoFalha (que agora recebe uma trie):
1 FunçãoFalha(T):
2
F inicialmente indefinido
3
Para cada nó N de T (percorrida por uma BFS):
4
Se N é raiz, F é indefinida
5
N` = pai de N
6
c = último caractere de N
7
Enquanto N` não for raiz:
8
N` = F(N`)
9
Se há uma aresta c partindo de N`:
10
F(N) = filho de N` pelo caractere c
11
Se F(N) ainda está indefinida:
12
F(N) = raiz
13
Retorn F
Pelo mesmo princípio do cálculo da função de falha para um único padrão (no
algoritmo de K.M.P.), a complexidade do cálculo da função de falha para uma trie é
linear no número de nós que ela contém. Cada nó aproveita o cálculo de seu pai, e o
tamanho da string que a função para tal nó representa é no máximo um caractere maior
do que a string que a função de seu pai representa e no mínimo zero.
Observa-se que a estrutura da trie continua praticamente a mesma, porém agora
com a inserção da função de falha. Com essa nova função, pode-se percorrer a trie agora
de forma não ingênua, sempre que não houver uma aresta com o caractere que está
sendo processado na string, o nó atual se torna o nó da função de falha, exceto se o nó
atual for a raiz, nesse caso, apenas se passa para o próximo caractere, não há préprocessamento para aproveitar. O pseudocódigo a seguir mostra a adaptação do
algoritmo ingênuo.
1 Ocorrências(S,L):
2
T = montar Trie a parti da lista L
3
F = FunçãoFalha(T)
4
n = tamanho de S
5
saída = {}
6
x=0
7
v = raiz de T
8
Enquanto x < n:
9
Se há aresta Sx partindo de v:
10
v = filho de v pela aresta Sx
11
Incremente x
12
Senão e v nào é raiz:
13
v = F(v)
14
Incremente x`
15
Se v é final:
16
Adicione a ocorrência à saída
17
Retorne saída
O problema que surge é quando se encontra um padrão, mas o nó atual na trie
não é marcado como final, pois aquele prefixo que ele representa não faz parte do
dicionário, porém (como foi achado um padrão) um sufixo desse nó faz parte. Como a
função de falha retorna o maior prefixo que é sufixo próprio, todos os sufixos de um nó
podem ser encontrados a parti de algumas iterações sobre a função falha: N, F(N),
F(F(N)), F(F(F(N))), etc, são todos os sufixos de N que se encontram na trie.
Para resolver isso, basta marcar como final o nó que tem F(N) como final
também (inclusive quando F(N) foi marcado por F(F(N)) ser final, isso é, considerando
também a recursão). Por uma BFS é possível aproveitar, pois o tamanha de N sempre
será maior que o tamanho de F(N) e a BFS atualizará os valores dos menores prefixos
primeiro. O pseudo-código a seguir mostra isso:
1
2
3
4
AtualizarFinal(T):
Para cada nó N de T (percorrida por uma BFS):
Se N não é raiz e F(N) é final:
Faça N também ser final
Na figura a seguir, cada seta azul representa a função de falha para o nó, com
exceção dos nós da primeira camada, aqueles que têm sua função igual à raiz, estão
implicitamente representados por não terem seta. Observe que os nós “CA” e “CORA”
tornaram-se finais, pois “A” é final.
Figura 8. Trie após o cálculo da função falha e atualização de nós finais.
ϵ
C
A
CA
CE
CO
CAR
CER
COR
CARR
CERC
CORA
CARRO
CERCA
CORAL
3.5. Outras abordagens
Existem outras abordagens eficientes para a busca de padrão em situações mais
específicas. As abordagens citadas anteriormente, por exemplo, não são as mais
indicadas quando há busca por padrões pequenos e imprevisíveis – como em indexação
do conteúdo de vários arquivos grandes de um sistema com consultas de pequenos
textos.
Para isso, pode-se trabalhar com árvore, vetor ou autômato de sufixos, técnicas
bastante eficientes com um pré-processamento linear único por texto indexado e busca
de padrão de em tempo logaritmos em relação ao texto indexado e linear em relação ao
padrão.
Outra técnica bastante usada consiste em representar um texto como um
polinômio com grau igual ao seu tamanho e coeficientes iguais a valores de seus
caracteres. Como o alfabeto é limitado, os coeficientes do polinômio também o são. Ao
usar uma base do tamanho do dicionário, é possível representar o texto como um
número.
Infelizmente, trabalhar com números muito grandes também é custoso, mas com
uma probabilidade muita alta de estar correto, é possível realizar operações com tais
números em módulo na máxima representação numérica primitiva (um inteiro de 64
bits, por exemplo) do sistema computacional envolvido.
4. Conclusão
Algoritmos são essenciais para a informática e áreas dependentes dela. A busca
constante para criar novos e aperfeiçoar os já existentes é tão necessária para o
desenvolvimento das áreas científicas quanto a evolução tecnológica, esse estudo
permite que problemas sejam resolvidos de forma mais eficiente. A análise focada em
alguns assuntos específicos pode resultar em vários algoritmos que podem ser aplicados
em diversas áreas.
O artigo exemplificou como a técnica de varredura linear pode ser usada para
resolver diversos problemas aparentemente não relacionados de forma similar.
Enquanto que estudos realizados em prefixos de strings resultaram em algoritmos e
estruturas de dados muito eficientes bastante usados e que permitem uma grande
evolução no tratamento de banco de dados para busca de padrões.
Referências
Aho, Alfred V., Corasick, Margaret J. (1975) "Efficient string matching: An aid to
bibliographic search". Communications of the ACM 18, número 6
Knuth, Donald E., Morris, James H., Pratt, Vaughan R. (1977) "Fast pattern matching in
strings". SIAM Journal on Computing 6, número 2
Graham, Ronald L., Knuth, Donald E., Patashnik, Oren (1994) “Concrete
Mathematics”, Second Edition. Addison-Wesley Publishing Company
Vladu, Adrian, Negruşeri, Cosmin (2005) "Suffix arrays - a programming contest
approach". GInfo 15/7, Novembro
de Berg, Mark, Cheong, Otfried, van Kreveld, Marc, Overmars, Mark (2008)
“Computational Geometry: Algorithms and Applications”, Third Edition. Springer.
Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. and Stein, Clifford (2009)
“Introduction to Algorithms”, Third Edition. The MIT Press