LZW compression: Difference between revisions

=={{header|11l}}==

{{trans|Python}}

V dict_size = 256

V dictionary = Dict((0 .< dict_size).map(i -> (String(Char(code' i)), i)))

V compressed = compress(‘TOBEORNOTTOBEORTOBEORNOT’)

print(compressed)

=={{header|Ada}}==

lzw.ads:

MAX_CODE : constant := 4095;

function Decompress (Data : in Compressed_Data) return String;

lzw.adb:

with Ada.Strings.Unbounded;

end Decompress;

test.adb:

with Ada.Text_IO;

Text_IO.Put_Line (Cleartext);

end;

=={{header|Arturo}}==

dict: #[]

loop 0..255 'i -> dict\[to :char i]: i

decompressed: decompress compressed

print "Decompressed:"

{{out}}

=={{header|BaCon}}==

PRINT "LZWData: ", lzw_data$

RETURN result$

{{out}}

<pre>LZWData: TOBEORNOTTOBEORTOBEORNOT

{{works with|BBC BASIC for Windows}}

Uses fixed bit-width (16 bits) and initial dictionary size = 256.

encodeLZW$ = FNencodeLZW(plaintext$)

FOR i% = 1 TO LEN(encodeLZW$) STEP 2

w$ = t$

NEXT

{{out}}

<pre>

'''WARNING: This code appears to have come from a GIF codec that has been modified to meet the requirements of this page, provided that the decoder works with the encoder to produce correct output. For writing GIF files the write_bits subroutine is wrong for Little Endian systems (it may be wrong for Big Endian as well.) The encoder also increases the number of bits in the variable length GIF-LZW after the N-2 code, whereas this must be done after N-1 to produce a working GIF file (just looking at the encoder, it's easy to see how this mistake could be made.)'''

#include <stdlib.h>

#include <string.h>

return 0;

=={{header|C sharp}}==

{{trans|Java}}

using System.Collections.Generic;

using System.Text;

}

}

{{out}}

=={{header|C++}}==

{{trans|D}}

#include <map>

return 0;

=={{header|Clojure}}==

(let [vals (range 0 256)]

(zipmap (map (comp #'list #'char) vals) vals)))

(reverse (if w (cons (get dict w) r) r))))))

{{out}}

=={{header|CoffeeScript}}==

This only does the encoding step for now.

lzw = (s) ->

dct = {} # map substrings to codes between 256 and 4096

console.log lzw "TOBEORNOTTOBEORTOBEORNOT"

{{out}}

<pre>

The exact encoding used is dependent upon the user's locale (<code>LC_CTYPE</code> on Unix).

vector-append))

(defun vector-append (old new &optional (start2 0) end2)

(assert (equal #2=(lzw-decompress-to-string (lzw-compress string)) string) ()

"Can't compress ~S properly, got ~S instead" string #2#)

And the format used:

T

CL-USER> (lzw-compress "TOBEORNOTTOBEORTOBEORNOT")

#(84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)

CL-USER> (lzw-decompress-to-string *)

=={{header|D}}==

===Simpler Version===

auto compress(in string original) pure nothrow {

auto comp = "TOBEORNOTTOBEORTOBEORNOT".compress;

writeln(comp, "\n", comp.decompress);

{{out}}

<pre>[84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]

===More Refined Version===

This longer version is a little more efficient and it uses stronger static typing.

import std.array: empty;

compressed.writeln;

LZW.decompress(compressed).assumeUTF.writeln;

{{out}}

<pre>[84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]

{{trans|C}}

This code retains part of the style of the original C code.

CLR = 256, // Clear table marker.

EOD = 257, // End-of-data marker.

"Decoded OK.".writeln;

{{out}}

<pre>Input size: 206403

=={{header|Dylan}}==

Synopsis: LZW implementation for Rosetta code

end;

=={{header|Eiffel}}==

class

APPLICATION

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

@encode_map Enum.into(0..255, Map.new, &{[&1],&1})

@decode_map Enum.into(0..255, Map.new, &{&1,[&1]})

IO.inspect enc = LZW.encode(str)

IO.inspect dec = LZW.decode(enc)

{{out}}

=={{header|Erlang}}==

-export([test/0, encode/1, decode/1]).

init1(0, D) -> D;

=={{header|Forth}}==

{{works with|GNU Forth|0.6.2}}

\ current string fragment

out out-size @ decompress cr

=={{header|Fortran}}==

!

! lzw_shared_parameters.f90

CALL CPU_TIME(finish)

PRINT '("Time = ",f6.3," seconds.")' , finish - start

=={{header|FreeBASIC}}==

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> input str: TOBEORNOTTOBEORTOBEORNOT

not just ASCII or valid UTF8 encoding

(tested with [https://github.com/dvyukov/go-fuzz go-fuzz]).

import (

}

fmt.Println(decompressed)

{{out}}

<pre>

=={{header|Groovy}}==

def dictionary = (0..<256).inject([:]) { map, ch -> map."${(char)ch}" = ch; map }

def w = '', compressed = []

result.toString()

Testing:

def compressed = compress(plaintext)

def result = decompress(compressed)

Plaintext: '$plaintext'

Compressed: $compressed

{{out}}

<pre>Plaintext: 'TOBEORNOTTOBEORTOBEORNOT'

=={{header|Haskell}}==

import Data.Maybe (fromJust)

print $

((==) <*> ((.) <$> undoLZW <*> doLZW) ['\NUL' .. '\255'])

{{Out}}

<pre>[84,79,66,69,79,82,78,79,84,256,258,260,265,259,261,263]

Straightforward implementations of encoding and decoding:

d=. ;/x

r=.0$0

end.

r, d i.<w

Test:

<pre> a. encodeLZW 'TOBEORNOTTOBEORTOBEORNOT'

84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263</pre>

Decoding:

d=.;/x

w=.r=. >d{~{.y

end.

;r

Test:

<pre> a. decodeLZW 84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263

=={{header|Java}}==

{{works with|Java|1.5+}}

public class LZW {

System.out.println(decompressed);

}

{{out}} (Command Line direct output):

=={{header|JavaScript}}==

var LZW = {

compress: function (uncompressed) {

comp = LZW.compress("TOBEORNOTTOBEORTOBEORNOT"),

decomp = LZW.decompress(comp);

This is the the same thing, but for ES6. The code has been refactored and cleaned up a bit to look neater.

/**

Namespace for LZW compression and decompression.

console.log(`${comp}

{{out}}

{{ works with|jq|1.4}}

{{trans|JavaScript}}

def lzw_compress:

def decode: [.] | implode;

| .[2] = $entry # w = entry

) | .[3]

'''Example''':

{{Out}}

$ jq -n -f LZW.jq

=={{header|Julia}}==

{{works with|Julia|1.1.1}}

dictsize = 256

dict = Dict{String,Int}(string(Char(i)) => i for i in 0:dictsize)

comprate = (length(word) - length(comp)) / length(word) * 100

println("Original: $word\n-> Compressed: $comp (compr.rate: $(round(comprate, digits=2))%)\n-> Decompressed: $decomp")

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

object Lzw {

val decompressed = Lzw.decompress(compressed)

println(decompressed)

{{out}}

It also has the option to write the encoding/decoding dictionaries to file so the encoder can be checked for accuracy.

This code directly follows the methodology described in an excellent web article by Juha Nieminen entitled "An efficient LZW implementation".

DIM JDlzw(1)

DIM JDch$(1)

fileTag$ = STR$(tagCount) + "_"

RETURN

=={{header|Lua}}==

local dictionary, result, dictSize, w, c = {}, {}, 255, ""

for i = 0, 255 do

local dec = decompress(com)

print(table.concat(com, ", "))

{{Out}}

=={{header|M2000 Interpreter}}==

{{trans|BBC BASIC}}

Module BBCtrans {

\\ LZW compression

}

BBCtrans

And here a change for using Inventories, where we have hash function, and we find entry in O(1).

Module FastM2000 {

plaintext$="TOBEORNOTTOBEORTOBEORNOT"

}

FastM2000

{{out}}

<pre >

=={{header|Mathematica}}/{{header|Wolfram Language}}==

{{trans|Ruby}}

Module[{dictsize, dictionary, w, result, wc},

dictsize = 256;

(*How to use:*)

compress["TOBEORNOTTOBEORTOBEORNOT"]

{{Out}}

<pre>{"T", "O", "B", "E", "O", "R", "N", "O", "T", 256, 258, 260, 265, 259, 261, 263}

=={{header|Nim}}==

proc compress*(uncompressed: string): seq[int] =

echo compressed

var decompressed = decompress(compressed)

{{out}}

=={{header|Objeck}}==

{{trans|Java}}

class LZW {

"]"->PrintLine();

}

<pre>[84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]

The class for the LZW compression algorithm:

#import <stdio.h>

}

Usage example:

int main()

}

return EXIT_SUCCESS;

{{out}} (reformatted by hand):

=={{header|OCaml}}==

#load "extLib.cma"

open ExtString

in

(List.rev result)

here is the interface:

How to use:<br />

So to know how many bits are required, you need to know how many bits are required for the greatest symbol in the list.

(** number of bits needed to encode the integer m *)

List.iter (Buffer.add_string buf) result;

(Buffer.contents buf)

=={{header|Ol}}==

This version use lazy streams which is pair (symbol . function-to-get-next-symbol).

(define (compress str)

(let loop ((dc (fold (lambda (f x) ; dictionary (simplest, not optimized), with reversed codes

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

And decoder (runes->string used to unify functions - both used string iterators):

(define (decompress str)

(let loop ((dc (fold (lambda (f x) ; dictionary (simplest, not optimized), with reversed codes

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

; => TOBEORNOTTOBEORTOBEEORNOT

=={{header|Perl}}==

In this version the hashes contain mixed typed data:

sub compress {

my $uncompressed = shift;

print "@compressed\n";

my $decompressed = decompress(@compressed);

{{out}}

=={{header|Phix}}==

{{trans|Lua}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">compress</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">uncompressed</span><span style="color: #0000FF;">)</span>

<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">com</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_Maxlen</span><span style="color: #0000FF;">,</span><span style="color: #000000;">90</span><span style="color: #0000FF;">})</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">decompress</span><span style="color: #0000FF;">(</span><span style="color: #000000;">com</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=={{header|PHP}}==

{{trans|JavaScript}}

{

function compress($unc) {

$dec = $lzw->decompress($com);

echo $com . "<br>" . $dec;

{{out}}

<pre>

=={{header|Picat}}==

S = "TOBEORNOTTOBEORTOBEORNOT",

println(s=S),

edit(Xs,Ys,D1,Diffs1),

D=D1+1,

{{out}}

=={{header|PicoLisp}}==

(let (Codes 255 Dict)

(balance 'Dict

(when W

(idx 'Dict (cons (inc 'Codes) (cons (last WC) W)) T) )

Test:

<pre>: (lzwCompress (chop "TOBEORNOTTOBEORTOBEORNOT"))

{{trans|REXX}}

The interesting point is the implementation of REXX's associative array (compound variable).

lzwt: Proc Options(main);

Return;

{{out}}

<pre>str=TOBEORNOTTOBEORTOBEORNOT

This is because PureBasic uses these to terminate strings.

Only slight modifications are necessary to handle Null values that would be present for a more generic routine that could be used with a buffer containing any data type.

;Compress a string to a list of output symbols

Input()

CloseConsole()

Sample output:

<pre>Type something: TOBEORNOTTOBEORTOBEORNOT

{{works with|Python|3.x}}

In this version the dicts contain mixed typed data:

"""Compress a string to a list of output symbols."""

print (compressed)

decompressed = decompress(compressed)

Output:

=={{header|Racket}}==

#lang racket

; utilities

(def decompressed (decompress compressed))

(displayln decompressed)

Output:

(formerly Perl 6) I just came across [https://stackoverflow.com/questions/30531078/ this SO question] by chance hence the update. Notably the ancestor Perl entry simply works without any further tweak.

{{trans|Perl}}

sub compress(Str $uncompressed --> Seq) {

@compressed = compress('こんにちは𝒳𝒴𝒵こんにちは𝒳𝒴𝒵こんにちは𝒳𝒴𝒵');

{{out}}

<pre>

===version 1===

{{trans|Java}}

* 20.07.2014 Walter Pachl translated from Java

* 21.07.2014 WP allow for blanks in the string

w=entry

End

'''Output:'''

<pre>str=TOBEORNOTTOBEORTOBEORNOT

This REXX version can execute on &nbsp; '''ASCII''' &nbsp; or &nbsp; '''EBCDIC''' &nbsp; systems.

$$$= '"There is nothing permanent except change." ─── Heraclitus [540 ── 475 BCE]'

parse arg text; if text='' then text= $$$ /*get an optional argument from the CL.*/

$= $ || ?

@.#= w || left(?, 1); w= ?; #= # + 1 /*bump dict. size*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

=={{header|Ring}}==

# Project : LZW compression

svect = left(svect, len(svect) - 1)

see svect + nl

Output:

<pre>

In this version the hashes contain mixed typed data:

def compress(uncompressed)

# Build the dictionary.

p compressed

decompressed = decompress(compressed)

Output:

{{trans|C Sharp}}

Handles arbitrary byte sequences.

fn compress(data: &[u8]) -> Vec<u32> {

let decompressed = String::from_utf8(decompressed).unwrap();

println!("{}", decompressed);

Output:

=={{header|Scala}}==

def compress(tc:String) = {

//initial dictionary

val result = decompress(compressed)

println(result)

=={{header|Scheme}}==

(define (member-string-ref m l)

(define r #f)

(display compressed) (newline)

(define decompressed (lzw-decompress compressed))

Output:<pre>(84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)

TOBEORNOTTOBEORTOBEORNOT</pre>

=={{header|Seed7}}==

const func string: lzwCompress (in string: uncompressed) is func

uncompressed := lzwDecompress(compressed);

writeln(uncompressed);

Output:

=={{header|Sidef}}==

{{trans|Perl}}

func compress(String uncompressed) -> Array {

say compressed.join(' ')

var decompressed = decompress(compressed)

{{out}}

<pre>T O B E O R N O T 256 258 260 265 259 261 263

=={{header|Swift}}==

{{trans|JavaScript}}

class func compress(_ uncompressed:String) -> [Int] {

var dict = [String : Int]()

if let decomp = LZW.decompress(comp) {

print(decomp)

{{out}}

<pre>

=={{header|Tcl}}==

variable char2int

variable chars

# or

=={{header|Wren}}==

{{trans|Kotlin}}

/* Compress a string to a list of output symbols. */

static compress(uncompressed) {

System.print(compressed)

var decompressed = LZW.decompress(compressed)

{{out}}

=={{header|Xojo}}==

{{trans|PHP}}

Function compress(str as String) As String

Dim i as integer

End Function

Test:

=={{header|zkl}}==

dictionary:=(256).pump(Dictionary(),fcn(n){ return(n.toChar(),n) });

w,compressed:="",List();

}

decommpressed.text

compressed.toString(*).println();

{{out}}

<pre>