Minimisez la distance de Hamming d'une chaîne binaire en définissant une sous-chaîne contenant uniquement K bits

La distance de Hamming entre deux cordes de même longueur est le nombre de toutes les positions où il y a des valeurs différentes aux positions correspondantes. On peut comprendre à travers l'exemple suivant :

S= « ramanisgoing »

La traduction chinoise est :

S= « ramanisgoing »

T="dishaisgoing"

Ici, 5 est la distance de Hamming entre deux chaînes S et T car raman et Disha sont deux mots qui rendent la différence entre les chaînes égale.

Énoncé du problème

Cependant, dans ce problème, nous devons trouver la distance de Hamming entre deux chaînes contenant uniquement des chiffres binaires. Une chaîne sera fournie par l'utilisateur, disons S, et une autre chaîne, disons T. Initialement, nous supposons qu'elle ne contient que des bits « 0 » et qu'elle est égale à la taille de la chaîne donnée. Nous obtiendrons un nombre 'k' dont la valeur représente le nombre d'éléments qu'une sous-chaîne ne peut contenir que des '1' comme éléments afin que nous placions cette sous-chaîne de taille k dans la chaîne (T) Toute position qui minimise la distance de Hamming entre deux sous-chaînes S et T.

Essayons de comprendre ce problème à travers quelques exemples.

Entrée − S = "100111" K = 5

Sortie - 3

Explication − La chaîne initiale T est égale à "000000", et la chaîne T sera modifiée pour comparer avec la chaîne S pour trouver la distance minimale de Hamming lorsque k=5, comme suit : "111110" et " 011111" .

La distance de Hamming entre 100111 et 000000 est de 4. La distance de Hamming entre 100111 et 111110 est de 3, et la distance de Hamming entre 100111 et 011111 est également de 3.

Mais la distance minimale de Hamming sera de 3 car 3 est inférieur à 4. Notre réponse est donc 3.

- S = "100101" K = 5

- 3

− Comme la chaîne initiale T sera égale à "000000", et la chaîne T sera modifiée pour comparer avec la chaîne S pour trouver la distance minimale de Hamming lorsque k=5, comme suit : "111110" et "011111". ".

La distance de Hamming entre 100101 et 000000 est de 3. La distance de Hamming entre 100101 et 111110 est de 4, et la distance de Hamming entre 100101 et 011111 est également de 4.

Mais la distance minimale de Hamming sera de 3 car 3 est inférieur à 4. Notre réponse est donc 3.

Explication du problème

Essayons de comprendre ce problème et de trouver une solution.

Solution 1 Solution brutale

Nous modifierons la chaîne T en changeant les positions des sous-chaînes avec différents points initial et final afin d'obtenir la plus petite distance de Hamming parmi toutes les chaînes possibles.

Exemple

Ce qui suit est l'implémentation du programme C++ de la méthode ci-dessus :

#include <bits/stdc++.h>
using namespace std;
// Make a function to get minimum hamming distance through iteration
int helper(string S,int k){
   // n is the size of the string
   int n=S.size();
   // Take another string T and initiate it with zero bits size equal to that of S
   string T;
   for(int i=0;i<n;i++){
      T+="0";
   }
   // Take another string v to initiate it same as T
   string v=T;
   // Define mini as the hamming distance between T and S
   int mini=0;
   int l=0; 
   while(l<n){
      if(S[l]!=T[l])mini++;
         l++;
   }
   for(int i=0;i<n-k+1;i++){
      int j=0,a=0,l=0;
      // alter string v by changing bits of size k
      while(j<k){
          v[j+i]='1';
          j++;
      }
      // calculate hamming distance
      while(l<n){
         if(S[l]!=v[l])a++;
           l++;
      }
      // Check if the previous hamming distance is greater than the current hamming distance, if yes then replace that distance element
      if(mini>a){
         mini=a;
      }
      // Again assign v as the T string
      v=T;
    }
    // return the minimum hamming distance found through the above iterations
    return mini;
}
int main() {
   // Give input string S
   string S = "100101";
   // Give the value of k that is the substring size
   int K = 5;
   // Call the helper function
   cout << "The minimum hamming distance is: "<< helper(S,K);
   return 0;
}

Sortie

The minimum hamming distance is: 3

Solution 2 Plan d'optimisation

Algorithme

• Calculez le nombre de 1 à l'aide du tableau de somme de préfixes et stockez-le comme distance de Hamming minimale

• Parcourez la chaîne S pour trouver les valeurs entre K différentes sous-chaînes dans la chaîne S.

• Si (i-1<0), alors prenez la valeur v comme arr[i+K-1], sinon prenez la valeur v comme (arr[i+K-1]-arr[i-1])

• Stockez la valeur minimale en trouvant la valeur minimale entre la distance de Hamming précédente et la distance de Hamming actuelle.

• La distance de Hamming actuelle peut être trouvée en opérant sur le nombre d'éléments nuls dans la sous-chaîne (K - v) et le nombre de zéros dans la sous-chaîne S actuelle

• Enfin, renvoyez la distance minimale globale.

Exemple

Ce qui suit est l'implémentation du programme C++ de la méthode ci-dessus

#include <bits/stdc++.h>
using namespace std;
// Make a helper function to get minimum hamming distance through iteration
int helper(string S, int K){
 // n is the size of the string
	int n = S.size();
	// initialize an array of size 'n'
	int arr[n];
	if(S[0]=='0')arr[0]=0;
	else arr[0]=1;
	// Count the number of 1's in the string S
	for (int i = 1; i < n; i++){
	    if(S[i]=='0')arr[i]=arr[i-1];
	    else arr[i]=arr[i-1]+1;
	}
	int cnt = arr[n - 1];	
	// Define mini as the hamming distance between T and S
	int mini = cnt;
	// Traverse through S to find the minimum
	for (int i = 0; i < n - K; i++) {
		int v;
		if(i-1==-1)v=arr[i+K-1];
		else v= arr[i+K-1]-arr[i-1];
		// Store the minimum
		mini = min(mini, cnt - v + (K - v));
	}
    // Return the minimum hamming distance
	return mini;
}
int main(){
	// Give input string S
    string S = "100101";
    // Give the value of k that is the substring size
    int K = 5;
    // Call the helper function
    cout << "The minimum hamming distance is: "<< helper(S,K);
    return 0;
}

Sortie

The minimum hamming distance is: 3

Conclusion

Dans cet article, pour trouver la distance minimale de Hamming nous verrons d'abord une méthode simple mais pour améliorer sa complexité temporelle nous utiliserons le concept de préfixe et de tableau grâce auquel nous pouvons éviter dans une boucle le nombre de répétitions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!