Matriz de sufixo completa

Question

Uma matriz de sufixos indexará todos os sufixos de uma determinada lista de strings, mas e se você estiver tentando indexar todas as substrings exclusivas possíveis?Eu sou um pouco novo nisso, então aqui está um exemplo do que quero dizer:

Dado o string

abcd

Um índice de matriz de sufixo (pelo menos no meu entendimento)

(abcd,bcd,cd,d)

Eu gostaria de indexar (todas as substrings)

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

É uma matriz de sufixos o que procuro?Em caso afirmativo, o que devo fazer para que todas as substrings sejam indexadas?Se não, onde devo procurar?Além disso, o que eu procuraria no Google para comparar "todas as substrings" com "substrings de sufixo"?

Answer 1

A matriz de sufixos já faz o que você precisa, porque cada substring é um prefixo de um dos sufixos. Especificamente, dada sua matriz de sufixo

abcd bcd CD d

e suponha que você esteja procurando pela substring "bc", então você pode descobrir isso procurando por todos os sufixos que começam com "bc" (há apenas um neste caso, "bcd"). Visto que uma matriz de sufixo é classificada lexicograficamente, encontrar todos os sufixos que compartilham um determinado prefixo corresponde a uma pesquisa binária na matriz de sufixo e o resultado será um intervalo contínuo de entradas da matriz de sufixo.

No entanto, existem métodos de pesquisa otimizados usando a matriz de sufixos combinada com estruturas de dados auxiliares, como a matriz LCP (prefixo comum mais longo) ou árvores wavelet. Consulte a pesquisa de Navarro de 2007 para obter uma descrição de tais métodos (DOI 10.1145 / 1216370.1216372).

Para levar em consideração os comentários feitos abaixo, sugiro combinar cada sufixo com o número de substrings que ele representa . Em um exemplo simples como o acima, isso seria

4 abcd
3 bcd
2 bc
1 d

porque, por exemplo, o primeiro sufixo "abcd" representa as 4 substrings "a", "ab", "abc", "abcd". No entanto, em um exemplo mais complexo, digamos para a string "abcabxdabe", as duas primeiras entradas da matriz de sufixo seriam

10 abcabxdabe
1 abe

porque a segunda entrada representa substrings "a", "ab" e "abe", mas "a" e "ab" também são representados pela primeira entrada.

Como calcular o número de substrings que uma entrada representa? -> O comprimento do sufixo menos o comprimento do prefixo mais longo que ele tem em comum com o sufixo anterior. Por exemplo. no exemplo "abe", que é 3 (seu comprimento) menos 2 (o comprimento de "ab", o prefixo mais longo que ele compartilha com a entrada anterior). Portanto, esses números podem ser gerados em uma passagem pela matriz de sufixo e ainda mais rápido se você também gerou a matriz LCP (prefixo comum mais longo).

A próxima etapa seria gerar contagens acumuladas:

10 abcabxdabe
11 abe
16 abxdabe
...

e depois encontrar uma forma eficiente de aproveitar as contagens acumuladas. Por exemplo. se você quiser obter a 13ª substring lexicograficamente, terá que encontrar a primeira entrada que possui uma contagem acumulada maior ou igual a 13. Isso seria "16 abxdabe" acima. Em seguida, remova o prefixo que compartilha com a entrada anterior (produz "xdabe") e, em seguida, pule para a posição após o segundo caractere (porque a entrada anterior acumulou contagem 11 e 13-11== 2), então você obtém " abxd "como a 13ª substring lexicograficamente.

Answer 2

Como já foi respondido, as substrings são prefixos de sufixos.Às vezes você gostaria de ir para o outro lado e obter sufixos de prefixos.

Além disso, não está claro o que você está procurando com "Substrings exclusivos".Eu sugiro que você procure as palavras: Tipo, Token, Maximal, Supermaximal.Você não deve ter problemas para encontrar estes na literatura de matriz de sufixo.

Answer 3

Você deve usar uma variação de 'Trie'.Essencialmente, se você tiver ABCD, crie uma árvore que é uma fusão de caminhos: root-> A-> B-> C-> D, root-> B-> C-> D, root-> C-> D e root-> D.Agora, em cada nó, mantenha uma lista de locais onde a string root -> .-> .-> nó foi observada.