Strona zawiera kody zrodlowe funkcji obliczajacych dopasowanie ciagow binarnych.
Funkcje te, zostaly zbadane w pracy magisterskiej autorstwa Michala Jankowiaka, pt "Analiza wlasciwosci miar dopasowania w zastosowaniu do sztucznego systemu immunologicnego, bazujacego na modelu sieci idiotypowej"
Prace zlozono 20-go wrzesnia 2004 roku.


Analizowane miary:

Miara FPP

Odleglosc Hamminga

Zasada ciagu r-bitow

Zasada wielu pod-ciagow bitow

Miara Rogersa i Tanimoto

Dodatkowo, zamieszczono wzor miary zaproponowanej przez autora. Miara ta, jest w trakcie badania - wzor ma charakter jedynie informacyjny


W rozdziale czwartym dokonano porownania miar dopasowania ciagow binarnych. W pracy nie jest jawnie powiedziane, dla jakiej wartosci progowej w przypadku miary FPP, zostaly przeprowadzone testy. Wartosc tego progu (s) byla rowna 2.


Parametrami funkcji sa dwa ciagi binarne. Funkcje zwracaja wartosc dopasowania przekazanych im ciagow.

#define tope_length 8
#define s 2

 

int Compute_FPP(string Ab1, string Ab2)

{

      int sum=0, sub_sum=0;

      unsigned int a=0;

      unsigned int b=0;

 

      // Compute matching

      for(int k=-(tope_length-s); k<=(tope_length-s); k++)

      {

            if(k<0)

            {

                  for(int n=abs(k); n<tope_length; n++)

                  {

                        char aa[2];

                        aa[0] = Ab2.at(n+k);

                        aa[1] = NULL;

                        char bb[2];

                        bb[0] = Ab1.at(n);

                        bb[1] = NULL;

                        sub_sum += abs(atoi(aa)-atoi(bb));

                  }

            }

            else

            {

                  for(int n=0; n<(tope_length-k); n++)

                  {

                        char aa[2];

                        aa[0] = Ab2.at(n+k);

                        aa[1] = NULL;

                        char bb[2];

                        bb[0] = Ab1.at(n);

                        bb[1] = NULL;

                        sub_sum += abs(atoi(aa)-atoi(bb));

                  }

            }

            sub_sum -= s;

            sub_sum++;

     

            if(sub_sum>0)

            {

                  sum += sub_sum;

            }

            sub_sum = 0;

           

      }

 

return sum;

}

 

int Compute_Hamming(string Ab1, string Ab2)

{

      int sum=0;

 

      for(int k=0; k<tope_length; k++)

      {

            if(Ab1[k]!=Ab2[k])

            {

                  sum++;

            }

      }

 

      return sum;

}

 

 

int Compute_r_bites_rule(string Ab1, string Ab2)

{

      int sum=0, max_sum=0;

      unsigned int a=0;

 

 

      for(int k=0; k<tope_length; k++)

      {

            if(Ab1[k]!=Ab2[k])

            {

                  sum++;

                 

                  if(sum>max_sum)

                  {

                        max_sum=sum;

                  }

            }

            else

            {

                  sum = 0;

            }

      }

 

return sum;

}

 

int Compute_multiple_r_bites_rule(string Ab1, string Ab2)

{

      int Hamming_sum = 0, sum=0, Total_sum = 0;

      unsigned int a=0;

 

 

      for(int k=0; k<tope_length; k++)

      {

            if(Ab1[k]!=Ab2[k])

            {

                  Hamming_sum++;

                  sum++;

            }

            else

            {

                  if(sum>=2)

                  {

                        Total_sum += (int)pow(2, sum);

                  }

                  sum = 0;

            }

      }

      return Total_sum+Hamming_sum;

}

 

 

double Compute_Rogers_Tanimoto(string Ab1, string Ab2)

{

      int a=0;

      int b=0;

      int c=0;

      int d=0;

 

      for(int k=0; k<tope_length; k++)

      {

            if((Ab1[k])=='1'&&(Ab2[k])=='1')

            {

                  a++;

            }

            else if((Ab1[k])=='1'&&((Ab2[k])=='0'))

            {

                  b++;

            }

            else if((Ab1[k])=='0'&&((Ab2[k])=='1'))

            {

                  c++;

            }

            else if((Ab1[k])=='0'&&((Ab2[k])=='0'))

            {

                  d++;

            }

      }

     

return ((a+d)/(a+d+2*(b+c)));

 

}

 

 

Pomysl na nowa miare MJ:
Porownywany ciag bitow, traktuje sie jako osobnika w cztero-wymiarowej przestrzeni.
Zakladamy, ze osobnik jest dlugosci osmiu bitow. Kazda, kolejna pare bitow, traktujemy jako kolejna wspolrzedna w przestrzeni.
Dziesietne wartosci tak przetransformowanych wspolrzednych (moga one przyjmowac trzy wartosci: 0, 1 i 2), podstawiamy do rownania: