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|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}}

"TOBEORNOTTOBEORTOBEORNOT"

true

</pre>

 

=={{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 function decompress(compressed) -- table

for i = 0, 255 do

dictionary[i] = string.char(i)

end

k = compressed[i]

if dictionary[k] then

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 >

</pre>

 

{{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}

"TOBEORNOTTOBEORTOBEORNOT"</pre>

 

=={{header|Nim}}==

 

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

 

 

for c in uncompressed:

var wc = w & c

w = wc

else:

w = $c

 

 

 

proc decompress*(compressed: var seq[int]): string =

 

 

compressed.delete(0)

 

for k in compressed:

entry = dictionary[k]

entry = w & w[0]

else:

raise newException(ValueError, "Bad compressed k: " & $k)

w = entry

 

 

when isMainModule:

echo compressed

var decompressed = decompress(compressed)

 

=={{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}}

{{out}}

<pre>

=={{header|PHP}}==

{{trans|JavaScript}}

{

function compress($unc) {

for ($i = 1; $i < count($com);$i++) {

$k = $com[$i];

$entry = $dictionary[$k];

} else {

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

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

{{out}}

<pre>

TOBEORNOTTOBEORTOBEORNOT

</pre>

 

=={{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.

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

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

<pre>

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

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

LZW integers= 34 84 104 101 114 101 32 105 115 32 110 111 116 104 105 110 103 32 112 259 109 97 110 101 110 116 32 101 120 99 101 112 281 99 104 277 103 101 46 34 32 296 196 298 296 32 72 259 97 99 108 105 116 117 264 32 91 53 52 48 32 299 52 55 53 32 66 67 69 93

</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]()

} else {

result.append(dict[w]!)

w = String(c)

}

 

result += entry

w = entry

}

if let decomp = LZW.decompress(comp) {

print(decomp)

{{out}}

<pre>

</pre>

 

=={{header|Tcl}}==

variable char2int

variable chars

 

# or

 

=={{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>