Maison > Article > développement back-end > 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.
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.
Essayons de comprendre ce problème et de trouver une solution.
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.
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; }
The minimum hamming distance is: 3
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
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.
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; }
The minimum hamming distance is: 3
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!