C'è un algoritmo di forza migliore da bruta per generare un grafico la cui relazione è String Edit Distance= 1?

Question

Sono interessato a creare un grafico i cui vertici sono stringhe, e i cui bordi rappresentano la relazione con una distanza di modifica di 1 sotto una determinata metrica stringa.

Un particolare approccio è quello di rendere tutte $ \ frac {n ^ 2-n} {2} $ confronti tra la $ N $ Verticanti, dandoci $ o (n ^ 2) $ complessità temporale.

Escludendo il parallelismo I confronti, c'è un algoritmo migliore in termini di complessità del tempo?

Sono interessato alle metriche di stringa dove sono consentite stringhe di lunghezza diversa.

Answer 1

Nel caso peggiore qualsiasi algoritmo funzionerà $ \ omega (n ^ 2) $ perché il tuo grafico può avere $ \ Omega (n ^ 2) $ bordi.

A proposito, sei interessato ad una particolare stringa metrica?

Answer 2

È possibile utilizzare BK-alberi per accelerare questo. Inserimento $ N $ Elementi nell'albero prende $ o (n \ log n) $ tempo. Dopo questo puoi interrogare l'albero per tutte le stringhe la cui distanza di modifica è esattamente una distanza dal tuo input. Fare di nuovo per tutte le stringhe richiede di nuovo $ o (n ^ 2) $ complessità, tuttavia con un fattore costante molto piccolo ( Questa pagina menziona solo il 5-8% dell'albero deve essere ispezionata per query ).

Ecco una breve descrizione di come funziona:

Struttura dei dati

Un albero BK è

.
• vuoto
• un nodo con un valore radice $ R $ e un insieme di bambini indicizzati $ c_i $ , Ogni albero BK (implementato utilizzando la mappa hash, array dinamico o simile)

Una funzione di distanza metrica (importante!) $ d (x, y) $ è usato per inserimento e query.

Inserimento della stringa $ s $

.
• Se l'albero è vuoto, renderlo un nuovo nodo con $ s $ come valore radice e nessun bambino
• Se l'albero è un nodo con root $ R $ e bambini $ c_i $ , lascia < Span Class="Math-Container"> $ k= d (r, s) $ .
  .
  • se $ k= 0 $ , salta l'inserimento come $ s $ è già alla radice < / li >.
  • inserisci in modo altrimenti ricorsivo $ s $ nella $ k $ -th albero bambino $ c_k $ .

L'ultimo passo assicura che tutti i nodi in $ c_i $ Avere distanza $ I $ al root

stringa di interrogazione $ s $

.
• Se l'albero è vuoto, non restituisce i risultati
• Se l'albero è un nodo con root $ R $ e bambini $ c_i $ , lascia < Span Class="Math-Container"> $ k= d (r, s) $ .
  .
  • se $ k= 1 $ , aggiungi $ r $ come risultato ( Nota : Questo passaggio è diverso dalle solite query BK-Tree)
  • Inoltre, interrogare ricorsivamente $ s $ dai bambini $ c_ {d-1} $ , $ c_d $ e $ c_ {d + 1} $ . Restituisce tutti i risultati da quelle query pure

L'ultimo passo c'è la magia dei BK-alberi, in quanto non ha bisogno di controllare gli altri bambini a causa della distanza metrica. Ecco una prova parziale del perché gli altri non hanno bisogno di essere controllato:

Supponiamo che c'era qualche stringa $ x $ che ha distanza uno dalla nostra query, quindi $ d (s, x)= 1 $ , ma è nell'albero figlio $ c_ {k + 2} $ . Sappiamo che $ d (r, x)= k + 2 $ dalla procedura di inserimento. Questo tuttavia (con la disuguaglianza del triangolo per gli spazi metrici) dà

$$ k + 2= d (r, x) \ leq d (r, s) + d (s, x)= k + 1 $$

Ma questa è una contraddizione! Simile può essere fatto per tutti i bambini con $ i> k + 1 $ e $ i . Ciò significa che tutte le stringhe in altri bambini non avranno distanza uno per costruzione, quindi non abbiamo bisogno nemmeno di controllarle, che salva il tempo di elaborazione.

Modifica: un'altra spiegazione: https://signal-to-noise.xyz / Post / BK-Tree /