Архивация.NEW!

Цитата maggot @ 27.03.08, 10:44

Сейчас я вам скажу способ идеального сжатия!!!

На входе алгоритма есть последовательность символов.
Находим в последовательности символов все возможные комбинации подпоследовательностей.
Это можно делать так же, как и строится контекстная модель. Только её глубину при максимальном сжатии нужно выбрать равной длине исходной последовательности. На практике при достаточно длинных последовательностях это не реализуемо ввиду большого расхода памяти. Поэтому её глубину можно выбирать разумно, чтобы хватило памяти.
Находим такую подпоследовательность, чтобы её длина была больше 1 и произведение её длины на количество её вхождений в исходную последовательность минус один было максимальным. L * (N - 1).
Расширяем алфавит символов ещё одним символом, который будет обозначать найденную подпоследовательность. Заменяем все её вхождения в исходную последовательность этим символом, а саму подпоследовательность добавляем в словарь.
Повторяем эти действия, пока не можно найти такие подпоследовательности. В итоге в исходной последовательности не останется ни одной пары рядом стоящих символов, которая бы повторялась два раза. То есть каждая пара рядом стоящих символов будет уникальна.
Далее полученную последовательность можно сжать арифметическим кодированием. Так же можно сжать некоторые последовательности из словаря.
Вот так вот!

cмешно и грустно.


Идеальное сжатие это ф-я копирования, это факт

Цитата esperanto @ 27.03.08, 11:37

Цитата maggot @ 27.03.08, 10:44

Сейчас я вам скажу способ идеального сжатия!!!

На входе алгоритма есть последовательность символов.
Находим в последовательности символов все возможные комбинации подпоследовательностей.
Это можно делать так же, как и строится контекстная модель. Только её глубину при максимальном сжатии нужно выбрать равной длине исходной последовательности. На практике при достаточно длинных последовательностях это не реализуемо ввиду большого расхода памяти. Поэтому её глубину можно выбирать разумно, чтобы хватило памяти.
Находим такую подпоследовательность, чтобы её длина была больше 1 и произведение её длины на количество её вхождений в исходную последовательность минус один было максимальным. L * (N - 1).
Расширяем алфавит символов ещё одним символом, который будет обозначать найденную подпоследовательность. Заменяем все её вхождения в исходную последовательность этим символом, а саму подпоследовательность добавляем в словарь.
Повторяем эти действия, пока не можно найти такие подпоследовательности. В итоге в исходной последовательности не останется ни одной пары рядом стоящих символов, которая бы повторялась два раза. То есть каждая пара рядом стоящих символов будет уникальна.
Далее полученную последовательность можно сжать арифметическим кодированием. Так же можно сжать некоторые последовательности из словаря.
Вот так вот!

cмешно и грустно.


Идеальное сжатие это ф-я копирования, это факт

Хах, может ты просто не понял, о чем я писал. По твоему такое сжатие не будет работать?

Не будет

Таак.
Тот алгоритм, который я описал, на практике наверное не применим (работает ооочень медленно), но он работает. И сжатие будет. Так что не гоните! Я его реализовал. Прямо точно так, как написал.

Ну для больших текстов сжатие будет, наверно. Но на универсвльный архиватор это естественно не тянет
Кстати, есть модификация LFF алгоритмов LZ, которая как раз и занимается поиском во входном потоке максимальных цепочек (независимо от их положения), которые затем сжимаются, и такая итерация повторяется. Вот только интересно, что сжатие самых длинных цепочек в результате не дает самого лучшего сжатия, а достигается оно при оптимальном разборе, нахождение которого есть NP-полная задача.

Цитата maggot @ 28.03.08, 17:15

Таак.
Тот алгоритм, который я описал, на практике наверное не применим (работает ооочень медленно), но он работает. И сжатие будет. Так что не гоните! Я его реализовал. Прямо точно так, как написал.

Т.е вы клянетесь, что ваш алгоритм работает?


Неубедительно. Все таки математика царица наук не просто так. И "мамой клянусь" не принимает

esperanto
Чесно говоря не понимаю, что смущает тебя...
Меня смущает только "подпоследовательность".
Автор имел ввиду, скорее всего, "цепочку символов".
Т.е. такие подпоследовательности, символы в которой стоят рядом.
В итоге получаем немного измененный LZ

Добавлено 28.03.08, 19:30
Ну еще вот это смущает:

Цитата

способ идеального сжатия!!!

Цитата Hsilgos @ 28.03.08, 19:29

esperanto
Чесно говоря не понимаю, что смущает тебя...
Меня смущает только "подпоследовательность".
Автор имел ввиду, скорее всего, "цепочку символов".
Т.е. такие подпоследовательности, символы в которой стоят рядом.
В итоге получаем немного измененный LZ

Добавлено 28.03.08, 19:30
Ну еще вот это смущает:

Цитата

способ идеального сжатия!!!

Меня смущает то, что автор привел алгоритм. Назвав его илеальным.


Мало того что не ясно что такое идеальный.
Не приведен анализ и доказательство работы алгоритма.

Цитата esperanto @ 28.03.08, 17:37

Цитата maggot @ 28.03.08, 17:15

Таак.
Тот алгоритм, который я описал, на практике наверное не применим (работает ооочень медленно), но он работает. И сжатие будет. Так что не гоните! Я его реализовал. Прямо точно так, как написал.

Т.е вы клянетесь, что ваш алгоритм работает?


Неубедительно. Все таки математика царица наук не просто так. И "мамой клянусь" не принимает

А если ты такой суперматематик, докажи, что в любом случае сжатия не будет. Или за весь курс математики выучил только то, что она царица наук? Я серьёзно. Докажи в таком случае, что алгоритм в любом случае не будет сжимать. А то вот так слово математика везде лепят в основном заучки-тугодумы - абсолютно бездарные математики.

Цитата

Не приведен анализ и доказательство работы алгоритма.

Его и не будет. И вообще алгоритм был придуман за время, когда я писал пост.

Цитата

Ну еще вот это смущает:
Цитата

Цитата

способ идеального сжатия!!!

А меня вся эта тема смущает. Вы что, верите, в то что придумаете алгоритм лучше существующих??

esperanto, а сама программа в прикреплённом файле.

А это код, если ты не веришь, что там этот алгоритм.

typedef std::basic_string<unsigned short int> mystring_type;
 
template<class T> class ContextModel{
    struct Node{
        struct pt{
            Node* _first;
            unsigned int _second;
            pt(): _second(0), _first(0){}
        };
        typedef Map<T, pt , NonHashed<VECTOR>, simpleLink> MapType;
        MapType transition;
        Node(){}
        void Print(const std::basic_string<T>& arg){
            for(MapType::iterator i = transition.first(); i; ++i){
                printString__(arg + (*i)._first);
                std::cout << " : " << ((*i)._second._second) << std::endl;
                if((*i)._second._first != 0) (*i)._second._first->Print(arg + (*i)._first);
            }
        }
    
        unsigned int getTheBest(unsigned int N, std::basic_string<T> & result){
            unsigned int maxFreq = 0;
            for(MapType::iterator i = transition.first(); i; ++i){
                std::basic_string<T> xStr;
                unsigned int xFreq = ((*i)._second._first != 0)?(*i)._second._first->getTheBest(N + 1, xStr) : 0;
                
                if(xFreq == 0 || ((N > 0) && (N + 1)*((*i)._second._second - 1) > (N + 1 + xStr.size())*(xFreq - 1))){
                    xStr = (*i)._first;
                    xFreq = (*i)._second._second;
                }else xStr = (*i)._first + xStr;
                if(maxFreq == 0 || ((N + xStr.size() > 1) && (N + xStr.size())*(xFreq - 1) > (N + result.size())*(maxFreq - 1))){
                    result = xStr;
                    maxFreq = xFreq;                
                }
            }
            return maxFreq;
        }
        ~Node(){
            for(MapType::iterator i = transition.first(); i; ++i)
                if((*i)._second._first != 0) delete (*i)._second._first;
        }
    };
    Node rootNode_;
    unsigned int depth_;
    void addSubstr(const std::basic_string<T>& arg, unsigned int index/*, unsigned int length*/){
        std::basic_string<T> x = arg.substr(index, depth_);
        Node *pNode = &rootNode_;
        for(unsigned int i = 0; i < x.size(); ++i){
            Node * nextNode = 0;
            try{nextNode = static_cast<Node::pt>(pNode->transition[x[i]])._first;} catch (const Out_Of_Range&){}
            if(nextNode == 0 && i != (x.size() - 1)) static_cast<Node::pt&>(pNode->transition[x[i]])._first = nextNode = new Node();
            ++static_cast<Node::pt&>(pNode->transition[x[i]])._second;
            pNode = nextNode;
        }
    }
public:
    ContextModel(unsigned int depth): depth_(depth){}
    void addString(const std::basic_string<T>& arg){
        for(unsigned int i = 0; i < arg.size(); ++i)
            addSubstr(arg, i);
        
    }
    void printCurrentState(){
        rootNode_.Print(std::basic_string<T>());
    }
    unsigned int getTheBestSubsting(std::basic_string<T>& result){
        unsigned int freq = rootNode_.getTheBest(0, result);
        return freq;
    }
};
class BitWriter{
    union BufT{
        unsigned __int64 asLongInt;
        unsigned int asUInt[2];
        unsigned char asUChar[8];
        char asChar[8];
    } buffer_;
    unsigned char shfind_;
    std::ofstream& stream_;
public:
    BitWriter(std::ofstream& stream): stream_(stream){buffer_.asLongInt = 0; shfind_ = 0;}
    void WriteBits(unsigned char bitscount, unsigned int data){
        bitscount %= 32;
        unsigned __int64 mask = 0x0000000000000000 | ((1 << bitscount) - 1);
        unsigned __int64 ldata = mask & data;
        buffer_.asLongInt |= ldata << (64 - shfind_ - bitscount);
        shfind_ += bitscount;
        while(shfind_ >= 8){
            stream_ << buffer_.asChar[7];
            buffer_.asLongInt <<= 8;
            shfind_ -= 8;
        }  
    }
    ~BitWriter(){
        stream_ << buffer_.asChar[7];
    }
};
 
void saveToFile(const Map<unsigned short int, mystring_type >& extCharsetTable, const mystring_type& dest_str, const char* destFName){
    std::ofstream oFile(destFName, std::ios::binary);
    BitWriter myBitWriter(oFile);
    myBitWriter.WriteBits(9, extCharsetTable.size());
    for(Map<unsigned short int, mystring_type >::iterator i = extCharsetTable.first(); i ; ++i){
        myBitWriter.WriteBits(2, (*i)._second.size() - 1);
        for(mystring_type::const_iterator j = (*i)._second.begin(); j != (*i)._second.end(); ++j)
            myBitWriter.WriteBits(9, *j);
    }
    myBitWriter.WriteBits(31, dest_str.size());
    for(mystring_type::const_iterator j = dest_str.begin(); j != dest_str.end(); ++j)
        myBitWriter.WriteBits(9, *j);
    
}
 
class BitReader{
    union BufT{
        unsigned __int64 asLongInt;
        unsigned int asUInt[2];
        unsigned char asUChar[8];
        char asChar[8];
    } buffer_;
    unsigned char shfind_;
    std::ifstream& stream_;
public:
    BitReader(std::ifstream& stream): stream_(stream){buffer_.asLongInt = 0; shfind_ = 0;}
    unsigned int ReadBits(unsigned char bitscount){
        bitscount %= 32;
        while(shfind_ < bitscount){
            buffer_.asLongInt <<= 8;
            stream_.get(buffer_.asChar[0]);
            shfind_ += 8;      
        }
        union{
            unsigned __int64 ldata;
            unsigned int asUInt[2];
        } x;
        x.ldata = buffer_.asLongInt;
        x.ldata >>= (shfind_ - bitscount);
        shfind_ -= bitscount;
        unsigned int mask = 0x00000000 | ((1 << bitscount) - 1);        
        unsigned int data = mask & x.asUInt[0];
        
        return data;
    }
};
void readFromFile(Map<unsigned short int, mystring_type >& extCharsetTable, mystring_type& dest_str, const char* destFName){
    std::ifstream iFile(destFName, std::ios::binary);
    BitReader myBitReader(iFile);
    unsigned int sz =  myBitReader.ReadBits(9);
    for(unsigned int i = 0; i < sz; ++i){
        mystring_type stri;
        unsigned int leng = myBitReader.ReadBits(2) + 1;
        for(unsigned int j = 0; j < leng; ++j)
            stri += static_cast<unsigned short>(myBitReader.ReadBits(9));
        extCharsetTable[256 + i] = stri;
    }
    unsigned int leng =  myBitReader.ReadBits(31);  
    for(unsigned int j =  0; j < leng; ++j)
        dest_str += static_cast<unsigned short>(myBitReader.ReadBits(9));  
}
 
 
void Compress(const char* sourceFName, const char* destFName){
    std::ifstream iFile(sourceFName, std::ios::binary);
    mystring_type mystr;
    char c;
    while (iFile.get(c)) mystr += 128 + c;
    unsigned int uncompressedStringSize = mystr.size();
 
    Map<unsigned short int, mystring_type > extendedCharsetTable;
    unsigned short int index = 255;
 
    std::cout << "Input file size: " << mystr.size() << " bytes" << std::endl;
    mystring_type bestStr;
    unsigned int maxCount = 255; //250
    do{
        
        ContextModel<unsigned short int> myCM(4);
        myCM.addString(mystr);
        unsigned int freq = myCM.getTheBestSubsting(bestStr);
        extendedCharsetTable[++index] = bestStr;
        std::cout << static_cast<char>(static_cast<unsigned char>(13)) << 100 * (255 - maxCount) / 255 << "% completed";
        
        mystring_type::iterator pos;
        pos = std::search (mystr.begin(), mystr.end(), bestStr.begin(),bestStr.end());
 
 
        while (pos != mystr.end()) {
            mystr.replace(pos, pos + bestStr.size(), 1, index);
            pos = std::search (mystr.begin(), mystr.end(), bestStr.begin(),bestStr.end());
        }
                --maxCount;
    } while(bestStr.size() > 1 && maxCount);
    std::cout << std::endl;
    unsigned int tblSize = 0;
    for(Map<unsigned short int, mystring_type >::iterator i = extendedCharsetTable.first(); i ; ++i) tblSize+= 2 + 9*((*i)._second.size());
    std::cout <<"Table size: " << tblSize/8 + 9 << " bytes" << std::endl;
    std::cout <<"Data size: " << 9*mystr.size()/8 + 31 << " bytes" << std::endl;
    std::cout <<"Compression : " << 100*(tblSize/8 + 9*mystr.size()/8 + 31 + 9) / uncompressedStringSize  << " %"<< std::endl;
 
    saveToFile(extendedCharsetTable, mystr, destFName);
}
void Decompress(const char* sourceFName, const char* destFName){
    mystring_type mystr2;
 
    Map<unsigned short int, mystring_type > extendedCharsetTable2;
    readFromFile(extendedCharsetTable2, mystr2, sourceFName);
    bool flag = true;
    while (flag){
        flag = false;
        mystring_type newString;
        for(unsigned int i = 0; i < mystr2.size(); ++i){
            unsigned int cChar = mystr2[i];
            if(cChar > 255){
                flag = true;
                newString += extendedCharsetTable2[cChar];
            }else newString += cChar;
        }
        mystr2 = newString;
    }
    std::cout << "Decompressed!" << std::endl;
    std::ofstream oFile(destFName, std::ios::binary);
    for(unsigned int i = 0; i < mystr2.size(); ++i){
        unsigned short int cChar = mystr2[i];
        if(cChar < 255) oFile << static_cast<char>(static_cast<int>(cChar) - 128);
    }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    _CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    
    if(argv[1] == std::string("compress"))
        Compress(argv[2], argv[3]);
    else if(argv[1] == std::string("decompress"))
        Decompress(argv[2], argv[3]);
    else std::cout << "compression.exe [compress/decompress] inputfile outputfile" << std::endl;
    return 0;
}

Сообщение отредактировано: maggot - 29.03.08, 09:38

Прикреплённый файлmycompression.rar (26.94 Кбайт, скачиваний: 193)

maggot, Как вы знаете "Один глупец может задавать вопросов на сотню мудрецов" (с)

Так вот, неужели вы думаете, я за свою жизнь преподавания и работы не встречал таких гениальных программистов как вы. "Я написал нечто докажите что это неправильно."
Не раз и не два.


Зачем?

Во-первых, это пустая трата, в данном случае, времени.
Во-вторых идеальным по шенону является то же энтропийное сжатие.
В-третих, вы даже не удосужились привести определение идеального.


Начните с определенния идеального алгоритма сжатия. Иначе разговор будет пустой тратой времени.

Цитата

Докажи в таком случае, что алгоритм в любом случае не будет сжимать

Цитата

Не возможно написать ВЗАИМНООДНОЗНАЧНУЮ функцию из пространства с большим числом измерений в меньшее. (поясню нельзя написать архиватор который для ЛЮБОГО ввода в 9 символов кодирует в 8)

Очень даже математически он доказал. Если не что-то непонятно - учи алгебру и ФАН.
Это значит, в частном случае, что для любого точного алгоритма можно найти такую последовательность символов, которую он не сожмет.

Добавлено 29.03.08, 10:48
http://ru.wikipedia.org/wiki/Арифметическое_кодирование

Добавлено 29.03.08, 10:54
Выдержка:

Цитата

Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона.
...
Однако в случае равновероятного распределения символов, например для строки бит 010101...0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.

[offtop

Цитата

А то вот так слово математика везде лепят в основном заучки-тугодумы - абсолютно бездарные математики.
Цитата
"Не приведен анализ и доказательство работы алгоритма."
Его и не будет. И вообще алгоритм был придуман за время, когда я писал пост.

Прямо comedy club на сорцах.
Вот на случай цитата от бездарного математика-тугодума:
"При грамотном программировании на тысячу строк программного текста нужно написать в десять раз больше рассуждений и доказательств, гарантирующих применимость программы".
Э. Дейкстра
offtop]

Цитата esperanto @ 29.03.08, 10:14

maggot, Как вы знаете "Один глупец может задавать вопросов на сотню мудрецов" (с)

Так вот, неужели вы думаете, я за свою жизнь преподавания и работы не встречал таких гениальных программистов как вы. "Я написал нечто докажите что это неправильно."
Не раз и не два.


Зачем?

Во-первых, это пустая трата, в данном случае, времени.
Во-вторых идеальным по шенону является то же энтропийное сжатие.
В-третих, вы даже не удосужились привести определение идеального.


Начните с определенния идеального алгоритма сжатия. Иначе разговор будет пустой тратой времени.

Да, это пустая трата времени, точно такая же, как и вся эта тема. Не понятно? Естественно, алгоритм не идеальный.
Я не претендую на изобретение нового алгоритма. Я просто написал очередной глупый ответ в эту тему. НО, заметьте, я же не написал полный бред, я за свои слова отвечаю - алгоритм работает и сжимает. Это можно проверить, запустив программу. А теоретически мне это доказывать неохото, да и я считаю, в этом нет смысла, тк алгоритм не эффективный.

А ваш опыт преподавания - это совсем не гарантия того, что вы всегда правы.
У меня был один учитель по программированию, который мне как то пытался объяснить, что указателя на указатель в языке программирования Паскале не может быть. Но вот моя программа почему то работала. Мне это тоже надо было доказывать?

Я не отрицаю роль доказтельств. Просто не во всех предметах можно строить хорошие доказательства. Можно в математическом анализе. В алгебре доказательства уже хуже. В теории графов тоже плохие. Хорошие - значит, что сложно усомниться в истинности этого доказтельства.

Цитата

В теории графов тоже плохие.

Наверное мы учили разные теории графов =)

А вообще, у нас в последнем семе на 5 курсе был веселый пропод. Проподавал препод "Историю математики".
И говорил он нам там удивительные вещи. В часности, что математика базируется на таких аксиомах, верность которых невозможно как доказать, так и опровергнуть.
Попал тогда под раздачу и матан, со своей "аксиомой выбора", о которой никто никогда не задумывался...
Основным его стремлением было донести, что все, что мы учили в универе, по сути, фуфло, и "строгой наукой" может назваться только с натяжкой. ( Тоже самое нам говорили на первом курсе про школьную математику =) )
Хороший был, препод, да...

Цитата Hsilgos @ 29.03.08, 11:36

И говорил он нам там удивительные вещи. В часности, что математика базируется на таких аксиомах, верность которых невозможно как доказать, так и опровергнуть.

Самое удивительное - то, что кто-то находт удивительным факт невозможности доказания аксиом.