Capitolo 5 Trasformazione generale di espressioni regolari in intervalli. Caso di studio: le “network expression”.

Capitolo 5

Trasformazione generale di espressioni

regolari in intervalli.

Caso di studio: le “network expression”.

expression”.

La scelta di questo tipo di espressioni non è casuale ed è motivata dal fatto che, per valutare l’efficienza del metodo proposto in questa tesi, occorrono data

set di espressioni reali.

Nel corso del capitolo mostriamo prima di tutto l’algoritmo implementato per determinare la stringa massima e la stringa minima del linguaggio definito da una generica espressione r (espressa con la notazione base) e poi mostriamo quali cambiamenti subiscono le regole (adottate all’interno dell’algoritmo), utilizzate

per determinare la stringa massima e la stringa minima, se consideriamo la sintassi e la semantica delle “network expression”; inoltre presentiamo anche l’euristica adottata per esprimere r attraverso un’unione disgiunta di più intervalli.

5.1 Algoritmo per determinare la stringa massima e la

stringa minima

In questa sezione mostriamo l’algoritmo realizzato per determinare la stringa massima e la stringa minima di un linguaggio regolare definito da una generica espressione r.

La fig. 5.1 mostra i passi fondamentali dell’algoritmo. Algoritmo CalcolaMaxMin(r)

Input: r ∈ R.

Output: stringa massima (max(L(r))) e stringa minima (min(L(r))) di L(r). 1. max(L(r)) := min(L(r)) := NULL;

2. p := lunghezza(r); 3. repeat

4. for each (sottoespressione r′e r′′di r) do

5. calcola massimo e minimo di r′e r′′ secondo le regole esposte;

6. if (min(L(r′′)) è prefisso max(L(r′′)))

7. min(L(r))

=

8. else min(L(r)) =MIN(min(L(r′′)) min(L(r′ )),

min(L(r′′)$)min(L(r′));

9. if (min(L(r′′)) è prefisso max(L(r′′)))

10. max(L(r))=MAX(min(L(r′′))max(L(r′)), max(L(r′′))max(L(r′)), max(L(r′′)$)max(L(r′));

11. else max(L(r)) = MAX(max(L(r′′)) max(L(r′)),

max(L(r′′)$)max(L(r′));

12. until (p = 0);

Abbiamo visto negli esempi fatti nel capitolo precedente come risulti abbastanza semplice e immediato applicare le regole, utilizzate per determinare la stringa massima e la stringa minima, a singole espressioni regolari (singolo simbolo, unione, stella di Kleene).

In realtà, l’algoritmo è utilizzato nel momento in cui si deve determinare

max(L(r)) e min(L(r)) di un’espressione in cui è presente l’operatore di concatenazione di due espressioni; infatti, la determinazione del max(L(r)) e del min(L(r)) di una espressione della forma r = (r1)(r2) viene eseguita effettuando

un “parsing” di r stessa a partire da destra (quindi in questo caso a partire da r2)

e si procede concatenando man mano max(L(r1)) (se L(r1) è finito, altrimenti si

considera L′(r1)) o min(L(r1)) a max(L(r2)) o min(L(r2)) a seconda che si voglia

determinare max(L(r)) oppure min(L(r)). In poche parole, considerando l’albero sintattico di r, si definisce un “parser” ricorsivo che applica la regola della concatenazione visitando i vari nodi dell’albero (foglie e nodi interni) a partire da destra e calcolando i risultati intermedi della stringa massima (o minima) delle espressioni incontrate fino a quel momento.

E’ da notare che per eseguire il “parsing” dell’espressione in ingresso a partire da destra, ovvero a partire dal fondo dell’espressione, il puntatore p, utilizzato nell’algoritmo per scorrere l’espressione r (vista come una stringa), punta alla fine di r.

Man mano che si procede da destra verso sinistra, si individua una generica sottoespressione r′ (rappresentante il primo termine della concatenazione); si

calcola la stringa massima e la stringa minima di r′, scendendo nell’albero

sintattico di r′ stessa e si procede individuando il termine successivo della

concatenazione, ovvero si individua una sottoespressione r′′. Anche per questa

sottoespressione si calcola la stringa massima e la stringa minima scendendo nell’albero sintattico di r′′ stessa. Una volta ottenuta la stringa massima e la

stringa minima di ciascuna sottoespressione, r′ e r′′, si applica la regola prevista

massima e una stringa minima parziali delle sottoespressioni esaminate fino a quel momento. Si procede concatenando, sempre secondo la regola della concatenazione esposta nel capitolo 4, il risultato parziale, ottenuto al passo precedente, con la stringa massima e la stringa minima della successiva sottoespressione da esaminare. Si continua sino a quando non si giunge alla fine (che sostanzialmente coincide con l’inizio se si parte da sinistra) dell’espressione in ingresso.

In pratica il tipo di “parser” che si utilizza nell’algoritmo è ricorsivo a destra. All’inizio dell’esecuzione si calcolano la stringa massima e la stringa minima della prima sottoespressione che si incontra e si procede con il calcolo della stringa massima e della stringa minima della sottoespressione successiva alla prima incontrata. Si determinano, in base alla regola della concatenazione, la stringa massima e la stringa minima parziali. Si procede concatenando i risultati parziali ottenuti con la stringa massima e minima della sottoespressione successiva nella concatenazione. Si prosegue ricorsivamente allo stesso modo sino a quando non si giunge alla cima di r.

La complessità dell’algoritmo esposto in fig. 5.1 è lineare; la correttezza segue dalla correttezza delle regole (sezione 4.9) utilizzate per determinare la stringa massima e minima di una generica espressione.

Per comprendere meglio il funzionamento dell’algoritmo forniamo un esempio di espressione a cui applichiamo man mano i passi dell’algoritmo.

Esempio 5.1 Consideriamo l’espressione regolare r = (a)*bc; in base a ciò che

abbiamo detto precedentemente, iniziamo facendo il “parsing” di r a partire da destra, quindi incontriamo ‘c’ che rappresenta r2 per cui calcoliamo max (L(r2)) = ‘c’ e min (L(r2)) = ‘c’; proseguendo incontriamo ‘b’ che rappresenta r1 per cui

calcoliamo max(L(r1)) = ‘b’ e min (L(r1)) = ‘b’. A questo punto, applicando la

regola, si ha che min(L(r1)) è prefisso di max(L(r1)) e quindi il valore

MAX(min(L(r1))max(L(r2)), max(L(r1))max(L(r2))) che è proprio uguale alla

stringa ‘bc’. Continuando il ‘parsing’ dell’espressione r incontriamo (a)* che rappresenta r1 , per cui calcoliamo max(L′(r1)) = ‘a ’1 e min(L′(r1)) = ε. Il min(L′(r1)) = ε è prefisso del max(L′(r1)) = ‘a ’ per cui il valore finale della

stringa massima di L(r) sarà ottenuto considerando MAX(min(L′(r1))max(L(r2)), max(L′(r1))max(L(r2))) = MAX ( ‘bc’, ‘a bc’) = ‘bc’.

Per il calcolo della stringa minima si procede allo stesso modo, cioè iniziamo facendo il “parsing” di r a partire da destra, quindi incontriamo ‘c’ che rappresenta r2 per cui calcoliamo max(L(r2)) = ‘c’ e min(L(r2)) = ‘c’;

proseguendo incontriamo ‘b’ che rappresenta r1 per cui calcoliamo max(L(r1)) = ‘b’ e min (L(r1)) = ‘b’. A questo punto, applicando la regola, si ha che min(L(r1))

è prefisso di max(L(r1)) e quindi il valore “intermedio” della stringa minima si

ottiene considerando MIN(max(L(r1))min(L(r2)), min(L(r1))min(L(r2))) che è

proprio uguale alla stringa ‘bc’. Continuando il “parsing” dell’espressione r incontriamo (a)* che rappresenta r1, per cui calcoliamo max(L′(r1)) = ‘a ’ e min(L′(r1)) = ε. Il min(L′(r1)) = ε è prefisso del max (L′(r1)) = ‘a ’ per cui il

valore finale della stringa minima di L(r) sarà ottenuto considerando MIN(max(L′(r1))min(L(r2)), min(L′(r1))min(L(r2))) = MIN (‘bc’, ‘a bc’) = ‘a bc’.

5.2 Regole per determinare la stringa massima e la stringa

minima nelle “network expression”

In questa sezione mostriamo alcune variazioni che subiscono le regole, utilizzate per determinare la stringa massima e la stringa minima, presentate nel capitolo 4.

Come abbiamo avuto modo di vedere nel capitolo 1, con le “network

expression”, vengono introdotte delle variazioni, sia a livello semantico che

sintattico, rispetto alla notazione base. Proprio questa variazione ci induce a modificare le regole esposte precedentemente.

Sebbene la regola, per determinare la stringa massima e la stringa minima, prevista per la concatenazione di espressioni non cambi, poiché il procedimento adottato rimane lo stesso anche per la tipologia di espressioni che stiamo prendendo in considerazione, ciò che induce a modificare le regole sono i token che possono comporre un generico pattern PROSITE.

Consideriamo tutti i tipi di token che possono comporre un generico pattern e per ciascuno definiamo le regole per calcolare la stringa massima e la stringa minima.

Ciascun token, che caratterizza un generico pattern, può essere:

1) un aminoacido ben fissato, quindi una A, oppure una C, oppure una D e così

via. In questo caso, la stringa massima e la stringa minima sono rappresentate dall’aminoacido specificato in quella determinata posizione. Per cui, si ha che: se r = A allora min(L(r)) = A e max(L(r)) = A per ogni simbolo A ∈ .

Se viene specificata la ripetizione di un aminoacido fissato A (per ogni simbolo A ∈ ), un numero costante di volte num, allora la stringa massima

e la stringa minima sono rappresentate entrambe dall’aminoacido A, concatenato num volte;

2) un aminoacido ambiguo che può essere indicato con:

a) x, che rappresenta un qualunque aminoacido. In questo caso, la stringa

massima e la stringa minima sono rappresentate rispettivamente dall’aminoacido “Tyrosine” (che rappresenta la lettera lessicograficamente più grande dell’alfabeto, cioè Y) e dall’aminoacido

“Alanine” (che rappresenta la lettera lessicograficamente più piccola

dell’alfabeto, cioè A). Per cui, si ha che: se r = x allora min(L(r)) = A e

Se viene specificata la ripetizione del token x, un numero costante di volte

num, allora la stringa massima e la stringa minima sono rappresentate

rispettivamente dalla lettera Y, concatenata num volte, e dalla lettera A, concatenata anch’essa num volte.

Se viene specificata la ripetizione del token x, un numero di volte variabile all’interno di un determinato intervallo di estremi (num, num′), allora la

stringa massima e la stringa minima sono rappresentate rispettivamente dalla lettera Y, concatenata num′ volte, e dalla lettera A, concatenata

anch’essa num′ volte;

b) le parentesi [ ], che esprimono una alternativa. In questo caso la stringa

massima e la stringa minima sono rappresentate rispettivamente dalla lettera lessicograficamente più grande (contenuta nell’espressione di alternativa) e dalla lettera lessicograficamente più piccola (contenuta nell’espressione di alternativa).

Se viene specificata la ripetizione del token [ ], un numero costante di volte num, allora la stringa massima e la stringa minima sono rappresentate rispettivamente dalla lettera lessicograficamente più grande (contenuta nell’espressione di alternativa), concatenata num volte, e dalla lettera lessicograficamente più piccola (contenuta nell’espressione di alternativa), concatenata anch’essa num volte;

c) le parentesi {}, che indicano qualunque aminoacido eccetto quelli inclusi

nelle parentesi. In questo caso, la determinazione della stringa massima e della stringa minima viene effettuata come nel caso b), visto che le parentesi {} equivalgono ad una espressione di alternativa che non contiene gli aminoacidi specificati nelle {} stesse.

E’ importante sottolineare che con le “network expression” non si utilizza la nozione di troncamento di un linguaggio L(r) infinito, poiché nella sintassi di questo tipo di espressioni non è incluso l’operatore stella di Kleene per cui è

sempre possibile determinare la stringa massima e la stringa minima di un generico pattern r, in quanto sempre esistenti.

Seguono degli esempi in cui mostriamo l’applicazione delle regole sopra descritte a singoli token.

Esempio 5.2 Consideriamo i seguenti due token: C(4) ed F(6). Questi token

indicano rispettivamente che l’aminoacido “Cysteine” occorre quattro volte nella sequenza, ovvero si ha la sottosequenza CCCC e l’aminoacido “Phenylalanine” occorre sei volte nella sequenza, ovvero si ha la sottosequenza FFFFFF. La stringa massima e la stringa minima del token C(4) sono rappresentate rispettivamente da CCCC e CCCC (in questo caso stringa massima e stringa minima coincidono). La stringa massima e la stringa minima del token F(6) sono rappresentate rispettivamente da FFFFFF e FFFFFF (ovviamente, anche in questo caso le due stringhe coincidono).

Esempio 5.3 Consideriamo i seguenti due token: x(4) ed x(2,6). Per quanto

riguarda x(4) la stringa massima e la stringa minima sono, rispettivamente, YYYY e AAAA.

Consideriamo il token x(2, 6). In questo caso si ha che la stringa massima è rappresentata da YYYYYY e la stringa minima è rappresentata da AAAAAA.

Esempio 5.4 Consideriamo i seguenti token: [ACDEFG], [STLVMF](6). Per

quanto riguarda il primo token, la stringa massima corrisponde a G e la stringa minima corrisponde ad A. Invece, per il secondo si ha che la stringa massima è uguale alla stringa VVVVVV e la stringa minima è uguale alla stringa FFFFFF.

Esempio 5.5 Consideriamo i seguenti due token: {ACDEFG}, {ASTLVMFY}(6).

Il primo equivale alla seguente espressione di alternativa:

E, F, G. In questo caso la stringa massima corrisponde alla stringa Y e la stringa

minima corrisponde alla stringa H.

Il secondo token, cioè {ASTLVMFY}(6), equivale all’espressione

[CDEGHIKNPQRW](6), in cui sono presenti tutti gli aminoacidi tranne S, T, L, V, M, F, A, Y. In questo caso la stringa massima corrisponde alla stringa WWWWWW e la stringa minima corrisponde a CCCCCC.

Abbiamo visto con questi esempi come non sia complicato, applicando le regole sopra esposte, determinare la stringa massima e la stringa minima di un determinato token.

In realtà, i pattern che consideriamo non sono costituiti solo da un token, ma sono caratterizzati dalla concatenazione di più token. Per determinare la stringa massima e la stringa minima di un pattern costituito da più token, è possibile applicare l’algoritmo esposto in fig. 5.1.

Esempio 5.5 Consideriamo il seguente pattern: [ADF]-V-x(6)-A(2). I passi che si

seguono applicando l’algoritmo di fig. 5.1 sono i seguenti: calcoliamo la stringa massima e la stringa minima della sottoespressione r′ = A(2). Otteniamo che

max(L(r′)) = min(L(r′)) = AA. Proseguiamo individuando la stringa massima e la

stringa minima della sottoespressione r′′ = x(6). Otteniamo che max(L(r′′)) = YYYYYY e min(L(r′′)) = AAAAAA. A questo punto in base alla regola della

concatenazione si ha che min(L(r′′)) = AAAAAA non è prefisso di max(L(r′′)) = YYYYYY per cui la stringa massima parziale risulta essere max(L(r)) = max(L(r′′))max(L(r′)) = YYYYYYAA e la stringa minima parziale risulta essere min(L(r)) = min(L(r′′))min(L(r′)) = AAAAAAAA. A questo punto calcoliamo la

stringa massima e la stringa minima della sottoespressione successiva nell’operazione di concatenazione, cioè r′′′ = V. Dalle regole esposte nella

sezione 5.1 otteniamo che max(L(r′′′)) = min(L(r′′′)) = V. Applicando l’algoritmo

della stringa massima bisogna scegliere MAX(VYYYYYYAA, VYYYYYYAA), ottenendo quindi la nuova stringa massima parziale max(L(r)) = VYYYYYYAA; per il calcolo della stringa minima bisogna scegliere MIN(VAAAAAAAA,

VAAAAAAAA), ottenendo quindi la nuova stringa minima parziale min(L(r)) = VAAAAAAAA. A questo punto esaminiamo l’ultima sottoespressione r′′′′ = [ADF]. In questo caso, max(L(r′′′′)) = F e min(L(r′′′′))=A. Applicando

l’algoritmo si ha che min(L(r′′′′)) = A non è prefisso di max(L(r′′′′)) = F, per cui

la stringa massima finale è max(L(r)) = FVYYYYYYAA e la stringa minima finale risulta essere min(L(r)) = AVAAAAAAAA.

Esempio 5.6 Consideriamo il seguente pattern: W-[LYVM]-x(2,6)-C(2). I passi

che si seguono applicando l’algoritmo di fig. 5.1 sono i seguenti: calcoliamo la stringa massima e la stringa minima della sottoespressione r′ = C(2). Otteniamo

che max(L(r′)) = min(L(r′)) = CC. Proseguiamo individuando la stringa massima

e la stringa minima della sottoespressione r′′ = x(2,6). Otteniamo che max(L(r′′))

= YYYYYY e min(L(r′′)) = AAAAAA. A questo punto in base alla regola della

concatenazione si ha che min(L(r′′)) = AAAAAA non è prefisso di max(L(r′′)) = YYYYYY per cui la stringa massima parziale risulta essere max(L(r)) = max(L(r′′))max(L(r′)) = YYYYYYCC e la stringa minima parziale risulta essere min(L(r)) = min(L(r′′))min(L(r′)) = AAAAAACC. A questo punto calcoliamo la

stringa massima e la stringa minima della sottoespressione successiva nell’operazione di concatenazione, cioè r′′′ = [LYVM]. Dalle regole esposte nella

sezione 5.1 otteniamo che max(L(r′′′)) = Y e min(L(r′′′)) = L. Applicando

l’algoritmo si ha che min(L(r′′′)) = L non è prefisso di max(L(r′′′)) = Y, per cui la

stringa massima parziale max(L(r)) = YYYYYYYCC; la stringa minima parziale

min(L(r)) = LAAAAAACC. A questo punto esaminiamo l’ultima sottoespressione r′′′′ = W. In questo caso, max(L(r′′′′)) = W e min(L(r′′′′)) = W. Applicando

l’algoritmo si ha che min(L(r′′′′)) = W è prefisso di max(L(r′′′′)) = W, per cui la

max(L(r)) = WYYYYYYYCC; la stringa minima finale sarà MIN(WLAAAAAACC, WLAAAAAACC), ovvero min(L(r)) = WLAAAAAACC.

Gli esempi appena fatti mostrano come l’algoritmo presentato in fig. 5.1 calcoli gli estremi dell’intervallo con cui si vuole rappresentare un generico pattern. Infatti, la stringa minima determinata dall’algoritmo corrisponde all’estremo sinistro dell’intervallo e la stringa massima corrisponde all’estremo destro.

Ad esempio, consideriamo il pattern definito nell’esempio 5.5. La stringa minima e la stringa massima che abbiamo determinato sono le seguenti:

max(L(r)) = FVYYYYYYAA e min(L(r)) = AVAAAAAAAA. Quindi, l’intervallo con

cui rappresentiamo il pattern è [AVAAAAAAAA, FVYYYYYYAA].

Consideriamo il pattern definito nell’esempio 5.6. La stringa minima e la stringa massima che abbiamo determinato sono le seguenti: max(L(r)) =

WYYYYYYYCC e min(L(r)) = WLAAAAAACC. Quindi, l’intervallo con cui

rappresentiamo il pattern è [WLAAAAAACC, WYYYYYYYCC].

L’idea di esprimere un’espressione attraverso un intervallo di stringhe da un lato facilita il trattamento dell’espressione stessa, poiché, in generale, l’espressione viene vista e trattata come un insieme di stringhe e ciò risulta più semplice che trattare l’automa che la rappresenta, dall’altro comporta l’introduzione di alcuni errori, nel senso che nell’intervallo che si costruisce non sono contenute solo le stringhe accettate da L(r), ma anche delle stringhe (falsi

positivi) che non sono accettate dall’automa che rappresenta r.

Al fine di rendere più precisa la rappresentazione di r attraverso un intervallo di stringhe, nella sezione che segue mostriamo il metodo adottato per limitare il più possibile il numero di falsi positivi contenuti nell’intervallo che rappresenta r.

5.3 Euristica utilizzata per contenere il numero di falsi

positivi

Esprimere un’espressione r attraverso un intervallo di stringhe vuol dire comprendere nell’intervallo non solo le stringhe appartenenti ad L(r), ma anche altre stringhe (falsi positivi) che non sono accettate da L(r).

Diminuire il più possibile il numero di falsi positivi, contenuti nell’intervallo che rappresenta l’espressione, vuol dire migliorare il rapporto

Infatti, la densità di r migliora quanto più il denominatore è piccolo e si avvicina al numeratore, ovvero quanto più l’intero rapporto tende a 1 (si veda la sezione 4.3).

In genere, quando un generico pattern r contiene sottoespressioni di alternativa, per il calcolo della stringa massima e minima, applichiamo la regola che determina la lettera lessicograficamente più grande e la lettera lessicograficamente più piccola tra quelle presenti nelle parentesi []. Questo modo di procedere è poco preciso poiché scegliendo la lettera più grande e la più piccola si includono, nell’intervallo che si va a costruire, anche tutte le lettere che sono sì comprese tra la più grande e la più piccola della sottoespressione di alternativa, ma che non sono contenute nelle parentesi [].

Al fine di migliorare d(r), ed ovviare all’inconveniente dell’approssimazione “grossolana” spiegata sopra, è possibile esprimere r attraverso l’unione disgiunta di più intervalli. Ovviamente, questo si può fare qualora il pattern, che si prende in considerazione, contenga sottoespressioni di alternativa. In questo caso è possibile esprimere il pattern iniziale r come l’unione di più sottoespressioni r1, r2, r3, r4, …, rn ottenute in funzione del numero di lettere che compongono le

sottoespressioni di alternativa. Quindi, per ciascuna sottoespressione ri

|L(r)|

d(r) =

(dove 1≤ i ≤ n) ottenuta, si applica l’algoritmo per determinare la stringa

massima e la stringa minima, in modo tale da determinare l’intervallo che rappresenta ri. Con questo procedimento, l’espressione iniziale viene

rappresentata con l’unione disgiunta degli intervalli che rappresentano ciascuna sottoespressione.

Ad esempio, consideriamo il pattern r = [ADF]-V-x(6)-A(2) dell’esempio 5.5. Abbiamo visto che l’intervallo associato ad r è [AVAAAAAAAA, FVYYYYYYAA]. In realtà, l’intero pattern definisce tre sottoespressioni (una per ciascuna lettera inclusa nelle parentesi []), ovvero r1 = D-V-x(6)-A(2), r2 = A-V-x(6)-A(2), r3 = F-V-x(6)-A(2), per cui è possibile vedere l’insieme L(r) come l’unione disgiunta

degli intervalli definiti da ciascuna sottoespressione. Quindi, possiamo rappresentare r = [ADF]-V-x(6)-A(2) con il seguente insieme di intervalli:

[AVAAAAAAAA,AVYYYYYYAA] ∪ [DVAAAAAAAA,DVYYYYYYAA] ∪

[FVAAAAAAAA,FVYYYYYYAA].

La stessa cosa accade per il pattern r = W-[LYVM]-x(2,6)-C(2) considerato nell’esempio 5.6. L’intervallo inizialmente associato ad esso è [WLAAAAAACC,

WYYYYYYYCC]. In realtà, l’intero pattern definisce quattro sottoespressioni,

ovvero r1 = W-L-x(2, 6)-C(2), r2 = W-Y-x(2, 6)-C(2), r3 = W-V-x(2, 6)-C(2), r4=W-M-x(2, 6)-C(2), per cui è possibile vedere l’insieme L(r) come l’unione

disgiunta degli intervalli definiti da ciascuna sottoespressione. Quindi, possiamo rappresentare r = W-[LYVM]-x(2,6)-C(2) con il seguente insieme di intervalli: [WLAAAAAACC, WLYYYYYYCC] ∪ [WYAAAAAACC, WYYYYYYYCC] ∪

[WVAAAAAACC, WVYYYYYYCC] ∪ [WMAAAAAACC, WMYYYYYYCC].

Come si può notare, sia nel primo esempio che nel secondo siamo riusciti ad abbassare notevolmente il numero di falsi positivi contenuti negli intervalli rappresentanti r. Infatti, nel primo caso, applicando l’euristica, consideriamo solo le stringhe che cominciano per A, D, F, escludendo tutte quelle che cominciano per C e per E (incluse invece se avessimo considerato l’intervallo iniziale); nel secondo caso consideriamo solo le stringhe che cominciano per WL…, WY…,

WV…, WM…, escludendo tutte quelle che cominciano per WN…, WP…, WQ…, WR…, WS…, WT…, WW….

In generale, considerato un generico pattern r, contenente sottoespressioni di alternativa, se applichiamo l’euristica sopra esposta ed esprimiamo r con l’unione disgiunta di più intervalli, il numero di intervalli facente parte dell’unione dipende dalle lettere incluse nelle sottoespressioni di alternativa. Quindi, se un pattern contiene diverse sottoespressioni di alternativa, otterremo un numero di intervalli pari al numero di tutte le possibili combinazioni tra le lettere incluse nelle sottoespressioni di alternativa.

Esempio 5.7 Consideriamo il seguente pattern: r = W-[LYVM]-x-[AC]-C(2).

Applicando l’euristica, il numero di intervalli facente parte dell’unione risulta essere 8, poiché bisogna considerare tutte le possibili combinazioni delle lettere

L, Y, V, M, contenute nella prima sottoespressione di alternativa, con le lettere A, C, contenute nella seconda sottoespressione di alternativa. Ciò che si ottiene è

che l’espressione r viene rappresentata con la seguente unione disgiunta di intervalli:

[WLAACC, WLYACC] ∪ [WYAACC, WYYACC] ∪[WVAACC, WVYACC] ∪

[WMAACC, WMYACC] ∪ [WLACCC, WLYCCC] ∪ [WYACCC, WYYCCC] ∪

[WVACCC, WVYCCC] ∪ [WMACCC, WMYCCC].

L’esempio appena fatto ci mostra come la precisione aumenti nel caso in cui esprimiamo un generico pattern r con l’unione disgiunta di più intervalli. Però, allo stesso tempo, il numero di intervalli che fa parte dell’unione è destinato a crescere in funzione del numero delle sottoespressioni di alternativa contenute nel pattern e del numero di lettere contenute all’interno delle sottoespressioni.

Quindi, se da un lato l’applicazione dell’euristica sopra esposta contribuisce al miglioramento del rapporto che esprime la densità di un generico pattern r,

dall’altro comporta l’introduzione di alcune inefficienze, viste in termini di spazio di memoria occupata.

Al fine di trovare un buon compromesso spazio- precisione, è possibile, data una generica espressione r ∈ R, espandere solo k sottoespressioni di alternativa

tra le n presenti, ovvero il parametro k, compreso tra 1 ed n, indica il numero di sottoespressioni di alternativa su cui applicare l’euristica prima esposta.

L’esempio che segue ci chiarirà meglio le idee.

Esempio 5.8 Consideriamo il seguente pattern: r =

W-[LYVM]-x-[AC]-[DFGHIMNPQRST]-[KLMNH]-[PQRS]-C(2).

Applicando l’euristica a tutte le sottoespressioni di alternativa (quindi vuol dire k = 5), il numero di intervalli facente parte dell’unione risulta essere 1920, poiché bisogna considerare tutte le possibili combinazioni delle lettere L, Y, V,

M, contenute nella prima sottoespressione di alternativa, con le lettere A, C,

contenute nella seconda sottoespressione di alternativa, con le lettere D, F, G, H,

I, M, N, P, Q, R, S, T contenute nella terza sottoespressione di alternativa e così

via.

Se invece il valore di k viene impostato a 3, il numero di intervalli, facente parte dell’unione, risulta essere 96, ovvero tutte le possibili combinazioni tra le lettere contenute nelle prime 3 sottoespressioni di alternativa. Naturalmente, le restanti sottoespressioni rimangono sottoespressioni di alternativa, nel senso che nel calcolo della stringa massima e minima vengono considerate come tali.