LZW compression: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Added Rust implementation.) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 616:
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|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}}==
Line 808 ⟶ 1,003:
CL-USER> (lzw-decompress-to-string *)
"TOBEORNOTTOBEORTOBEORNOT"</lang>
=={{header|D}}==
Line 1,425 ⟶ 1,426:
format-out("%=\n", compress("TOBEORNOTTOBEORTOBEORNOT"))</lang>
=={{header|Eiffel}}==
<lang Eiffel>
Line 1,755 ⟶ 1,757:
out out-size @ decompress cr
\ TOBEORNOTTOBEORTOBEORNOT</lang>
=={{header|FreeBASIC}}==
<lang freebasic>' version 22-02-2019
Line 2,884 ⟶ 2,887:
RETURN
''''''''''''''''''''''''''''''''''''''''</lang>
=={{header|Lua}}==
<lang lua>local function compress(uncompressed) -- string
Line 2,940 ⟶ 2,944:
TOBEORNOTTOBEORTOBEORNOT
</pre>
=={{header|M2000 Interpreter}}==
Line 3,675 ⟶ 3,678:
print "$decompressed\n";</lang>
{{out}}
<pre>
Line 3,909 ⟶ 3,861:
: (pack (lzwDecompress @))
-> "TOBEORNOTTOBEORTOBEORNOT"</pre>
=={{header|PL/I}}==
Line 4,315 ⟶ 4,266:
TOBEORNOTTOBEORTOBEORNOT
(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
</pre>
| |||