LZW compression: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
|||
Line 8:
=={{header|11l}}==
{{trans|Python}}
<
V dict_size = 256
V dictionary = Dict((0 .< dict_size).map(i -> (String(Char(code' i)), i)))
Line 51:
V compressed = compress(‘TOBEORNOTTOBEORTOBEORNOT’)
print(compressed)
print(decompress(&compressed))</
=={{header|Ada}}==
Line 57:
lzw.ads:
<
MAX_CODE : constant := 4095;
Line 67:
function Decompress (Data : in Compressed_Data) return String;
end LZW;</
lzw.adb:
<
with Ada.Strings.Unbounded;
Line 185:
end Decompress;
end LZW;</
test.adb:
<
with Ada.Text_IO;
Line 208:
Text_IO.Put_Line (Cleartext);
end;
end Test;</
=={{header|Arturo}}==
<
dict: #[]
loop 0..255 'i -> dict\[to :char i]: i
Line 263:
decompressed: decompress compressed
print "Decompressed:"
print decompressed</
{{out}}
Line 274:
=={{header|BaCon}}==
<
PRINT "LZWData: ", lzw_data$
Line 349:
RETURN result$
END FUNCTION</
{{out}}
<pre>LZWData: TOBEORNOTTOBEORTOBEORNOT
Line 359:
{{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
Line 406:
w$ = t$
NEXT
= o$</
{{out}}
<pre>
Line 421:
'''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>
Line 678:
return 0;
}</
=={{header|C sharp}}==
{{trans|Java}}
<
using System.Collections.Generic;
using System.Text;
Line 762:
}
}
}</
{{out}}
Line 770:
=={{header|C++}}==
{{trans|D}}
<
#include <map>
Line 850:
return 0;
}</
=={{header|Clojure}}==
<
(let [vals (range 0 256)]
(zipmap (map (comp #'list #'char) vals) vals)))
Line 871:
(reverse (if w (cons (get dict w) r) r))))))
(compress "TOBEORNOTTOBEORTOBEORNOT")</
{{out}}
<
=={{header|CoffeeScript}}==
This only does the encoding step for now.
<
lzw = (s) ->
dct = {} # map substrings to codes between 256 and 4096
Line 915:
console.log lzw "TOBEORNOTTOBEORTOBEORNOT"
</syntaxhighlight>
{{out}}
<pre>
Line 947:
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)
Line 1,056:
(assert (equal #2=(lzw-decompress-to-string (lzw-compress string)) string) ()
"Can't compress ~S properly, got ~S instead" string #2#)
t)</
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 *)
"TOBEORNOTTOBEORTOBEORNOT"</
=={{header|D}}==
===Simpler Version===
<
auto compress(in string original) pure nothrow {
Line 1,108:
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]
Line 1,115:
===More Refined Version===
This longer version is a little more efficient and it uses stronger static typing.
<
import std.array: empty;
Line 1,209:
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]
Line 1,217:
{{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.
Line 1,438:
"Decoded OK.".writeln;
}</
{{out}}
<pre>Input size: 206403
Line 1,446:
=={{header|Dylan}}==
<
Synopsis: LZW implementation for Rosetta code
Line 1,488:
end;
format-out("%=\n", compress("TOBEORNOTTOBEORTOBEORNOT"))</
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,604:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,613:
=={{header|Elixir}}==
{{trans|Erlang}}
<
@encode_map Enum.into(0..255, Map.new, &{[&1],&1})
@decode_map Enum.into(0..255, Map.new, &{&1,[&1]})
Line 1,651:
IO.inspect enc = LZW.encode(str)
IO.inspect dec = LZW.decode(enc)
IO.inspect str == dec</
{{out}}
Line 1,661:
=={{header|Erlang}}==
<
-export([test/0, encode/1, decode/1]).
Line 1,717:
init1(0, D) -> D;
init1(N, D) -> D1 = dict:store(N,[N],D), init1(N-1, D1).</
=={{header|Forth}}==
{{works with|GNU Forth|0.6.2}}
<
\ current string fragment
Line 1,819:
out out-size @ decompress cr
\ TOBEORNOTTOBEORTOBEORNOT</
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
!
! lzw_shared_parameters.f90
Line 2,244:
CALL CPU_TIME(finish)
PRINT '("Time = ",f6.3," seconds.")' , finish - start
END PROGRAM MAIN</
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 2,355:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> input str: TOBEORNOTTOBEORTOBEORNOT
Line 2,370:
not just ASCII or valid UTF8 encoding
(tested with [https://github.com/dvyukov/go-fuzz go-fuzz]).
<
import (
Line 2,464:
}
fmt.Println(decompressed)
}</
{{out}}
<pre>
Line 2,472:
=={{header|Groovy}}==
<
def dictionary = (0..<256).inject([:]) { map, ch -> map."${(char)ch}" = ch; map }
def w = '', compressed = []
Line 2,508:
result.toString()
}</
Testing:
<
def compressed = compress(plaintext)
def result = decompress(compressed)
Line 2,517:
Plaintext: '$plaintext'
Compressed: $compressed
Uncompressed: '$result'""".stripIndent()</
{{out}}
<pre>Plaintext: 'TOBEORNOTTOBEORTOBEORNOT'
Line 2,525:
=={{header|Haskell}}==
<
import Data.Maybe (fromJust)
Line 2,562:
print $
((==) <*> ((.) <$> undoLZW <*> doLZW) ['\NUL' .. '\255'])
"TOBEORNOTTOBEORTOBEORNOT"</
{{Out}}
<pre>[84,79,66,69,79,82,78,79,84,256,258,260,265,259,261,263]
Line 2,573:
Straightforward implementations of encoding and decoding:
<
d=. ;/x
r=.0$0
Line 2,586:
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
Line 2,606:
end.
;r
)</
Test:
<pre> a. decodeLZW 84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263
Line 2,624:
=={{header|Java}}==
{{works with|Java|1.5+}}
<
public class LZW {
Line 2,690:
System.out.println(decompressed);
}
}</
{{out}} (Command Line direct output):
<
TOBEORNOTTOBEORTOBEORNOT</
=={{header|JavaScript}}==
<
var LZW = {
compress: function (uncompressed) {
Line 2,777:
comp = LZW.compress("TOBEORNOTTOBEORTOBEORNOT"),
decomp = LZW.decompress(comp);
document.write(comp + '<br>' + decomp);</
Line 2,784:
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.
Line 2,893:
console.log(`${comp}
${decomp}`);</
{{out}}
Line 2,902:
{{ works with|jq|1.4}}
{{trans|JavaScript}}
<
def lzw_compress:
def decode: [.] | implode;
Line 2,947:
| .[2] = $entry # w = entry
) | .[3]
;</
'''Example''':
<
{{Out}}
$ jq -n -f LZW.jq
Line 2,956:
=={{header|Julia}}==
{{works with|Julia|1.1.1}}
<
dictsize = 256
dict = Dict{String,Int}(string(Char(i)) => i for i in 0:dictsize)
Line 3,005:
comprate = (length(word) - length(comp)) / length(word) * 100
println("Original: $word\n-> Compressed: $comp (compr.rate: $(round(comprate, digits=2))%)\n-> Decompressed: $decomp")
end</
{{out}}
Line 3,020:
=={{header|Kotlin}}==
{{trans|Java}}
<
object Lzw {
Line 3,081:
val decompressed = Lzw.decompress(compressed)
println(decompressed)
}</
{{out}}
Line 3,094:
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".
<syntaxhighlight lang="text"> DIM LZW(1, 1)
DIM JDlzw(1)
DIM JDch$(1)
Line 3,373:
fileTag$ = STR$(tagCount) + "_"
RETURN
''''''''''''''''''''''''''''''''''''''''</
=={{header|Lua}}==
<
local dictionary, result, dictSize, w, c = {}, {}, 255, ""
for i = 0, 255 do
Line 3,426:
local dec = decompress(com)
print(table.concat(com, ", "))
print(dec)</
{{Out}}
Line 3,436:
=={{header|M2000 Interpreter}}==
{{trans|BBC BASIC}}
<syntaxhighlight lang="m2000 interpreter">
Module BBCtrans {
\\ LZW compression
Line 3,489:
}
BBCtrans
</syntaxhighlight>
And here a change for using Inventories, where we have hash function, and we find entry in O(1).
<syntaxhighlight lang="m2000 interpreter">
Module FastM2000 {
plaintext$="TOBEORNOTTOBEORTOBEORNOT"
Line 3,550:
}
FastM2000
</syntaxhighlight>
{{out}}
<pre >
Line 3,559:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Ruby}}
<syntaxhighlight lang="text">compress[uncompressed_] :=
Module[{dictsize, dictionary, w, result, wc},
dictsize = 256;
Line 3,595:
(*How to use:*)
compress["TOBEORNOTTOBEORTOBEORNOT"]
decompress[%]</
{{Out}}
<pre>{"T", "O", "B", "E", "O", "R", "N", "O", "T", 256, 258, 260, 265, 259, 261, 263}
Line 3,603:
=={{header|Nim}}==
<syntaxhighlight lang="text">import tables
proc compress*(uncompressed: string): seq[int] =
Line 3,655:
echo compressed
var decompressed = decompress(compressed)
echo decompressed</
{{out}}
Line 3,663:
=={{header|Objeck}}==
{{trans|Java}}
<
class LZW {
Line 3,766:
"]"->PrintLine();
}
}</
<pre>[84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]
Line 3,777:
The class for the LZW compression algorithm:
<
#import <stdio.h>
Line 3,862:
}
@end</
Usage example:
<
int main()
Line 3,886:
}
return EXIT_SUCCESS;
}</
{{out}} (reformatted by hand):
Line 3,896:
=={{header|OCaml}}==
<
#load "extLib.cma"
open ExtString
Line 3,975:
in
(List.rev result)
;;</
here is the interface:
<
val decompress : compressed:int list -> string list</
How to use:<br />
Line 3,985:
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 *)
Line 4,023:
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
Line 4,053:
(print (compress "TOBEORNOTTOBEORTOBEORNOT")) ; => (84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)
</syntaxhighlight>
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
Line 4,084:
(decompress (runes->string '(84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)))))
; => TOBEORNOTTOBEORTOBEEORNOT
</syntaxhighlight>
=={{header|Perl}}==
In this version the hashes contain mixed typed data:
<
sub compress {
my $uncompressed = shift;
Line 4,153:
print "@compressed\n";
my $decompressed = decompress(@compressed);
print "$decompressed\n";</
{{out}}
Line 4,163:
=={{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>
Line 4,221:
<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>
Line 4,230:
=={{header|PHP}}==
{{trans|JavaScript}}
<
{
function compress($unc) {
Line 4,294:
$dec = $lzw->decompress($com);
echo $com . "<br>" . $dec;
</syntaxhighlight>
{{out}}
<pre>
Line 4,302:
=={{header|Picat}}==
<
S = "TOBEORNOTTOBEORTOBEORNOT",
println(s=S),
Line 4,386:
edit(Xs,Ys,D1,Diffs1),
D=D1+1,
Diffs = [[delete=X,xPos=Xs.length,yPos=Ys.length]|Diffs1].</
{{out}}
Line 4,398:
=={{header|PicoLisp}}==
<
(let (Codes 255 Dict)
(balance 'Dict
Line 4,428:
(when W
(idx 'Dict (cons (inc 'Codes) (cons (last WC) W)) T) )
(setq W WC) ) ) ) ) ) )</
Test:
<pre>: (lzwCompress (chop "TOBEORNOTTOBEORTOBEORNOT"))
Line 4,439:
{{trans|REXX}}
The interesting point is the implementation of REXX's associative array (compound variable).
<
lzwt: Proc Options(main);
Line 4,588:
Return;
End;</
{{out}}
<pre>str=TOBEORNOTTOBEORTOBEORNOT
Line 4,600:
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
Line 4,696:
Input()
CloseConsole()
EndIf</
Sample output:
<pre>Type something: TOBEORNOTTOBEORTOBEORNOT
Line 4,705:
{{works with|Python|3.x}}
In this version the dicts contain mixed typed data:
<
"""Compress a string to a list of output symbols."""
Line 4,767:
print (compressed)
decompressed = decompress(compressed)
print (decompressed)</
Output:
Line 4,776:
=={{header|Racket}}==
<
#lang racket
; utilities
Line 4,834:
(def decompressed (decompress compressed))
(displayln decompressed)
</syntaxhighlight>
Output:
Line 4,846:
(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}}
<syntaxhighlight lang="raku"
sub compress(Str $uncompressed --> Seq) {
Line 4,891:
@compressed = compress('こんにちは𝒳𝒴𝒵こんにちは𝒳𝒴𝒵こんにちは𝒳𝒴𝒵');
say decompress(@compressed);</
{{out}}
<pre>
Line 4,902:
===version 1===
{{trans|Java}}
<
* 20.07.2014 Walter Pachl translated from Java
* 21.07.2014 WP allow for blanks in the string
Line 4,977:
w=entry
End
Return res</
'''Output:'''
<pre>str=TOBEORNOTTOBEORTOBEORNOT
Line 4,995:
This REXX version can execute on '''ASCII''' or '''EBCDIC''' 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.*/
Line 5,018:
$= $ || ?
@.#= w || left(?, 1); w= ?; #= # + 1 /*bump dict. size*/
end /*k*/; return $</
{{out|output|text= when using the default input:}}
<pre>
Line 5,028:
=={{header|Ring}}==
<
# Project : LZW compression
Line 5,107:
svect = left(svect, len(svect) - 1)
see svect + nl
</syntaxhighlight>
Output:
<pre>
Line 5,117:
In this version the hashes contain mixed typed data:
<
def compress(uncompressed)
# Build the dictionary.
Line 5,173:
p compressed
decompressed = decompress(compressed)
puts decompressed</
Output:
Line 5,184:
{{trans|C Sharp}}
Handles arbitrary byte sequences.
<
fn compress(data: &[u8]) -> Vec<u32> {
Line 5,260:
let decompressed = String::from_utf8(decompressed).unwrap();
println!("{}", decompressed);
}</
Output:
Line 5,269:
=={{header|Scala}}==
<
def compress(tc:String) = {
//initial dictionary
Line 5,315:
val result = decompress(compressed)
println(result)
</syntaxhighlight>
=={{header|Scheme}}==
<
(define (member-string-ref m l)
(define r #f)
Line 5,402:
(display compressed) (newline)
(define decompressed (lzw-decompress compressed))
(display decompressed) (newline)</
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
Line 5,481:
uncompressed := lzwDecompress(compressed);
writeln(uncompressed);
end func;</
Output:
Line 5,493:
=={{header|Sidef}}==
{{trans|Perl}}
<
func compress(String uncompressed) -> Array {
Line 5,564:
say compressed.join(' ')
var decompressed = decompress(compressed)
say decompressed</
{{out}}
<pre>T O B E O R N O T 256 258 260 265 259 261 263
Line 5,571:
=={{header|Swift}}==
{{trans|JavaScript}}
<
class func compress(_ uncompressed:String) -> [Int] {
var dict = [String : Int]()
Line 5,635:
if let decomp = LZW.decompress(comp) {
print(decomp)
}</
{{out}}
<pre>
Line 5,643:
=={{header|Tcl}}==
<
variable char2int
variable chars
Line 5,702:
# or
if {$s eq [LZW::decode [LZW::encode $s]]} then {puts success} else {puts fail} ;# ==> success</
=={{header|Wren}}==
{{trans|Kotlin}}
<
/* Compress a string to a list of output symbols. */
static compress(uncompressed) {
Line 5,765:
System.print(compressed)
var decompressed = LZW.decompress(compressed)
System.print(decompressed)</
{{out}}
Line 5,775:
=={{header|Xojo}}==
{{trans|PHP}}
<syntaxhighlight lang="vb">
Function compress(str as String) As String
Dim i as integer
Line 5,882:
End Function
</syntaxhighlight>
Test:
Line 5,899:
=={{header|zkl}}==
<
dictionary:=(256).pump(Dictionary(),fcn(n){ return(n.toChar(),n) });
w,compressed:="",List();
Line 5,926:
}
decommpressed.text
}</
<
compressed.toString(*).println();
lzwUncompress(compressed).println();</
{{out}}
<pre>
|