sabato 19 ottobre 2013

Misura di Distanza per Stringhe in Dinamica Simbolica


Concetti di Base 

Consideriamo un Sistema Dinamica Astratto come un Sistema Dinamico che elabora stringhe di varia lunghezza

Anzitutto sarà necessario definire
$ S $ Alfabeto che contiene Lettere che formano le Stringhe in questione

Indichiamo quindi con 
  • $ S^{n} $ Stringhe di Lunghezza Fissa e pari a $ n $ lettere 
  • $ S^{*} $ Insieme di tutte le Stringhe a Lunghezza Finita ovvero
    $ S^{*} = \cup_{i=1}^{n} S^{i} $ 

Si può quindi estendere il Concetto di Stringa a Lunghezza Finita a quello di Srtinga a Lunghezza Infinita, definendolo come 
$ S^{\infty} $ Insieme delle Stringhe tali che qualsiasi troncamento all’i-esima lettera (a partire dall'inizio) delle stesse sia un Elemento di $ S^{i} $ e questo $ \forall i \in \mathbb{N} $


Misura di Distanza tra Stringhe 

Sappiamo che per trasformare lo Spazio $ S^{\infty} $ in uno Spazio Metrico è necessario dotarlo di una Definizione di Distanza. 

Trattandosi di Stringhe è naturale pensare ad una Distanza tipo Hamming ma bisogna fare attenzione al fatto che si tratta di Stringhe di Lunghezza Infinita e quindi l'utilizzo di una tale misura porterebbe questa a divergere.

Si può quindi ovviare a questo inconventiente introducendo un opportuno Fattore di Peso che smorzi il valore assegnato alle differenze al crescere dell’indice delle lettere della stringa, in modo tale che la Misura così generata converga.


Si può ad esempio utilizzare la Serie Geometrica 
$$ \sum_{i=0}^{n} \frac{1}{2^{i}} = 2 $$


Da essa si può ottenere l’opportuno Fattore di Peso $ 2^{-i} $ con cui pesare la Hamming Distance tra le Lettere nella i-esima Posizione

Quindi in definitiva la Distanza tra 2 Stringhe di Lunghezza Infinita potrebbe essere definita come 
\begin{align}
& d(w^{(1)}, w^{(2)}) = \sum_{i=0}^{n} \frac{\delta \left ( w^{(1)}_{i}, w^{(2)}_{i} \right )}{2^{i}} \nonumber
\end{align}

Con 
\begin{align}
& \delta \left ( w^{(1)}_{i}, w^{(2)}_{i} \right ) = \left\{\begin{matrix}
1 & w^{(1)}_{i} = w^{(2)}_{i}\\
0 & w^{(1)}_{i} \neq w^{(2)}_{i}
\end{matrix}\right.  \nonumber
\end{align}

Nel caso più estremo, ovvero quello in cui ogni lettera fosse diversa, si avrebbe semplicemente la Serie Geometrica iniziale e quindi una Distanza Convergente.

Questo costituisce un Upper Bound sulla Distanza in questione e quindi garantisce che la Distanza converga sempre.


Nessun commento:

Posta un commento