mr.hankey
Сообщений: 2
Оценки: 0
Присоединился: 2010-05-28 21:37:33.110000
|
Ребята, выручайте. В понедельник сдавать курсовую работу, а ПО не работает, как положено . Кто чем может, кто советом, кто консультацией.
Суть дела: Делал программу по алгоритму данного метода. В результате получил программу, которая не сжимает текстовые файлы, а наоборот в раза два, три увеличивает. Но всё-таки, у меня есть надежда, потому что программа писалась не отклонясь от алгоритма. Писать с нуля думаю нет смысла, хочу произвести оптимизацию, но пока не выходит. Почему именно присутвует надежда: потому что, есть тестовые примеры подобранные мной , которые показывают превосходные результаты, сжатие в 8 раз.Но на реальном и на маленьком тексте сжатие становится отрицательным.
FileFormatException.cs
using System;
namespace TermPaper
{
class FileFormatException : Exception
{
public FileFormatException(string message)
: base(message)
{
}
}
}
С этим куском кода всё понятно и ясно.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace TermPaper
{
class Program
{
#region Constants
private const int HashTableSize = 65536;
private const int LzpMatchFlag = 1;
private const int LzpNoMatchFlag = 0;
private const int ContextLength = 2;
private const int BitsInByte = 8;
#endregion
/// <summary>
/// Compresses file
/// </summary>
/// <param name="inputFileName">Input file name</param>
/// <param name="outputFileName">Output file name</param>
private static void Pack(string inputFileName, string outputFileName)
{
Dictionary<ushort, int> hashTable = new Dictionary<ushort, int>(HashTableSize);
// load entire file into the array of bytes
byte[] input = File.ReadAllBytes(inputFileName);
using (FileStream fs = new FileStream(outputFileName, FileMode.OpenOrCreate))
{
int currentOffset = 0;
// output first 2 bytes - context
fs.Write(input, 0, currentOffset += ContextLength);
while (currentOffset < input.Length)
{
ushort hash = (ushort)((input[currentOffset - ContextLength] << BitsInByte) + input[currentOffset - ContextLength + 1]);
if (hashTable.ContainsKey(hash))
{
int matchingLength = CompareSubArrays(input, currentOffset, hashTable[hash]);
if (matchingLength > 0)
{
// write the matching byte and the count of matching bytes
fs.WriteByte(LzpMatchFlag);
byte[] bytesToWrite = BitConverter.GetBytes(matchingLength);
fs.Write(bytesToWrite, 0, bytesToWrite.Length);
hashTable[hash] = currentOffset;
currentOffset += matchingLength;
continue;
}
}
// no hashtable record - create a new one
hashTable[hash] = currentOffset;
fs.WriteByte(LzpNoMatchFlag);
fs.WriteByte(input[currentOffset]);
currentOffset++;
}
}
}
/// <summary>
/// Decompresses file
/// </summary>
/// <param name="inputFileName">Input file name</param>
/// <param name="outputFileName">Output file name</param>
private static void Unpack(string inputFileName, string outputFileName)
{
Dictionary<ushort, int> hashTable = new Dictionary<ushort, int>(HashTableSize);
// load entire file into the array of bytes
byte[] input = File.ReadAllBytes(inputFileName);
// this is ineffective, but who cares:)
List<byte> outputBytes = new List<byte>();
int currentInputOffset = 0;
// output first 2 bytes - context
AddBytes(outputBytes, input, 0, currentInputOffset += ContextLength);
int outputOffset = ContextLength;
while (currentInputOffset < input.Length)
{
ushort hash = BitConverter.ToUInt16(
GetBytes(outputBytes, outputOffset - ContextLength, sizeof(ushort)), 0);
if (input[currentInputOffset] == LzpMatchFlag)
{
byte[] intBytes = ExtractIntBytes(input, currentInputOffset);
int matchingLength = BitConverter.ToInt32(intBytes, 0);
AddBytes(outputBytes,
GetBytes(outputBytes, hashTable[hash], matchingLength),
0,
matchingLength);
currentInputOffset += intBytes.Length;
hashTable[hash] = outputOffset;
outputOffset += matchingLength;
}
else if (input[currentInputOffset] == LzpNoMatchFlag)
{
currentInputOffset++;
outputBytes.Add(input[currentInputOffset]);
hashTable[hash] = outputOffset;
outputOffset++;
}
else
{
throw new FileFormatException(string.Format("Wrong file format: unexpected byte at the offset {0}", currentInputOffset));
}
currentInputOffset++;
}
File.WriteAllBytes(outputFileName, outputBytes.ToArray());
}
/// <summary>
/// Adds bytes to the list
/// </summary>
/// <param name="bytesList">Output list</param>
/// <param name="inputArray">Array to take bytes from</param>
/// <param name="offset">Input array offset</param>
/// <param name="count">Bytes count</param>
private static void AddBytes(List<byte> bytesList, byte[] inputArray, int offset, int count)
{
if (inputArray.Length < offset + count)
{
throw new ArgumentException("Offset and count mismatch");
}
for (int i = 0; i < count; i++)
{
bytesList.Add(inputArray[offset + i]);
}
}
/// <summary>
/// Gets bytes subarray from the given list
/// </summary>
/// <param name="bytesList">Given list</param>
/// <param name="offset">List offset</param>
/// <param name="count">Number of bytes</param>
/// <returns></returns>
private static byte[] GetBytes(List<byte> bytesList, int offset, int count)
{
if (bytesList.Count < offset + count)
{
throw new ArgumentException("Offset and count mismatch");
}
byte[] result = new byte[count];
for (int i = 0; i < count; i++)
{
result[i] = bytesList[offset + i];
}
return result;
}
/// <summary>
/// Extracts int subarray in the correct order from the input array
/// </summary>
/// <param name="input">Input array</param>
/// <param name="offset">Offset in the input array</param>
/// <returns></returns>
private static byte[] ExtractIntBytes(byte[] input, int offset)
{
int sizeOfInt = sizeof(int);
byte[] result = new byte[sizeOfInt];
for (int i = sizeOfInt - 1; i >= 0; i--)
{
result[i] = input[offset + i + 1];
}
return result;
}
/// <summary>
/// Compares 2 subarrays in the given array
/// </summary>
/// <param name="input">Input array</param>
/// <param name="inputOffset">First offset</param>
/// <param name="hashTableOffset">Second offset</param>
/// <returns>Match length</returns>
private static int CompareSubArrays(byte[] input, int inputOffset, int hashTableOffset)
{
int matchingLength = 0;
while ((inputOffset + matchingLength < input.Length) // bounds check
&& (inputOffset > hashTableOffset + matchingLength) // do not intersect subarrays!
&& (input[inputOffset + matchingLength] == input[hashTableOffset + matchingLength]))
{
matchingLength++;
}
return matchingLength;
}
static void Main(string[] args)
{
Pack("Base.txt", "Compressed.txt");
Unpack("Compressed.txt", "Uncompressed.txt");
}
}
}
Ну и собственно, полная реализация алгоритма LZP. Также выкладываю проект программы с тестовым примером, показывающим превосходное сжатие.
|
Программная реализация алгоритма сжатия текста методом LZP (c#) - 
