บทนำการเข้ารหัส Huffman
การเข้ารหัส Huffman เกี่ยวข้องกับปัญหาการจับคู่การเข้ารหัสของอักขระและไบนารีที่สอดคล้องกับตัวละครซึ่งแบ่งออกเป็นการเข้ารหัสและการถอดรหัสโดยมีวัตถุประสงค์เพื่อบีบอัดความยาวของข้อมูลไบนารีที่สอดคล้องกับอักขระ เรารู้ว่าเมื่อตัวละครถูกจัดเก็บและถ่ายโอนพวกเขาจะเป็นไบนารี (คอมพิวเตอร์รู้เพียง 0/1) ดังนั้นจึงมีความสัมพันธ์การทำแผนที่ระหว่างตัวละครและไบนารี อักขระอยู่ในชุดอักขระ (charset) ตัวละครจะต้องจัดเก็บและส่งในไบนารีผ่านการเข้ารหัส เมื่อแสดงพวกเขาจะต้องถอดรหัสกลับไปที่ตัวละคร ชุดอักขระและวิธีการเข้ารหัสเป็นความสัมพันธ์แบบหนึ่งต่อหลายคน (Unicode สามารถเข้ารหัสด้วย UTF-8, UTF-16 ฯลฯ ) หลังจากทำความเข้าใจกับชุดอักขระการเข้ารหัสและถอดรหัสปัญหาของรหัสที่อ่านไม่ออกที่บินไปทั่วท้องฟ้าสามารถแก้ไขได้อย่างง่ายดาย การใช้ตัวพิมพ์เล็ก A ของตัวอักษรภาษาอังกฤษเป็นตัวอย่างในการเข้ารหัส ASCII ทศนิยมคือ 97 และไบนารีคือ 01100001 ตัวละครแต่ละตัวใน ASCII จะถูกเข้ารหัสด้วย 8 บิต (1BYTE) หากมีการส่งอักขระ 1,000 ตัวต้องส่ง 8000 บิต ปัญหาคือความถี่ของการใช้ตัวอักษร E เป็นภาษาอังกฤษคือ 12.702%ในขณะที่ Z คือ 0.074% อดีตมีมากกว่า 100 เท่าของหลัง แต่ใช้ไบนารีที่มีตัวเลขเดียวกัน มันสามารถทำได้ดีกว่าวิธีการเข้ารหัสความยาวตัวแปร หลักการชี้นำคือการเข้ารหัสความถี่ที่สูงขึ้นด้วยตัวเลขที่สั้นกว่าและผู้ที่มีความถี่ต่ำที่มีตัวเลขนานขึ้น อัลกอริทึมการเข้ารหัส Huffman เกี่ยวข้องกับปัญหาดังกล่าว
Huffman เข้ารหัสการใช้งาน Java
โครงสร้างข้อมูลส่วนใหญ่ใช้โดยอัลกอริทึมการเข้ารหัส Huffman คือต้นไม้ไบนารีเต็มรูปแบบและคิวลำดับความสำคัญ หลังใช้ java.util.priorityqueue และอดีตใช้ตัวเอง (ทั้งหมดเป็นคลาสภายใน) รหัสมีดังนี้:
ต้นไม้คลาสคงที่ {รูทโหนดส่วนตัว; โหนดสาธารณะ getRoot () {return root; } โมฆะสาธารณะ setroot (โหนดรูท) {this.root = root; }} โหนดคลาสแบบคงที่ใช้การเปรียบเทียบ <node> {สตริงส่วนตัว chars = ""; ความถี่ int ส่วนตัว = 0; ผู้ปกครองโหนดส่วนตัว; โหนดส่วนตัวซ้าย โหนดส่วนตัวขวา @Override สาธารณะ int compereto (node n) {ความถี่ส่งคืน - n.frequency; } บูลีนสาธารณะ isleaf () {return chars.length () == 1; } บูลีนสาธารณะ isroot () {return parent == null; } บูลีนสาธารณะ isleftchild () {return parent! = null && this == parent.leftnode; } public int getFrequence () {ความถี่ส่งคืน; } โมฆะสาธารณะ setFrequence (ความถี่ int) {this.frequency = ความถี่; } สตริงสาธารณะ getChars () {return chars; } โมฆะสาธารณะ setChars (chars สตริง) {this.chars = chars; } โหนดสาธารณะ getParent () {return parent; } โมฆะสาธารณะ setParent (โหนดพาเรนต์) {this.parent = parent; } โหนดสาธารณะ getLeftNode () {return leftNode; } โมฆะสาธารณะ setleftNode (โหนดซ้าย) {this.leftNode = leftNode; } โหนดสาธารณะ getrightNode () {return rightNode; } โมฆะสาธารณะ setrightNode (โหนดขวา) {this.rightNode = rightNode; - สถิติ
เนื่องจากจำเป็นต้องจัดตารางการเข้ารหัสตามความถี่แน่นอนคุณต้องได้รับข้อมูลทางสถิติของความถี่ ฉันใช้วิธีการจัดการกับปัญหาดังกล่าว หากมีสถิติอยู่แล้วให้แปลงเป็นแผนที่ <อักขระจำนวนเต็ม> หากข้อมูลที่คุณได้รับคือเปอร์เซ็นต์ให้คูณด้วย 100 หรือ 1,000 หรือ 10,000 มันสามารถแปลงเป็นจำนวนเต็มได้เสมอ ตัวอย่างเช่น 12.702% คูณด้วย 1,000 คือ 12702 และการเข้ารหัส Huffman เพียงแค่ใส่ใจกับปัญหาขนาดเท่านั้น วิธีการทางสถิติถูกนำไปใช้ดังนี้:
แผนที่สาธารณะคงที่ <อักขระ, จำนวนเต็ม> สถิติ (char [] chararray) {แผนที่ <อักขระ, จำนวนเต็ม> map = new hashmap <อักขระ, จำนวนเต็ม> (); สำหรับ (charc c: chararray) {ตัวละคร = ตัวละครใหม่ (c); if (map.containskey (อักขระ)) {map.put (อักขระ, map.get (อักขระ) + 1); } else {map.put (อักขระ, 1); }} คืนแผนที่; - สร้างต้นไม้
การสร้างต้นไม้เป็นขั้นตอนหลักในอัลกอริทึมการเข้ารหัส Huffman แนวคิดคือการแขวนอักขระทั้งหมดบนโหนดใบไม้ของต้นไม้ไบนารีอย่างสมบูรณ์และความถี่ของโหนดซ้ายของโหนดเด็กที่ไม่ใช่หน้าใด ๆ ไม่ปรากฏมากกว่าโหนดขวา อัลกอริทึมแปลงสถิติเป็นโหนดและเก็บไว้ในคิวลำดับความสำคัญ ทุกครั้งที่สองโหนดที่มีความถี่ต่ำสุดจะปรากฏขึ้นจากคิวโหนดพาเรนต์ใหม่ (โหนดที่ไม่ใช่ใบ) จะถูกสร้างขึ้น ผลรวมของทั้งสองโหนดที่มีเนื้อหาตัวละครปรากฏขึ้นและความถี่ก็เป็นผลรวมของพวกเขา ป๊อปอัพตัวแรกถูกใช้เป็นโหนดลูกด้านซ้ายและโทนถัดไปจะใช้เป็นโหนดลูกที่เหมาะสมและโหนดพาเรนต์ที่สร้างขึ้นใหม่จะถูกวางไว้ในคิว ทำซ้ำการกระทำข้างต้น N-1 ครั้งคือจำนวนอักขระที่แตกต่างกัน (จำนวนในคิวลดลง 1 ในแต่ละครั้ง) สิ้นสุดขั้นตอนข้างต้นมีโหนดที่เหลืออยู่ในคิวและโหนดรูทของต้นไม้จะปรากฏขึ้น รหัสมีดังนี้:
Tree Static Tree Private Tree (แผนที่ <อักขระ, จำนวนเต็ม> สถิติ, รายการ <node> ใบไม้) {อักขระ [] keys = statistics.keyset (). toarray (อักขระใหม่ [0]); PriorityQueue <Node> priorityQueue = new PriorityQueue <Node> (); สำหรับ (อักขระอักขระ: ปุ่ม) {node node = new node (); node.chars = character.toString (); node.frequency = statistics.get (อักขระ); PriorityQueue.add (Node); ใบไม้. add (โหนด); } ขนาด int = priorityQueue.size (); สำหรับ (int i = 1; i <= size - 1; i ++) {node node1 = priorityqueue.poll (); Node Node2 = priorityQueue.poll (); โหนด sumnode = new node (); sumnode.chars = node1.chars + node2.chars; sumnode.frequency = node1.fraquence + node2.fraquence; sumnode.leftNode = node1; sumnode.rightNode = node2; node1.parent = sumnode; node2.parent = sumnode; priorityqueue.add (sumnode); } ต้นไม้ต้นไม้ = ต้นไม้ใหม่ (); tree.root = priorityqueue.poll (); ต้นไม้กลับ; - การเข้ารหัส
การเข้ารหัสอักขระที่สอดคล้องกันคือการค้นหาจากโหนดใบไม้ที่มีตัวละครอยู่ หากโหนดอักขระเป็นโหนดด้านซ้ายของโหนดพาเรนต์ให้เพิ่ม 0 ก่อนที่อักขระที่เข้ารหัสมิฉะนั้นถ้าเป็นโหนดที่ถูกต้องให้เพิ่ม 1 จนกว่าโหนดรูท ตราบใดที่ได้รับความสัมพันธ์ระหว่างตัวละครและรหัสไบนารีการเข้ารหัสนั้นง่ายมาก รหัสมีดังนี้:
String String สาธารณะเข้ารหัส (String OriginalSTR, MAP <อักขระ, จำนวนเต็ม> สถิติ) {ถ้า (OriginalStr == NULL || OriginalStr.equals ("")) {return ""; } char [] chararray = Originalstr.toChararray (); รายการ <node> lefnodes = new ArrayList <Node> (); buildtree (สถิติ, leafnodes); แผนที่ <อักขระ, สตริง> encodinfo = buildencodingInfo (leafnodes); StringBuffer buffer = new StringBuffer (); สำหรับ (char c: chararray) {อักขระตัวละคร = ตัวละครใหม่ (c); buffer.append (encodinfo.get (ตัวละคร)); } return buffer.toString (); } แผนที่คงที่ส่วนตัว <อักขระ, สตริง> buildenCodingInfo (รายการ <node> leafnodes) {แผนที่ <อักขระ, สตริง> codewords = new hashmap <อักขระ, สตริง> (); สำหรับ (โหนด leafnodes: leafnodes) {ตัวละครอักขระ = ตัวละครใหม่ (leafnode.getChars (). Charat (0)); String codeword = ""; โหนด currentNode = lefnode; ทำ {ถ้า (currentNode.isleftchild ()) {codeword = "0" + codeword; } else {codeword = "1" + codeword; } currentNode = currentNode.parent; } ในขณะที่ (currentNode.parent! = null); codewords.put (อักขระ, codeword); } ส่งคืน codewords; - การถอดรหัส
เนื่องจากอัลกอริทึมการเข้ารหัส Huffman สามารถมั่นใจได้ว่ารหัสไบนารีใด ๆ จะไม่เป็นคำนำหน้าของรหัสอื่นการถอดรหัสจึงง่ายมาก นำไบนารีแต่ละบิตตามลำดับค้นหาจากรากต้นไม้ 1 ไปทางขวา 0 ไปทางซ้ายไปถึงโหนดใบไม้ (ตี) และกลับไปที่โหนดรูทและทำซ้ำการกระทำข้างต้นต่อไป รหัสมีดังนี้:
การถอดรหัสสตริงคงที่สาธารณะ (String BinaryStr, Map <อักขระ, จำนวนเต็ม> สถิติ) {ถ้า (binarystr == null || binarystr.equals ("")) {return ""; } char [] binaryChararray = binarystr.tochararray (); LinkedList <caricy> binaryList = new LinkedList <caricy> (); ขนาด int = binarychararray.length; สำหรับ (int i = 0; i <size; i ++) {binarylist.addlast (ตัวละครใหม่ (BinaryChararray [i])); } list <node> lefnodes = new ArrayList <Node> (); Tree Tree = buildTree (สถิติ, leafnodes); StringBuffer buffer = new StringBuffer (); ในขณะที่ (binarylist.size ()> 0) {node node = tree.root; ทำ {อักขระ c = binarylist.removefirst (); if (c.charvalue () == '0') {node = node.leftNode; } else {node = node.rightNode; }} ในขณะที่ (! node.isleaf ()); buffer.append (node.chars); } return buffer.toString (); - ทดสอบและเปรียบเทียบ
การทดสอบต่อไปนี้เกี่ยวกับความถูกต้องของการเข้ารหัส Huffman (เข้ารหัสก่อนจากนั้นถอดรหัสรวมถึงภาษาจีน) และการเปรียบเทียบการเข้ารหัส Huffman กับอักขระทั่วไปที่เข้ารหัสสายไบนารี รหัสมีดังนี้:
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {string oristr = "รหัส Huffman บีบอัดข้อมูลได้อย่างมีประสิทธิภาพมาก: การออม 20% ถึง 90% เป็นเรื่องปกติ" + "ขึ้นอยู่กับลักษณะของข้อมูลที่ถูกบีบอัดการเพิ่มขึ้นของจีน"; แผนที่ <อักขระ, จำนวนเต็ม> สถิติ = สถิติ (oristr.toChararray ()); String encodedBinaristr = ENCODE (oristr, สถิติ); String decodedStr = decode (encodedbinaristr, สถิติ); System.out.println ("สตริงต้นฉบับ:" + oristr); System.out.println ("Huffman Encoed Binary String:" + ENCODEDBINARISTER); System.out.println ("สตริงถอดรหัสจากสตริง binariy:" + decodedstr); System.out.println ("สตริงไบนารีของ UTF-8:" + getStringOfByte (oristr, charset.forName ("UTF-8")))); System.out.println ("สตริงไบนารีของ UTF-16:" + getStringOfByte (oristr, charset.forname ("UTF-16")))); System.out.println ("สตริงไบนารีของ us-ascii:" + getStringofbyte (oristr, charset.forname ("us-ascii")))); System.out.println ("สตริงไบนารีของ GB2312:" + getStringOfByte (oristr, charset.forname ("GB2312")))); } สตริงคงที่สาธารณะ getStringOfByte (สตริง str, charset charset) {ถ้า (str == null || str.equals ("")) {return ""; } byte [] byteArray = str.getBytes (charset); ขนาด int = bytearray.length; StringBuffer buffer = new StringBuffer (); สำหรับ (int i = 0; i <size; i ++) {byte temp = bytearray [i]; buffer.append (getStringofbyte (temp)); } return buffer.toString (); } สตริงคงที่สาธารณะ getStringOfByte (byte b) {StringBuffer buffer = new StringBuffer (); สำหรับ (int i = 7; i> = 0; i--) {byte temp = (byte) ((b >> i) & 0x1); buffer.append (string.valueof (temp)); } return buffer.toString (); -ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น