2
« en: Martes 18 de Noviembre de 2008, 04:47 »
Hola soy nuevo por aki... miren este es mi problema me mandaron a estudiarme el codigo del algoritmo de compresion LZ77 en C#, entonces encontre el codigo ese en internet pero no entiedno casi nada, queria ver si me podian ayudar a entender esto.
写了一个比较垃圾的lz77算法
/* 代码编写 : 张郎 */
using System;
using System.IO;
/////////////////////////////////////
// lz77压缩算法
/////////////////////////////////////
public class lz77
{
public lz77()
{
}
#region 压缩数据
public static void zipData(string souceFilePath, string targetFilePath)
{
/////////////////////////////////
// 初始化变量
/////////////////////////////////
FileStream data = new FileStream(souceFilePath, FileMode.Open);
FileStream zipedData = new FileStream(targetFilePath, FileMode.Create);
int p, wPos, wLen, tPos, tLen;
int dataLength = (int)data.Length;
int bufferLength = 0;
byte[] buffer = new byte[4096];
byte[] buffer_zip = new byte[8092];
int[] nextSamePoint = new int[4096];
int bufferDP;
bool f, ff;
byte tByteLen = 0;
int tInt = 0;
/////////////////////////////////
// 开始分组压缩
/////////////////////////////////
while((bufferLength = data.Read(buffer, 0, 4096)) > 0)
{
// 如果buffer长度太短直接保存
if(bufferLength < 6)
{
for(int i = 0; i < Math.Min(3, bufferLength); i++)
{
tInt = (tInt << 8) + buffer;
zipedData.WriteByte((byte)(tInt >> tByteLen));
tInt = getRightByte(tInt, tByteLen);
}
for(int i = 3; i < bufferLength; i++)
{
tInt = (tInt << 9) + buffer;
tByteLen += 9;
while(tByteLen >= 8)
{
zipedData.WriteByte((byte)(tInt >> (tByteLen -= 8) << 24 >> 24));
}
tInt = getRightByte(tInt, tByteLen); // 记录剩余信息
}
break;
}
// 提前计算出下一个相同字节的位置
for(int i = 0; i < bufferLength; i++)
{
for(int j = i + 1; j < bufferLength; j++)
{
nextSamePoint = 4096;
if(buffer == buffer[j])
{
nextSamePoint = j;
break;
}
}
}
// 初始化字典和滑块
tInt = (tInt << 8) + buffer[0];
buffer_zip[0] = (byte)(tInt >> tByteLen);
tInt = getRightByte(tInt, tByteLen);
tInt = (tInt << 8) + buffer[1];
buffer_zip[1] = (byte)(tInt >> tByteLen);
tInt = getRightByte(tInt, tByteLen);
tInt = (tInt << 8) + buffer[2];
buffer_zip[2] = (byte)(tInt >> tByteLen);
tInt = getRightByte(tInt, tByteLen);
p = 3;
wPos = 0;
wLen = 3;
tPos = -1;
tLen = 0;
bufferDP = 2;
////////////////////////////////
// 开始编码
////////////////////////////////
while(bufferLength - 3 >= p)
{
while(wPos + wLen <= p && p + wLen <= bufferLength)
{
// 判断滑块是否匹配
f = true;
if(buffer[wPos] == buffer[p])
{
ff = true;
for(int i = 1; i < wLen; i++)
{
if(buffer[wPos + i] != buffer[p + i])
{
f = false;
break;
}
}
}
else
{
f = false;
ff = false;
}
// 匹配则增加滑块长度，否则移动
if(!f)
{
// 滑块移动
if(ff)
{
wPos = nextSamePoint[wPos];
}
else
{
wPos++;
}
}
else
{
// 增加滑块长度
while(wPos + wLen != p && p + wLen != bufferLength && wLen < 1024)
{
if(buffer[wPos + wLen] == buffer[p + wLen])
{
wLen++;
}
else
{
break;
}
}
tPos = wPos;
tLen = wLen;
// 滑块移动并增加1长度
wPos = nextSamePoint[wPos];
wLen++;
}
}
//////////////////////////////////
// 写入buffer_zip
//////////////////////////////////
if(tPos == -1)
{
// 单个字节
tInt = (tInt << 9) + buffer[p];
tByteLen += 9;
p++;
}
else
{
// 匹配的字节串
tInt = (((tInt << 1) + 1 << 12) + tPos << 11) + tLen;
tByteLen += 24;
p += tLen;
}
while(tByteLen >= 8)
{
buffer_zip[++bufferDP] = (byte)(tInt >> (tByteLen -= 8) << 24 >> 24);
}
tInt = getRightByte(tInt, tByteLen); // 记录剩余信息
////////////////////////////////////
// 初始化滑块
////////////////////////////////////
wPos = 0;
wLen = 3;
tPos = -1;
tLen = 0;
}
// 写入剩余字节
for(int i = p; i < bufferLength; i++)
{
tInt = (tInt << 9) + buffer;
tByteLen += 9;
buffer_zip[++bufferDP] = (byte)(tInt >> (tByteLen -= 8));
tInt = getRightByte(tInt, tByteLen);
}
// 写入Stream
zipedData.Write(buffer_zip, 0, bufferDP + 1);
}
if(tByteLen != 0) zipedData.WriteByte((byte)(tInt << 8 - tByteLen)); // 写入剩余信息
data.Close();
zipedData.Close();
}
#endregion
#region 解压数据
public static void unzipData(string souceFilePath, string targetFilePath)
{
/////////////////////////////////
// 初始化变量
/////////////////////////////////
FileStream zipedData = new FileStream(souceFilePath, FileMode.Open);
FileStream data = new FileStream(targetFilePath, FileMode.Create);
uint wPos = 0, wLen = 0;
int buffer_zipLength = (int)zipedData.Length;
byte[] buffer = new byte[4096];
byte[] buffer_zip = new byte[buffer_zipLength];
int buffer_zipDP = -1;
int bufferDP = -1;
byte tByteLen = 0;
uint tInt = 0;
zipedData.Read(buffer_zip, 0, buffer_zipLength);
/////////////////////////////////
// 开始解压
/////////////////////////////////
while(buffer_zipDP < buffer_zipLength - 3)
{
// 写入前3个字节
tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
buffer[0] = (byte)(tInt >> tByteLen);
tInt = getRightByte(tInt, tByteLen);
tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
buffer[1] = (byte)(tInt >> tByteLen);
tInt = getRightByte(tInt, tByteLen);
tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
buffer[2] = (byte)(tInt >> tByteLen);
tInt = getRightByte(tInt, tByteLen);
bufferDP = 2;
while(bufferDP < 4095)
{
// 读入充足数据
while(tByteLen < 24 && buffer_zipDP < buffer_zipLength - 1)
{
tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
tByteLen += 8;
}
// 写入buffer
if(tInt >> tByteLen - 1 == 0)
{
// 单个字节
tByteLen -= 1;
tInt = getRightByte(tInt, tByteLen);
buffer[++bufferDP] = (byte)(tInt << 32 - tByteLen >> 24);
tByteLen -= 8;
tInt = getRightByte(tInt, tByteLen);
}
else
{
// 字节串
tByteLen -= 1;
tInt = getRightByte(tInt, tByteLen);
wPos = tInt >> (tByteLen -= 12);
tInt = getRightByte(tInt, tByteLen);
wLen = tInt >> (tByteLen -= 11);
tInt = getRightByte(tInt, tByteLen);
for(int i = 0; i < wLen; i++)
{
buffer[++bufferDP] = buffer[wPos + i];
}
}
// 判断是否解压完成
if(buffer_zipDP == buffer_zipLength - 1 && tByteLen < 9) break;
}
// 写入Stream
data.Write(buffer, 0, bufferDP + 1);
}
// 写入剩余的信息
for(int i = buffer_zipDP + 1 ; i < buffer_zipLength; i++)
{
data.WriteByte(buffer_zip);
}
zipedData.Close();
data.Close();
}
#endregion
#region private item
private static int getLeftByte(int dataLine, int s)
{
return dataLine << 32 - s >> 24;
}
private static uint getLeftByte(uint dataLine, int s)
{
return dataLine << 32 - s >> 24;
}
private static int getRightByte(int dataLine, int l)
{
if(l == 0)
{
return 0;
}
else
{
return dataLine << (32 - l) >> (32 -l);
}
}
private static uint getRightByte(uint dataLine, int l)
{
if(l == 0)
{
return 0;
}
else
{
return dataLine << (32 - l) >> (32 -l);
}
}
#endregion
}
No entiendo nada del trabajo con los operadores >>, <<, se que son para el corrimiento de bit pero no se como funciona, empiezo a hacer un traceo y me pierdo. Mi problema, me podrian ayudar a entender esto ? Gracias de todas formas.
Pd: disculpen lo largo....
Mostrar Mensajes
