我 8 岁的侄女昨天在学校上了摩尔斯电码课，她的作业是将各种短语转换为摩尔斯电码。其中一个短语包括她的年龄，她没有写 ---..，而是写了 3-2. 因为(用她的话说)，“这样写比较少。”这种基本的“压缩算法”激发了我的好奇心，因此我编写了一些代码来实现它。

但是，我们在此过程中进行了一些更改。我向她指出，如果你只写 .......-----，则无法判断作者的意思是否是 50 或 eeeeettttt。实际上，每个单词的每个字母和每个单词之间都有停顿，所以这不是问题，但我们的方案没有。我拿出一些方格纸并建议用另一个符号填充每个符号的摩尔斯电码，以方便编码并消除方案中的歧义。我建议使用 +，因为“没有人会把这些写成句子”。 (哎呀，我最近毕业并获得了数学学位，但还算公平。)

因为我们中的一些人确实用+书写，而且我们都使用连字符和句点/点，这会与我们对摩尔斯电码的标准定义相冲突，所以这些符号是分别替换为 p、h 和 d。当然，这给我们带来了如何处理扩展摩尔斯电码中 undefined symbol 的问题。我的侄女想简单地忽略它们，所以这就是我们所做的。为了对文本消息区分大小写，大写字母在代码中不小写；它们只是按原样进行并用 + 填充。

算法总结:

1. 用 +
向右填充摩尔斯电码至 5 个字符
2. 我们扩展了摩尔斯电码以用 p 代替 +，用 d 代替 . 和 h 为 -。
3. 未在我们的“扩展”摩尔斯电码中定义的符号将原封不动地通过。
4. 除非只出现一个连续的字符，否则符号的运行将被替换，在这种情况下，数字将被省略。

潜在的陷阱:

1. 我的填充方案可能会降低压缩的效率。
2. 使用大于 5 个字符的 block 可能会提高压缩率
3. 如果我的侄女或我对压缩算法有所了解，我们可能会利用它来取得成功。
4. 这显然不适合生产，但由于有许多有效的压缩算法可用于此类目的，我暂时忽略该问题。
5. ???

示例:

在我们的算法中，“Hello, World”转换为

H++++.++++.-..+.-..+---++,+++++++++W++++---++.-.++.-..+-..++

并压缩为

H4+.4+.-2.+.-2.+3-2+,9+W4+3-2+.-.2+.-2.+-2.2+

这是我拼凑的 Python 代码:

#!/usr/bin/python3

import itertools
import string

class MorseString(str):
    def __init__(self, string):
        # or, pad values during iteration but this seems neater
        self._char_morse_map = {"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":"--..+", "1":".----", "2":"..---", \
                                "3":"...--", "4":"....-", "5":".....", "6":"-....", \
                                "7":"--...", "8":"---..", "9":"----.", "0":"-----",
                                " ":"+++++", ".":"d++++", "+":"p++++", "-":"h++++"}
        
        self._morse_char_map = dict()
        for letter, code in self._char_morse_map.items():
            self._morse_char_map[code] = letter

        self._string = string

        # convert the string to "Morse code". Could also use c.lower()
        self._morse_string = "".join([self._char_morse_map.get(c, c.ljust(5, "+")) for c in self._string])

    def compress(self):
        def grouper(n, k):
            return str(n) + k if n > 1 else k

        # could just use lambda
        return "".join([grouper(len(list(g)), k) for k, g in itertools.groupby(self._morse_string)])

    def decompress(self):
        i = 0
        start = 0
        chars = list()
        sc = self.compress()
        while i < len(sc):
            curr = sc[i]
            i += 1
            if not(curr in string.digits):
                num = 1 if start + 1 == i else int(sc[start:i-1])
                chars.append("".join(curr * num))
                start = i

        code = "".join(chars)
        chars = list()

        for i in range(0, len(code), 5):
            piece = "".join(code[i:i+5])
            chars.append(self._morse_char_map.get(piece, piece[0]))
            
        return "".join(chars)


def main():
    s0 = "Hello, World"
    ms0 = MorseString(s0)
    print(ms0._morse_string)
    print(ms0.compress())
    assert(s0 == ms0.decompress())
    
    s1 = "Hello  2 world."
    ms1 = MorseString(s1)
    assert(s1 == ms1.decompress())

    s2 = "The quick brown fox jumped over the lazy dog."
    ms2 = MorseString(s2)
    assert(s2 == ms2.decompress())

    s3 = "abc  -.+"
    ms3 = MorseString(s3)
    ms3
    assert(s3 == ms3.decompress())

if __name__ == "__main__":
    main()

有哪些简单方法可以 a) 改进我们的算法，b) 相对容易向我 8 岁的侄女解释？虽然最后一点显然是主观的，但我还是尽量满足她的好奇心。

我也欢迎对代码进行任何改进，因为它的结构不是很好(我相当确定它的结构很差，实际上，但它又快又脏)，尽管这完全是为了我的利益，因为我还没有得到我的侄女使用 Python (YET)。

更新

这是代码的更新版本，它试图将 user1884905 对算法的修改和 Karl 对代码本身的改进结合起来。

import itertools
import string

_char_morse_map = {"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":"--..", "1":".----", "2":"..---", \
                   "3":"...--", "4":"....-", "5":".....", "6":"-....", \
                   "7":"--...", "8":"---..", "9":"----.", "0":"-----",
                   " ":"", ".":"d", "+":"p", "-":"h"}

_morse_char_map = {
    code: letter
    for letter, code in _char_morse_map.items()
}


def encode(s):
    return "".join(_char_morse_map.get(c, c) + "+" for c in s)

def decode(encoded):
    return "".join(decode_gen(encoded))

def decode_gen(encoded):
    word = ""
    for c in encoded:
        if c != "+":
            word += c
        else:
            yield _morse_char_map.get(word, word) if word != "" else " "
            word = ""

def compress(s):
    def grouper(n, k):
        return str(n) + k if n > 1 else k

    return "".join(grouper(len(list(g)), k) for k, g in itertools.groupby(s))

def decompress(compressed):
    return "".join(decompress_gen(compressed))

def decompress_gen(compressed):
    digits = ""
    for c in compressed:
        if c in string.digits:
            digits += c
        else:
            number = int(digits) if digits else 1
            yield "".join(c * number)
            digits = ""

最佳答案

一个简单的改变可以压缩你的输出(至少在大多数情况下)是保持两个字母之间停顿的想法，并让你的 +-signs 表示这个停顿(即加号用作新字符字符而不是将它们用作填充)。

这将使所有数字 0-9 变长一个字符，但会使相当多的常见字母变短。

例如a、e、i和t会变成.-+、.+、..+ 和 -+ 而不是 .-+++、.++++、..+++ 和 -++++。 (并且 space 可以表示为 + 而不是 +++++)

因此您的Hello, World 示例将变为:

H+.+.-..+.-..+---+,++W+---+.-.+.-..+-..+

代替

H++++.++++.-..+.-..+---++,+++++++++W++++---++.-.++.-..+-..++

并压缩为

H+.+.-2.+.-2.+3-+,2+W+3-+.-.+.-2.+-2.+

代替

H4+.4+.-2.+.-2.+3-2+,9+W4+3-2+.-.2+.-2.+-2.2+

理解了这个推理，霍夫曼编码似乎只是自然而然的下一步，其基本思想是让最常见的字符占用尽可能少的空间。

编辑:

另请参阅 dichotomatic search 的维基百科图片显示最常出现的字符的表格靠近树的顶部。

关于python - 我该如何分析或改进我侄女基于摩尔斯电码的简单压缩算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15673523/