Правильность работы алгоритма LZW
Код:
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace LZW
{
class LzwStringTable
{
public LzwStringTable(int numBytesPerCode)
{
maxCode = (1 << (8 * numBytesPerCode)) - 1;
}
public void AddCode(string s)
{
if (nextAvailableCode <= maxCode)
{
if (s.Length != 1 && !table.ContainsKey(s))
table[s] = nextAvailableCode++;
}
else
{
throw new Exception("LZW string table overflow");
}
}
public int GetCode(string s)
{
if (s.Length == 1)
return (int)s[0];
else
return table[s];
}
public bool Contains(string s)
{
return s.Length == 1 || table.ContainsKey(s);
}
private Dictionary<string, int> table = new Dictionary<string, int>();
private int nextAvailableCode = 256;
private int maxCode;
}
class Program
{
private const int NumBytesPerCode = 2;
static int ReadCode(BinaryReader reader)
{
int code = 0;
int shift = 0;
for (int i = 0; i < NumBytesPerCode; i++)
{
byte nextByte = reader.ReadByte();
code += nextByte << shift;
shift += 8;
}
return code;
}
static void WriteCode(BinaryWriter writer, int code)
{
int shift = 0;
int mask = 0xFF;
for (int i = 0; i < NumBytesPerCode; i++)
{
byte nextByte = (byte)((code >> shift) & mask);
writer.Write(nextByte);
shift += 8;
}
}
static void Compress(StreamReader input, BinaryWriter output)
{
LzwStringTable table = new LzwStringTable(NumBytesPerCode);
char firstChar = (char)input.Read();
string match = firstChar.ToString();
while (input.Peek() != -1)
{
char nextChar = (char)input.Read();
string nextMatch = match + nextChar;
if (table.Contains(nextMatch))
{
match = nextMatch;
}
else
{
WriteCode(output, table.GetCode(match));
table.AddCode(nextMatch);
match = nextChar.ToString();
}
}
WriteCode(output, table.GetCode(match));
}
static void TestCompress()
{
FileStream inputStream = new FileStream("Input.txt", FileMode.Open);
StreamReader inputReader = new StreamReader(inputStream);
FileStream outputStream = new FileStream("Compressed.txt", FileMode.Create);
BinaryWriter outputWriter = new BinaryWriter(outputStream);
Compress(inputReader, outputWriter);
outputWriter.Close();
outputStream.Close();
inputReader.Close();
inputStream.Close();
}
static void Main(string[] args)
{
TestCompress();
}
}
}
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace LZW
{
class LzwStringTable
{
public LzwStringTable(int numBytesPerCode)
{
maxCode = (1 << (8 * numBytesPerCode)) - 1;
}
public void AddCode(string s)
{
if (nextAvailableCode <= maxCode)
{
if (s.Length != 1 && !table.ContainsKey(s))
table[s] = nextAvailableCode++;
}
else
{
throw new Exception("LZW string table overflow");
}
}
public int GetCode(string s)
{
if (s.Length == 1)
return (int)s[0];
else
return table[s];
}
public bool Contains(string s)
{
return s.Length == 1 || table.ContainsKey(s);
}
private Dictionary<string, int> table = new Dictionary<string, int>();
private int nextAvailableCode = 256;
private int maxCode;
}
class Program
{
private const int NumBytesPerCode = 2;
static int ReadCode(BinaryReader reader)
{
int code = 0;
int shift = 0;
for (int i = 0; i < NumBytesPerCode; i++)
{
byte nextByte = reader.ReadByte();
code += nextByte << shift;
shift += 8;
}
return code;
}
static void WriteCode(BinaryWriter writer, int code)
{
int shift = 0;
int mask = 0xFF;
for (int i = 0; i < NumBytesPerCode; i++)
{
byte nextByte = (byte)((code >> shift) & mask);
writer.Write(nextByte);
shift += 8;
}
}
static void Compress(StreamReader input, BinaryWriter output)
{
LzwStringTable table = new LzwStringTable(NumBytesPerCode);
char firstChar = (char)input.Read();
string match = firstChar.ToString();
while (input.Peek() != -1)
{
char nextChar = (char)input.Read();
string nextMatch = match + nextChar;
if (table.Contains(nextMatch))
{
match = nextMatch;
}
else
{
WriteCode(output, table.GetCode(match));
table.AddCode(nextMatch);
match = nextChar.ToString();
}
}
WriteCode(output, table.GetCode(match));
}
static void TestCompress()
{
FileStream inputStream = new FileStream("Input.txt", FileMode.Open);
StreamReader inputReader = new StreamReader(inputStream);
FileStream outputStream = new FileStream("Compressed.txt", FileMode.Create);
BinaryWriter outputWriter = new BinaryWriter(outputStream);
Compress(inputReader, outputWriter);
outputWriter.Close();
outputStream.Close();
inputReader.Close();
inputStream.Close();
}
static void Main(string[] args)
{
TestCompress();
}
}
}
Wiki есть разбор примера.
Ну, даже в