Algoritmos de String
Algoritmos de string processam sequências de símbolos — texto, DNA ou outros dados lineares — para encontrar padrões, indexar grandes textos para busca rápida e alinhar sequências por similaridade.
Definition
Algoritmos de string são procedimentos e estruturas de dados que operam em strings — sequências finitas de caracteres extraídos de um alfabeto — para resolver problemas como localizar padrões, indexar para busca rápida e medir ou alinhar a similaridade entre sequências.
Scope
Esta área abrange algoritmos e estruturas de dados especializados para strings: casamento de padrões exato e aproximado, estruturas de índice (tries, árvores e arrays de sufixos) que pré-processam texto para consultas repetidas, e métodos de alinhamento de sequências para comparar strings. Conecta-se à programação dinâmica (alinhamento), estruturas de dados (árvores e arrays) e aplicações em biologia computacional, recuperação de texto e processamento de linguagem natural.
Sub-topics
Core questions
- Como um padrão pode ser localizado em um texto mais rapidamente do que a comparação ingênua caractere por caractere?
- Como um texto grande é pré-processado para que muitas consultas posteriores sejam rápidas?
- Como a similaridade entre duas strings é definida e calculada?
- Como o tamanho do alfabeto e o comprimento da string afetam a eficiência dos algoritmos de string?
- Como os métodos de casamento exato se estendem ao casamento aproximado ou de múltiplos padrões?
Key concepts
- alfabeto e string
- casamento de padrões exato
- Knuth-Morris-Pratt e Boyer-Moore
- tries
- árvores de sufixos e arrays de sufixos
- distância de edição
- alinhamento de sequências
- casamento aproximado
Key theories
- Casamento de padrões exato em tempo linear
- Ao pré-processar o padrão para explorar informações de casamentos parciais, algoritmos como Knuth-Morris-Pratt e Boyer-Moore encontram todas as ocorrências de um padrão em tempo linear em relação ao comprimento do texto, evitando o custo quadrático do casamento ingênuo.
- Estruturas de índice para texto
- Árvores de sufixos e arrays de sufixos pré-processam um texto para que consultas de padrões arbitrários, repetições e questões de substring comum mais longa possam ser respondidas rapidamente, trocando o custo de construção por uma busca repetida rápida.
Clinical relevance
Algoritmos de string são fundamentais para a busca de texto e bioinformática: o casamento de padrões impulsiona utilitários de busca, editores de texto e detecção de intrusões; estruturas de sufixos indexam motores de busca e bancos de dados genômicos; e o alinhamento de sequências é central para comparar sequências de DNA, RNA e proteínas em biologia molecular.
History
O casamento de strings eficiente surgiu na década de 1970 com os algoritmos de Knuth-Morris-Pratt (1977) e Boyer-Moore (1977). Árvores de sufixos (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) e, posteriormente, arrays de sufixos (Manber e Myers, 1990) proporcionaram uma indexação poderosa, e o campo se expandiu rapidamente através da biologia computacional, conforme abordado no texto de Gusfield de 1997.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- Por que pré-processar o padrão ou texto em vez de pesquisar diretamente?
- O casamento ingênuo pode levar um tempo proporcional ao produto dos comprimentos do padrão e do texto. O pré-processamento do padrão (como em Knuth-Morris-Pratt) proporciona uma busca em tempo linear, e o pré-processamento do texto em um índice (árvore ou array de sufixos) permite que muitas consultas posteriores sejam executadas muito mais rapidamente, o que compensa quando o mesmo texto é pesquisado repetidamente.
- Como os algoritmos de string são usados em biologia?
- DNA, RNA e proteínas são naturalmente representados como strings, então o casamento de padrões localiza motivos, estruturas de sufixos indexam genomas para busca rápida, e algoritmos de alinhamento de sequências quantificam a similaridade entre sequências para inferir relações evolutivas e função.