How to resolve the algorithm LZW compression step by step in the Ol programming language

Published on 12 May 2024 09:40 PM
#Ol

How to resolve the algorithm LZW compression step by step in the Ol programming language

Table of Contents

Problem Statement

The Lempel-Ziv-Welch (LZW) algorithm provides loss-less data compression. You can read a complete description of it in the   Wikipedia article   on the subject.   It was patented, but it entered the public domain in 2004.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm LZW compression step by step in the Ol programming language

Source code in the ol programming language

(define (compress str)
(let loop ((dc (fold (lambda (f x) ; dictionary (simplest, not optimized), with reversed codes
                        (cons (list x) (cons x f)))
                  '() (iota 256)))
           (w '()) ; output sequence (reversed)
           (s 256) ; maximal dictionary code value + 1
           (x '()) ; current sequence
           (r (str-iter str))); input stream
   (cond
      ((null? r)
         (reverse (cons (cadr (member x dc)) w)))
      ((pair? r)
         (let ((xy (cons (car r) x)))
            (if (member xy dc)
               (loop dc w s xy (cdr r))
               (loop (cons xy (cons s dc))         ; update dictionary with xy . s
                     (cons (cadr (member x dc)) w) ; add code to output stream
                     (+ s 1) ; increase code
                     (list (car r)) ; new current sequence
                     (cdr r))))) ; next input
      (else
         (loop dc w s x (r)))))
)

(print (compress "TOBEORNOTTOBEORTOBEORNOT")) ; => (84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)


(define (decompress str)
(let loop ((dc (fold (lambda (f x) ; dictionary (simplest, not optimized), with reversed codes
                        (cons x (cons (list x) f)))
                  '() (iota 256)))
           (w '()) ; output sequence (reversed)
           (s 256) ; maximal dictionary code value + 1
           (x '()) ; current symbols sequence
           (r (str-iter str))); input stream
   (cond
      ((null? r)
         (reverse w))
      ((pair? r)
         (let*((y (cadr (member (car r) dc)))
               (xy (append y x)))
            (if (member xy dc)
               (loop dc (append y w) s xy (cdr r)) ; вряд ли такое будет...
               (loop (cons s (cons xy dc))          ; update dictionary with xy . s
                     (append y w) ; add phrase to output stream
                     (+ s 1)
                     y ; new initial code
                     (cdr r))))) ; next input
      (else
         (loop dc w s x (r))))))

(print (runes->string
   (decompress (runes->string '(84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)))))
; => TOBEORNOTTOBEORTOBEEORNOT


  

You may also check:How to resolve the algorithm Compare a list of strings step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Roots of a function step by step in the Arturo programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the Raku programming language
You may also check:How to resolve the algorithm Tau number step by step in the PL/M programming language
You may also check:How to resolve the algorithm Pi step by step in the FreeBASIC programming language