Minimumkan jarak Hamming rentetan binari dengan menetapkan subrentetan yang mengandungi bit K sahaja

Jarak Hamming antara dua rentetan yang sama panjang ialah bilangan semua kedudukan yang terdapat nilai berbeza pada kedudukan yang sepadan. Kita boleh faham melalui contoh berikut:

S= “ramanisgoing”

Terjemahan bahasa Cina ialah:

S= “ramanisgoing”

T=“dishaisgoing”

Di sini, 5 ialah jarak Hamming antara dua rentetan S dan T kerana raman dan disha ialah dua perkataan yang membuat perbezaan dalam rentetan itu sama.

Pernyataan Masalah

Namun, dalam masalah ini, kita perlu mencari jarak Hamming antara dua rentetan yang mengandungi digit binari sahaja. Satu rentetan akan disediakan oleh pengguna, katakan S, dan rentetan lain, katakan T. Pada mulanya, kita menganggap ia mengandungi bit '0' sahaja dan sama dengan saiz rentetan yang diberikan. Kami akan mendapat nombor 'k' yang nilainya mewakili bilangan elemen subrentetan boleh terdiri daripada hanya '1 sebagai elemennya supaya kami meletakkan subrentetan saiz k dalam rentetan(T) Mana-mana kedudukan yang meminimumkan jarak Hamming antara dua subrentetan S dan T.

Mari cuba memahami masalah ini melalui beberapa contoh.

Input − S = "100111" K = 5

Output - 3

Penjelasan − Rentetan awal T adalah sama dengan "000000", dan rentetan T akan ditukar untuk dibandingkan dengan rentetan S untuk mencari jarak Hamming minimum apabila k=5, seperti berikut: "111110" dan " 011111" .

Jarak Hamming antara 100111 dan 000000 ialah 4. Jarak Hamming antara 100111 dan 111110 ialah 3, dan jarak Hamming antara 100111 dan 011111 juga adalah 3.

Tetapi jarak Hamming minimum ialah 3 kerana 3 adalah kurang daripada 4. Oleh itu, jawapan kami ialah 3.

- S = "100101" K = 5

- 3

− Oleh kerana rentetan awal T akan bersamaan dengan "000000", dan rentetan T akan ditukar untuk dibandingkan dengan rentetan S untuk mencari jarak Hamming minimum apabila k=5, seperti berikut: "111110" dan "011111 ".

Jarak Hamming antara 100101 dan 000000 ialah 3. Jarak Hamming antara 100101 dan 111110 ialah 4, dan jarak Hamming antara 100101 dan 011111 juga 4.

Tetapi jarak Hamming minimum ialah 3 kerana 3 adalah kurang daripada 4. Oleh itu, jawapan kami ialah 3.

Penjelasan masalah

Jom cuba fahami masalah ini dan cari jalan penyelesaian.

Penyelesaian 1 Penyelesaian kejam

Kami akan mengubah suai rentetan T dengan menukar kedudukan subrentetan dengan titik awal dan akhir yang berbeza untuk mendapatkan jarak Hamming terkecil antara semua rentetan yang mungkin.

Contoh

Berikut ialah pelaksanaan program C++ bagi kaedah di atas:

#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;
}

Output

The minimum hamming distance is: 3

Pelan Pengoptimuman Penyelesaian 2

Algoritma

• Kira nombor 1 menggunakan tatasusunan jumlah awalan dan simpan sebagai jarak Hamming minimum kami

• Lintas rentetan S untuk mencari nilai antara K subrentetan berbeza dalam rentetan S.

• Jika (i-1<0), kemudian ambil nilai v sebagai arr[i+K-1], jika tidak, ambil nilai v sebagai (arr[i+K-1]-arr[i-1])

• Simpan nilai minimum dengan mencari nilai minimum antara jarak Hamming sebelumnya dan jarak Hamming semasa.

• Jarak Hamming semasa boleh didapati dengan mengendalikan bilangan elemen sifar dalam subrentetan (K - v) dan bilangan sifar dalam subrentetan S semasa

• Akhir sekali, kembalikan jarak minimum keseluruhan.

Contoh

Berikut ialah pelaksanaan program C++ bagi kaedah di atas

#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;
}

Output

The minimum hamming distance is: 3

Kesimpulan

Dalam artikel ini, untuk mencari jarak Hamming minimum kita akan mula-mula melihat kaedah yang mudah tetapi untuk meningkatkan kerumitan masanya kita akan menggunakan konsep awalan dan tatasusunan yang boleh kita elakkan dalam kiraan Ulang gelung.

Atas ialah kandungan terperinci Minimumkan jarak Hamming rentetan binari dengan menetapkan subrentetan yang mengandungi bit K sahaja. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!