هوفمان تشفير مقدمة
يتعامل تشفير Huffman مع مشكلة الاقتران في الترميز والأحرف الثنائية المقابلة للأحرف ، والتي تنقسم إلى ترميز وفك تشفير ، بهدف ضغط طول البيانات الثنائية المقابلة للأحرف. نحن نعلم أنه عندما يتم تخزين الشخصيات ونقلها ، فهي ثنائية (يعرف الكمبيوتر فقط 0/1) ، لذلك هناك علاقة رسم الخرائط بين الشخصيات والثنائي. الشخصيات تنتمي إلى مجموعة الأحرف (charset). يجب تخزين الشخصيات ونقلها في ثنائي من خلال الترميز. عند عرضها ، يجب فك تشفيرها إلى الشخصيات. تعد أساليب مجموعة الأحرف وطرق الترميز علاقات واحدة إلى حد ذاتية (يمكن ترميز Unicode باستخدام UTF-8 ، UTF-16 ، إلخ). بعد فهم مجموعة الأحرف والترميز وفك التشفير ، يمكن حل مشكلة الكود المشوهة التي تحلق في جميع أنحاء السماء بسهولة. أخذ الحرف الصغيرة A من الحرف الإنجليزي كمثال ، في ترميز ASCII ، العشري هو 97 والثنائي هو 01100001. يتم ترميز كل حرف في ASCII مع 8 بت (1byte). إذا كان هناك 1000 حرف يتم نقله ، فيجب إرسال 8000 بت. المشكلة هي أن تواتر استخدام الحرف E باللغة الإنجليزية هو 12.702 ٪ ، في حين أن Z هو 0.074 ٪. السابق هو أكثر من 100 مرة من هذا الأخير ، ولكنه يستخدم ثنائي مع نفس الأرقام. يمكن القيام به بشكل أفضل ، فإن الطريقة متغيرة الترميز. المبدأ التوجيهي هو تشفير التردد الأعلى بأرقام أقصر ، وتلك التي لديها تردد منخفض مع أرقام أطول. تتناول خوارزمية ترميز Huffman مثل هذه المشكلات.
Huffman ترميز تنفيذ Java
هياكل البيانات المستخدمة بشكل أساسي من قبل خوارزمية ترميز هوفمان هي أشجار ثنائية كاملة وقوائم ذات أولوية. يستخدم الأخير java.util.priorityqueue ، والأوائد السابقة نفسها (كلها فصول داخلية). الرمز كما يلي:
شجرة فئة ثابتة {جنود العقدة الخاصة ؛ العقدة العامة getRoot () {return root ؛ } public void setroot (node root) {this.root = root ؛ }} تنفذ عقدة الفئة الثابتة <Node> {private string chars = "" ؛ تردد int الخاص = 0 ؛ الوالد العقدة الخاصة ؛ عقدة خاصة LeftNode ؛ عقدة خاصة يمين ؛ Override public int compareto (node n) {return treensency - n.frequency ؛ } boolean public isLeaf () {return chars.length () == 1 ؛ } boolean public isRoot () {return parent == null ؛ } boolean public isleftchild () {return parent! = null && this == parent.leftnode ؛ } public int getFrequence () {return treenency ؛ } public void setFrequence (int tenergency) {this.frequency = التردد ؛ } السلسلة العامة getChars () {return chars ؛ } public void setchars (string chars) {this.chars = chars ؛ } العقدة العامة getParent () {return parent ؛ } public void setParent (node parent) {this.parent = parent ؛ } العقدة العامة getleftnode () {return LeftNode ؛ } public void setLeftnode (node LeftNode) {this.leftnode = LeftNode ؛ } العقدة العامة getRightNode () {return reightNode ؛ } public void setRightNode (node rightNode) {this.rightNode = rightNode ؛ }} إحصائيات
نظرًا لأن جدول الترميز يحتاج إلى ترتيب وفقًا للتردد ، ثم بالطبع ، يجب عليك الحصول على المعلومات الإحصائية للتردد. لقد قمت بتنفيذ طريقة للتعامل مع مثل هذه المشكلة. إذا كانت هناك إحصائيات بالفعل ، فعليك التحويل إلى خريطة <حرف ، integer>. إذا كانت المعلومات التي تحصل عليها هي نسبة مئوية ، أو مضاعفة بمقدار 100 أو 1000 ، أو 10000. يمكن تحويلها دائمًا إلى عدد صحيح. على سبيل المثال ، 12.702 ٪ مضروبة على 1000 هو 12702 ، وترميز هوفمان فقط يهتم بمشكلات الحجم. يتم تنفيذ الطريقة الإحصائية على النحو التالي:
الخريطة الثابتة العامة <الحرف ، integer> Statistics (char [] chararray) {map <الحرف ، integer> map = new hashmap <الحرف ، integer> () ؛ لـ (charc c: chararray) {حرف الحرف = حرف جديد (c) ؛ if (map.containskey (حرف)) {map.put (حرف ، map.get (حرف) + 1) ؛ } آخر {map.put (حرف ، 1) ؛ }} خريطة الإرجاع ؛ } بناء شجرة
بناء شجرة هو خطوة أساسية في خوارزمية ترميز هوفمان. تتمثل الفكرة في تعليق جميع الشخصيات على عقدة ورقة لشجرة ثنائية تمامًا ، ولا يظهر تواتر العقدة اليسرى لأي عقدة طفل غير صفحات أكثر من العقدة اليمنى. تقوم الخوارزمية بتحويل الإحصائيات إلى العقد وتخزنها في قائمة انتظار ذات أولوية. في كل مرة يتمتع فيها العقدان مع الحد الأدنى للتردد من خلال قائمة الانتظار ، يتم إنشاء عقدة الوالدين الجديدة (العقدة غير الورقية). مجموع العقدتين اللذين يبرز محتوى الشخصيات ، والتردد هو أيضًا مجموعهما. يتم استخدام المنبثقة الأولى كعقدة الطفل اليسرى ، ويتم استخدام العقدة التالية كعقدة الطفل الأيمن ، ويتم وضع العقدة الأم التي تم إنشاؤها حديثًا في قائمة الانتظار. كرر الإجراءات المذكورة أعلاه N-1 مرات ، N هو عدد الأحرف المختلفة (يتم تقليل الرقم في قائمة الانتظار بمقدار 1 في كل مرة). قم بإنهاء الخطوات المذكورة أعلاه ، هناك عقدة تركت في قائمة الانتظار ، وتظهر عقدة الجذر للشجرة. الرمز كما يلي:
BuildTree Static Tree BuildTree (خريطة <حرف ، integer> ، قائمة <Node> الأوراق) {character [] keys = statistics.keyset (). tararray (حرف جديد [0]) ؛ priorityqueue <Node> phiretIqueue = new PriorityQueue <Node> () ؛ لـ (حرف الحرف: مفاتيح) {node node = new node () ؛ node.chars = character.toString () ؛ node.frequency = statistics.get (حرف) ؛ priorityqueue.add (العقدة) ؛ Leaves.Add (العقدة) ؛ } int size = phiretiqueue.size () ؛ لـ (int i = 1 ؛ i <= size - 1 ؛ i ++) {node node1 = phiretivequeue.poll () ؛ node node2 = phiretivequeue.poll () ؛ عقدة sumnode = node 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 = phiretiqueue.poll () ؛ شجرة العودة } الترميز
الترميز المقابل للحرف هو البحث عن عقدة الورقة حيث يوجد الحرف. إذا كانت عقدة الحرف هي العقدة اليسرى للعقدة الأصل ، فأضف 0 قبل الحرف المشفر ، وإلا إذا كانت العقدة اليمنى ، أضف 1 حتى عقدة الجذر. طالما تم الحصول على علاقة التعيين بين الأحرف والرمز الثنائي ، يكون الترميز بسيطًا للغاية. الرمز كما يلي:
Encode Static String Public (String OriginalStr ، MAP <حرف ، integer> Statistics) {if (OriginalStr == null || OriginalStr.equals ("")) {return "" ؛ } char [] chararray = OriginalStr.ToChararray () ؛ قائمة <Node> leafnodes = new ArrayList <Node> () ؛ BuildTree (الإحصائيات ، Leafnodes) ؛ خريطة <farter ، string> encodinfo = buildenCodingInfo (leafnodes) ؛ StringBuffer Buffer = new StringBuffer () ؛ لـ (char c: chararray) {حرف حرف = حرف جديد (c) ؛ buffer.append (encodinfo.get (حرف)) ؛ } return buffer.toString () ؛ } الخريطة الثابتة الخاصة <الحرف ، string> buildenCodingInfo (قائمة <Node> leafnodes) {MAP <FARHITY ، string> codewords = new hashmap <حرف ، string> () ؛ لـ (node leafnodes: leafnodes) {حرف حرف = حرف جديد (leafnode.getChars (). charat (0)) ؛ سلسلة codeword = "" ؛ Node CurrentNode = leafnode ؛ do {if (currentnode.isleftchild ()) {codeword = "0" + codeword ؛ } آخر {codeword = "1" + codeword ؛ } currentNode = currentNode.parent ؛ } بينما (currentNode.parent! = null) ؛ codewords.put (حرف ، codeword) ؛ } codewords الإرجاع ؛ } فك التشفير
نظرًا لأن خوارزمية ترميز Huffman يمكن أن تضمن أن أي رمز ثنائي لن يكون بادئة رمز آخر ، فإن فك التشفير بسيط للغاية. قم بإخراج كل جزء من الثنائي بالتسلسل ، وابحث لأسفل من جذر الشجرة ، 1 إلى اليمين ، 0 إلى اليسار ، واتصل إلى عقدة الورقة (HIT) ، والعودة إلى عقدة الجذر ومواصلة تكرار الإجراءات أعلاه. الرمز كما يلي:
decode static static static (String BinaryStr ، Map <حرف ، integer> statistics) {if (binarystr == null || binarystr.equals ("")) {return "" ؛ } char [] BinaryChararray = BinaryStr.ToChararray () ؛ LinkedList <Farhtor> BinaryList = New LinkedList <Former> () ؛ حجم int = binarychararray.length ؛ لـ (int i = 0 ؛ i <size ؛ i ++) {binarylist.addlast (حرف جديد (binarychararray [i])) ؛ } قائمة <Node> leafnodes = new ArrayList <Node> () ؛ شجرة الشجرة = BuildTree (إحصائيات ، eafnodes) ؛ StringBuffer Buffer = new StringBuffer () ؛ بينما (BinaryList.size ()> 0) {node node = tree.root ؛ do {character c = BinaryList.RemoveFirst () ؛ if (c.charvalue () == '0') {node = node.leftnode ؛ } آخر {node = node.rightnode ؛ }} بينما (! node.isleaf ()) ؛ buffer.append (node.chars) ؛ } return buffer.toString () ؛ } الاختبار والمقارنة
الاختبارات التالية على صحة ترميز هوفمان (مشفرة أولاً ، ثم فك تشفيرها ، بما في ذلك الصينية) ، ومقارنة ترميز هوفمان مع سلاسل ثنائية تشفير الأحرف الشائعة. الرمز كما يلي:
الفراغ الثابت العام (سلسلة [] args) {String oristr = "رموز Huffman ضغط البيانات بشكل فعال للغاية: إن توفير من 20 ٪ إلى 90 ٪ نموذجية ،" + "اعتمادًا على خصائص البيانات التي يتم ضغطها. ارتفاع الصين" ؛ الخريطة <الحرف ، integer> الإحصائيات = الإحصائيات (oristr.tochararray ()) ؛ سلسلة encodedBinaristr = encode (oristr ، إحصائيات) ؛ سلسلة decodedstr = decode (encodedBinaristr ، الإحصائيات) ؛ System.out.println ("السلسلة الأصلية:" + oristr) ؛ System.out.println ("Huffman Encoed Binary String:" + encodedBinaristr) ؛ System.out.println ("سلسلة فك التشفير من سلسلة binariy:" + decodedstr) ؛ System.out.println ("سلسلة ثنائية من UTF-8:" + getStringOfByte (oristr ، charset.forname ("utf-8"))) ؛ System.out.println ("سلسلة ثنائية من UTF-16:" + getTringOfByte (oristr ، charset.forname ("UTF-16"))) ؛ System.out.println ("سلسلة ثنائية من الولايات المتحدة-ASCII:" + getStringOfByte (oristr ، charset.forname ("us-ascii"))) ؛ System.out.println ("سلسلة ثنائية من GB2312:" + getTringOfByte (oristr ، charset.forname ("GB2312")))) ؛ } السلسلة الثابتة العامة getTringOfByte (String str ، charset charset) {if (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 () ؛ } السلسلة الثابتة العامة getTringOfByte (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 أكثر.