Trovare tutte le coppie di sequenze che differiscono esattamente una posizione

Question

Ho bisogno di una struttura di dati che rappresenta un insieme di sequenze (tutti della stessa, nota, lunghezza) con la seguente operazione non standard:

cerca due sequenze nel set che differiscono esattamente da un indice. (O stabilire che tale coppia esiste.)

Se N è la lunghezza delle sequenze e M il numero di sequenze, v'è un ovvio O(N*M*M) algoritmo. Mi chiedo se esiste un modo standard per risolverlo in modo più efficiente. Sono disposto ad applicare la pre-elaborazione, se necessario.

Punti bonus se invece di restituire una coppia, l'algoritmo restituisce tutte le sequenze che si differenziano nello stesso punto.

alternativa, sono interessati anche a una soluzione in cui posso controllare efficacemente se una sequenza particolare differisce a un indice con qualsiasi sequenza nel set. Se aiuta, possiamo supporre che nel set, nessuna delle due sequenze abbia quella proprietà.

Modifica: è possibile assumere N per essere ragionevolmente piccolo. Con questo, intendo miglioramenti come O(log(N)*M*M) non sono immediatamente utili per il mio caso d'uso.

Answer 1

Per ogni sequenza e ogni posizione ho in quella sequenza, calcola un hash della sequenza senza posizione i e aggiungerlo a una tabella hash. Se c'è già una voce nella tabella, hai trovato una coppia potenziale che differisce solo in una posizione. Utilizzando rolling hashes dall'inizio e dalla fine e combinandoli, è possibile calcolare ciascun hash in tempo costante. Il tempo di esecuzione totale è previsto O (N * M).

Answer 2

Selezionare j set di indici k ciascuno a caso (assicurarsi che nessuno degli insiemi si sovrapponga).

Per ogni set XOR gli elementi.

Ora avete le impronte digitali j per ogni documento.

Confrontare le sequenze basate su queste impronte digitali. le impronte digitali j-1 devono corrispondere se le sequenze corrispondono effettivamente. Ma il contrario potrebbe non essere vero e potrebbe essere necessario controllare la posizione per posizione.

Ulteriori chiarimenti sulla parte di confronto: ordinare tutte le impronte digitali da tutti i documenti (o utilizzare la tabella hash). In questo modo non devi confrontare ogni coppia, ma solo le coppie che hanno un'impronta digitale corrispondente.

Answer 3

Un semplice approccio ricorsivo:

• Trova tutte le serie di sequenze che hanno lo stesso primo tempo con ordinamento o hash.

• Per ciascuno di questi set, ripetere l'intero processo ora guardando solo la seconda metà.

• Trova tutti i set di sequenze che hanno lo stesso secondo tempo tramite ordinamento o hash.

• Per ciascuno di questi set, ripetere l'intero processo ora guardando solo la prima metà.

• Quando hai raggiunto la lunghezza 1, tutti quelli che non corrispondono sono quelli che stai cercando.

pseudo-codice:

findPairs(1, N) 

findPairs(set, start, end) 
    mid = (start + end)/2 
    sort set according to start and mid indices 
    if end - start == 1 
    last = '' 
    for each seq: set 
     if last != '' and seq != last 
     DONE - PAIR FOUND 
     last = seq 
    else 
    newSet = {} 
    last = '' 
    for each seq: set 
     if newSet.length > 1 and seq and last don't match from start to mid indices 
     findPairs(newSet, mid, end) 
     newSet = {} 
     newSet += seq 
     last = seq 

Dovrebbe essere abbastanza facile da modificare il codice per essere in grado di trovare tutte le coppie.

complessità? I può essere sbagliato, ma:

La profondità massima è log M. (Credo) il caso peggiore sarebbe se tutte le sequenze fossero identiche. In questo caso il lavoro svolto sarà O(N*M*log M*log M), che è migliore di O(N*M*M).