Nhờ giúp đỡ 1 code sưu tầm về thuật toán huffman

nguyenthevuot

New Member
1/12/13
1
0
1
29
Chào cả nhà!
mình đang tìm hiểu java và các thuật toán!
Mày mò tìm hiểu bên các diễn đàn nước ngoài thì thấy 1 cái source code về thuật toán huffman!
Code:
import com.sun.org.apache.bcel.internal.generic.GOTO;
import javax.swing.JOptionPane;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Nevil
*/
public class Node
        implements Comparable
{

        private int    value;
        private char    content;
        private Node    left;
        private Node    right;
        static char con[]=new char[26];
        static String pat[]=new String[26];
        static int m=0;

        public Node(char content, int value)
        {
                this.content  = content;
                this.value    = value;
        }

        public Node(Node left, Node right)
        {
                // Assumes that the left three is always the one that is lowest
                this.content  = (left.content < right.content) ? left.content : right.content;
                this.value    = left.value + right.value;
                this.left        = left;
                this.right    = right;
        }

    Node() {

    }
        public char check(String str)
        {
            char ch='1';
            for(int i=0;i<25;i++)
            {
                if(str.equals(pat[i]))
                {
                    ch=con[i];
                    System.out.println(ch);
                    break;
                }
            }
            return ch;

        }

        public void Decode(String decodestr,javax.swing.JTextArea j2)
        {
            try
            {
            char a[]=decodestr.toCharArray();
            System.out.println(a);
            int strlen=decodestr.length();

            String b="",substr="";
            char d;
            int i=0;

          while(true)
            {
                substr=decodestr.substring(i,i+3);
                System.out.println(substr + "nevil");

          if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+3;
                    if(i==strlen)
                    {
                        break;
                    }
                  continue;
                }

                substr=decodestr.substring(i,i+4);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+4;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

                substr=decodestr.substring(i,i+5);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+5;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

                substr=decodestr.substring(i,i+6);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+6;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

                substr=decodestr.substring(i,i+7);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+7;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

                substr=decodestr.substring(i,i+8);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+8;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

                substr=decodestr.substring(i,i+9);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+9;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

                substr=decodestr.substring(i,i+10);
                System.out.println(substr + "nevil");

                if((d=check(substr))!='1')
                {
                    b+=d;
                    i=i+10;
                    if(i==strlen)
                    {
                        break;
                    }
                continue;

                }

            }

                System.out.println(b);
                j2.setText(b);
            }
            catch(Exception ex)
            {
                JOptionPane.showMessageDialog(j2, "Enter Valid String");
            }
        }

        public void Encode(String encodestr,javax.swing.JTextArea j1)
        {

            char a[]=encodestr.toCharArray();
            String b="";
            System.out.println(a);
            try
            {
                for(int i=0;a[i]>='A' && a[i]<='Z';i++)
                {
                    for(int k=0;k<26;k++)
                    {
                    //  System.out.println(a[i]);
                    //  System.out.println(con[k]);
                        if(a[i]==con[k])
                        {
                        //  System.out.println("hi");
                            b+=pat[k];
                            break;
                        }
                    }
                //  System.out.println(b);
                }
            }
            catch(Exception ex)
            {
                j1.setText(b);
            }
        }
        public int compareTo(Object arg)
        {
                Node other = (Node) arg;

                // Content value has priority and then the lowest letter
                if (this.value == other.value)
                        return this.content-other.content;
                else
                        return this.value-other.value;
        }

        ////////////////

        private void printNode(String path)
        {
                if ((left==null) && (right==null))
                {
                        con[m]=content;
                        pat[m]=path;
                        System.out.println(content + " " + path);
                        System.out.println(con[m] + " " + pat[m]);
                        m++;

                }

                if (left != null)
                        left.printNode(path + '0');
                if (right != null)
                        right.printNode(path + '1');
        }

        public static void printTree(Node tree)
        {
                tree.printNode("");
        }
}
đây là class node!

Code:
import java.util.TreeSet;
import javax.swing.JOptionPane;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/*
* Huffman.java
*
* Created on Dec 9, 2012, 2:54:28 AM
*/

/**
*
* @author Nevil
*/
public class Huffman extends javax.swing.JFrame {

    /** Creates new form Huffman */
    String encodestr,decodestr;
    Node n;
    TreeSet<Node> trees    = new TreeSet<Node>();

    public Huffman() {
        initComponents();
    }

    /** This method is called from within the constructor to
    * initialize the form.
    * WARNING: Do NOT modify this code. The content of this method is
    * always regenerated by the Form Editor.
    */
    @SuppressWarnings("unchecked")
    // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents
    private void initComponents() {

        button_Encode = new javax.swing.JButton();
        button_Decode = new javax.swing.JButton();
        jScrollPane1 = new javax.swing.JScrollPane();
        jTextArea1 = new javax.swing.JTextArea();
        jLabel1 = new javax.swing.JLabel();
        jScrollPane2 = new javax.swing.JScrollPane();
        jTextArea2 = new javax.swing.JTextArea();
        jLabel2 = new javax.swing.JLabel();
        jLabel3 = new javax.swing.JLabel();

        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);

        button_Encode.setText("Encode");
        button_Encode.setName("button_Encode"); // NOI18N
        button_Encode.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                button_EncodeActionPerformed(evt);
            }
        });

        button_Decode.setText("Decode");
        button_Decode.setName("button_Decode"); // NOI18N
        button_Decode.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                button_DecodeActionPerformed(evt);
            }
        });

        jScrollPane1.setName("jScrollPane1"); // NOI18N

        jTextArea1.setColumns(20);
        jTextArea1.setRows(5);
        jTextArea1.setName("jTextArea1"); // NOI18N
        jScrollPane1.setViewportView(jTextArea1);

        jLabel1.setFont(new java.awt.Font("Tahoma", 0, 14)); // NOI18N
        jLabel1.setText("Enter Message to be encoded or decoded :");
        jLabel1.setName("jLabel1"); // NOI18N

        jScrollPane2.setName("jScrollPane2"); // NOI18N

        jTextArea2.setColumns(20);
        jTextArea2.setRows(5);
        jTextArea2.setName("jTextArea2"); // NOI18N
        jScrollPane2.setViewportView(jTextArea2);

        jLabel2.setFont(new java.awt.Font("Tahoma", 0, 14)); // NOI18N
        jLabel2.setText("Output Message :");
        jLabel2.setName("jLabel2"); // NOI18N

        jLabel3.setFont(new java.awt.Font("Tahoma", 1, 18)); // NOI18N
        jLabel3.setText("Huffman Algorith Implementation");
        jLabel3.setName("jLabel3"); // NOI18N

        javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
        getContentPane().setLayout(layout);
        layout.setHorizontalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup()
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)
                    .addGroup(layout.createSequentialGroup()
                        .addContainerGap()
                        .addComponent(jLabel2)
                        .addGap(33, 33, 33))
                    .addGroup(layout.createSequentialGroup()
                        .addContainerGap()
                        .addComponent(jLabel1)
                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)))
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING, false)
                    .addComponent(jScrollPane2, javax.swing.GroupLayout.Alignment.TRAILING)
                    .addComponent(jScrollPane1, javax.swing.GroupLayout.Alignment.TRAILING, javax.swing.GroupLayout.DEFAULT_SIZE, 284, Short.MAX_VALUE))
                .addGap(32, 32, 32))
            .addGroup(layout.createSequentialGroup()
                .addGap(135, 135, 135)
                .addComponent(jLabel3)
                .addContainerGap(158, Short.MAX_VALUE))
            .addGroup(layout.createSequentialGroup()
                .addGap(97, 97, 97)
                .addComponent(button_Encode, javax.swing.GroupLayout.PREFERRED_SIZE, 109, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addGap(171, 171, 171)
                .addComponent(button_Decode, javax.swing.GroupLayout.PREFERRED_SIZE, 111, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addContainerGap(112, Short.MAX_VALUE))
        );
        layout.setVerticalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(layout.createSequentialGroup()
                .addGap(46, 46, 46)
                .addComponent(jLabel3)
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addGroup(layout.createSequentialGroup()
                        .addGap(28, 28, 28)
                        .addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 78, javax.swing.GroupLayout.PREFERRED_SIZE))
                    .addGroup(layout.createSequentialGroup()
                        .addGap(52, 52, 52)
                        .addComponent(jLabel1)))
                .addGap(35, 35, 35)
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)
                    .addComponent(button_Encode, javax.swing.GroupLayout.PREFERRED_SIZE, 39, javax.swing.GroupLayout.PREFERRED_SIZE)
                    .addComponent(button_Decode, javax.swing.GroupLayout.PREFERRED_SIZE, 38, javax.swing.GroupLayout.PREFERRED_SIZE))
                .addGap(24, 24, 24)
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addGroup(layout.createSequentialGroup()
                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                        .addComponent(jScrollPane2, javax.swing.GroupLayout.PREFERRED_SIZE, 77, javax.swing.GroupLayout.PREFERRED_SIZE))
                    .addGroup(layout.createSequentialGroup()
                        .addGap(32, 32, 32)
                        .addComponent(jLabel2)))
                .addGap(56, 56, 56))
        );

        pack();
    }// </editor-fold>//GEN-END:initComponents

    private void button_EncodeActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_button_EncodeActionPerformed

        jTextArea2.setText("");
    System.out.println("encodestr");
        n=new Node();
        encodestr=jTextArea1.getText();
        char ch[]=encodestr.toCharArray();
        try
        {
            for(int i=0;ch[i]!='\0';i++)
            {
                if(ch[i]<'A' || ch[i]>'Z')
                {
                    JOptionPane.showMessageDialog(rootPane,"Enter Upper Case letetrs only");
                    return;
                }
            }
        }
        catch(Exception ex)
        {
            System.out.println(encodestr);
            n.Encode(encodestr,jTextArea2);
        }

    }//GEN-LAST:event_button_EncodeActionPerformed

    private void button_DecodeActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_button_DecodeActionPerformed
        jTextArea2.setText("");
        n=new Node();
        decodestr=jTextArea1.getText();
        System.out.println(decodestr);
        n.Decode(decodestr,jTextArea2);
    }//GEN-LAST:event_button_DecodeActionPerformed

    /**
    * @param args the command line arguments
    */
    public static void main(String args[]) {
        java.awt.EventQueue.invokeLater(new Runnable() {
            public void run() {
                new Huffman().setVisible(true);
                processFile();
            }
        });
    }

    private static void processFile()
        {
                TreeSet<Node> trees    = new TreeSet<Node>();

        int[] frequency={14810,2715,4943,7874,21912,4200,3693,10795,13318,188,1257,7253,4761,12666,14003,3316,205,10977,11450,16587,5246,2019,3819,315,3853,128};

                // Build up the initial trees
                for (int i=0; i<'Z'-'A'+1; i++)
                {
                        if (frequency[i] > 0)
                        {
                                Node n = new Node((char)('A'+i), frequency[i]);
                                trees.add(n);
                        }
                }

                // Huffman algoritm
                while (trees.size() > 1)
                {
                        Node tree1 = (Node) trees.first();
                        trees.remove(tree1);
                        Node tree2 = (Node) trees.first();
                        trees.remove(tree2);

                        Node merged = new Node(tree1, tree2);
                        trees.add(merged);
                }

                // Print the resulting tree
                if (trees.size() > 0)
                {
                        Node theTree = (Node) trees.first();
                        Node.printTree(theTree);
                }
                else
                        System.out.println("The file didn't contain useful characters.");
        }

    // Variables declaration - do not modify//GEN-BEGIN:variables
    private javax.swing.JButton button_Decode;
    private javax.swing.JButton button_Encode;
    private javax.swing.JLabel jLabel1;
    private javax.swing.JLabel jLabel2;
    private javax.swing.JLabel jLabel3;
    private javax.swing.JScrollPane jScrollPane1;
    private javax.swing.JScrollPane jScrollPane2;
    private javax.swing.JTextArea jTextArea1;
    private javax.swing.JTextArea jTextArea2;
    // End of variables declaration//GEN-END:variables

}
đây là class huffman
mình chạy chương trình bằng eclipse thì ổn cả
Nhưng mà giờ mình muốn là khi mình nhập 1 chuỗi vào thì không nhất thiết là chữ cái in hoa nó mới nén được!
làm thế nào để cả chữ hoa và chữ thường trong 1 chuỗi nó cũng có thể nén được!
Ai giúp mình với
Mình cảm ơn!
code đã được mình chỉnh sửa 1 số chỗ!
 

SITUVN

Well-Known Member
25/2/12
965
262
63
Thấy có đoạn này:
Code:
for(int i=0;a[i]>='A' && a[i]<='Z';i++)
Nó giới hạn từ A-Z đấy.
 

Joe

Thành viên VIP
21/1/13
2,744
1,259
113
Nguyenthevuot,
the codes you copied or the codes generated by your "DIE" (SITUVN, thanks for this wonderful shuffling of the word IDE) are really horrible. When you "sưu tầm" you can do it completely, not halfheartedly. Example:
PHP:
        try
        {
            for(int i=0;ch[i]!='\0';i++)
            {
                if(ch[i]<'A' || ch[i]>'Z')
                {
                    JOptionPane.showMessageDialog(rootPane,"Enter Upper Case letetrs only");
                    return;
                }
            }
        }
        catch(Exception ex)
        {
            System.out.println(encodestr);
            n.Encode(encodestr,jTextArea2);
        }
I can only see an exception occur when the index in your loop exceeds the upper boundary and that's the worst way of coding. Otherwise the try-catch is superfluous Think about that and improve your coding technique. The line for(int i=0;ch!='\0';i++) is a nonsense -you mix C++ with Java.
làm thế nào để cả chữ hoa và chữ thường trong 1 chuỗi nó cũng có thể nén được
If you are not a student of computer science then you have to take time and study the ASCII code table. The number starts at 0 (x30) and ends at 9 (x39). The letter starts with A (x41) and ends with Z (x5A) and a (x61) to z (x7A). So you have 2 choices:
1) compare with literals (see SITUVN)
2) compare with hex codes.
To convert a letter to Uppercase you AND the letter with 0x4F. Exp. x61 & x4F = x41 = 'A'
To convert a letter to Lowercase you OR the letter with 0x20. Exp. x41 | x20 = x61 = 'a'
A loop with a running index is faster than a loop with an array of literals.