le idee

[l'idea intuitiva dell'algoritmo]
[i grafi bPgraph]
[generazione di bPgraph schematizzata]
[calcolo della copertura di T]

l'idea intuitiva dell'algoritmo

top

Il problema è stato già affrontato e risolto in una versione in cui la sovrapposizione tra sequenze non viene però considerata: l'algoritmo descritto da JS Varré, JP Delahaye ed E Rivals ha una complessità in tempo nel caso pessimo di O(n⁶) ed in pratica un'inefficenza in spazio che lo rende inapplicabile già per sequenze di lunghezza 100kb, essi parlano però di un'altro algoritmo compact script graph mostrando un grafo in cui il tempo richiesto al calcolo sembra essere quadratico in tempo rispetto alla lunghezza delle sequenze in esame, completamente assente l'analisi della complessità in spazio.
La mia idea consiste nel dividere il problema in due parti distinte.
Nella prima parte si esegue un'elaborazione della sequenza S generando un oggetto che permette di riconoscere in tempo rapido ed in spazio lineare le sottosequenze o le sottosequenze inverse complementate contenute in S.
La seconda parte, data una sequenza T e gli oggetti generati nella prima parte (G per le sottosequenze dirette di S e G' per le sue sottosequenze inverse complementate), consiste nel calcolare una copertura massima usando la quantità minima di sottosequenze riconosciute da G o da G' che abbiano però una lunghezza minima l.
Dividendo in questo modo, la preelaborazione di S, computazionalmente più pesante della seconda parte, viene eseguita una sola volta per tutte, permettendo poi un rapido calcolo della copertura massima per ogni altra possibile sequenza T.

i grafi bPgraph

top

Ottenere un oggetto che riconosca rapidamente tutte le possibili sottosequenze di una data sequenza S non è compito difficile, ma lo può divenire se si aggiunge il requisito di mantenere una bassa complessità in spazio e di poterlo generare in tempi abbastanza rapidi.
L'idea intuitiva del grafo bPgraph parte dal voler predisporre delle strade forzate su di un grafo (una per ogni sottosequenza e riusando per sottosequenze diverse tratti comuni, ove possibile) i cui nodi sono etichettati dai vari caratteri dell'alfabeto in uso, il matching di una stringa u viene stabilito facendo percorrere da un oggetto posto sui nodi, chiamato cursore, una strada attraverso nodi e archi del grafo che passi nel giusto ordine su una sequenza di nodi le cui etichette concatenate formino u.
Le strade sono intese forzate quando, dato un certo cursore posto su di un nodo ed il carattere successivo di u da matchare, un solo arco tra quelli uscenti dal nodo in cui si trova il cursore può essere percorribile, se esiste. Per ottenere questa proprietà senza dover generare un grafo di dimensioni enormi, i cursori hanno uno stato interno il cui valore limita gli archi da considerare validi. Lo stato può variare ogni volta che il cursore, percorrendo un arco, si sposta da un nodo ad un'altro.
Data la sequenza u ed un cursore fuori dal grafo nello stato di partenza, u è sottosequenza di S se e solo se il cursore riesce a trovare un percorso che lo porti nel giusto ordine su una serie di nodi le cui etichette formino la sequenza di u, ovviamente esiste anche un modo per far entrare nel grafo il cursore al primo carattere letto e dato che ogni passo del percorso deve essere completamente determinato dallo stato del cursore e dal carattere da matchare, deve esistere uno ed un solo punto di ingresso per ogni carattere dell'alfabeto che compare in S.
Grazie alla presenza dello stato posto sul cursore, possono essere percorsi da cursori con stati diversi dei tratti di strada comuni senza però perdere la capacità di distinguerli ed eventualmente dividerli su percorsi distinti qualora ve ne fosse bisogno.
Questa possibilità di utilizzare tratti di percorsi per il riconoscimento di più di una sottostringa è la proprietà del bPgraph che gli permette di risultare lineare in spazio con la lunghezza di S, la forzatura del percorso è la proprietà che invece permette ai cursori di individuare una strada lunga m su bPgraph in un tempo O(m log(maxlink)) in cui maxlink è la massima quantità di archi che possono partire da un nodo ed utilizzando i bPgraph generati con l'algoritmo che segue il massimo numero di tali archi risulta essere lineare con la lunghezza di S (n), quindi il tempo è O(m log(n/m)) (nel caso pessimo).
Gli archi che formano i tratti di strada che possono essere percorsi da ogni cursore, indipendentemente dal suo stato interno, sono chiamati diretti, gli archi che possono essere percorsi solo da determinati cursori sono chiamati laterali.
Nell'algoritmo che segue tutti gli archi diretti formano un unico percorso, monodirezionale aciclico, che parte da un nodo etichettato con il primo carattere della sequenza S e attraversa in ordine i nodi che rappresentano tutti i caratteri di S, fino all'ultimo, e questi nodi sono tutti i nodi di cui il grafo è costituito. Rappresentando quindi il bPgraph come una fila di nodi, ognuno dei quali è collegato al successivo tramite arco diretto, gli archi laterali collegano un nodo ad un'altro più distante di quello immediatamente successivo, che compare più avanti nella sequenza.

generazione di bPgraph schematizzata

top

I cursori vengono utilizzati anche nella creazione del grafo, in questo caso però hanno un comportamento lievemente diverso da quelli utilizzati, durante la ricerca di un match, sul grafo ultimato.

alfabeto di dimensione d
S = c0 c1 c2... cn EOF

l'oggetto cursore ha come campi
-nodeId : il nodo su cui è posizionato
-from   : il suo stato interno

l'oggetto nodo ha come campi
-id     : il suo identificativo
-label  : il carattere che rappresenta

l'oggetto arco ha come campi
-id     : il suo identificativo
-label  : il carattere del nodo a cui porta (non è un dato
          necessario ma velocizza l'utilizzo del grafo)
-from   : se l'arco è diretto, = 0
          altrimenti, se è laterale, specifica il
          valore del campo from che devono avere i cursori
          per poterlo percorrere
-toNode : l'identificativo del nodo a cui porta

l'array STARTS[], di dimensione d, ha come elementi gli
identificativi dei nodi che costituiscono i punti d'ingresso
del grafo, a seconda del primo carattere preso in esame, per
i cursori che devono iniziare a percorrerlo

gli archi, che sono monodirezionali, vengono posizionati sui
nodi da cui partono, dato un nodo si ha quindi accesso alla lista
dei suoi archi uscenti


makegraph(S) {
[INIT]	l'array STARTS[] viene inizializzato di dimensione d
	ed i suoi elementi settati a -1
	i=0
[READ]	assegno a c ci, l'i-esimo carattere dell'input
	if(c!=EOF) {
[ADD]		newNodeId=nextNodeId()
		aggiungo un nuovo nodo con id=newNodeId e con label=c
		if(i!=0) {
			aggiungo un nuovo arco diretto con id=nextLinkId() e
			label=c al nodo inserito nella precedente iterazione
			che porti al nodo con id newNodeId appena inserito
			(from=0 essendo di tipo diretto)
			}
[WALK]		per ogni cursore attivo {
			se nel nodo di indice pari al campo nodeId del cursore
			esiste un arco con label c che sia diretto oppure
			laterale ma con campo from pari al campo from del
			cursore {
				percorro tale arco, cioè:
				-il campo nodeId del cursore viene aggiornato
				 con l'id del nodo a cui punta l'arco
				-se l'arco è laterale (from!=0) aggiorno il
				 campo from del cursore assegnandogli il
				 valore del campo id dell'arco
				}
			else {
				creo un nuovo arco laterale con id=nextLinkId(),
				label=c e from pari al valore del campo from del
				cursore, che porti al nodo appena creato (quello con
				newNodeId) e aggiungo tale arco al nodo con id
				pari al campo nodeId del cursore
				rimuovo il cursore
				}
			}
[CURSOR]	if STARTS[c]==-1 then STARTS[c]=newNodeId
		else aggiungo un nuovo cursore con nodeId=STARTS[c] e from=c
		i++
		goto [READ]
		}
	END
	}

calcolo della copertura di T

top

Il calcolo della copertura massima della sequenza T, utilizzando la minima quantità di sottosequenze e di sottosequenze inverse complementate di lunghezza almeno l contenute in S, richiede l'uso dei due grafi G e G', calcolati da S, che riconoscono rispettivamente le sottosequenze dirette e quelle inverse complementate.
L'algoritmo scorre la sequenza T iniziando a considerare la prima base come possibile inizio di una sottosequenza e procede per iterazioni, scorrendo in avanti, fino a raggiungere il termine di T.
Ad ogni iterazione possono verificarsi due casi: se vale l'ipotesi che la base immediatamente precedente a quella in analisi non può essere coperta da alcuna sottosequenza, allora si è nel caso 1, se invece si è riusciti ad individuare una sottosequenza della copertura che termina appena prima alla base in analisi, si è nel caso 2.
Definisco c0 la base in esame e ci la base distante i posizioni da c0 nella sequenza T.
La notazione c^c indica il complemento di c.

caso 1
Vale l'ipotesi che la base immediatamente precedente a quella in esame (c-1) non può essere coperta da alcuna sottosequenza, quindi c0 può essere coperta solo se è proprio l'inizio di una sottosequenza. Parto con il cercare, se esiste, una sottosequenza diretta lunga almeno l che, partendo da c0, copra T almeno fino a cl-1, tale sequenza esiste solo se passando in sequenza cl-1^c, cl-2^c, cl-3^c ... c0^c ad un cursore del grafo G', egli riesce sempre a trovare un percorso, cioè se cl-1^c cl-2^c ... c0^c formano una sottosequenza inversa complementata di S.
Se questa operazione utilizzando G' ha successo, allora c0 è proprio l'inizio di una sottosequenza diretta lunga almeno l, passo quindi in sequenza le basi di T a partire da c0 ad un cursore su G, finchè, passando ci, non fallisce nel trovare un percorso, e ho individuato la sottosequenza diretta che parte da c0 e va fino a ci-1, lunga almeno l.
Se invece la ricerca della sottosequenza inversa a partire da cl-1 fallisce mentre gli passo un certo ci, questo significa che c0 non può essere coperto da una sottosequenza diretta lunga almeno l, perchè tale sottosequenza dovrebbe contenere la sottosequenza ci ci+1 ... cl-1 che, non essendo sottosequenza diretta di S (non essendo il suo inverso complementato riconosciuto da G'), non può essere contenuta in nessuna possibile sottosequenza diretta di S, quindi, per l'ipotesi del caso 1, c0 non può essere coperto da nessuna sottosequenza diretta, ma allora anche c1 ricade nel caso 1 (almeno per le sottosequenze dirette) e per le stesse ragioni non può essere coperto, quindi abbiamo che tutte le basi fino a ci inclusa non possono essere coperte da sottosequenze dirette.
Per cercare sottosequenze inverse complementate che partano da c0 seguo lo stesso procedimento usato per le dirette, complementando però le basi di T e usando G al posto di G' e viceversa.
Possono verificarsi 3 situazioni:
-se ho trovato solo una sottosequenza, diretta o inversa complementata, che parta da c0, allora l'aggiungo alla copertura e procedo l'analisi dalla prima base di T che non è coperta da questa sottostringa, andando nel caso 2.
-se ho trovato sia una sottosequenza diretta che una inversa complementata allora aggiungo alla copertura solo quella più lunga e procedo nell'analisi della prima base di T che non è coperta da questa sottostringa, andando nel caso 2.
-se non ho trovato né una sottosequenza diretta, né una sottosequenza inversa complementata, allora non considero tutte le basi che sono state escluse come copribili sia dalle dirette che dalle inverse complementate e procedo nell'analisi della base ad esse immediatamente successiva, restando nel caso 1.

caso 2
Vale l'ipotesi che c-1 è l'ultima base di una sottostringa di copertura, quindi tutte la basi almeno fino a c-l compresa sono coperte e c0 potrebbe allora non solo essere l'inizio di una nuova sottostringa, ma potrebbe anche comparire nella parte centrale, se non addirittura come base finale, di una sottostringa lunga almeno l e parzialmente sovrapposta a quella che termina in c-1.
Per cercare la migliore sottosequenza diretta, se esiste, si procede passando ad un cursore su G le basi c0 c1 ... ci finchè nell'ultimo, ci, non fallisce nel trovare un percorso. Se i>=l allora ho già concluso, tale sequenza potrebbe anche essere la parte finale di una sottosequenza parzialmente sovrapposta con quella precedente, ma di sicuro non ve ne sono di parzialmente sovrapposte che vanno più in la di ci-1, non essendo c0 c1 ... ci una sottosequenza diretta (e quindi non può essere contenuta in una sottosequenza diretta).
Se invece i<l allora devo cercare la sottosequenza diretta, parzialmente sovrapposta a quella precedente, che copra la massima quantità di basi attualmente scoperte, sapendo già che non potrà raggiungere la base ci (non essendo c0 c1 ... ci una sottosequenza diretta). A partire da c0 passo ad un cursore su G' le basi c0^c, c-1^c ... c-k^c, finchè il cursore trova un percorso e finchè k<l (oltre non è necessario), ho quindi che c-1^c c-2^c c-3^c c-k^c sono una sottosequenza inversa complementata e i loro complementi rappresentano il massimo prefisso possibile, lungo k, della sottosequenza diretta che sto cercando. Il massimo suffisso (c0 c1 c2 ... ci-1) è lungo i, se k+i<l allora ho già fallito, altrimenti passo ad un cursore su G le basi ci-l ci-l+1 ci-l+2 ... ci-1.
Se il cursore trova la strada su G fino a ci-1 allora ho trovato una sottosequenza diretta che copre tutto il massimo suffisso, se invece fallisce durante l'analisi della base cj allora vuol dire che la sequenza ci-l ci-l+1 ... cj non è una sottosequenza diretta, quindi, non potendo essere inclusa in nessuna sottosequenza diretta lunga almeno l, non potendo ci-l+1 essere l'inizio di una sequenza lunga almeno l che arriva fino a ci-1 (sarebbe lunga solo l-1), la lunghezza del massimo prefisso si riduce da i a j, se k+j<l fallisco, altrimenti reitero lo stesso procedimento cambiando il valore di i. Nel caso pessimo, veramente improbabile, occorre ripetere al massimo l-1 di questi passaggi per individuare, se esiste la sottosequenza diretta cercata.
Per cercare sottosequenze inverse complementate che partano da c0 seguo lo stesso procedimento usato per le dirette, complementando però le basi di T e usando G al posto di G' e viceversa.
Possono verificarsi 3 situazioni:
-se ho trovato solo una sottosequenza, diretta o inversa complementata, allora l'aggiungo alla copertura e procedo l'analisi dalla prima base di T che non è coperta da questa sottostringa, restando nel caso 2.
-se ho trovato sia una sottosequenza diretta che una inversa complementata allora aggiungo alla copertura solo quella che copre più basi ancora scoperte e procedo nell'analisi della prima base di T che non è coperta da questa sottostringa, restando nel caso 2.
-se non ho trovato né una sottosequenza diretta, né una sottosequenza inversa complementata, allora significa che c0 non può essere in nessun caso coperta da alcuna sottosequenza, procedo nell'analisi della base c1, andando nel caso 1.