Matriz de sufixo

Na ciência da computação, uma matriz de sufixo é uma matriz que especifica os sufixos de uma sequência de caracteres em ordem lexicográfica .

exemplo

Considere a string = de comprimento 11. Uma vez que a string vazia também é um sufixo válido, adicionamos o marcador de final ao final de para poder expressar a string vazia ou o final de . A string com as posições associadas de seus caracteres é assim: ${\ displaystyle S}$abracadabra${\ displaystyle S}$$${\ displaystyle S}$

Eu	1	2	3	4º	5	6	7º	8º	9	10	11	12º
${\ displaystyle S [i]}$	uma	b	r	uma	c	uma	d	uma	b	r	uma	$

Esta string tem doze sufixos, que também podem ser descritos por sua posição inicial iem : ${\ displaystyle S}$

A string vazia é lexicograficamente menor do que qualquer sufixo de . Portanto, por convenção , o marcador final também é lexicograficamente menor do que qualquer outro caractere na string. Assim, todos os sufixos podem ser classificados lexicograficamente: ${\ displaystyle S}$$

Representado como uma matriz de resultados {$, a$, abra$, …}.

Se a string original for conhecida, cada sufixo pode ser especificado usando o índice de seu primeiro caractere para economizar espaço. A matriz de sufixo é uma matriz desses índices em ordem lexicográfica. A abracadabra$matriz de sufixos para a string é assim = : O sufixo “a” ou “a $” começa no décimo primeiro caractere, “abra” no oitavo caractere e assim por diante. ${\ displaystyle A}${12,11,8,1,4,6,9,2,5,7,10,3}

O marcador final $é útil ao combinar várias strings. Por exemplo, em = é imediatamente claro que o texto consiste em duas cadeias de caracteres e . Se apenas uma string for considerada, este sufixo pode ser ignorado: Como a string vazia é sempre classificada lexicograficamente antes de todas as outras, nenhuma informação é perdida neste caso. ${\ displaystyle S '}$abracadabra$mississippi$abracadabramississippi

Algoritmos

Existem vários algoritmos para construir uma matriz de sufixos a partir de um determinado texto de comprimento n . Os métodos usados ​​para classificação de sufixo podem ser divididos aproximadamente em três classes: classificação iterativa, recursiva e induzida.

Classificação parcial iterativa

A maneira mais simples é usar um algoritmo de classificação baseado em comparação eficiente que requer no máximo comparações. Como a comparação de dois sufixos leva tempo, o tempo de execução completo desse procedimento é . Algoritmos mais desenvolvidos melhoram isso usando os resultados de comparações parciais e, assim, evitando comparações redundantes. ${\ displaystyle O (n \ log n)}$${\ displaystyle O (n)}$${\ displaystyle O (n ^ {2} \ log n)}$${\ displaystyle O (n \ log n)}$

Para este fim, apenas a primeira letra de cada sufixo é considerada e uma matriz de sufixos preliminar é construída a partir dela, que ainda não classificou sufixos com a mesma primeira letra entre si. No entanto, sufixos com letras iniciais diferentes já estão incluídos na ordem correta. Em uma segunda etapa, cada grupo de sufixos com a mesma letra inicial é classificado de forma que sejam classificados corretamente em relação às duas primeiras letras. A terceira etapa classifica todos os grupos de sufixos com duas primeiras letras idênticas para que sejam classificados corretamente em relação às primeiras quatro, a quarta etapa para que sejam classificados corretamente em relação às primeiras oito e assim por diante. Após as etapas, cada sufixo é classificado de forma completamente correta e a matriz de sufixos é totalmente construída. Cada etapa parcial é possível no tempo , de modo que os resultados de tempo de execução total .${\ displaystyle \ log _ {2} n}$${\ displaystyle O (n)}$${\ displaystyle O (n \ log n)}$

Essa classe inclui o algoritmo de matriz de sufixo clássico de Manber e Myers e o algoritmo de Larsson e Sadakane, que é muito mais eficiente na prática.

Algoritmos recursivos

Essa classe de algoritmos só é pesquisada desde 2003. Os caracteres da string são divididos em duas strings de caracteres x e y . O algoritmo é então chamado recursivamente em x . Com a matriz de sufixo de x calculada dessa maneira , a matriz de sufixo de y pode ser calculada de forma eficiente (“induzida”). Uma vez que a divisão em x e y é conhecido, a matriz de sufixo podem ser lidos a partir dele. ${\ displaystyle S}$${\ displaystyle S}$

Por inteligentemente escolha x e y , a maioria destes algoritmos têm uma duração de . No entanto, como a recursão é cara na prática, nem sempre é preferível.${\ displaystyle O (n)}$

Seleção induzida

Aqui também, com uma matriz de sufixos já calculada de uma seqüência de caracteres x, a matriz de sufixos de uma seqüência de caracteres y é calculada de forma eficiente (induzida). Em vez de um método de trabalho recursivo, por exemplo, a string pode ser executada várias vezes em diferentes direções. Os caracteres são classificados em x ou y , parcialmente classificados e posteriormente classificados em uma etapa posterior com base em outros resultados parciais. Os algoritmos desta classe são muito diversos. Quase todos eles têm em comum, entretanto, que eles são geralmente mais rápidos do que algoritmos recursivos na prática, apesar do tempo de execução de pior caso geralmente pobre . Eles também geralmente requerem muito menos espaço de armazenamento do que outros algoritmos.${\ displaystyle S}$${\ displaystyle O (n ^ {2} \ log n)}$

O algoritmo mais rápido atualmente nesta classe é o algoritmo de ordenação induzida por matriz de sufixo (SAIS para abreviar) de Nong, Zhang e Chan. Ele só precisa de um tempo de execução em . O algoritmo SAIS também prova ser muito rápido na prática quando vários efeitos, como B. As falhas de cache são levadas em consideração.${\ displaystyle O (n)}$

Formulários

Depois de construída, a matriz de sufixos pode ser usada como um índice do texto para executar com eficiência as operações subsequentes. Essas operações incluem consultas de pesquisa e métodos de compactação.

Consultas de pesquisa exatas (correspondência de string)

Uma consulta de pesquisa exata consiste em um padrão de pesquisa que deve ser pesquisado em um texto . Uma passagem de texto só conta como uma ocorrência exata se todos os caracteres na passagem de texto corresponderem. Desta forma, essas consultas diferem das consultas inexatas nas quais um número especificado de caracteres divergentes é permitido. É nas consultas de pesquisa exatas entre solicitações de decisão ("Come in before?"), Número de solicitações ("Quantas vezes na frente?") E solicitações de enumeração ("Em que pontos está na frente?"), Dependendo de onde as solicitações de decisão , se necessário, usando pedidos de número e consultas de número podem ser respondidas com consultas de enumeração. ${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle T}$

Para determinar o número de ocorrências exatas de , todos os sufixos que começam com devem ser procurados na matriz de sufixos de . Como a matriz de sufixos é classificada, esses sufixos estão todos diretamente atrás uns dos outros e formam um bloco. Portanto, é suficiente determinar o sufixo lexicograficamente menor e o maior lexicograficamente com o qual começam. Com a ajuda da pesquisa binária, eles podem ser encontrados em, onde em a seguir representa o comprimento de e o comprimento de . O número de ocorrências de é então igual ao número de sufixos neste bloco. Isso permite que o número total de ocorrências em seja determinado. Se, além disso, a saída das posições iniciais de todas as ocorrências exatas for necessária, os valores da matriz de sufixos no bloco devem ser retornados. O tempo de execução para isso é , onde representa o número de ocorrências de in . ${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle O (m \ cdot \ log n)}$${\ displaystyle m}$${\ displaystyle P}$${\ displaystyle n}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle O (m \ cdot \ log n)}$${\ displaystyle O (m \ cdot \ log n + \ vert O_ {P} \ vert)}$${\ displaystyle \ vert O_ {P} \ vert}$${\ displaystyle P}$${\ displaystyle T}$

Métodos refinados podem alcançar melhores tempos de execução com a ajuda de estruturas de dados adicionais. Se a assim chamada matriz LCP (prefixo comum mais longo) foi determinada e uma estrutura de dados RMQ adequada (consulta de intervalo mínimo) foi construída para a matriz LCP, as consultas de decisão e número em e as consultas de enumeração podem ser respondidas . ${\ displaystyle T}$${\ displaystyle O (m)}$${\ displaystyle O (m + \ vert O_ {P} \ vert)}$

Construção de uma árvore de sufixo

A matriz de sufixos de um texto é freqüentemente usada como uma etapa intermediária para construir a árvore de sufixos associada no tempo linear. A árvore de sufixos também pode ser usada como um índice para responder a consultas de pesquisa. ${\ displaystyle T}$

compressão

Vários métodos de compressão podem ser implementados de forma eficiente usando a matriz de sufixo. Desta forma, a fatoração da compressão LZ77 pode ser implementada em tempo linear. Além disso, a transformação de Burrows-Wheeler do texto pode ser calculada a partir de uma matriz de sufixo existente com muito pouco esforço . Para isso, para cada sufixo da matriz de sufixo, o caractere que está exatamente uma posição antes do sufixo no texto é determinado e armazenado em uma matriz. A matriz resultante é então idêntica à transformação Burrows-Wheeler do texto e pode ser usada, por exemplo, para o método de compressão bzip2 .

história

Matrizes de sufixo foram originalmente desenvolvidas por Gene Myers e Udi Manber em 1990 para reduzir o consumo de memória em comparação com árvores de sufixo . Depois de alguns anos, nenhuma descoberta significativa surgiu, as matrizes de sufixos têm sido um tópico de pesquisa popular desde cerca de 2000. Desde então, uma variedade de algoritmos de design foram desenvolvidos com inúmeras propriedades desejáveis.

Algoritmos existem desde 1999 que são mais rápidos do que os algoritmos de tempo linear existentes na maioria das aplicações, mas no pior caso requerem um tempo na faixa de . Os primeiros algoritmos de tempo linear garantido (ou seja, aqueles com o pior caso de tempo de execução ) só são conhecidos desde 2003. É sabido desde 2004 que as matrizes de sufixo podem resolver qualquer problema com a mesma complexidade de tempo que as árvores de sufixo . Desde então, o mais tardar, matrizes de sufixos têm sido o método de escolha para quase todas as tarefas de classificação de sufixos e strings. ${\ displaystyle O (n \ log n)}$${\ displaystyle O (n ^ {2} \ log n)}$${\ displaystyle O (n)}$

A partir de 2005, o armazenamento eficiente de matrizes de sufixos também foi considerado, além do design. Além de matrizes de sufixo puras, as matrizes de sufixo compactadas agora também podem ser construídas e usadas com eficiência. Eles também são úteis para índices de texto completo compactados com base na transformação Burrows-Wheeler .

literatura

• Udi Manber, Gene Myers: matrizes de sufixo: um novo método para pesquisas de string on-line . In: SIAM Journal on Computing , Volume 22, Issue 5, October 1993, pp. 935-948.
• Pang Ko, Srinivas Aluru: Construção linear em tempo eficiente de matrizes de sufixo . In: Combinatorial Pattern Matching (CPM 03) . LNCS 2676, Springer, 2003, pp. 203-210.
• Juha Kärkkäinen, Peter Sanders: Construção de matriz de sufixo de trabalho linear simples . (PDF; 193 kB) In: Proc. 30º Colóquio Internacional sobre Autômatos, Linguagens e Programação (ICALP '03) . LNCS 2719, Springer, 2003, pp. 943-955.
• Enno Ohlebusch: Algoritmos de Bioinformática: Análise de Seqüência, Reorganizações de Genoma e Reconstrução Filogenética . Oldenbusch, Bremen 2013, uni-ulm.de
• Klaus-Bernd Schürmann, Jens Stoye: Um algoritmo incomplex para construção rápida de array de sufixos . (PDF; 204 kB) In: Anais da ALENEX , 2005.

Links da web

• Exemplo de uso de matrizes de sufixo para pesquisar palavras em um dicionário

Evidência individual

1. ↑ ^{a b c} Simon J. Puglisi, WF Smyth, Andrew H. Turpin: A Taxonomy of Suffix Array Construction Algorithms . In: ACM Computing Surveys (CSUR) 39.2 (2007)
2. ↑ ^{a b} U. Manber, GW Myers: Matrizes de sufixo: Um novo método para pesquisas de strings on-line . Em Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (1990)
3. ↑ ^{a b} J.N. Larsson, K. Sadakane: Faster sufixo sorting . Em representante técnico. LU-CS-TR: 99-214 , Dep. of Computer Science, Lund University, Sweden (1999)
4. ^ Nong Ge, Sen Zhang, Wai Hong Chan: T wo algoritmos eficientes para a construção da matriz de sufixo de tempo linear . In: IEEE Transactions on Computers 60 , no.10 (outubro de 2011), pp. 1471-1484.
5. ↑ Nataliya Timoshevskaya, Wu-chun Feng: SAIS-OPT: Sobre a caracterização e otimização do algoritmo SA-IS para a construção de matrizes de sufixos . In: 2014 IEEE 4ª Conferência Internacional sobre Avanços Computacionais em Ciências Biomédicas (ICCABS) , 2014.
6. ↑ Enno Ohlebusch: Algoritmos de bioinformática. Análise de Seqüência, Reorganização do Genoma e Reconstrução Filogenética. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2 , página 116.
7. ↑ Enno Ohlebusch: Algoritmos de bioinformática. Análise de Seqüência, Reorganização do Genoma e Reconstrução Filogenética. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2 , pp. 120-125.
8. ↑ Enno Ohlebusch: Algoritmos de bioinformática. Análise de Seqüência, Reorganização do Genoma e Reconstrução Filogenética. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2 , pp. 117-118.
9. ↑ Enno Ohlebusch: Algoritmos de bioinformática. Análise de Seqüência, Reorganização do Genoma e Reconstrução Filogenética. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2 , pp. 113-114.
10. ↑ Enno Ohlebusch: Algoritmos de bioinformática. Análise de Seqüência, Reorganização do Genoma e Reconstrução Filogenética. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2 , página 130.
11. ↑ Juha Kärkkäinen: BWT rápido em espaço pequeno por classificação de sufixo em bloco. In: Ciência da Computação Teórica. Volume 387, No. 3, 2007, p. 251 ( PDF; 227 KB )
12. ↑ S. Burkhardt, J. Kärkkäinen: Construção e verificação rápida e leve da matriz de sufixos . In: Anais do 14º Simpósio Anual CPM 2003
13. ↑ P. Ko, S. Aluru: Espaço eficiente linear em tempo de construção de matrizes de sufixo . In: Anais do 14º Simpósio Anual CPM 2003
14. ↑ Juha Kärkkäinen, Peter Sanders: Construção de matriz de sufixo de trabalho linear simples . (PDF; 193 kB) In_ Proc. 30º Colóquio Internacional sobre Autômatos, Linguagens e Programação (ICALP '03) . LNCS 2719, Springer, 2003, pp. 943-955
15. ↑ MI Abouelhoda, S. Kurtz, E. Ohlebusch: Substituindo árvores de sufixo por matrizes de sufixo . Em J. Disc. Algor. 2 , 1, 2004, pp. 53-86
16. ^ R. Grossi, J. Vitter: matrizes de sufixo compactadas e árvores de sufixo com aplicações para indexação de texto e correspondência de string . Em SIAM J. Comput. 35.2, 2005, pp. 378-407
17. ^ G. Navarro, V. Mäkinen: Compressed full-text indexes . In_ ACM Comput. Serv. , 39, 1.2, 2007