Java プログラミングスキル - データ構造とアルゴリズム「ハフマンコーディング」

基本的な紹介

ハフマン符号化は、(ハフマンコーディング) とも訳されます。ハフマン符号化は、ハフマンコーディングとも呼ばれ、コーディング方法およびプログラムアルゴリズムです。
ハフマン符号化は、電気通信におけるハフマンツリーの典型的な応用シナリオの 1 つです。
ハフマン符号化はデータファイルの圧縮に広く使用されています。圧縮率は通常 20% から 90% の間です。
ハフマンコードは可変長符号化 (VLC) の一種です。ハフマンは 1952 年に、最適符号化と呼ばれる符号化方式を提案しました。

原理分析

通信分野における情報処理方式1：固定長符号化

たとえば、i like like like java do you like a javaはスペースを含めて合計40文字です。対応するASCIIコードとバイナリエンコードは次のとおりです。

バイナリデータの合計長は359（スペースを含む）です。

通信分野における情報処理方式2：可変長符号化

i like like like java do you like a java は、スペースを含めて合計 40 文字です。可変長エンコード処理は以下の通り

文字のエンコーディングは、他の文字エンコーディングのプレフィックスになることはできません。この要件を満たすエンコーディングはプレフィックスエンコーディングと呼ばれ、重複したエンコーディングは一致しないことを意味します。

通信分野における情報処理方法3：ハフマン符号化

i like like like java do you like a java は、スペースを含めて合計 40 文字です。可変長エンコード処理は以下の通り

上記の文字の出現回数を重みとして使用して、その回数に応じてハフマンツリーを構築します。

ハフマンツリーによれば、各文字にはコード (プレフィックスコード) が割り当てられ、左へのパスは 0、右へのパスは 1 です。コードは次のようになります。

上記のハフマン符号化によれば、「i like like like java do you like a java」という文字列に対応するエンコードは次のようになります (ここではロスレス圧縮を使用していることに注意してください)。

例:

元の長さは359で、(359-133)/359=62.9%に圧縮されます。

このエンコーディングはプレフィックスエンコーディングの要件を満たしています。つまり、文字のエンコーディングは他の文字エンコーディングのプレフィックスになることはできません。一致の曖昧さは発生しません。

ハフマン符号化はロスレス圧縮です!!

知らせ：

このハフマンツリーはソート方法によって異なる場合があり、対応するハフマンコードはまったく同じではありませんが、wpl は同じで、最小になります。たとえば、新しく生成されたバイナリツリーを、同じ重みを持つバイナリツリーの中で常に最後にランク付けすると、生成されたバイナリツリーは次のようになります。

対応するハフマン木を作成する

データを圧縮するためのハフマン符号化の原理によれば、「私はJavaが好きですか、あなたはJavaが好きですか」に対応するハフマンツリーを作成する必要があります。

アイデア:

まず、Node ノードを作成します。Node {data{store data}, weight (weight), left, right};

「i like like like java do you like a java」に対応する byte[] 配列を取得します。

ハフマンツリーに構築するノードをリストに入れるメソッドを記述します。集める;

コレクションリストを使用することができます対応するハフマンツリーを作成します。

ハフマンツリーの応用例

文字列を圧縮および解凍する

パッケージ com.xie.huffmancode; 
 
 java.util.* をインポートします。 
 
パブリッククラスHuffmanCode {
公共 静的void main(String[] args) {
        文字列 str = "私は Java が好きです、あなたは Java が好きですか" ;
        byte[] contentBytes = str.getBytes();
        システム.out .println( "contentBytes=" + Arrays.toString(contentBytes));
        リスト<Node> ノード = getNodes(contentBytes); 
 
        //ハフマン木を生成する
        ノード hufffmanTreeRoot = createHufffmanTree(nodes); 
 
        //生成されたハフマン符号化テーブル
        getCodes(hufffmanTreeRoot, "" , stringBuilder); 
 
        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
        システム.out.println ( "huffmanCodeBytes = " + Arrays.toString(huffmanCodeBytes)); 
 
        byte[] デコード = decode(huffmanCodes、huffmanCodeBytes);
        System.out.println ( "ハフマンデコード後の対応する配列" + new String(decode)); 
 
        /**
         107、101、32、108、105、107、101、32、108、105、107、101、32、106、97、118、97、32、100、111、32、121、111、117、32、108、105、107、101、32、97、32、106、97、118、97]
         * ハフマンコードバイト = [-88、-65、-56、-65、-56、-65、-55、77、-57、6、-24、-14、-117、-4、-60、-90、28]
         * ハフマンデコード後の対応する配列は次のようになります のように  Javaが好きですか？ Javaが好きですか？
         */ 
 
    } 
 
    //データを解凍するというアイデアを完成させる
    //1. ハフマンコードバイト[-88、-65、-56、-65、-56、-65、-55、77、-57、6、-24、-14、-117、-4、-60、-90、28]
    // ハフマン コード"101010001011111111001000101111...."に対応するバイナリ文字列に変換します。  
    //2. ハフマン コーディングに対応するバイナリ文字列"101010001011111111001000101111...." => ハフマン コーディング テーブルを比較 => "i like like like java do you like a java"   
 
    /**
     * 圧縮データのデコードを完了する
     *
     * @param huffmanCodes ハフマンコーディングテーブル
     * @param huffmanBytes ハフマンエンコードによって得られたバイト配列
     * @return元の文字列に対応する配列
     */
公共 静的byte[]デコード(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        StringBuilder の stringBuilder = 新しい StringBuilder();
 ( int i = 0; i < huffmanBytes.length; i++) {
            // 最後のバイトかどうかをチェックする
            ブールフラグ = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, huffmanBytes[i]));
        } 
 
        Map<String, Byte> map = new HashMap<>();
 Map.Entry<Byte, String> エントリの場合: huffmanCodes.entrySet()) {
            バイト k = entry.getKey();
            文字列 v = entry.getValue();
            map.put(v, k);
        } 
 
        リスト<Byte> リスト = 新しい ArrayList<>();
 ( int i = 0; i < stringBuilder.length();)の場合{
整数 カウント= 1;
            ブールフラグ = true ;
            バイト b = null ;
            while (フラグ) {
                String key = stringBuilder.substring ( i, i + count ); //i は変化せず、文字が一致するまでcountが移動します
                b = map.get(キー);
                b == null の場合
カウント++;
                }それ以外{
                    フラグ = false ;
                }
            }
            リストに追加(b);
            i +=カウント;
        }
        byte[] bytes = 新しいbyte[ list.size ()];
 ( int i = 0; i < list.size ( ) ); i++) {
            バイト[i] = list.get(i);
        }
バイトを返します。
    } 
 
    /**
     * バイトをバイナリ文字列に変換する
     *
     * @param フラグは、上位ビットを埋める必要があるかどうかを示します。 trueの場合、上位ビットを埋める必要があることを示します。 falseの場合、埋める必要がないことを意味します。最後のバイトの場合、上位ビットを埋める必要はありません。
     * @param b 受信バイト
     * @returnバイトに対応するバイナリ文字列（補数で返されることに注意してください）
     */
公共 静的文字列 byteToBitString(boolean flag, byte b) {
        //bをintに変換する 
整数 温度= b; 
 
        // tempが正の数の場合は、上位ビットを埋める必要があります
        if (フラグ) {
            // ビット単位の OR、例えば 256|1=> 1 0000 0000|0000 0001 => 1 0000 0001
温度|= 256;
        } 
 
        //返される値はtempの2進数の補数です
        文字列 bitStr = Integer .toBinaryString( temp );
        if (フラグ) {
            // 最後の8ビットを取得します
bitStr.substring ( bitStr.length () - 8)を返します。
        }それ以外{
 bitStrを返します。
        }
    } 
 
    /**
     * 元のバイト配列をハフマンバイト配列にカプセル化する
     *
     * @param バイト
     * @戻る 
     */
公共 静的byte[] huffmanZip(byte[] バイト) {
        リスト<Node> ノード = getNodes(bytes); 
 
        //ハフマン木を作成する
        ノード hufffmanTreeRoot = createHufffmanTree(nodes);
        //ハフマンコードを生成する
        getCodes(hufffmanTreeRoot, "" , stringBuilder);
        //圧縮されたハフマンエンコードされたバイト配列を返す
zip(bytes, huffmanCodes)を返します。 
 
    } 
 
    /**
     * 文字列に対応するbyte[]配列をハフマン符号化テーブルに渡し、ハフマン符号化された圧縮byte[]を返す
     *
     * @param bytes 元の文字列に対応するbyte[]
     * @param huffmanCodes 生成されたハフマンコード
     * @returnハフマン符号化後のbyte[]を返します
     */
公共 静的byte[] zip(byte[] バイト、Map<Byte、String> huffmanCodes) {
        //huffmanCodesを使用してバイトをハフマンコードに対応する文字列に変換します
        StringBuilder の stringBuilder = 新しい StringBuilder();
 (バイトb:バイト)の場合{
            文字列ビルダーに追加します(huffmanCodes.get(b));
        } 
 
        // "10101000101111111001000101111...."を byte[] に変換します
        // 統計はbyte[] huffmanCodeBytesの長さを返す
長さ;
        (stringBuilder.length() % 8 == 0) の場合 {
            len = stringBuilder.length() / 8;
        }それ以外{
            len = stringBuilder.length() / 8 + 1;
        }
        //圧縮されたデータを格納するためのbyte[]配列を作成する
        byte[] huffmanCodeBytes = 新しいbyte[len];
整数 インデックス= 0;
 ( int i = 0 ; i < stringBuilder.length(); i += 8) {
            文字列 strByte;
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring (i);
            }それ以外{
                strByte = stringBuilder.substring (i, i + 8);
            }
            //strByte をバイトに変換し、huffmanCodeBytes に格納します
            huffmanCodeBytes[インデックス] = (バイト) Integer .parseInt(strByte, 2);
インデックス++;
        }
 huffmanCodeBytesを返します。
    } 
 
    //ハフマン木に対応するハフマン符号化テーブルを生成する
    // アイデア:
    //1. ハフマン符号化テーブルを 32->01,97->100... の形式で Map<Byte,String> に格納します。
静的Map<Byte, String> huffmanCodes = new HashMap<>();
    //2. ハフマンコーディングテーブルを生成するときは、パスを連結し、リーフノードのパスを格納するStringBuilderを定義する必要があります。
静的StringBuilder stringBuilder = 新しい StringBuilder(); 
 
    /**
     * 渡されたノードのすべてのリーフのハフマンコードを取得し、それらをhuffmanCodesセットに格納します。
     *
     * @param node 受信ノード
     * @param コードパス: 左の子ノードは 0、右の子ノードは 1
     * @param stringBuilderはパスを連結するために使用されます
     */
公共 静的void getCodes(Node ノード、文字列コード、StringBuilder 文字列ビルダー) {
        StringBuilder の stringBuilder2 = 新しい StringBuilder(stringBuilder);
        stringBuilder2.append(コード);
        if (ノード != null ) {
            //現在のノードがリーフノードか非リーフノードかを判断する
            if (node.data == null ){//非リーフノード
 
                //左への再帰処理
                getCodes( node.left , "0" , stringBuilder2);
                //右方向への再帰処理
                getCodes( node.right , "1" , stringBuilder2);
            } else {// リーフノード
                huffmanCodes.put(node.data、stringBuilder2.toString());
            }
        }
    } 
 
    // 事前順序トラバーサル
公共 静的void preOrder(ノードルート) {
        ルートがnullの場合
            ルートを事前注文します。
        }それ以外{
            System.out.println ( "ハフマンツリーは空にできません~~" );
        }
    } 
 
    /**
     * バイト配列をノードコレクションに変換する
     *
     * @param bytes バイト配列
     * @戻る 
     */
公共 静的リスト<Node> getNodes(byte[] bytes) {
        ArrayList<Node> ノード = 新しい ArrayList<>(); 
 
        //各バイトの出現回数を保存する
        Map<Byte, Integer > counts = new HashMap<>();
 (バイトb:バイト)の場合{
            counts.merge(b, 1, (a, b1) -> a + b1);
        } 
 
        //各キーと値のペアをノード オブジェクトに変換し、ノード コレクションに追加します。
        counts.forEach((k, v) -> nodes.add(新しい Node(k , v)));
ノードを返します。
    } 
 
    /**
     * ハフマン木を生成する
     * @param nodes 渡されたノード
     * @戻る 
     */
公共 静的ノードcreateHufffmanTree(List<Node>ノード) {
        ノードサイズ() > 1の場合{
            // 小さい順から大きい順に並べ替える
            コレクション.sort(ノード); 
 
            //(1) 重みが最小のノードを取り出す（二分木）
            ノード leftNode = nodes.get(0); 
 
            //(2) 2番目に小さい重みを持つノードを取り出す（二分木）
            ノード rightNode = nodes.get(1);
            //(3) 新しいバイナリツリーを構築する
            ノードの親 = 新しいノード ( null 、 leftNode.weight + rightNode.weight )。
            親.left = leftNode ;
            親.right = rightNode ; 
 
            //(4) ArrayListから処理済みのバイナリツリーを削除する
            ノードを削除します(左ノード)。
            ノードを削除します。(右ノード)
            //(5) ノードに親を追加する
            nodes.add (親);
        }
        //ノードの最後のノードはハフマン木のルートノードです
nodes.get(0)を返します。
    }
 } 
 
 //データと重みを持つノードを作成する
クラスNodeはComparable<Node>を実装します。
    //データ自体を保存します。たとえば、 'a' => '97' 、 ' ' => '32'  
    バイトデータ。
    //重み、文字の出現回数を示す
整数の重量; 
 
    ノード左;
    ノード右; 
 
パブリックノード(バイトデータ、 int重み) {
        this.data = データ;
        this.weight = 重量;
    } 
 
パブリックボイドpreOrder() {
        System.out.println (これ) ;
        if ( this.left != null ) {
            this.left.preOrder ();
        }
        if ( this.right != null ) {
            this.right .preOrder();
        }
    } 
 
    @オーバーライド
公共  int compareTo(ノードo) {
        // 小さい順から大きい順に並べ替える
this.weight - o.weightを返します。
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ノード{」 +
 「データ=」 + データ +
 ", 重量=" + 重量 +
 '}' ;
    }
 }