SCIP in C++11 ― 2.3.4節

Huffman符号と問題2.67～2.70

ふーん、ウィキペによるとJPEGやZIPのエンコードで実際に使われてるのか。

make-leafが自前のListのLeafを作る関数と名前がかぶってしまっているので、

makeHuffmanLeafとかにする。ちょっと長いなあ。

ちゃんとやろうと思ったら、namespaceとかしっかりしないといけないが、

面倒なのでそこまではしない。

問題2.71, 2.72は特にコードを書かないので略。

いや大事な問題だし解いてるけど、SICPの問題解説サイトは他にいくらでもあるから、

そちらに譲る。

----

//---------abstraction barrier---------

typedef int Weight;

typedef string Symbol;

typedef List HuffmanTree;

const HuffmanTree makeHuffmanLeaf

(const List& leafSymbol,const List& leafWeight)

{return(makeList(makeLeaf("leaf"),leafSymbol,leafWeight));}

template<typename SymbolType>

const HuffmanTree makeHuffmanLeaf

(const SymbolType& leafSymbol,const Weight& leafWeight)

{return(makeHuffmanLeaf(makeLeaf(leafSymbol),makeLeaf(leafWeight)));}

template<typename SymbolType>

const HuffmanTree makeHuffmanLeaf

(const SymbolType& leafSymbol,const List& leafWeight)

{return(makeHuffmanLeaf(makeLeaf(leafSymbol),leafWeight));}

const HuffmanTree makeHuffmanLeaf

(const List& leafSymbol,const Weight& leafWeight)

{return(makeHuffmanLeaf(leafSymbol,makeLeaf(leafWeight)));}

const bool isHuffmanLeaf(const HuffmanTree& object)

{

    return(isEq("leaf",car(object)));

}

const Symbol symbolLeaf(const HuffmanTree& x)

{return(value<Symbol>(cadr(x)));}

const Weight weightLeaf(const HuffmanTree& x)

{return(value<Weight>(caddr(x)));}

const List symbols(const HuffmanTree& tree)

{

    if(isHuffmanLeaf(tree)){return(makeList(symbolLeaf(tree)));}

    return(caddr(tree));

}

const Weight weight(const HuffmanTree& tree)

{

    if(isHuffmanLeaf(tree)){return(weightLeaf(tree));}

    return(value<Weight>(cadddr(tree)));

}

const HuffmanTree makeCodeTree

(const HuffmanTree left, const HuffmanTree& right)

{

    return(makeList(left,right,append(symbols(left),symbols(right)),

                    weight(left)+weight(right)));

}

const HuffmanTree leftBranch(const HuffmanTree& tree)

{return(car(tree));}

const HuffmanTree rightBranch(const HuffmanTree& tree)

{return(cadr(tree));}

const HuffmanTree chooseBranch

(const List& bit, const HuffmanTree& branch)

{

    if(isEqual(0,bit)){return(leftBranch(branch));}

    if(isEqual(1,bit)){return(rightBranch(branch));}

    cerr<<"bad bit -- CHOOSE-BRANCH "<<listString(bit)<<endl;

    return(makeList());

}

const List decode(const List& bits, const HuffmanTree& tree)

{

    function<List(List,HuffmanTree)> decode1;

    decode1=[&decode1,tree](const List& bits,

                       const HuffmanTree& currentBranch)

        {

            if(isNull(bits)){return(makeList());}

            const HuffmanTree nextBranch

            (chooseBranch(car(bits),currentBranch));

            if(isHuffmanLeaf(nextBranch)){

                return(cons(symbolLeaf(nextBranch),

                            decode1(cdr(bits),tree)));

            }

            return(decode1(cdr(bits),nextBranch));

        };

    return(decode1(bits,tree));

}

const List encodeSymbol

(const List& symbolLeaf,const HuffmanTree& tree)

{

    if(!isElementOfSet(symbolLeaf,symbols(tree))){

        cerr<<"The specified symbol is not in the code book."<<endl;

        exit(1);

    }

    function<List(HuffmanTree)> encode1;

    encode1=[&encode1,symbolLeaf]

        (const HuffmanTree& currentBranch){

        if(isHuffmanLeaf(currentBranch)){return(makeList());}

        if(isElementOfSet(symbolLeaf,symbols(leftBranch(currentBranch))))

            {return(cons(0,encode1(leftBranch(currentBranch))));}

        return(cons(1,encode1(rightBranch(currentBranch))));

    };

    return(encode1(tree));

}

const List encode(const List& message, const HuffmanTree& tree)

{

    if(isNull(message)){return(makeList());}

    return(append(encodeSymbol(car(message),tree),

                  encode(cdr(message),tree)));

}

const HuffmanTree adjoinSet(const HuffmanTree& xLeaf,

                            const HuffmanTree& setTree)

{

    if(isNull(setTree)){return(makeList(xLeaf));}

    if(weight(xLeaf)<weight(car(setTree))){return(cons(xLeaf,setTree));}

    return(cons(car(setTree),adjoinSet(xLeaf,cdr(setTree))));

}

const HuffmanTree makeLeafSet(const List& pairs)

{

    if(isNull(pairs)){return(makeList());}

    const List pair(car(pairs));

    return(adjoinSet(makeHuffmanLeaf(car(pair),cadr(pair)),

                     makeLeafSet(cdr(pairs))));

}

const HuffmanTree successiveMerge(const List& leafSet)

{

    if(isNull(cdr(leafSet))){return(car(leafSet));}

    return(successiveMerge

           (adjoinSet

            (makeCodeTree

             (car(leafSet),cadr(leafSet)),cddr(leafSet))));

}

const HuffmanTree generateHuffmanTree(const List& pairs)

{

    return(successiveMerge(makeLeafSet(pairs)));

}

//---------abstraction barrier---------

int main(int argc, char** argv)

{

    cout<<"Excersize 2.67:"<<endl;

    const auto sampleTree

        (makeCodeTree

         (makeHuffmanLeaf("A",4),

          makeCodeTree

          (makeHuffmanLeaf("B",2),

           makeCodeTree

           (makeHuffmanLeaf("D",1),makeHuffmanLeaf("C",1)))));

    const auto sampleMessage(makeList(0,1,1,0,0,1,0,1,0,1,1,1,0));

    const auto decodedMessage(decode(sampleMessage,sampleTree));

    cout<<"sample-tree = "<<endl<<listString(sampleTree)<<endl;

    cout<<"sample-message = "<<listString(sampleMessage)<<endl;

    cout<<"(decode sample-message sample-tree) = "

        <<listString(decodedMessage)<<endl;

    cout<<endl<<"Excersize 2.68:"<<endl;

    const auto encodedMessage(encode(decodedMessage,sampleTree));

    cout<<"(encode (decode sample-message sample-tree) sample-tree) = "

        <<endl<<listString(encodedMessage)<<endl;

    cout<<endl<<"Excersize 2.69:"<<endl;

    const auto sampleList

        (makeList

         (makeList("A",4),makeList("B",2),

          makeList("C",1),makeList("D",1)));

    cout<<"sample-list = "<<listString(sampleList)<<endl;

    cout<<"(generate-huffman-tree sample-list) = "<<endl

        <<listString(generateHuffmanTree(sampleList))<<endl;

   

    cout<<endl<<"Excersize 2.70:"<<endl;

    const auto RockLylicParts

        (makeList

         (makeList("a",2),makeList("boom",1),

          makeList("Get",2),makeList("job",2),

          makeList("na",16),makeList("Sha",3),

          makeList("yip",9),makeList("Wah",1)));

    const auto lylic

        (makeList("Get","a","job",

                  "Sha","na","na","na","na","na","na","na","na",

                  "Get","a","job",

                  "Sha","na","na","na","na","na","na","na","na",

                  "Wah","yip","yip","yip","yip","yip",

                  "yip","yip","yip","yip",

                  "Sha","boom"));

    const auto encodedLylic(encode(lylic,generateHuffmanTree(RockLylicParts)));

    cout<<listString(encodedLylic)<<endl;

    cout<<length(encodedLylic)<<"bits"<<endl;

    return(0);

}

----

出力

----

Excersize 2.67:

sample-tree =

(('leaf 'A 4) (('leaf 'B 2) (('leaf 'D 1) ('leaf 'C 1) ('D 'C) 2) ('B 'D 'C) 4) ('A 'B 'D 'C) 8)

sample-message = (0 1 1 0 0 1 0 1 0 1 1 1 0)

(decode sample-message sample-tree) = ('A 'D 'A 'B 'B 'C 'A)

Excersize 2.68:

(encode (decode sample-message sample-tree) sample-tree) =

(0 1 1 0 0 1 0 1 0 1 1 1 0)

Excersize 2.69:

sample-list = (('A 4) ('B 2) ('C 1) ('D 1))

(generate-huffman-tree sample-list) =

(('leaf 'A 4) (('leaf 'B 2) (('leaf 'D 1) ('leaf 'C 1) ('D 'C) 2) ('B 'D 'C) 4) ('A 'B 'D 'C) 8)

Excersize 2.70:

(1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

84bits