漢明距離 Hamming distance

漢明距離（Hamming distance）是指兩個相同長度的序列（sequence）在相同位置上，有多少個數值不同，對二進位序列來說就是「相異位元的數目」。漢明距離同時也是一種編輯距離，即是將一個字串轉換成另一個字串，需要經過多少次置換操作（substitute）。

漢明距離多應用於編碼理論中的錯誤更正（error-correcting），漢明碼（Hammming code）中計算距離的演算法即為漢明距離。

本次實作的程式碼置於

API 文件中。

位元版實作

計算相異位元的數目其實就是一堆位元運算，如下：


#![allow(unused)]
fn main() {
pub fn hamming_distance(source: u64, target: u64) -> u32 {
    let mut count = 0;
    let mut xor = source ^ target; // 1

    // 2
    while xor != 0 {
        count += xor & 1; // 3
        xor >>= 1; // 4
    }

    count as u32
}
}
  1. 透過 XOR 操作，讓兩序列相異位元為 1，相同位元為 0。
  2. 如果 XOR 操作不為零，表示還有相異位元，繼續計算。
  3. 將 XOR 結果和 1 做 AND 運算，看最低有效位（least significant digit）是否為 1。
  4. 將 XOR 做位元右移，捨棄最低有效位，並回到步驟二。

根據 《The Rust Reference》 指出，Rust 的位元右移在

  • 無符號整數（unsigned）是邏輯右移（logical right shift），也就是直接在最高有效位補 0；
  • 有符號整數（signed）則是算術右移（arithmetic right shift），右移之後符號會被保留。

實際上，Rust 提供了一個原生的計算整數有多少個零的方法 {integer_type}::count_ones，可以省去自己做位元運算的麻煩，實作如下，帥：


#![allow(unused)]
fn main() {
pub fn hamming_distance(source: u64, target: u64) -> u32 {
     (source ^ target).count_ones()
}
}

字串版實作

字串版的漢明距離就相對好懂了。


#![allow(unused)]
fn main() {
pub fn hamming_distance_str(source: &str, target: &str) -> usize {
    let mut count = 0;
    // 1
    let mut source = source.chars();
    let mut target = target.chars();

    loop {
        // 2
        match (source.next(), target.next()) {
            // 3
            (Some(c1), Some(c2)) if c1 != c2 => count += 1,
            // 4
            (None, Some(_)) | (Some(_), None) => panic!("Must have the same length"),
            // 5
            (None, None) => break,
            // 6
            _ => continue,
        }
    }

    count
}
}

字串版同樣吃 source 和 target 兩個輸入。

  1. 用 str::chars 讓漢明距離可以比對 Unicode 字串，而非只有 ASCII，而 str::chars 是 Iterator，所以透過 Iterator::next 逐一比較每個字元。
  2. 這裡 if c1 != c2 叫做 match guard，是在模式匹配之外，額外條件式檢查，因此，只有 source 和 target 都有下一個字元而且兩字元不相等才會進入這個匹配分支。
  3. 若有任何一個是 None，另外一個是 Some，標示輸入字串的長度不同，直接噴錯。
  4. 如果都沒有下一個字元，直接結束迴圈。
  5. 其他情況，例如兩個字元相同，就繼續疊代。

效能

長度為 n 的序列，計算漢明距離的時間複雜度為 $O(n)$，空間複雜度為 $O(1)$。

參考資料