Uma matriz de sufixos é uma matriz que permite a você encontrar correspondências exatas de substrings. A ideia principal é que você gere uma matriz ordenada por posições usando uma função de comparação que compara os sufixos começando por suas respectivas posições.

Construindo uma matriz de sufixos

Este é um dos casos em que algumas linhas de código são mais esclarecedoras do que a explicação em si.

def make_suffix_array(text):
    size = len(text)
    def compare_suffix(i,j):
        return cmp(text[i:],text[j:])

    indexes = range(size)
    indexes.sort(cmp = compare_suffix)
    return indexes

Se você tentar isso na string de “Suffix Arrays Rock?” e imprimir os índices classificados da matriz, juntamente com os sufixos que se iniciam lá, você vai começar a ver tanto o potencial quanto as fraquezas.

 

Nota: Este método de criação de matrizes de sufixos é absurdamente ineficiente, mas é suficiente para explicar o conceito. Existem algoritmos para fazer isso em tempo linear.

Você pode usar a matriz de sufixos para procurar uma string no texto utilizando pesquisa binária. Algo mais ou menos assim:

def find(sa, text, q):
    size = len(sa)
    qsize = len(q)
    hi = size -1
    lo = 0
    while hi >= lo:
        mid = (hi + lo) / 2
        begin = sa[mid]
        end = min(size, begin + qsize)
        test = text[begin: end]
        if test > q:
            hi = mid -1
        elif test < q:
            lo = mid + 1
        else:
            return begin
    return None

Você possui uma busca rápida que permite retornar à posição exata da substring. Ainda melhor: todas as correspondências estão agrupadas na matriz de sufixos. Local perfeito.

Documentos múltiplos

O conceito se estende facilmente para vários documentos.

def make_multi(texts):
    indexes = []
    nt = len(texts)
    for d in xrange(nt): 
        size = len(texts[d])
        for i in xrange(size):
            e = d,i
            indexes.append(e)

    def compare(e0,e1):
        d0, i0 = e0
        d1, i1 = e1
        s0 = texts[d0][i0:]
        s1 = texts[d1][i1:]
        return cmp(s0,s1)

    indexes.sort(cmp = compare)
    return indexes

Um exemplo mínimo com três textos muito pequenos e um pouco de código para despejar a matriz de sufixos juntamente com os sufixos.

def print_multi(sam, texts):
    for e in sam:
        d, i = e
        suffix = texts[d][i:]
        print "(%2i,%2i)\t%s" % (d,i,suffix)

texts = ["Suffix Arrays Rock?",
         "Redundant Array of Inexpensive Disks",
         "Metal is not Rock!"]
r0 = make_multi(texts)
print_multi(r0, texts)

Resulta em:

( 1, 9)	 Array of Inexpensive Disks
( 0, 6)	 Arrays Rock?
( 1,30)	 Disks
( 1,18)	 Inexpensive Disks
( 2,12)	 Rock!
( 0,13)	 Rock?
( 2, 5)	 is not Rock!
( 2, 8)	 not Rock!
( 1,15)	 of Inexpensive Disks
...
( 1,28)	ve Disks
( 0, 5)	x Arrays Rock?
( 1,22)	xpensive Disks
( 1,14)	y of Inexpensive Disks
( 0,11)	ys Rock?

Tudo bem, isso parece ter propriedades de escalabilidade quase perfeitas. Qual é o truque?

O truque

Existem algumas desvantagens graves para matriz de sufixos.

Texto necessário durante a busca

A grande desvantagem para matriz de sufixos é que você precisa ter acesso ao texto enquanto faz uma busca. Isso significa que a matriz de sufixos e o texto precisam ser mantidos perto um do outro.

Necessidades de armazenamento

Se pararmos para pensar sobre isso, um texto é um array de caracteres (ascii, não unicode). Sua matriz de sufixos é uma matriz de posições. Suponha que você armazene uma posição e ids de documento como palavras de 32 bits. Lembre-se de que você precisa armazenar o texto, bem como a matriz de sufixos. Se o tamanho do texto é n, as necessidades totais são 9n. Para piorar a situação: já que você vai saltando ao redor da  matriz de sufixos, bem como do texto, os esquemas de compressão não são realmente viáveis.

Atualizações?

Até mesmo as atualizações mínimas do texto irão invalidar a matriz de sufixos e você precisa reconstruí-la. O que é pior: se você tiver uma matriz sobre documentos múltiplos, uma atualização em um dos documentos anula toda a estrutura.

Correspondências exatas

Você recebe o que pediu. Procurar o texto de exemplo de ‘suffix’ não vai produzir um resultado.

Exagero

Você pode procurar por uma correspondência exata em uma string de comprimento arbitrário, mas ninguém precisa encontrar correspondências exatas em grandes strings. Há uma exceção notável: se você está tentando procurar fragmentos de DNA em uma string grande de DNA, isso é exatamente o que você precisa. Para todos os outros, é um exagero.

Melhorando o tempo todo

Bem, não poderia ficar tão pior agora, podia?

Não precisa ser assim tão ruim, e você pode escolher realmente o quanto de dor você quer infligir a si mesmo.

• pesquisa começa no início das palavras

Na maioria das vezes, não é necessário ser capaz de procurar substrings de palavras. Por exemplo, você provavelmente não precisa encontrar os ‘rays’ em ‘arrays’. Ele divide o número de posições para ordenar pelo tamanho médio da palavra.

• remover o ruído da linguagem

Nem todas as palavras precisam ser consideradas. Na verdade, as palavras mais frequentes são ruídos.

• versões antigas podem ser penalizadas

Se todas as versões de todos os seus documentos possuem uma única id, você pode penalizar as ids mais antigas de documentos indesejados, e filtrá-las antes de retornar os resultados. Isso significa que você não precisa fazer atualizações imediatamente, mas pode programá-las quando for melhor para você.

• o tamanho do texto não é o tamanho do documento

Suponha que seus documentos estão em pdf. O tamanho real do texto é pequeno quando comparado com todas as outras informações do arquivo (marcação, imagens, fontes,…). Além disso, o texto de armazenamento não destruirá o seu armazenamento. Por exemplo, um romance peso pesado (em todos os sentidos) como Guerra e Paz possui cerca de 3.2 MB. Todo o corpo de artigos da Wikipédia em inglês, que são armazenados como XML, tem um pouco mais de 30 GB.

• matrizes de sufixos múltiplas

Você não precisa adicionar todos os seus documentos a uma matriz de sufixos grande. É possível ter muitos deles que melhoram a situação de mais de uma maneira. A busca pode ser paralela e adicionar um novo documento é mais comum também.

O que isso tem a ver com “The Cloud”?

Já que existe uma rede entre o cliente emitindo o pedido e a infraestrutura de cloud que oferece o serviço de pesquisa, isso significa que você tem uma latência não negligenciável.

Ou seja, a latência adicionada pelo serviço só precisa ser pequena comparada com a latência global, o que torna a vida um pouco mais fácil.

Além disso, a natureza de “The Cloud” leva as pessoas a armazenar dados consolidados em vez de ativos, o que é atamente o mais adequado para matriz de sufixos.

Palavras de encerramento

Matriz de sufixos é uma ideia que foi concebida no passado, quando “online” ainda tinha outras semânticas. Na época (1991) eles eram vistos como muito dispendiosos para pesquisa geral, mas voltaram quando os grandes discos rígidos tinham menos de 100 MB de capacidade. Talvez matriz de sufixo mereça um segundo olhar.

Sinto vontade de agitar um e-mail de serviço de busca/indexação em algumas centenas de linhas de código, ou um serviço de pesquisa privado na wikipedia.

Só uma pergunta permanece: o que há de acontecer? ocaml ou haskell? Hm, difícil.

Divirta-se.

***

Texto original disponível em http://blog.incubaid.com/2012/02/03/cloud-search-using-suffix-arrays-well-maybe/