Quantas strings estão próximas a um determinado conjunto de strings?

Essa pergunta foi solicitada por estruturas de dados eficientes para criar um verificador ortográfico rápido .

Dadas duas cordas $u,v$, dizemos que eles estão perto de se sua distância Damerau – Levenshtein ¹ for pequena, ou seja, para um fixo . Informalmente, é o número mínimo de operações de exclusão, inserção, substituição e troca (vizinho) necessárias para transformar em . Pode ser calculado em por programação dinâmica. Observe que é uma métrica , especialmente simétrica.$k$$\operatorname{LD}(u,v) \geq k$$k \in \mathbb{N}$$\operatorname{LD}(u,v)$$u$$v$$\Theta(|u|\cdot|v|)$$\operatorname{LD}$

A questão do interesse é:

Dado um conjunto de cadeias acima de com comprimentos no máximo , qual é a cardinalidade de$S$$n$$\Sigma$$m$

$\qquad \displaystyle S_k := \{ w \in \Sigma^* \mid \exists v \in S.\ \operatorname{LD}(v,w) \leq k \}$ ?

Como até duas cordas do mesmo comprimento têm números diferentes de cordas close², pode ser difícil (impossível?) Encontrar uma fórmula / abordagem geral. Portanto, podemos ter que calcular o número explicitamente para cada fornecido , levando-nos à pergunta principal:$k$$S$

Qual é a complexidade (de tempo) de encontrar a cardinalidade do conjunto para (arbitrário) ?$\{w\}_k$$w \in \Sigma^*$

Observe que a quantidade desejada é exponencial em, portanto, a enumeração explícita não é desejável. Um algoritmo eficiente seria ótimo.$|w|$

Se ajudar, pode-se supor que temos realmente um conjunto (grande) de , ou seja, resolvemos a primeira questão destacada.$S$

1. As variantes possíveis incluem o uso da distância de Levenshtein .
2. Considere e . Os conjuntos de cadeias close sobre são (8 palavras) e (10 palavras), respectivamente.$aa$$ab$$1$$\{a,b\}$$\{ a, aa,ab,ba,aaa,baa,aba,aab \}$$\{a,b,aa,bb,ab,ba,aab,bab,abb,aba\}$

Veja o artigo de Levenshtein . Ele contém limites nas seqüências numéricas obtidas da inserção e exclusão de uma sequência. E se$n$ é o comprimento da string e a string é binária, então o número máximo de vizinhos mais próximos na distância de Levenshtein é $\Theta(n^2)$. É relativamente mais difícil dizer algo sobre$k$vizinhos mais próximos, mas pode-se obter limites. Eles devem fornecer uma estimativa da complexidade.

Se seu $k$ é fixo e você tem permissão para fazer o pré-processamento, isso é algo que você pode tentar

1. Construa um gráfico de modo que os nós sejam palavras e exista uma aresta entre dois nós se a distância entre essas duas palavras for 1.
2. Obtenha a matriz de adjacência correspondente ao gráfico (digamos $M$)
3. Calcular $M^k$

Agora, você poderá usar a matriz final para responder a todas as perguntas. Se você pode armazenar$M, M^2, M^4, M^8 \ldots$ etc. Você pode responder por uma variedade maior de $k$ em vez de fixo $k$, é claro que se pagará aqui com o custo da multiplicação da matriz.