[ocaml] LZW-simple

Viewer

copydownloadembedprintName: LZW-simple
  1.  
  2. let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  3.  
  4. (**
  5.   LZW encode : string -> int list
  6. *)
  7. let encode s =
  8.   let dict = Hashtbl.create (String.length alphabet) in
  9.   let add_to_dictionary w = Hashtbl.add dict w (Hashtbl.length dict + 1) in
  10.   let is_in_dictionary = Hashtbl.mem dict in
  11.   let input = ref "" in
  12.   let output = ref [] in
  13.   let emit_index_of w = output := Hashtbl.find dict w :: !output in
  14.  
  15.   alphabet |> String.iter (fun c -> c |> String.make 1 |> add_to_dictionary) ;
  16.  
  17.   for i = 0 to String.length s - 1 do
  18.     let c = String.sub s i 1 in
  19.     let w = !input in
  20.     let wc = w ^ c in
  21.     if wc |> is_in_dictionary then
  22.       input := wc
  23.     else begin
  24.       emit_index_of w ;
  25.       input := c ;
  26.       add_to_dictionary wc
  27.     end
  28.   done ;
  29.   emit_index_of !input ;
  30.  
  31.   List.rev !output
  32.  
  33. (**
  34.   LZW decode : int list -> string
  35. *)
  36. let decode codes =
  37.   match codes with
  38.   | [] -> ""
  39.   | first_code :: rest_codes ->
  40.     let dict = Hashtbl.create (String.length alphabet) in
  41.     let add_to_dictionary w = Hashtbl.add dict (Hashtbl.length dict + 1) w in
  42.     let word_for = Hashtbl.find_opt dict in
  43.     let first_symbol_of s = String.sub s 0 1 in
  44.  
  45.     alphabet |> String.iter (fun c -> c |> String.make 1 |> add_to_dictionary) ;
  46.  
  47.     let first = (match word_for first_code with Some w -> w | None -> failwith "invalid input") in
  48.     let output = ref first in
  49.     let previous = ref first in
  50.     let emit w = output := !output ^ w ; previous := w in
  51.  
  52.     rest_codes |> List.iter (fun code ->
  53.       match word_for code with
  54.       | Some w ->
  55.         let v = !previous ^ first_symbol_of w in
  56.         add_to_dictionary v ;
  57.         emit w
  58.       | None ->
  59.         let v = !previous ^ first_symbol_of !previous in
  60.         add_to_dictionary v ;
  61.         emit v
  62.     );
  63.  
  64.   !output
  65.  
  66. (* ---------------------------------------------------------------- *)
  67.  
  68. let test_phrase = "TOBEORNOTTOBEORTOBEORNOT"
  69.  
  70. let _ =
  71.   print_endline test_phrase ;
  72.   let encoded = encode test_phrase in
  73.   List.iter (Printf.printf "%d ") encoded ; print_endline "" ;
  74.   let decoded = decode encoded in
  75.   print_endline decoded
  76.  

Editor

You can edit this paste and save as new:


File Description
  • LZW-simple
  • Paste Code
  • 28 Jul-2022
  • 2.11 Kb
You can Share it: