[ Codewars  ]

使用 K-Means 算法解码真实莫尔斯电码

之前在 Codewars 上见到这样一道题:解码真实莫尔斯电码。

用莫尔斯电码来编码一串文字,如 HEY JUDE,结果是 ···· · −·−− ·−−− ··− −·· ·;但它如果被人工编码为高低电平,有可能会是

0000000011011010011100000110000001111110100111110011111100000000000111011111111011111011111000000101100011111100000111110011101100000100000

因为发报员只能根据”相对“长短来控制自己的点按时间,比如遇到 . 就短按,遇到 - 就长按,而且人工发报员不可能做到周期完全稳定,可能有的会稍微长一点,有的稍微短一点。所以这对于解码器如何解码是一个难题。

而 K-Means 算法的出现最早就是为了解决信号处理中的向量量化问题 (vector quantization)。所以这个题目的本意也是让我们用 K-Means 来解决。

K-Means 算法简述

K-Means 是机器学习中的一个常见的聚类算法。通过不断移动每个聚类的中心(均值),并调整每个样本所属的聚类,最终达到稳定。这个算法描述如下:

\begin{algorithm}
\caption{K-Means}
\begin{algorithmic}
\INPUT a training set $T=\{x^{(1)},\dots,x^{(m)}\}$, $K$: the number of clusters
\OUTPUT $C$: $C[i]$ is the cluster of $x^{(i)}$

\STATE Initialize cluster centroids $\mu_1,\mu_2,\dots,\mu_K\in\mathbb{R}^n$ randomly
\REPEAT
	\FORALL{$i\in\{1,\dots,m\}$}
		\STATE $C^{(i)}\gets\argmin_j||x^{(i)}-\mu_j||^2$
	\ENDFOR
	\FORALL{$j\in\{1,\dots,K\}$}
		\STATE $\mu_j\gets\frac{\sum_{i=1}^m\mathbb{I}\{C^{(i)}=j\}x^{(i)}}{\sum_{i=1}^m\mathbb{I}\{C^{(i)}=j\}}$
	\ENDFOR
\UNTIL{$converge$}
\RETURN $C$
\end{algorithmic}
\end{algorithm}	

这里的距离计算是欧式距离$\vert\vert\cdot\vert\vert_2$,也可以用其他距离度量。

实现

我用 Python 实现了这个程序,首先是莫尔斯电码对应码表:

MORSE_CODE = {
    '.-': 'A',
    '-...': 'B',
    '-.-.': 'C',
    '-..': 'D',
    '.': 'E',
    '..-.': 'F',
    '--.': 'G',
    '....': 'H',
    '..': 'I',
    '.---': 'J',
    '-.-': 'K',
    '.-..': 'L',
    '--': 'M',
    '-.': 'N',
    '---': 'O',
    '.--.': 'P',
    '--.-': 'Q',
    '.-.': 'R',
    '...': 'S',
    '-': 'T',
    '..-': 'U',
    '...-': 'V',
    '.--': 'W',
    '-..-': 'X',
    '-.--': 'Y',
    '--..': 'Z',
    '-----': '0',
    '.----': '1',
    '..---': '2',
    '...--': '3',
    '....-': '4',
    '.....': '5',
    '-....': '6',
    '--...': '7',
    '---..': '8',
    '----.': '9',
    '.-.-.-': '.',
    '--..--': ',',
    '..--..': '?',
    '.----.': "'",
    '-.-.--': '!',
    '-..-.': '/',
    '-.--.': '(',
    '-.--.-': ')',
    '.-...': '&',
    '---...': ':',
    '-.-.-.': ';',
    '-...-': '=',
    '.-.-.': '+',
    '-....-': '-',
    '..--.-': '_',
    '.-..-.': '"',
    '...-..-': '$',
    '.--.-.': '@',
    '...---...': 'SOS'
}
MORSE_CODE["_"] = " "

然后是实现 K-Means 的类,这里仅根据问题做了简化,不具有通用性。也可以使用更加通用的 Scikit-Learn 提供的 K-Means 实现,我测试过,在我的程序也可以使用。

class KMeans:
    def __init__(self, n_clusters=5):
        self.n_clusters = n_clusters
        self.cluster_centers_ = []

    def fit_predict(self, X):
        self.labels_ = [None] * len(X)

        # initialize cluster centers
        lb = min(X)
        ub = max(X)
        self.cluster_centers_ = []
        pt = lb
        while pt <= ub:
            self.cluster_centers_.append(pt)
            pt += (ub - lb) / (self.n_clusters - 1)

        all_pts_ok = False
        while not all_pts_ok:
            all_pts_ok = True

            # update cluster/label to each x
            for i, x in enumerate(X):
                last_label = self.labels_[i]
                min_dist = float('inf')
                label = 0
                for idx, center in enumerate(self.cluster_centers_):
                    dist = abs(center - x)
                    if dist < min_dist:
                        min_dist = dist
                        label = idx
                self.labels_[i] = label
                if last_label != label:
                    all_pts_ok = False

            # calculate new centers
            for i in range(self.n_clusters):
                X_in_cluster = []
                for j, x in enumerate(X):
                    if self.labels_[j] == i:
                        X_in_cluster.append(x)
                self.cluster_centers_[i] = sum(X_in_cluster) / len(
                    X_in_cluster)
        return self.labels_

下面的作用是将高低电平转换为 vector 数组,数组中的数字代表这段电平的长度:

def code_to_vector(bits):
    bits = bits.strip('0')
    vector = []
    cur_bit = bits[0]
    cur_len = 1
    for bit in bits[1:]:
        if bit != cur_bit:
            if cur_bit == '1':
                vector.append(int(cur_len))
            else:
                vector.append(-int(cur_len))
            cur_bit = bit
            cur_len = 1
        else:
            cur_len += 1

    if cur_bit == '1':
        vector.append(int(cur_len))
    else:
        vector.append(-int(cur_len))

    return vector

接下来是解码器,目的是将比特位(高低电平)转化为标准莫尔斯电码:

def decodeBitsAdvanced(bits):
    decoded = ''
    vector = code_to_vector(bits)

    # clustering by k-means
    kmeans = KMeans(5)
    classes = kmeans.fit_predict(vector)

    kmeans.indices = []
    sorted_centers = sorted(list(kmeans.cluster_centers_))
    for center in kmeans.cluster_centers_:
        kmeans.indices.append(sorted_centers.index(center))
    # print kmeans.indices
    for c in classes:
        i = kmeans.indices[c]
        if i == 0:
            decoded += '   '
        elif i == 1:
            decoded += ' '
        elif i == 2:
            continue
        elif i == 3:
            decoded += '.'
        else:
            decoded += '-'

    return decoded

最后一步是将标准莫尔斯电码通过查询转化为 ASCII 可读字符串:

def decodeMorse(morseCode):
    return ' '.join(''.join(MORSE_CODE[l] for l in w.split())
                    for w in morseCode.split('   '))

现在测试程序:

if __name__ == "__main__":
    code = '0000000011011010011100000110000001111110100111110011111100000000000111011111111011111011111000000101100011111100000111110011101100000100000'
    print(decodeMorse(decodeBitsAdvanced(code)))

输出结果:

参考