Matriz de sufixo - Suffix array

Matriz de sufixo
Modelo	Variedade
Inventado por	Manber e Myers (1990)
Complexidade de tempo; em notação grande O

Na ciência da computação , um array de sufixos é um array ordenado de todos os sufixos de uma string . É uma estrutura de dados usada, entre outros, em índices de texto completo, algoritmos de compressão de dados e no campo da bibliometria .

Matrizes de sufixo foram introduzidas por Manber & Myers (1990) como uma alternativa simples e eficiente em termos de espaço para árvores de sufixo . Eles foram independentemente descobertos por Gaston Gonnet em 1987 sob o nome de matriz PAT ( Gonnet, Baeza-Yates & Snider 1992 ).

Li, Li & Huo (2016) deram o primeiro algoritmo de construção de matriz de sufixo de tempo no local que é ideal tanto no tempo quanto no espaço, onde no local significa que o algoritmo só precisa de espaço adicional além da string de entrada e da matriz de sufixo de saída. ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (1)}$

Matrizes de sufixo aprimoradas (ESAs) são matrizes de sufixo com tabelas adicionais que reproduzem a funcionalidade completa das árvores de sufixo preservando o mesmo tempo e complexidade de memória. A matriz de sufixos para um subconjunto de todos os sufixos de uma string é chamada de matriz de sufixos esparsos . Vários algoritmos probabilísticos foram desenvolvidos para minimizar o uso de memória adicional, incluindo um tempo ideal e algoritmo de memória.

Definição

Let ser uma -string e deixe denotar a substring variando de a inclusive. ${\ displaystyle S = S [1] S [2] ... S [n]}$ ${\ textstyle n}$ ${\ displaystyle S [i, j]}$ ${\ displaystyle S}$ ${\ displaystyle i}$ ${\ displaystyle j}$

A matriz de sufixos de agora é definida como uma matriz de inteiros fornecendo as posições iniciais dos sufixos de na ordem lexicográfica . Este meio, uma entrada contém a posição de partida da menor sufixo -ésimo em e, assim, para todos : . ${\ displaystyle A}$ ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle A [i]}$ ${\ displaystyle i}$ ${\ displaystyle S}$ ${\ displaystyle 1 <i \ leq n}$ ${\ displaystyle S [A [i-1], n] <S [A [i], n]}$

Cada sufixo de aparece exatamente uma vez. Os sufixos são strings simples. Essas strings são classificadas (como em um dicionário de papel), antes que suas posições iniciais (índices inteiros) sejam salvas em . ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle A}$

Exemplo

Considere o texto = a ser indexado: ${\ displaystyle S}$ banana$

eu	1	2	3	4	5	6	7
${\ displaystyle S [i]}$	b	uma	n	uma	n	uma	$

O texto termina com a carta sentinela especial $que é única e lexicograficamente menor do que qualquer outro caractere. O texto possui os seguintes sufixos:

Sufixo	eu
banana $	1
anana $	2
nana $	3
ana $	4
na $	5
um $	6
$	7

Esses sufixos podem ser classificados em ordem crescente:

Sufixo	eu
$	7
um $	6
ana $	4
anana $	2
banana $	1
na $	5
nana $	3

A matriz de sufixos contém as posições iniciais desses sufixos classificados: ${\ displaystyle A}$

i =	1	2	3	4	5	6	7
${\ displaystyle A [i]}$ =	7	6	4	2	1	5	3

A matriz de sufixos com os sufixos escritos verticalmente por baixo para maior clareza:

i =	1	2	3	4	5	6	7
${\ displaystyle A [i]}$ =	7	6	4	2	1	5	3
1	$	uma	uma	uma	b	n	n
2		$	n	n	uma	uma	uma
3			uma	uma	n	$	n
4			$	n	uma		uma
5				uma	n		$
6				$	uma
7					$

Portanto, por exemplo, contém o valor 4 e, portanto, refere-se ao sufixo começando na posição 4 dentro , que é o sufixo . ${\ displaystyle A [3]}$ ${\ displaystyle S}$ ana$

Correspondência para árvores de sufixo

Matrizes de sufixo estão intimamente relacionadas às árvores de sufixo :

Matrizes de sufixo podem ser construídas executando uma travessia em profundidade de uma árvore de sufixo. A matriz de sufixos corresponde aos rótulos de folha fornecidos na ordem em que são visitados durante a travessia, se as arestas forem visitadas na ordem lexicográfica de seu primeiro caractere.
Uma árvore de sufixo pode ser construída em tempo linear usando uma combinação de array de sufixos e array LCP . Para obter uma descrição do algoritmo, consulte a seção correspondente no artigo da matriz LCP .

Foi demonstrado que cada algoritmo de árvore de sufixo pode ser sistematicamente substituído por um algoritmo que usa uma matriz de sufixo aprimorada com informações adicionais (como a matriz LCP ) e resolve o mesmo problema na mesma complexidade de tempo. Vantagens de matrizes de sufixo sobre árvores de sufixo incluem requisitos de espaço aprimorados, algoritmos de construção linear de tempo mais simples (por exemplo, em comparação com o algoritmo de Ukkonen ) e localidade de cache aprimorada.

Eficiência de espaço

Arrays de sufixo foram introduzidos por Manber & Myers (1990) para melhorar os requisitos de espaço das árvores de sufixo : Arrays de sufixo armazenam inteiros. Assumindo que um inteiro requer bytes, uma matriz de sufixo requer bytes no total. Isso é significativamente menor do que os bytes exigidos por uma implementação cuidadosa da árvore de sufixos. ${\ displaystyle n}$ ${\ displaystyle 4}$ ${\ displaystyle 4n}$ ${\ displaystyle 20n}$

No entanto, em certas aplicações, os requisitos de espaço de matrizes de sufixo ainda podem ser proibitivos. Analisado em bits, um array de sufixos requer espaço, enquanto o texto original sobre um alfabeto de tamanho requer apenas bits. Pois um genoma humano com e a matriz de sufixos ocuparia, portanto, cerca de 16 vezes mais memória do que o próprio genoma. ${\ displaystyle {\ mathcal {O}} (n \ log n)}$ ${\ displaystyle \ sigma}$ ${\ displaystyle {\ mathcal {O}} (n \ log \ sigma)}$ ${\ displaystyle \ sigma = 4}$ ${\ displaystyle n = 3,4 \ vezes 10 ^ {9}}$

Essas discrepâncias motivaram uma tendência para matrizes de sufixos compactados e índices de texto completo compactados baseados no BWT , como o índice FM . Essas estruturas de dados requerem apenas espaço dentro do tamanho do texto ou até menos.

Algoritmos de construção

Uma árvore de sufixo pode ser construída e convertida em uma matriz de sufixo percorrendo a árvore em profundidade, também em , portanto, existem algoritmos que podem construir uma matriz de sufixo em . ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$

Uma abordagem ingênua para construir uma matriz de sufixo é usar um algoritmo de classificação baseado em comparação . Esses algoritmos requerem comparações de sufixo, mas uma comparação de sufixo é executada no tempo, portanto, o tempo de execução geral dessa abordagem é . ${\ displaystyle {\ mathcal {O}} (n \ log n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n ^ {2} \ log n)}$

Algoritmos mais avançados tiram vantagem do fato de que os sufixos a serem classificados não são strings arbitrárias, mas relacionadas entre si. Esses algoritmos se esforçam para atingir os seguintes objetivos:

complexidade assintótica mínima ${\ displaystyle \ Theta (n)}$
leve no espaço, o que significa pouca ou nenhuma memória de trabalho ao lado do texto e a própria matriz de sufixo é necessária
rápido na prática

Um dos primeiros algoritmos a atingir todos os objetivos é o algoritmo SA-IS de Nong, Zhang & Chan (2009) . O algoritmo também é bastante simples (<100 LOC ) e pode ser aprimorado para construir simultaneamente o array LCP . O algoritmo SA-IS é um dos mais rápidos algoritmos de construção de matriz de sufixo conhecidos. Uma implementação cuidadosa de Yuta Mori supera a maioria das outras abordagens de construção linear ou superlinear.

Além dos requisitos de tempo e espaço, os algoritmos de construção de matriz de sufixo também são diferenciados por seu alfabeto compatível : alfabetos constantes em que o tamanho do alfabeto é limitado por uma constante, alfabetos inteiros onde os caracteres são inteiros em um intervalo dependendo de e alfabetos gerais onde apenas comparações de caracteres são permitidas . ${\ displaystyle n}$

A maioria dos algoritmos de construção de matriz de sufixo é baseada em uma das seguintes abordagens:

Algoritmos de duplicação de prefixo são baseados na estratégia de Karp, Miller & Rosenberg (1972) . A ideia é encontrar prefixos que honrem a ordenação lexicográfica dos sufixos. O comprimento do prefixo avaliado dobra em cada iteração do algoritmo até que um prefixo seja único e forneça a classificação do sufixo associado.
Algoritmos recursivos seguem a abordagem do algoritmo de construção de árvore de sufixo de Farach (1997) para classificar recursivamente um subconjunto de sufixos. Esse subconjunto é então usado para inferir uma matriz de sufixos dos sufixos restantes. Ambas as matrizes de sufixo são então mescladas para calcular a matriz de sufixo final.
Os algoritmos de cópia induzida são semelhantes aos algoritmos recursivos no sentido de que usam um subconjunto já classificado para induzir uma classificação rápida dos sufixos restantes. A diferença é que esses algoritmos favorecem a iteração em vez da recursão para classificar o subconjunto de sufixos selecionado. Uma pesquisa desse grupo diversificado de algoritmos foi elaborada por Puglisi, Smyth & Turpin (2007) .

Um algoritmo recursivo bem conhecido para alfabetos inteiros é o algoritmo DC3 / skew de Kärkkäinen & Sanders (2003) . Ele roda em tempo linear e tem sido usado com sucesso como base para algoritmos de construção de matriz de sufixo de memória externa e paralela .

Trabalho recente de Salson et al. (2010) propõe um algoritmo para atualizar a matriz de sufixos de um texto editado em vez de reconstruir uma nova matriz de sufixos do zero. Mesmo que a complexidade de tempo teórica de pior caso seja , ela parece funcionar bem na prática: resultados experimentais dos autores mostraram que sua implementação de matrizes de sufixos dinâmicos é geralmente mais eficiente do que reconstruir quando se considera a inserção de um número razoável de letras no texto original. ${\ displaystyle {\ mathcal {O}} (n \ log n)}$

No trabalho prático de código aberto , uma rotina comumente usada para a construção de array de sufixos era qsufsort, com base no algoritmo Larsson-Sadakane de 1999. Essa rotina foi substituída pelo DivSufSort de Yuta Mori, "o algoritmo de classificação de sufixo mais rápido conhecido na memória principal" em 2017. Ele também pode ser modificado para calcular um array LCP. Ele usa uma cópia induzida combinada com Itoh-Tanaka. Em 2021, uma implementação mais rápida do algoritmo foi apresentada por Ilya Grebnov que, em média, apresentou melhoria de desempenho de 65% em relação à implementação do DivSufSort no Silesia Corpus.

Matriz de sufixo generalizado

O conceito de matriz de sufixo pode ser estendido a mais de uma string. Isso é chamado de array de sufixos generalizado (ou GSA), um array de sufixos que contém todos os sufixos para um conjunto de strings (por exemplo, e é classificado lexicograficamente com todos os sufixos de cada string. ${\ displaystyle S = S_ {1}, S_ {2}, S_ {3}, ..., S_ {k}}$

Formulários

A matriz de sufixos de uma string pode ser usada como um índice para localizar rapidamente cada ocorrência de um padrão de substring dentro da string . Encontrar todas as ocorrências do padrão é equivalente a encontrar todos os sufixos que começam com a substring. Graças à ordem lexicográfica, esses sufixos serão agrupados na matriz de sufixos e podem ser encontrados de forma eficiente com duas pesquisas binárias . A primeira pesquisa localiza a posição inicial do intervalo, e a segunda determina a posição final: ${\ displaystyle P}$ ${\ displaystyle S}$

n = len(S)
def search(P: str) -> Tuple[int, int]:
    """
    Return indices (s, r) such that the interval A[s:r] (including the end
    index) represents all suffixes of S that start with the pattern P.
    """
    # Find starting position of interval
    l = 0  # in Python, arrays are indexed starting at 0
    r = n
    while l < r:
        mid = (l + r) // 2  # division rounding down to nearest integer
        # suffixAt(A[i]) is the ith smallest suffix
        if P > suffixAt(A[mid]):
            l = mid + 1
        else:
            r = mid
    s = l
    
    # Find ending position of interval
    r = n
    while l < r:
        mid = (l + r) // 2
        if suffixAt(A[mid]).startswith(P):
            l = mid + 1
        else:
            r = mid
    return (s, r)

Encontrar o padrão de substring de comprimento na string de comprimento leva tempo, visto que uma única comparação de sufixo precisa comparar caracteres. Manber e Myers (1990) descrevem como esse limite pode ser aprimorado para o tempo usando as informações do LCP . A ideia é que uma comparação de padrões não precise comparar novamente determinados caracteres, quando já se sabe que eles fazem parte do maior prefixo comum do padrão e do intervalo de busca atual. Abouelhoda, Kurtz & Ohlebusch (2004) melhoram o limite ainda mais e alcançam um tempo de busca de como conhecido a partir de árvores de sufixo . ${\ displaystyle P}$ ${\ displaystyle m}$ ${\ displaystyle S}$ ${\ displaystyle n}$ ${\ displaystyle {\ mathcal {O}} (m \ log n)}$ ${\ displaystyle m}$ ${\ displaystyle {\ mathcal {O}} (m + \ log n)}$ ${\ displaystyle {\ mathcal {O}} (m)}$

Algoritmos de classificação de sufixo podem ser usados para calcular a transformada de Burrows – Wheeler (BWT) . O BWT requer a classificação de todas as permutações cíclicas de uma string. Se esta string terminar em um caractere especial de fim de string que é lexicograficamente menor que todos os outros caracteres (ou seja, $), então a ordem da matriz BWT rotacionada classificada corresponde à ordem dos sufixos em uma matriz de sufixos. A BWT pode, portanto, ser calculado em tempo linear pela primeira construção de uma matriz sufixo do texto e, em seguida, deduzir a BWT string: . ${\ displaystyle BWT [i] = S [A [i] -1]}$

Matrizes de sufixo também podem ser usadas para pesquisar substrings na tradução automática baseada em exemplos , exigindo muito menos armazenamento do que uma tabela de frases completa, conforme usada na tradução automática estatística .

Muitos aplicativos adicionais da matriz de sufixo requerem a matriz LCP . Alguns deles são detalhados na seção de aplicação deste último.

Notas

Referências

Manber, Udi ; Myers, Gene (1990). Matrizes de sufixo: um novo método para pesquisas de strings on-line . Primeiro Simpósio Anual ACM-SIAM sobre Algoritmos Discretos. pp. 319–327.
Manber, Udi ; Myers, Gene (1993). "Matrizes de sufixo: um novo método para pesquisas de strings on-line" . SIAM Journal on Computing . 22 (5): 935–948. doi : 10.1137 / 0222058 . S2CID 5074629 .
Gawrychowski, Paweł; Kociumaka, Tomasz (janeiro de 2017). "Construção de árvore de sufixo esparsa em tempo e espaço ideais". Procedimentos do Vigésimo Oitavo Simpósio Anual ACM-SIAM sobre Algoritmos Discretos . Filadélfia, PA: Society for Industrial and Applied Mathematics: 425-439. arXiv : 1608,00865 . doi : 10.1137 / 1.9781611974782.27 . ISBN 9781611974782. S2CID 6608776 .
Li, Zhize; Li, Jian; Huo, Hongwei (2016). Classificação ideal de sufixo no local . Anais do 25º Simpósio Internacional sobre Processamento de String e Recuperação de Informação (SPIRE). Notas de aula em Ciência da Computação. 11147 . Springer. pp. 268–284. arXiv : 1610.08305 . doi : 10.1007 / 978-3-030-00479-8_22 . ISBN 978-3-030-00478-1.
Shi, Fei (1996). Matrizes de sufixo para várias strings: Um método para pesquisas on-line de várias strings . Notas de aula em Ciência da Computação. 1179 . Springer Berlin Heidelberg. pp. 11–22. doi : 10.1007 / BFb0027775 . ISBN 978-3-540-62031-0.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array e suas aplicações à análise do genoma . Algoritmos em Bioinformática. Notas de aula em Ciência da Computação . 2452 . doi : 10.1007 / 3-540-45784-4_35 . ISBN 978-3-540-44211-0.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (março de 2004). "Substituindo árvores de sufixo por matrizes de sufixo aprimoradas" . Journal of Discrete Algorithms . 2 (1): 53–86. doi : 10.1016 / S1570-8667 (03) 00065-0 . ISSN 1570-8667 .
Gonnet, GH; Baeza-Yates, RA; Snider, T (1992). "Novos índices para texto: árvores PAT e matrizes PAT" . Recuperação de Informação: Estruturas de Dados e Algoritmos .
Kurtz, S (1999). "Reduzindo a necessidade de espaço das árvores de sufixo". Prática e experiência em software . 29 (13): 1149–1171. doi : 10.1002 / (SICI) 1097-024X (199911) 29:13 <1149 :: AID-SPE274> 3.0.CO; 2-O . hdl : 10338.dmlcz / 135448 .
Puglisi, Simon J .; Smyth, WF; Turpin, Andrew H. (2007). "Uma taxonomia de algoritmos de construção de matriz de sufixo" . Pesquisas de computação ACM . 39 (2): 4. doi : 10.1145 / 1242471.1242472 . S2CID 2653529 .
Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Construção de matriz de sufixo linear por classificação induzida quase pura . Conferência de compressão de dados de 2009. p. 193. doi : 10.1109 / DCC.2009.42 . ISBN 978-0-7695-3592-0.
Fischer, Johannes (2011). Induzindo o LCP-Array . Algoritmos e estruturas de dados. Notas de aula em Ciência da Computação. 6844 . p. 374. arXiv : 1101.3448 . doi : 10.1007 / 978-3-642-22300-6_32 . ISBN 978-3-642-22299-3.
Salson, M .; Lecroq, T .; Léonard, M .; Mouchard, L. (2010). "Matrizes de sufixos estendidos dinâmicos" . Journal of Discrete Algorithms . 8 (2): 241. doi : 10.1016 / j.jda.2009.02.007 .
Burkhardt, Stefan; Kärkkäinen, Juha (2003). Construção e verificação da matriz de sufixo leve e rápida . Correspondência de padrões combinatórios. Notas de aula em Ciência da Computação. 2676 . p. 55. doi : 10.1007 / 3-540-44888-8_5 . ISBN 978-3-540-40311-1.
Karp, Richard M .; Miller, Raymond E .; Rosenberg, Arnold L. (1972). Identificação rápida de padrões repetidos em strings, árvores e matrizes . Anais do quarto simpósio anual da ACM em Teoria da Computação - STOC '72. p. 125. doi : 10.1145 / 800152.804905 .
Farach, M. (1997). Ótima construção em árvore de sufixos com grandes alfabetos . Proceedings 38º Simpósio Anual sobre Fundamentos de Ciência da Computação. doi : 10.1109 / SFCS.1997.646102 . ISBN 0-8186-8197-7.
Kärkkäinen, Juha; Ukkonen, Esko (1996). Árvores de sufixo esparsas . Notas de aula em Ciência da Computação. 1090 . Springer Berlin Heidelberg. pp. 219–230. doi : 10.1007 / 3-540-61332-3_155 . ISBN 978-3-540-61332-9.
Kärkkäinen, Juha; Sanders, Peter (2003). Construção de matriz de sufixo de trabalho linear simples . Autômatos, Linguagens e Programação. Notas de aula em Ciência da Computação. 2719 . doi : 10.1007 / 3-540-45061-0_73 . ISBN 978-3-540-40493-4.
Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). "Melhor construção de matriz de sufixo de memória externa" . Journal of Experimental Algorithmics . 12 : 1-24. doi : 10.1145 / 1227161.1402296 . S2CID 12296500 .
Kulla, Fabian; Sanders, Peter (2007). "Construção de matriz de sufixo paralela escalonável". Computação paralela . 33 (9). doi : 10.1016 / j.parco.2007.06.004 .

Languages

In other projects