Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Правильность работы алгоритма LZW

86K
20 марта 2013 года
203
3 / / 20.02.2013
Здравствуйте. Помогите пожалуйста разобраться в коде. Есть реализация lzw, но я не могу понять правильно он работает или нет и вообще по какому принципу работает код. Пример: я ввожу строку "abacabadabacabae" для кодировке, на выходе я получаю "abacĀadĄăāe" правильно ли это я не знаю. Прошу вашей помощи, заранее спасибо.
Код:
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();
        }
    }
}
326
06 мая 2013 года
sadovoya
757 / / 19.11.2005
Ну, даже в Wiki есть разбор примера.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог