82 lines
2.4 KiB
C#
82 lines
2.4 KiB
C#
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();
|
|
}
|
|
}
|
|
}
|