私の 8 歳の姪は、昨日学校でモールス信号のレッスンを受けました。彼女の課題は、さまざまなフレーズをモールス信号に変換することでした。フレーズの 1 つに彼女の年齢が含まれていまし---..た3-2.。この初歩的な「圧縮アルゴリズム」が私の好奇心をかき立てたので、それを実装するためのコードを少し書きました。
ただし、途中でいくつかの変更を加えました。私は彼女に、あなたが単に と書いた場合、その書き手が を意図していたのか、それとも.....-----を意図していたのかを判断する方法はないことを指摘しました。実際には、各単語の各文字とすべての単語の間に一時停止があるため、これは問題にはなりませんが、私たちのスキームにはそれがありませんでした。私は方眼紙をいくつか取り出し、コーディングを容易にし、スキームからあいまいさを取り除くために、各シンボルのモールス符号を別のシンボルでパディングすることを提案しました。私のいい人は、「誰もそれらを文章で書いたことがない」ので、使用を提案しました。（ああ、私は最近数学の学位を取得して卒業しましたが、十分公平です。）50eeeeettttt+
私たちの何人かはで書き、+全員がハイフンとピリオド/ドットを使用していますが、これはモールス信号の標準的な定義と矛盾するため、これらの記号はそれぞれp、h、 に置き換えられdます。もちろん、これにより、拡張モールス信号で定義されていない記号をどうするかという問題が生じます。私の姪は単にそれらを無視したかったので、それが私たちがしたことです。テキストメッセージの大文字と小文字を区別して保存するために、大文字はコード内で小文字になりません。それらはそのまま実行され、 で埋められ+ます。
アルゴリズムの要約:
- モールス信号は、右に 5 文字までパディングされます。
+ - モールス信号を拡張して、 、 、を置き換え
pました。+d.h- - 「拡張」モールス符号で定義されていない記号は、そのまま渡されます。
- 連続する文字が 1 つしかない場合は、数字が省略されます。
潜在的な落とし穴:
- 私のパディングスキームは、おそらく圧縮の有効性を低下させます。
- 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 (まだ) を使用します。
アップデート
これは、アルゴリズムに対する 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 = ""
