2
Il grafo consente di catturare anche altre proprietà dell’insieme di
parole come il ritardo di decifrazione finito e la sincronizzazione.
Il primo passo dell’algoritmo prevede la costruzione di una Pattern
Matching Machine utilizzata in generale per individuare in una stringa
testuale le occorrenze dei patterns (parole chiave) forniti in input.
L’implementazione della Patten Matching Machine presentata in
questo lavoro di tesi è stata effettuata seguendo l’algoritmo di Aho-
Corasick [1]; essa consiste di tre funzioni:
ƒ La funzione goto è rappresentata da un grafo definito in base
alle parole chiave fornite in input: i vertici rappresentano i
prefissi di tali parole, mentre gli archi collegano i vertici in modo
tale da formare un percorso che identifichi la singola parola
chiave;
ƒ La funzione failure è computata per tutti i vertici del grafo
(funzione goto) e tale valore viene preso in considerazione
quando si verifica un fallimento nell’utilizzo della funzione goto;
ƒ La funzione output costruita in due parti, la prima dalla goto e la
seconda dalla failure, definita per quei vertici che identificano
una parola chiave.
La Pattern Matching Machine è fondamentale per la creazione del
grafo R(X) effettuata nei due passi centrali dell’algoritmo: l’insieme dei
vertici è lo stesso definito per la funzione goto mentre si sfruttano le
funzioni failure e output per determinare l’insieme degli archi, che
possono essere di due tipologie:
ƒ Archi EReach: sono identificati attraverso la funzione output;
ƒ Archi EDivisor: sono individuati dalla funzione failure.
3
L’ultimo passo consiste nell’effettuare una ricerca in ampiezza (BFS)
sul grafo R(X) per trovare almeno un cammino non banale dai vertici di
un insieme S(X), contenente i vertici che rappresentano parole che
siano prefissi di altre parole dell’insieme X, a vertici che rappresentano
parole dell’insieme X.
Dopo aver verificato che l’insieme delle parole X sia un codice, si
passa alla verifica del ritardo di decifrazione finito e della
sincronizzazione.
La prima consente di non dover aspettare l’intera ricezione del
messaggio per effettuare la decodifica. La seconda permette di avere
un fattore speciale w all’interno di un messaggio di cui non si conosce
l’inizio e la fine, e w consente di decodificare il messaggio dall’inizio
fino a w’ e da w’’ fino alla fine, dove w’w’’ = w.
Capocelli e Hoffmann hanno dimostrato che un codice ha ritardo di
decifrazione finito se e solo se sul grafo non esistono cicli dai vertici di
S(X) a vertici in X; mentre la proprietà di sincronizzazione è provata se
il grafo R(X) risulta essere aciclico.
La verifica di entrambe le proprietà è stata effettuata sfruttando un ben
noto teorema nella teoria dei grafi che afferma che un grafo orientato è
aciclico se e solo se una visita in profondità (DFS) sul grafo non
produce archi all’indietro, ossia che connettono un vertice ad un suo
antenato [6].
Il progetto realizzato in Java 1.4 ha seguito le linee guide di tale
algoritmo.
La classe Pmm riceve in input l’insieme X delle parole e costruisce la
Pattern Matching Machine cioè implementa le tre funzioni che la
costituiscono:
4
ƒ getGraph() è il metodo che genera la funzione goto ossia
costruisce un grafo orientato e decorato, implementato
attraverso liste di adiacenza e usando la struttura Mappa,
implementata con tabella Hash, per gestire la decorazione;
ƒ getFailure(graph) costruisce la funzione failure definita, per tutti i
vertici del grafo ricevuto in input, come un array di elementi di
tipo Failure.
ƒ getOutputGoto(graph) e getOutputFailure(failure[ ]) generano la
funzione output, restituita come un array di elementi di tipo
Output, costruita nel primo metodo attraverso il grafo (funzione
goto) e nel secondo attraverso i valori contenuti nell’array che
identifica la funzione failure.
La classe UniqueDec svolge il resto del lavoro testando le tre proprietà
succitate. In particolare, crea il grafo R(X) inserendo gli stessi vertici
del grafo (funzione goto) costruito dalla Pmm e aggiungendo gli archi
attraverso i seguenti metodi:
ƒ getEReach(output[ ]): genera gli archi EReach usando i valori
dell’array che identifica la funzione output della Pmm;
ƒ getEDivisor(failure[ ]): identifica gli archi EDivisor tramite l’array
che rappresenta la funzione failure della Pmm.
La verifica dell’ univoca decifrabilità, del ritardo di decifrazione finito e
della sincronizzazione è ottenuta attraverso i metodi:
ƒ isCode(): verifica se l’insieme delle parole è un codice
effettuando una visita in ampiezza sul grafo R(X); visita
5
realizzata dalla classe Bfs che implementa l’algoritmo standard
per la visita in ampiezza;
ƒ isFinitelyDec(): testa il ritardo di decifrazione finito nel caso
l’insieme di parole sia un codice attraverso un’istanza della
classe Dfs che esegue la visita in profondità sul grafo R(X) per
verificare l’esistenza di un ciclo da vertici di S(X), individuati dal
metodo getPrefixSet(), a vertici di X.
ƒ isSynchronizable(): nel caso l’insieme X sia un codice, prova se
X gode della proprietà di sincronizzazione attraverso una visita in
profondità su R(X) realizzata dalla classe Dfs, per verificare che
il grafo sia aciclico.
A completamento del progetto si è prodotto un output grafico
visualizzando le fasi salienti dell’algoritmo di decisione.
Il progetto è stato sviluppato utilizzando l’ambiente di sviluppo Java
Eclipse; si tratta di un framework basato su un sistema di API
pubbliche e di plug-in che fornisce funzionalità testuali (editor, debug,
ecc…) e grafiche.
Capitolo 1 Preliminari
6
CAPITOLO 1
Preliminari
In questo primo capitolo diamo una breve panoramica delle nozioni
base utilizzate, con particolare riferimento alle definizioni di alfabeto,
monoide, parola, linguaggio e codice tratte da [3].
1.1 Monoide
Un alfabeto A è un insieme finito i cui elementi sono detti lettere o
simboli.
Capitolo 1 Preliminari
7
Un monoide M è un insieme dotato di un’operazione associativa
binaria e di un elemento neutro. L’operazione è denotata con • ,
talvolta omesso se chiaro dal contesto. L’elemento neutro è unico ed è
denotato da λ
M
o semplicemente da λ.
Siano X, Y ⊂ M, definiamo
XY = { xy | x ∈ X, y ∈ Y }.
Un sottomonoide di M è un sottoinsieme N che è stabile con
l’operazione e contiene l’elemento neutro di M, ossia
NN ⊂ N, (1.1.1)
λ
M
∈ N. (1.1.2)
Si noti che un sottoinsieme N di M che soddisfa la (1.1.1) non sempre
verifica λ
M
= λ
N
e quindi può capitare che N sia un monoide senza
essere sottomonoide di M.
Un morfismo da un monoide M in un monoide N è una funzione
φ : M → N
tale che per ogni m, m’ ∈ M, si ha
φ (mm’) = φ (m) φ (m’),
e ancora
φ (λ
M
) = λ
N
.
Un idempotente di un monoide è un elemento e di M tale che
e = e
2
.
Per ogni idempotente e di un monoide M, l’insieme
M(e) = eMe
Capitolo 1 Preliminari
8
è un monoide contenuto in M.
Ricordiamo anche che un semigruppo è un insieme dotato di
un’operazione associativa ma senza il requisito dell’esistenza
dell’elemento neutro. Le nozioni di sottosemigruppo e morfismo di
semigruppo sono definite nello stesso modo delle corrispondenti
nozioni per monoidi.
Sia M un monoide. Per x, y ∈ M, definiamo
x
-1
y = { z ∈ M | xz = y} e xy
-1
= { z ∈ M | x = zy}.
Per sottoinsiemi X, Y di M, questa notazione è estesa a
X
-1
Y = U
x∈X
U
y∈Y
x
-1
y e XY
-1
= U
x∈X
U
y∈Y
xy
-1
(1.1.3)
Le seguenti identità sono valide per sottoinsiemi X, Y, Z di M:
(XY)
-1
Z = Y
-1
(X
-1
Z) e X
-1
(YZ
-1
) = (X
-1
Y)Z
-1
.
Dato un sottoinsieme X di un monoide M, definiamo
F(X) = M
-1
XM
-1
come l’insieme dei fattori degli elementi in X. Abbiamo
F(X) = { m ∈ M | ∃ u, v ∈ M: umv ∈ X }.
Solitamente usiamo la notazione F(X) per denotare il complemento di
F(X) in M,
F(X) = M – F(X).
Capitolo 1 Preliminari
9
1.2 Parole
Sia A un alfabeto. Una parola ω sull’alfabeto A è una sequenza finita
di elementi di A
ω = ( a
1
, a
2
, ……, a
n
), a
i
∈ A
L’insieme di tutte le parole sull’alfabeto A è denotato da A
*
ed è dotato
di un’operazione associativa definita dalla concatenazione di due
sequenze
( a
1
, a
2
, ……, a
n
)( b
1
, b
2
, ……, b
m
) = ( a
1
, a
2
, ……, a
n
, b
1
, b
2
, ……, b
m
)
Questa operazione è associativa e permette di scrivere
ω = a
1
a
2
……a
n
invece di ω = ( a
1
, a
2
, ……, a
n
), identificando ciascun elemento a ∈ A
con la sequenza (a).
La sequenza vuota è chiamata parola vuota, è denotata da λ e
rappresenta l’elemento neutro. Così A
*
è dotato della struttura di un
monoide ed è chiamato monoide libero su A.
L’insieme delle parole non vuote su A è rappresentato con A
+
e quindi
avremo
A
+
= A
*
/ λ.
La lunghezza |ω| della parola ω = a
1
a
2
…… a
n
è il numero n di lettere
in ω. Chiaramente, | λ | = 0.
La funzione ω → |ω| è un morfismo da A
*
nel monoide additivo N
degli interi non negativi. Per n ≥ 0, usiamo la notazione
A
(n)
= { ω ∈ A
*
| |ω| ≤ n-1 }
ed inoltre
A
[n]
= { ω ∈ A
*
| |ω| ≤ n }.
Capitolo 1 Preliminari
10
In particolare, A
(0)
= ∅ e A
[0]
= { λ }.
Una parola ω ∈ A
*
è un fattore di una parola x ∈ A
*
se esiste u, v ∈
A
*
tale che x = uωv.
La relazione è un fattore di, è un ordine parziale su A
*
. Un fattore ω di
x è proprio se ω ≠ x.
Una parola ω è un prefisso di una parola x ∈ A
*
se c’è una parola u ∈
A
*
tale che x = ωu. Il fattore ω è chiamato proprio se ω ≠ x. La
relazione “ è un prefisso di ”, è ancora un ordine parziale su A
*
che
prende il nome di ordinamento prefisso.
Scriviamo ω ≤ x quando ω è prefisso di x e ω < x ogni qualvolta ω è
prefisso proprio di x.
Questo ordine gode di una proprietà fondamentale:
Proposizione 1.1:
Siano ω, ω’, x ∈ A
*
. Se
ω ≤ x, ω’ ≤ x,
allora ω e ω’ sono confrontabili, cioè
(a) ω ≤ ω’ o (b) ω’ ≤ ω.
ω ω’’
x
ω’ ω’’’ ω’ ω’’’
(a) (b)
x x
Figura 1.1
Capitolo 1 Preliminari
11
In altre parole, se vω = v’ω’, allora esiste s ∈ A
*
tale che v = v’s (ed
inoltre sω = ω’) oppure esiste t ∈ A
*
tale che v’ = vt (ed allora ω = tω’).
Un insieme P ⊂ A
*
è chiamato chiuso per prefissi se contiene i
prefissi dei suoi elementi: uv ∈ P ⇒ u ∈ P.
Similarmente possiamo introdurre la nozione di suffisso.
Una parola ω è un suffisso di una parola x ∈ A
*
se c’è una parola v ∈
A
*
tale che x = vω. Il suffisso ω sarà proprio se ω ≠ x.
Un insieme S ⊂ A
*
è chiamato chiuso per suffisso se contiene i suffissi
dei suoi elementi: uv ∈ S ⇒ v ∈ S.
La potenza n-esima di una parola ω è data dalla concatenazione
della parola stessa per n volte:
λ se n = 0
ω
n-1
ω altrimenti
Introduciamo ora una nozione chiave nella teoria dei codici.
Una fattorizzazione di una parola ω ∈ A
*
è una sequenza { u
1
, u
2
, ……,
u
n
} di n ≥ 0 parole di A
*
tale che
ω = u
1
u
2
……u
n
.
Per un sottoinsieme X di A
*
, denotiamo con X*, il sottomonoide
generato da X,
X* = { x
1
x
2
…… x
n
| n ≥ 0, x
i
∈ X }
Un insieme X che genera un sottomonoide libero M di A* è chiamato
la base di M.
⎩
⎨
⎧
ω
n
=
Capitolo 1 Preliminari
12
Analogamente, denotiamo con X
+
il sottosemigruppo generato da X,
X
+
= { x
1
x
2
……x
n
| n ≥ 1, x
i
∈ X }.
Abbiamo
Per definizione, ogni parola ω in X* ammette almeno una
fattorizzazione (x
1
, x
2
……, x
n
) i cui elementi sono tutti in X. Una tale
fattorizzazione è chiamata X – fattorizzazione.
1.3 Linguaggi
1.3.1 Definizioni di base e alcune operazioni
Sia A un alfabeto. Un linguaggio L su A ( indicato con L ⊆ A* ) è un
insieme di parole definite su A.
L’insieme vuoto ∅ e l’insieme { λ }, costituito dalla sola parola vuota,
sono due linguaggi di qualunque alfabeto. L’insieme A
*
rappresenta il
linguaggio costituito da tutte le parole sull’alfabeto A.
La cardinalità di un linguaggio L è data dal numero di parole in esso
contenute ed è denotata da |L|.
Siano L e K due linguaggi, la concatenazione LK è l’insieme ottenuto
concatenando le parole di L con le parole di K.
⎩
⎨
⎧
X
+
=
X* / λ se λ ∉ X
X* altrimenti
Capitolo 1 Preliminari
13
LK = { xy | x ∈ L e y ∈ K }
Concatenando un linguaggio L con l’insieme vuoto ∅ avremo
L∅ = ∅
mentre concatenando L con l’insieme { λ }, costituito dalla sola parola
vuota, avremo
L{ λ } = L.
La potenza n-esima di un linguaggio L è ottenuta concatenando L
con se stesso per n volte:
L’operazione star di Kleene L* del linguaggio L è data dall’unione di
tutte le potenze di L
L* = U
h = 0…∞
L
h
= { λ } U L
1
U L
2
……
Siano L e K due linguaggi, l’insieme L / K, detto quoziente dei
linguaggi L e K, contiene i prefissi di L che, concatenati con le parole
di K, costituiscono parole contenute in L
L / K = { x | xy ∈ L e y ∈ K }.
Sia A un alfabeto e A* il monoide libero su A. Se X,Y ⊆ A* denoteremo
con X
-1
Y e YX
-1
i sottoinsiemi di A* definiti come in (1.1.3).
Le operazioni X
-1
Y e YX
-1
sono dette operazioni quozienti sinistro e
destro rispettivamente.
⎩
⎨
⎧
L
n
=
λ se m = 0
L
n-1
L altrimenti
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
