Existe um algoritmo de força melhor que brute para gerar um gráfico cuja relação é a diferença de seqüência de caracteres= 1?

Question

Estou interessado em criar gráficos cujos vértices são cordas, e cujas bordas representam a relação de ter uma distância de edição de 1 em uma determinada métrica de string.

Uma abordagem óbvia é fazer toda $ \ frac {n ^ 2-n} {2} $ comparações entre a $ n $ vértices, dando-nos $ o (n ^ 2) $ complexidade de tempo.

Excluindo paralelizar as comparações, existe um algoritmo melhor em termos de complexidade de tempo?

Estou interessado em métricas de string, onde as cordas de comprimento diferente são permitidas.

Answer 1

Na pior das hipóteses, tal algoritmo funcionará $ \ ômega (n ^ 2) $ porque o seu gráfico pode ter $ \ Ômega (n ^ 2) $ bordas.

A propósito, você está interessado em alguma métrica de string particular?

Answer 2

É possível usar bk-treer para acelerar isso. Inserindo $ n $ Elementos na árvore leva $ o (n \ log n) $ tempo. Depois disso, você pode consultar a árvore para todas as strings cuja distância de edição é exatamente uma da sua entrada. Fazendo isso para todas as cordas novamente leva $ O (n ^ 2) $ complexidade, no entanto, com um fator constante muito pequeno ( esta página Menciona apenas 5-8% da árvore precisa ser inspecionada por consulta ).

Aqui está uma breve descrição de como funciona:

Estrutura de dados

uma bk-tree é

• vazio
• um nó com um valor raiz $ R $ e um conjunto de crianças indexadas $ c_i $ , cada um bk-tree (implementado usando Hash Map, matriz dinâmico ou similar)

uma métrica (importante!) Função de distância $ D (x, y) $ é usado para inserção e consultas.

Inserindo string $ S $

• Se a árvore estiver vazia, faça-lhe um novo nó com $ s $ como o valor raiz e sem filhos
• Se a árvore é um nó com raiz $ R $ e crianças $ c_i $ , deixe < span class="recipiente de matemática"> $ k= D (r, s) $ .
  • se $ k= 0 $ , ignorar a inserção como $ s $ já está na raiz < / li >.
  • de outra forma recursivamente inserir $ s $ na $ k $ -th árvore de criança $ c_k $ .

A última etapa garante que todos os nós na $ c_i $ têm distância $ i $ para o raiz

seqüência de consulta $ S $

• Se a árvore estiver vazia, não retorne nenhum resultado
• Se a árvore é um nó com raiz $ R $ e crianças $ c_i $ , deixe < span class="recipiente de matemática"> $ k= D (r, s) $ .
  • se $ k= 1 $ , adicionar $ R $ como resultado ( nota : Esta etapa é diferente das consultas usuais da bk-tree)
  • Além disso, consulta recursivamente $ s $ das crianças $ c_ {d-1} $ , $ c_d $ e $ c_ {d + 1} $ . Retorna todos os resultados daquelas consultas também

O último passo há a magia das árvores Bk, como não precisa verificar as outras crianças devido à distância sendo métrica. Aqui está uma prova parcial de por que os outros não precisam ser verificados:

Vamos supor que havia alguma string $ x $ que tem distância um de nossa consulta, então $ D (S, x)= 1 $ , mas é na árvore de criança $ c_ {k + 2} $ . Sabemos que $ D (r, x)= k + 2 $ do procedimento de inserção. Isso, no entanto, (com a desigualdade do triângulo para espaços métricos) dá

$$ K + 2= D (R, X) \ LEQ D (R, S) + D (S, X)= K + 1 $$

Mas esta é uma contradição! Semelhante pode ser feito para todas as crianças com $ i> k + 1 $ e $ i . Isso significa que todas as strings em outras crianças não terão distância uma por construção, então não precisamos nem verificá-las, o que economiza tempo de processamento.

editar: Outra explicação: https://signal-to-noise.xyz / post / bk-tree /