LZW compression: Difference between revisions
Content added Content deleted
(Added Rust implementation.) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 616: | Line 616: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|C sharp}}== |
|||
{{trans|Java}} |
|||
<lang C sharp>using System; |
|||
using System.Collections.Generic; |
|||
using System.Text; |
|||
namespace LZW |
|||
{ |
|||
public class Program |
|||
{ |
|||
public static void Main(string[] args) |
|||
{ |
|||
List<int> compressed = Compress("TOBEORNOTTOBEORTOBEORNOT"); |
|||
Console.WriteLine(string.Join(", ", compressed)); |
|||
string decompressed = Decompress(compressed); |
|||
Console.WriteLine(decompressed); |
|||
} |
|||
public static List<int> Compress(string uncompressed) |
|||
{ |
|||
// build the dictionary |
|||
Dictionary<string, int> dictionary = new Dictionary<string, int>(); |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary.Add(((char)i).ToString(), i); |
|||
string w = string.Empty; |
|||
List<int> compressed = new List<int>(); |
|||
foreach (char c in uncompressed) |
|||
{ |
|||
string wc = w + c; |
|||
if (dictionary.ContainsKey(wc)) |
|||
{ |
|||
w = wc; |
|||
} |
|||
else |
|||
{ |
|||
// write w to output |
|||
compressed.Add(dictionary[w]); |
|||
// wc is a new sequence; add it to the dictionary |
|||
dictionary.Add(wc, dictionary.Count); |
|||
w = c.ToString(); |
|||
} |
|||
} |
|||
// write remaining output if necessary |
|||
if (!string.IsNullOrEmpty(w)) |
|||
compressed.Add(dictionary[w]); |
|||
return compressed; |
|||
} |
|||
public static string Decompress(List<int> compressed) |
|||
{ |
|||
// build the dictionary |
|||
Dictionary<int, string> dictionary = new Dictionary<int, string>(); |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary.Add(i, ((char)i).ToString()); |
|||
string w = dictionary[compressed[0]]; |
|||
compressed.RemoveAt(0); |
|||
StringBuilder decompressed = new StringBuilder(w); |
|||
foreach (int k in compressed) |
|||
{ |
|||
string entry = null; |
|||
if (dictionary.ContainsKey(k)) |
|||
entry = dictionary[k]; |
|||
else if (k == dictionary.Count) |
|||
entry = w + w[0]; |
|||
decompressed.Append(entry); |
|||
// new sequence; add it to the dictionary |
|||
dictionary.Add(dictionary.Count, w + entry[0]); |
|||
w = entry; |
|||
} |
|||
return decompressed.ToString(); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263 |
|||
TOBEORNOTTOBEORTOBEORNOT</pre> |
|||
=={{header|C++}}== |
|||
{{trans|D}} |
|||
<lang cpp>#include <string> |
|||
#include <map> |
|||
// Compress a string to a list of output symbols. |
|||
// The result will be written to the output iterator |
|||
// starting at "result"; the final iterator is returned. |
|||
template <typename Iterator> |
|||
Iterator compress(const std::string &uncompressed, Iterator result) { |
|||
// Build the dictionary. |
|||
int dictSize = 256; |
|||
std::map<std::string,int> dictionary; |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary[std::string(1, i)] = i; |
|||
std::string w; |
|||
for (std::string::const_iterator it = uncompressed.begin(); |
|||
it != uncompressed.end(); ++it) { |
|||
char c = *it; |
|||
std::string wc = w + c; |
|||
if (dictionary.count(wc)) |
|||
w = wc; |
|||
else { |
|||
*result++ = dictionary[w]; |
|||
// Add wc to the dictionary. |
|||
dictionary[wc] = dictSize++; |
|||
w = std::string(1, c); |
|||
} |
|||
} |
|||
// Output the code for w. |
|||
if (!w.empty()) |
|||
*result++ = dictionary[w]; |
|||
return result; |
|||
} |
|||
// Decompress a list of output ks to a string. |
|||
// "begin" and "end" must form a valid range of ints |
|||
template <typename Iterator> |
|||
std::string decompress(Iterator begin, Iterator end) { |
|||
// Build the dictionary. |
|||
int dictSize = 256; |
|||
std::map<int,std::string> dictionary; |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary[i] = std::string(1, i); |
|||
std::string w(1, *begin++); |
|||
std::string result = w; |
|||
std::string entry; |
|||
for ( ; begin != end; begin++) { |
|||
int k = *begin; |
|||
if (dictionary.count(k)) |
|||
entry = dictionary[k]; |
|||
else if (k == dictSize) |
|||
entry = w + w[0]; |
|||
else |
|||
throw "Bad compressed k"; |
|||
result += entry; |
|||
// Add w+entry[0] to the dictionary. |
|||
dictionary[dictSize++] = w + entry[0]; |
|||
w = entry; |
|||
} |
|||
return result; |
|||
} |
|||
#include <iostream> |
|||
#include <iterator> |
|||
#include <vector> |
|||
int main() { |
|||
std::vector<int> compressed; |
|||
compress("TOBEORNOTTOBEORTOBEORNOT", std::back_inserter(compressed)); |
|||
copy(compressed.begin(), compressed.end(), std::ostream_iterator<int>(std::cout, ", ")); |
|||
std::cout << std::endl; |
|||
std::string decompressed = decompress(compressed.begin(), compressed.end()); |
|||
std::cout << decompressed << std::endl; |
|||
return 0; |
|||
}</lang> |
|||
=={{header|Clojure}}== |
|||
<lang lisp>(defn make-dict [] |
|||
(let [vals (range 0 256)] |
|||
(zipmap (map (comp #'list #'char) vals) vals))) |
|||
(defn compress [#^String text] |
|||
(loop [t (seq text) |
|||
r '() |
|||
w '() |
|||
dict (make-dict) |
|||
s 256] |
|||
(let [c (first t)] |
|||
(if c |
|||
(let [wc (cons c w)] |
|||
(if (get dict wc) |
|||
(recur (rest t) r wc dict s) |
|||
(recur (rest t) (cons (get dict w) r) (list c) (assoc dict wc s) (inc s)))) |
|||
(reverse (if w (cons (get dict w) r) r)))))) |
|||
(compress "TOBEORNOTTOBEORTOBEORNOT")</lang> |
|||
{{out}} |
|||
<lang lisp>(84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)</lang> |
|||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
Line 808: | Line 1,003: | ||
CL-USER> (lzw-decompress-to-string *) |
CL-USER> (lzw-decompress-to-string *) |
||
"TOBEORNOTTOBEORTOBEORNOT"</lang> |
"TOBEORNOTTOBEORTOBEORNOT"</lang> |
||
=={{header|C++}}== |
|||
{{trans|D}} |
|||
<lang cpp>#include <string> |
|||
#include <map> |
|||
// Compress a string to a list of output symbols. |
|||
// The result will be written to the output iterator |
|||
// starting at "result"; the final iterator is returned. |
|||
template <typename Iterator> |
|||
Iterator compress(const std::string &uncompressed, Iterator result) { |
|||
// Build the dictionary. |
|||
int dictSize = 256; |
|||
std::map<std::string,int> dictionary; |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary[std::string(1, i)] = i; |
|||
std::string w; |
|||
for (std::string::const_iterator it = uncompressed.begin(); |
|||
it != uncompressed.end(); ++it) { |
|||
char c = *it; |
|||
std::string wc = w + c; |
|||
if (dictionary.count(wc)) |
|||
w = wc; |
|||
else { |
|||
*result++ = dictionary[w]; |
|||
// Add wc to the dictionary. |
|||
dictionary[wc] = dictSize++; |
|||
w = std::string(1, c); |
|||
} |
|||
} |
|||
// Output the code for w. |
|||
if (!w.empty()) |
|||
*result++ = dictionary[w]; |
|||
return result; |
|||
} |
|||
// Decompress a list of output ks to a string. |
|||
// "begin" and "end" must form a valid range of ints |
|||
template <typename Iterator> |
|||
std::string decompress(Iterator begin, Iterator end) { |
|||
// Build the dictionary. |
|||
int dictSize = 256; |
|||
std::map<int,std::string> dictionary; |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary[i] = std::string(1, i); |
|||
std::string w(1, *begin++); |
|||
std::string result = w; |
|||
std::string entry; |
|||
for ( ; begin != end; begin++) { |
|||
int k = *begin; |
|||
if (dictionary.count(k)) |
|||
entry = dictionary[k]; |
|||
else if (k == dictSize) |
|||
entry = w + w[0]; |
|||
else |
|||
throw "Bad compressed k"; |
|||
result += entry; |
|||
// Add w+entry[0] to the dictionary. |
|||
dictionary[dictSize++] = w + entry[0]; |
|||
w = entry; |
|||
} |
|||
return result; |
|||
} |
|||
#include <iostream> |
|||
#include <iterator> |
|||
#include <vector> |
|||
int main() { |
|||
std::vector<int> compressed; |
|||
compress("TOBEORNOTTOBEORTOBEORNOT", std::back_inserter(compressed)); |
|||
copy(compressed.begin(), compressed.end(), std::ostream_iterator<int>(std::cout, ", ")); |
|||
std::cout << std::endl; |
|||
std::string decompressed = decompress(compressed.begin(), compressed.end()); |
|||
std::cout << decompressed << std::endl; |
|||
return 0; |
|||
}</lang> |
|||
=={{header|C sharp}}== |
|||
{{trans|Java}} |
|||
<lang C sharp>using System; |
|||
using System.Collections.Generic; |
|||
using System.Text; |
|||
namespace LZW |
|||
{ |
|||
public class Program |
|||
{ |
|||
public static void Main(string[] args) |
|||
{ |
|||
List<int> compressed = Compress("TOBEORNOTTOBEORTOBEORNOT"); |
|||
Console.WriteLine(string.Join(", ", compressed)); |
|||
string decompressed = Decompress(compressed); |
|||
Console.WriteLine(decompressed); |
|||
} |
|||
public static List<int> Compress(string uncompressed) |
|||
{ |
|||
// build the dictionary |
|||
Dictionary<string, int> dictionary = new Dictionary<string, int>(); |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary.Add(((char)i).ToString(), i); |
|||
string w = string.Empty; |
|||
List<int> compressed = new List<int>(); |
|||
foreach (char c in uncompressed) |
|||
{ |
|||
string wc = w + c; |
|||
if (dictionary.ContainsKey(wc)) |
|||
{ |
|||
w = wc; |
|||
} |
|||
else |
|||
{ |
|||
// write w to output |
|||
compressed.Add(dictionary[w]); |
|||
// wc is a new sequence; add it to the dictionary |
|||
dictionary.Add(wc, dictionary.Count); |
|||
w = c.ToString(); |
|||
} |
|||
} |
|||
// write remaining output if necessary |
|||
if (!string.IsNullOrEmpty(w)) |
|||
compressed.Add(dictionary[w]); |
|||
return compressed; |
|||
} |
|||
public static string Decompress(List<int> compressed) |
|||
{ |
|||
// build the dictionary |
|||
Dictionary<int, string> dictionary = new Dictionary<int, string>(); |
|||
for (int i = 0; i < 256; i++) |
|||
dictionary.Add(i, ((char)i).ToString()); |
|||
string w = dictionary[compressed[0]]; |
|||
compressed.RemoveAt(0); |
|||
StringBuilder decompressed = new StringBuilder(w); |
|||
foreach (int k in compressed) |
|||
{ |
|||
string entry = null; |
|||
if (dictionary.ContainsKey(k)) |
|||
entry = dictionary[k]; |
|||
else if (k == dictionary.Count) |
|||
entry = w + w[0]; |
|||
decompressed.Append(entry); |
|||
// new sequence; add it to the dictionary |
|||
dictionary.Add(dictionary.Count, w + entry[0]); |
|||
w = entry; |
|||
} |
|||
return decompressed.ToString(); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263 |
|||
TOBEORNOTTOBEORTOBEORNOT</pre> |
|||
=={{header|Clojure}}== |
|||
<lang lisp>(defn make-dict [] |
|||
(let [vals (range 0 256)] |
|||
(zipmap (map (comp #'list #'char) vals) vals))) |
|||
(defn compress [#^String text] |
|||
(loop [t (seq text) |
|||
r '() |
|||
w '() |
|||
dict (make-dict) |
|||
s 256] |
|||
(let [c (first t)] |
|||
(if c |
|||
(let [wc (cons c w)] |
|||
(if (get dict wc) |
|||
(recur (rest t) r wc dict s) |
|||
(recur (rest t) (cons (get dict w) r) (list c) (assoc dict wc s) (inc s)))) |
|||
(reverse (if w (cons (get dict w) r) r)))))) |
|||
(compress "TOBEORNOTTOBEORTOBEORNOT")</lang> |
|||
{{out}} |
|||
<lang lisp>(84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263)</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Line 1,425: | Line 1,426: | ||
format-out("%=\n", compress("TOBEORNOTTOBEORTOBEORNOT"))</lang> |
format-out("%=\n", compress("TOBEORNOTTOBEORTOBEORNOT"))</lang> |
||
=={{header|Eiffel}}== |
=={{header|Eiffel}}== |
||
<lang Eiffel> |
<lang Eiffel> |
||
Line 1,755: | Line 1,757: | ||
out out-size @ decompress cr |
out out-size @ decompress cr |
||
\ TOBEORNOTTOBEORTOBEORNOT</lang> |
\ TOBEORNOTTOBEORTOBEORNOT</lang> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
<lang freebasic>' version 22-02-2019 |
<lang freebasic>' version 22-02-2019 |
||
Line 2,884: | Line 2,887: | ||
RETURN |
RETURN |
||
''''''''''''''''''''''''''''''''''''''''</lang> |
''''''''''''''''''''''''''''''''''''''''</lang> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
<lang lua>local function compress(uncompressed) -- string |
<lang lua>local function compress(uncompressed) -- string |
||
Line 2,940: | Line 2,944: | ||
TOBEORNOTTOBEORTOBEORNOT |
TOBEORNOTTOBEORTOBEORNOT |
||
</pre> |
</pre> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
Line 3,675: | Line 3,678: | ||
print "$decompressed\n";</lang> |
print "$decompressed\n";</lang> |
||
{{out}} |
|||
<pre> |
|||
T O B E O R N O T 256 258 260 265 259 261 263 |
|||
TOBEORNOTTOBEORTOBEORNOT |
|||
</pre> |
|||
=={{header|Perl 6}}== |
|||
{{trans|Perl}} |
|||
<lang perl6>sub compress(Str $uncompressed --> Seq) { |
|||
my $dict-size = 256; |
|||
my %dictionary = (.chr => .chr for ^$dict-size); |
|||
my $w = ""; |
|||
gather { |
|||
for $uncompressed.comb -> $c { |
|||
my $wc = $w ~ $c; |
|||
if %dictionary{$wc}:exists { $w = $wc } |
|||
else { |
|||
take %dictionary{$w}; |
|||
%dictionary{$wc} = +%dictionary; |
|||
$w = $c; |
|||
} |
|||
} |
|||
take %dictionary{$w} if $w.chars; |
|||
} |
|||
} |
|||
sub decompress(@compressed --> Str) { |
|||
my $dict-size = 256; |
|||
my %dictionary = (.chr => .chr for ^$dict-size); |
|||
my $w = shift @compressed; |
|||
join '', gather { |
|||
take $w; |
|||
for @compressed -> $k { |
|||
my $entry; |
|||
if %dictionary{$k}:exists { take $entry = %dictionary{$k} } |
|||
elsif $k == $dict-size { take $entry = $w ~ $w.substr(0,1) } |
|||
else { die "Bad compressed k: $k" } |
|||
%dictionary{$dict-size++} = $w ~ $entry.substr(0,1); |
|||
$w = $entry; |
|||
} |
|||
} |
|||
} |
|||
my @compressed = compress('TOBEORNOTTOBEORTOBEORNOT'); |
|||
say @compressed; |
|||
my $decompressed = decompress(@compressed); |
|||
say $decompressed;</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,909: | Line 3,861: | ||
: (pack (lzwDecompress @)) |
: (pack (lzwDecompress @)) |
||
-> "TOBEORNOTTOBEORTOBEORNOT"</pre> |
-> "TOBEORNOTTOBEORTOBEORNOT"</pre> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
Line 4,315: | Line 4,266: | ||
TOBEORNOTTOBEORTOBEORNOT |
TOBEORNOTTOBEORTOBEORNOT |
||
(T O B E O R N O T 256 258 260 265 259 261 263) |
(T O B E O R N O T 256 258 260 265 259 261 263) |
||
TOBEORNOTTOBEORTOBEORNOT |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{trans|Perl}} |
|||
<lang perl6>sub compress(Str $uncompressed --> Seq) { |
|||
my $dict-size = 256; |
|||
my %dictionary = (.chr => .chr for ^$dict-size); |
|||
my $w = ""; |
|||
gather { |
|||
for $uncompressed.comb -> $c { |
|||
my $wc = $w ~ $c; |
|||
if %dictionary{$wc}:exists { $w = $wc } |
|||
else { |
|||
take %dictionary{$w}; |
|||
%dictionary{$wc} = +%dictionary; |
|||
$w = $c; |
|||
} |
|||
} |
|||
take %dictionary{$w} if $w.chars; |
|||
} |
|||
} |
|||
sub decompress(@compressed --> Str) { |
|||
my $dict-size = 256; |
|||
my %dictionary = (.chr => .chr for ^$dict-size); |
|||
my $w = shift @compressed; |
|||
join '', gather { |
|||
take $w; |
|||
for @compressed -> $k { |
|||
my $entry; |
|||
if %dictionary{$k}:exists { take $entry = %dictionary{$k} } |
|||
elsif $k == $dict-size { take $entry = $w ~ $w.substr(0,1) } |
|||
else { die "Bad compressed k: $k" } |
|||
%dictionary{$dict-size++} = $w ~ $entry.substr(0,1); |
|||
$w = $entry; |
|||
} |
|||
} |
|||
} |
|||
my @compressed = compress('TOBEORNOTTOBEORTOBEORNOT'); |
|||
say @compressed; |
|||
my $decompressed = decompress(@compressed); |
|||
say $decompressed;</lang> |
|||
{{out}} |
|||
<pre> |
|||
T O B E O R N O T 256 258 260 265 259 261 263 |
|||
TOBEORNOTTOBEORTOBEORNOT |
TOBEORNOTTOBEORTOBEORNOT |
||
</pre> |
</pre> |