Qual o comprimento das suas cordas?

Se eles forem relativamente curtos (por exemplo, palavras em inglês; avg_len=5) e você tiver armazenamento de banco de dados de sobra, tente esta abordagem:

• Para cada palavra que você deseja armazenar na tabela, use todos os sufixos possíveis dessa palavra. Em outras palavras, você continua removendo o primeiro caractere até não sobrar nada. Por exemplo, a palavra value dá:
  • value
  • value
  • lue
  • ue
  • e
• Armazenar cada desses sufixos no banco de dados.
• Agora você pode pesquisar substrings usando LIKE 'alu%' (que encontrará 'alu' como parte de 'valor').

Ao armazenar todos os sufixos, você eliminou a necessidade do curinga principal (permitindo que um índice seja usado para pesquisa rápida), ao custo de espaço de armazenamento.

Custo de armazenamento

O número de caracteres necessários para armazenar uma palavra se torna word_len*word_len / 2 , ou seja, quadrático no comprimento da palavra, por palavra. Aqui está o fator de aumento para vários tamanhos de palavras:

• Palavra de 3 letras:(3*3/2) / 3 = 1.5
• Palavra de 5 letras:(5*5/2) / 5 = 2.5
• Palavra de 7 letras:(7*7/2) / 7 = 3.5
• Palavra de 12 letras:(12*12/2) / 12 = 6

O número de linhas necessárias para armazenar uma palavra aumenta de 1 para word_len . Esteja atento a esta sobrecarga. Colunas adicionais devem ser reduzidas ao mínimo para evitar o armazenamento de grandes quantidades de dados redundantes. Por exemplo, um número de página em que a palavra foi originalmente encontrada deve ser bom (pense unsigned smallint), mas metadados extensos sobre a palavra devem ser armazenados em uma tabela separada por palavra, em vez de para cada sufixo.

Considerações

Há uma troca em que dividimos 'palavras' (ou fragmentos). Como um exemplo do mundo real:o que fazemos com hífens? Armazenamos o adjetivo five-letter como uma palavra ou duas?

A troca é a seguinte:

• Tudo o que está dividido não pode ser encontrado como um único elemento. Se armazenarmos five e letter separadamente, procurando por five-letter ou five-letter falhará.
• Qualquer coisa que não seja quebrado ocupará mais espaço de armazenamento. Lembre-se de que o requisito de armazenamento aumenta quadraticamente no comprimento da palavra.

Por conveniência, você pode remover o hífen e armazenar fiveletter . A palavra agora pode ser encontrada pesquisando five , letter , e five-letter . (Se você também remover os hífens de qualquer consulta de pesquisa, os usuários ainda poderão encontrar five-letter .)

Finalmente, existem maneiras de armazenar arrays de sufixos que não incorrem em muita sobrecarga, mas ainda não tenho certeza se eles traduzem bem em bancos de dados.