Concetti di Base
Consideriamo un Sistema Dinamica Astratto come un Sistema Dinamico che elabora stringhe di varia lunghezzaAnzitutto 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} $
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
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
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}
& 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.
& \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