java huffman tree precedence

Question

私はここ数日間、私が研究している以下のコードについて2つの質問があります。一文字のグループに複数の文字よりも優先順位を付けると、アルファベット順に複数のタイ（同じ周波数数を意味する）がある場合、次のルールを実装するにはどうすればよいですか？私の2番目の質問は、誰かが私のコードをエンコード/デコードするための書き込み方向で私を指すことができるということですか？私はそれを私の主な声明を通して実装するか、新しいクラスを完全に書くべきでしょうか？私はどこから始めるべきかちょっと固まっています。あなたの最初の質問に応えて

import java.util.*; 


//The following is code that is hardcoded with two separate arrays consisting of 
//characters and their corresponding frequency. The application takes in these two 
//arrays and constructs a Huffman Encoding Tree. It begins by showing the user the 
//letters, frequency, and the Huffman Code that will be assigned to that letter. 
//The application then takes in a .txt file with various strings and encodes them. 
//This result is also shown. [still working on this part-- question above] 


abstract class HuffmanTree implements Comparable<HuffmanTree> { 
public final int frequency; // the frequency of this tree 
public HuffmanTree(int freq) { frequency = freq; } 

// compares on the frequency 
public int compareTo(HuffmanTree tree) { 
    return frequency - tree.frequency; 
} 
} 

class HuffmanLeaf extends HuffmanTree { 
public final char value; // the character this leaf represents 

public HuffmanLeaf(int freq, char val) { 
    super(freq); 
    value = val; 
} 
} 

class HuffmanNode extends HuffmanTree { 
public final HuffmanTree left, right; // subtrees 

public HuffmanNode(HuffmanTree l, HuffmanTree r) { 
    super(l.frequency + r.frequency); 
    left = l; 
    right = r; 
} 
} 

public class Huffman { 

public static void main(String[] args) { 
    //Symbols that are given to us to hard code 
    String letters = "abcdefghijklmnopqrstuvwxyz"; 

    //converting string to character array 
    char[] letterArray = letters.toCharArray(); 

    //Frequency of the letters given to us above: 
    int[] letterFreqs = {19, 16, 17, 11, 42, 12, 14, 17, 16, 5, 10, 20, 19, 24, 18, 13, 
     1, 25, 35, 25, 15, 5, 21, 2, 8, 3}; 


    // build tree 
    HuffmanTree tree = constructTree(letterFreqs,letterArray); 

    // print out results 
    System.out.println("Letter\tFrequency\tEncoding"); 
    printCodes(tree, new StringBuffer()); 
    } 




// input is an array of frequencies and a string of letters 
public static HuffmanTree constructTree(int[] charFreqs, char[] letters) { 

    //sets up the priority queue to begin constructing the tree 
    PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>(); 

    //for loop to take in the characters and there frequencies 
    for (int i = 0; i < charFreqs.length; i++) 
     if (charFreqs[i] > 0) 
      trees.offer(new HuffmanLeaf(charFreqs[i], letters[i])); 

    assert trees.size() > 0; 
    // loop until there is only one tree left 
    while (trees.size() > 1) { 

     // find the two lowest frequencies 
     HuffmanTree a = trees.poll(); 
     HuffmanTree b = trees.poll(); 

     // construct a new node and re-insert into queue 
     trees.offer(new HuffmanNode(a, b)); 
    } 
    return trees.poll(); 
} 

public static void printCodes(HuffmanTree tree, StringBuffer prefix) { 

    assert tree != null; 
    if (tree instanceof HuffmanLeaf) { 
     HuffmanLeaf leaf = (HuffmanLeaf)tree; 

     // print out character, frequency, and code for this leaf (which is just the prefix) 
     System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + "\t" + prefix); 


    } else if (tree instanceof HuffmanNode) { 
     HuffmanNode node = (HuffmanNode)tree; 

     // traverse left 
     prefix.append('0'); 
     printCodes(node.left, prefix); 
     prefix.deleteCharAt(prefix.length()-1); 

     // traverse right 
     prefix.append('1'); 
     printCodes(node.right, prefix); 
     prefix.deleteCharAt(prefix.length()-1); 
    } 
} 

} 

Answer 1

、あなたはcompareTo()の実装を経由して優先順位キュー内の順序を制御するので、私は、次のような何かしたい：抽象的な2については

abstract class HuffmanTree implements Comparable<HuffmanTree> { 
    public final int frequency; // the frequency of this tree 

    public HuffmanTree(int freq) { 
     frequency = freq; 
    } 

    @Override 
    public int compareTo(HuffmanTree tree) { 
     int comparison = frequency - tree.frequency; 
     if (0 == comparison) { 
      comparison = comparisonTieBreaker(tree); 
     } 

     return comparison; 
    } 
    private int comparisonTieBreaker(HuffmanTree tree) { 
    int comparison = 0; 
    if (this.size() == 1) { 
     if (tree.size() == 1) { 
      // alphabetical comparison between 2 single-character groups: 
      Character.compare(this.firstChar(), tree.firstChar()); 
     } 
     else { 
      comparison = -1; // single < multiple 
     } 
    } else if (tree.size() == 1) { 
     comparison = 1; // multiple > single 
    } 
    return comparison; 
} 

public abstract int size(); 

public abstract char firstChar(); 
} 

をメソッドでは、HuffmanLeaf、size()は1を返し、firstChar()はその文字を返します。 HuffmanNodeでsize()はleft.size() + right.size()（基本的な再帰）を返し、firstChar()はleft.firstChar()を返すことができますが、HuffmanNodeでは通常firstChar()が呼び出されません。

Huffmanクラスまたは別のクラスのいずれかにある、encode()とdecode()のメソッドを使用する必要があります。あなたは明らかにメインからそれらを呼び出すことができますが、私は他の場所で再利用される可能性があるものをメインメソッドから抜き出しています。

編集：あなたは詳細を教えてください。あなたの2番目の質問はあまり明確ではありませんでしたが、エンコーディングとデコードを進める方法に固執しているようです。まず、HuffmanTreeのメソッドtoMapForDecoding()とtoMapForEncoding()を追加します。それぞれのマップは、どちらのメソッドでもキーと値が逆の基本マップです。これらのマップ（encode()とdecode()メソッドで使用される）は、入力シンボルと（エンコードされたまたはデコードされた）出力シンボルの間の一定時間の変換を可能にします。これらのメソッドの実装は、すでにprintCodes()で行ったものと非常によく似ています。 encode()とdecode()メソッドをどこに置くかについては、それによってブロックされないようにしてください。便利な場所に置いて、必要に応じて後で移動してください。