from jyquickhelper import add_notebook_menu
add_notebook_menu()
from IPython.display import Image
Image("330px-International_Morse_Code-fr.svg.png")
On se propose de répondre à deux questions :
Cette optimisation est possible puisque l'alphabet Morse transcrit les lettres avec des codes de longueurs différentes. Il faudra aussi vérifier qu'une fois l'alphabet choisi, il n'autorise qu'un seul décodage de la transcription. On suppose qu'on conserve les contraintes du Morse : chaque lettre de l'alphabet est constituée de traits courts et long et qu'il n'y a pas de séparation entre lettres. Vous pouvez vous inspirez de cet article sur la Compression de données ou celui sur le code de Huffman.
On remarque que tous les chiffres sont codés sur cinq caractères alors que les lettres non. Cela vient du fait que toutes les combinaisons de lettres ne sont pas possible. En alphabet morse H=EEE=ooo
mais aucun mot ne contient de séquence EEE
. En pratique 26 + 10 + 1 = 37 et $2^5 < 37 < 2^6$. Cela explique le choix des 5 traits ou points pour les chiffres au maximum. Les tailles sont plus courtes pour les lettres car toutes les combinaisons ne sont pas possibles. On voit aussi que les lettres fréquentes sont des séquences courtes en morse. La séquence ooo-ooo
peut dire EELE
ou STS
.
alphabet = dict(A='o-', B='-ooo', C='-o-o', D='-oo', E='o', F='oo-o', G='--o',
H='oooo', I='oo', J='o---', K='-o-', L='o-oo', M='--', N='-o',
O='---', P='o--o', Q='--o-', R='o-o', S='ooo', T='-', U='oo-',
V='ooo-', W='o--', X='-oo-', Y='-o--', Z='--oo')
alphabet.update({
'0': '-----', '1': 'o----',
'2': 'oo---', '3': 'ooo--',
'4': 'oooo-', '5': 'ooooo',
'6': '-oooo', '7': '--ooo',
'8': '---oo', '9': '----o',
})
def word2morse(word, alpha=None):
"Code un mot en morse"
if alpha is None:
alpha = alphabet
return "".join(alpha[c] for c in word)
word2morse('XAVIER')
'-oo-o-ooo-oooo-o'
word2morse('LISON')
'o-ooooooo----o'
word2morse('EELE'), word2morse('STS')
('ooo-ooo', 'ooo-ooo')
On utilise une expression régulière pour découper en mot tout en sachant qu'on ne sait pas ce que les ambiguïtés pourraient devenir.
exp = "^({})+$".format("|".join("({})".format(v) for v in alphabet.values()))
exp
'^((o-)|(-ooo)|(-o-o)|(-oo)|(o)|(oo-o)|(--o)|(oooo)|(oo)|(o---)|(-o-)|(o-oo)|(--)|(-o)|(---)|(o--o)|(--o-)|(o-o)|(ooo)|(-)|(oo-)|(ooo-)|(o--)|(-oo-)|(-o--)|(--oo)|(-----)|(o----)|(oo---)|(ooo--)|(oooo-)|(ooooo)|(-oooo)|(--ooo)|(---oo)|(----o))+$'
import re
rev_alpha = {v:k for k, v in alphabet.items()}
reg_exp = re.compile(exp)
for el in reg_exp.finditer("-o-o-o-o-o"):
for gr in el.groups():
if gr is None:
continue
print(gr, '->', rev_alpha.get(gr, '?'))
-o -> N -o-o -> C -o -> N
Ce n'est pas hyperprobant. Je me souviens d'avoir lu quelque chose qui parlait des problèmes de répétitions dans les expressions régulières sans pouvoir vraiment m'en souvenir. Alors pour faire simple et pas efficace, j'ai décidé de relancer une recherche après avoir ôté la première trouvée.
dec_exp = '-o-o-o-o-o'
res = []
while len(dec_exp) > 0:
for el in reg_exp.finditer(dec_exp):
for gr in el.groups():
if gr is None:
continue
res.append(gr)
dec_exp = dec_exp[len(gr):]
break
break
res
['-o', '-o-o', '-o-o']
[rev_alpha[r] for r in res]
['N', 'C', 'C']
La fonction de décodage pourrait se suffire des trois dernières lignes, on vérifie qu'elle décode bien les lettres.
def decode_morse(word, reg=None, alpha=None):
if alpha is None:
alpha = alphabet
rev_alpha = {v:k for k, v in alpha.items()}
if reg is None:
exp = "^({})+$".format("|".join("({})".format(v) for v in rev_alpha.keys()))
reg = re.compile(exp)
res = []
while len(word) > 0:
for el in reg_exp.finditer(word):
for gr in el.groups():
if gr is None:
continue
res.append(gr)
word = word[len(gr):]
break
break
return ''.join(rev_alpha.get(g, g) for g in res)
word = "EEEE"
word2morse(word), decode_morse(word2morse(word))
('oooo', 'EEEE')
La fonction gère mal les confusions comme le montre la table suivante.
word = "F"
word2morse(word), decode_morse(word2morse(word))
('oo-o', 'EEN')
for letter in sorted(alphabet)[5:16]:
m = word2morse(letter)
m += " " * (6 - len(m))
print(letter, m, decode_morse(word2morse(letter)))
5 ooooo EEEEE 6 -oooo EEEEE 7 --ooo EB 8 ---oo DEE 9 ----o GN A o- A B -ooo B C -o-o C D -oo D E o E F oo-o EEN
Pour améliorer le décodage, il faudrait améliorer l'expression régulière pour placer les lettres morses les plus longues.
def decode_morse_longer_first(word, reg=None, alpha=None):
if alpha is None:
alpha = alphabet
rev_alpha = {v:k for k, v in alpha.items()}
if reg is None:
keys = [k[1] for k in sorted([(len(k), k) for k in rev_alpha.keys()],
reverse=True)]
exp = "^({})+$".format("|".join("({})".format(v) for v in keys))
reg = re.compile(exp)
res = []
while len(word) > 0:
for el in reg_exp.finditer(word):
for gr in el.groups():
if gr is None:
continue
res.append(gr)
word = word[len(gr):]
break
break
return ''.join(rev_alpha.get(g, g) for g in res)
word = "5"
word2morse(word), decode_morse_longer_first(word2morse(word))
('ooooo', 'EEEEE')
Ca ne marche pas mieux... J'ai la flemme de chercher pourquoi. La solution la plus simple me paraît de simplifier l'expression régulière pour éviter d'avoir des choses comme (aaaa|a)+
mais pluôt a{1,4}
. Ca me paraît plus drôle d'écrire un algorithme qui compresse une liste de patrons en une expression régulière ou de faire mon propre algorithme et de sortir toutes les interprétations possibles.
L'objectif est de sortir toutes les interprétations possibles. oo
peut être I
ou EE
. La version qui suit est loin d'être la plus efficace... La version actuelle n'est pas la plus efficace. On cherche simple à trouver tous les chemins possibles reliant deux noeuds d'un graphe. On peut aussi utiliser des Graph Transformer Network. On peut également voir cela comme un système de complétion (les listes déroulantes de préfix dans les barres de saisie sur Internet). Dans ce second cas, les suggestions serait les lettres morses.
def decompose_morse(word, alpha=None):
if alpha is None:
alpha = alphabet
rev_alpha = {v:k for k, v in alpha.items()}
letters = list(sorted(alpha.values()))
options = [([], 0)]
addition = 1
while addition > 0:
addition = 0
new_options = []
for stack, pos in options:
if pos == len(word):
new_options.append((stack, pos))
else:
prefix = word[pos:]
for w in letters:
if prefix.startswith(w):
path = stack.copy()
path.append(w)
new_options.append((path, pos + len(w)))
addition += 1
options = new_options
unique = set()
for stack, pos in options:
if pos != len(word):
continue
path = tuple(stack)
unique.add(''.join(rev_alpha.get(c, c) for c in path))
return list(sorted(unique))
decompose_morse('oo')
['EE', 'I']
Le code morse laisse plein d'ambiguïtés qu'il faut éliminer à l'aide d'un dictionnaire.
decompose_morse(word2morse('XA'))
['DK', 'DNT', 'DTA', 'DTET', 'NAA', 'NAET', 'NEK', 'NENT', 'NETA', 'NETET', 'NRT', 'TEAA', 'TEAET', 'TEEK', 'TEENT', 'TEETA', 'TEETET', 'TERT', 'TFT', 'TIK', 'TINT', 'TITA', 'TITET', 'TUA', 'TUET', 'XA', 'XET']
Vu l'explosion des possibilités, j'en déduis que les télégraphes devaient marquer une sorte de pause entre les lettres.