mercredi 23 janvier 2013
Code Morse

Nous allons réaliser un programme simple effectuant la transcription depuis et vers du code Morse.

Le code Morse

Le code Morse est un encodage de caractères alphanumériques utilisant des impulsions sonores courtes et longues. Les impulsions courtes seront représentées par le caractère . (point) et les longues par le caractère _ (trait bas). Les codes de deux lettres d'un mot sont séparées par un espace, et les mots par deux espaces.

Nous souhaitons que notre programme prenne en argument la chaîne à encoder ou décoder, ainsi qu'une option indiquant s'il s'agit de coder ou décoder. Ensuite, nous procéderons comme suit:

  • Pour le codage d'un texte vers du code Morse: Pour chaque caractère, appliquer un mapping vers le code Morse associé. Si ce n'est pas le dernier caractère, on ajoute un espace en plus.
  • Pour le décodage depuis du code Morse: On découpe la chaîne selon les espaces. On applique un mapping de chaque "mot" vers la lettre ou le chiffre correspondant. La chaîne vide (issue de deux espaces consécutifs) est transformée en un espace, séparateur de mot.
Mapping

La première chose à faire est d'implémenter la correspondance entre lettre ou chiffre et code Morse. Pour cela, nous définissons une liste de ces correspondances, qui est une liste de paires (caractère, chaîne):

# let mapping =
  [ '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', "____." ;
  ] ;;
val mapping : (char * string) list =
  [('A', "._"); ('B', "_..."); ('C', "_._."); ('D', "_.."); ('E', ".");
   ('F', ".._."); (...); ...]
Encodage

Pour l'encodage, il nous faut définir une fonction prenant un caractère et retournant la chaîne du code Morse associé.

Une première possibilité serait d'utiliser la fonction List.assoc qui parcourerait le mapping à la recherche de la chaîne associée à un caractère en paramètre. Cependant, ce n'est pas très efficace, car cela nécessite de parcourir souvent une bonne partie de la liste. On pourrait mettre en tête de la liste les caractères les plus utilisés, mais nous préférons utiliser un dictionnaire, grâce au module Map de la bibliothèque standard d'OCaml.

Pour créer notre dictionnaire, nous définissons un module permettant d'utiliser les caractères comme clé de notre dictionnaire. Il doit avoir la signature Map.OrderedType, c'est-à-dire que c'est un module définissant un type t et une fonction de comparaison sur ce type, appelée compare. Nous définissons donc simplement ce module en disant que le type t est le type char et la fonction de comparaison est Pervasives.compare, fonction polymorphe du système permettant la comparaison sur n'importe quelle structure de données:

# module Char_key = struct type t = char let compare = Pervasives.compare end;;
module Char_key : sig type t = char val compare : 'a -> 'a -> int end

Il ne nous reste plus qu'à appliquer le foncteur Map.Make sur notre module définissant le type de la clé pour obtenir un module permettant de manipuler des dictionnaires avec des caractères comme clés:

module Char_map = Map.Make (Char_key);;

Puisque le module Char contient déjà un type t et une fonction compare pour la comparaison de caractères, nous aurions pu également appliquer directement le foncteur sur le module Char sans définir notre module Char_key:

module Char_map = Map.Make(Char);;

L'étape suivante consiste à créer un dictionnaire associant les caractères et leur représentation en code Morse. Pour cela, nous allons itérer sur la liste de correspondances, en remplissant un dictionnaire, du type Char_map.t. Le dictionnaire initial utilisé lors de l'itération est le dictionnaire vide Char_map.empty:

# let map_to_morse = List.fold_left
  (fun map (char, morse_code) -> Char_map.add char morse_code map)
  Char_map.empty mapping;;
val map_to_morse : string Char_map.t = <abstr>

On se référera à la documentation de la fonction List.fold_left si on ne la connaît pas.

Avec ce dictionnaire, nous pouvons maintenant facilement définir une fonction prenant en paramètre un caractère et renvoyant son code Morse ou, si le caractère est invalide, levant l'exception Invalid_argument avec le caractère en question. Nous ajoutons un traitement spécial pour gérer le caractère d'espace, séparateur de mot: dans ce cas, la fonction renvoie une chaîne vide; un espace supplémentaire sera rajouté si ce n'est pas le dernier caractère, ce qui permettra bien d'avoir deux caractères pour séparer les mots (voir plus bas):

# let char_to_morse = function
  ' ' -> ""
| c ->
  try Char_map.find c map_to_morse
  with Not_found ->
     let msg = Printf.sprintf "char_to_morse: invalid character %C" c in
    raise (Invalid_argument msg)
;;
val char_to_morse : Char_map.key -> string = <fun>

Pour encoder un message complet, il nous reste à définir une fonction procédant de la façon suivante:

  • Création d'un buffer pour ajouter des chaînes,
  • Parcours du texte à encoder: pour chaque caractère, on ajoute au buffer le code correspondant, en utilisant notre fonction char_to_morse; on ajoute un espace si ce n'est pas le dernier caractère,
  • On retourne le contenu du buffer.
# let to_morse str =
  let len = String.length str in
  let buf = Buffer.create 256 in
  let on_char i c =
    Buffer.add_string buf (char_to_morse c);
    if i < len - 1 then Buffer.add_char buf ' '
  in
  String.iteri on_char str;
  Buffer.contents buf
;;
val to_morse : string -> string = <fun>
# (* Pour tester *)
let morse_formation_ocaml = to_morse "FORMATION OCAML";;
val morse_formation_ocaml : string =
  ".._. ___ ._. __ ._ _ .. ___ _.  ___ _._. ._ __ ._.."
Décodage

Pour le décodage, nous définissons également un dictionnaire à partir de la liste de correspondances. Cette fois la clé est une chaîne (le code Morse). A titre d'exemple, nous utilisons un module anonyme pour créer notre module de dictionnaire:

module Str_map =
  Map.Make (struct type t = string let compare = Pervasives.compare end);;
# let map_from_morse = List.fold_left
  (fun map (char, morse) -> Str_map.add morse char map)
  Str_map.empty mapping ;;
val map_from_morse : char Str_map.t = <abstr>

La fonction de décodage d'une chaîne ressemble à celle d'encodage:

# let char_from_morse = function
  "" -> ' '
| str ->
   try Str_map.find str map_from_morse
   with Not_found ->
     let msg = Printf.sprintf "char_from_morse: invalid Morse code %S" str in
     raise (Invalid_argument msg)
;;
val char_from_morse : Str_map.key -> char = <fun>

Pour itérer sur les codes Morse d'une chaîne, nous devons d'abord découper cette chaîne en codes, en utilisant l'espace comme séparateur. Pour cela, nous définissons une fonction découpant une chaîne en mots, et gardant les mots vides quand il y a deux espaces. Cela nous permettra de savoir quand insérer un espace supplémentaire pour séparer des mots dans la chaîne décodée:

# let split_string s =
  let len = String.length s in
  let rec iter acc pos =
    if pos >= len then
      match acc with
        "" -> []
      | _ -> [acc]
    else
      match s.[pos] with
       ' ' -> acc :: (iter "" (pos + 1))
      | c -> iter (Printf.sprintf "%s%c" acc c) (pos + 1)
  in
  iter "" 0
;;
val split_string : string -> string list = <fun>
# (* pour tester *)
split_string "maître corbeau sur un arbre  perché";;
- : string list =
["ma\195\174tre"; "corbeau"; "sur"; "un"; "arbre"; ""; "perch\195\169"]

Il ne nous reste plus qu'à définir la fonction décodant un texte en Morse:

# let from_morse str =
  let words = split_string str in
  let buf = Buffer.create 256 in
  let on_word i str = Buffer.add_char buf (char_from_morse str) in
  List.iteri on_word words;
  Buffer.contents buf
;;
val from_morse : string -> string = <fun>
# (* Pour test *)
from_morse morse_formation_ocaml;;
- : string = "FORMATION OCAML"
Le programme

Pour terminer notre programme, il ne nous reste qu'à implémenter la gestion de la ligne de commande: une option -d pour demander le décodage au lieu du codage, et concaténer les autres chaînes passées en paramètre. On pourra se référer à la documentation du module Arg.

# let main () =
  let decode = ref false in
  let options = [ "-d", Arg.Set decode, " decode Morse code" ] in
  let args = ref [] in
  Arg.parse options
    (fun arg -> args := arg :: !args)
    (Printf.sprintf "Usage: %s [-d] <text|Morse>" Sys.argv.(0));
  let text = String.concat " " (List.rev !args) in
  let result = (if !decode then from_morse else to_morse) text in
  print_endline result
;;
val main : unit -> unit = <fun>
try main ()
with Invalid_argument msg ->
  prerr_endline msg;
  exit 1
;;

Si notre code se trouve dans le fichier code_morse.ml, nous pourons le compiler avec la commande suivante:

$ ocamlopt -o code_morse code_morse.ml

Et nous pouvons tester le résultat:

$ ./code_morse --help
Usage: ./code_morse [-d] <text|Morse>
  -d  decode morse code
  -help  Display this list of options
  --help  Display this list of options
$ ./code_morse "C EST LA FORMATION OCAML"
_._.  . ... _  ._.. ._  .._. ___ ._. __ ._ _ .. ___ _.  ___ _._. ._ __ ._..
$ ./code_morse -d "_._.  . ... _  ._.. ._  .._. ___ ._. __ ._ _ .. ___ _.  ___ _._. ._ __ ._.."
C EST LA FORMATION OCAML
$ ./code_morse "erreur ce sont des minuscules"
char_to_morse: invalid character 'e'
$ ./code_morse -d "____...___" # code inconnu
char_from_morse: invalid Morse code "____...___"