Доброго времени суток.Возник вопрос.Каким образом можно приведённый программный код перестроить под поиск вероятностей появления двубуквенных сочетаний?
Код:
// скомпилируйте и введите java HuffmanTest
class Tree {
public Tree child0; // потомки "0" и "1"
public Tree child1;
public boolean leaf; // признак листового дерева
public int character; // входной символ
public int weight; // вес этого символа
public Tree() {}
public Tree(int character, int weight, boolean leaf) {
this.leaf = leaf;
this.character = character;
this.weight = weight;
}
/* Обход дерева с генерацией кодов
1. "Распечатать" листовое дерево и записать код Хаффмана в массив
2. Рекурсивно обойти левое поддерево (с генерированием кода).
3. Рекурсивно обойти правое поддерево.
*/
public void traverse(String code, Huffman h) {
if (leaf) {
System.out.println((char)character +" "+ weight +" "+ code);
h.code[character] = code;
}
if ( child0 != null) child0.traverse(code + "0", h);
if ( child1 != null) child1.traverse(code + "1", h);
}
}
class Huffman {
public static final int ALPHABETSIZE = 256;
Tree[] tree = new Tree[ALPHABETSIZE]; // рабочий массив деревьев
int weights[] = new int[ALPHABETSIZE]; // веса символов
public String[] code = new String[ALPHABETSIZE]; // коды Хаффмана
private int getLowestTree(int used) { // ищем самое "легкое" дерево
int min=0;
for (int i=1; i<used; i++)
if (tree[i].weight < tree[min].weight ) min = i;
return min;
}
public void growTree( int[] data ) { // растим дерево
for (int i=0; i<data.length; i++) // считаем веса символов
weights[data[i]]++;
// заполняем массив из "листовых" деревьев
int used = 0; // с использованными символами
for (int c=0; c < ALPHABETSIZE; c++) {
int w = weights[c];
if (w != 0) tree[used++] = new Tree(c, w, true);
}
while (used > 1) { // парами сливаем легкие ветки
int min = getLowestTree( used ); // ищем 1 ветку
int weight0 = tree[min].weight;
Tree temp = new Tree(); // создаем новое дерево
temp.child0 = tree[min]; // и прививаем 1 ветку
tree[min] = tree[--used]; // на место 1 ветки кладем
// последнее дерево в списке
min = getLowestTree( used ); // ищем 2 ветку и
temp.child1 = tree[min]; // прививаем ее к нов.дер.
temp.weight = weight0 + tree[min].weight; // считаем вес нов.дер.
tree[min] = temp; // нов.дер. кладем на место 2 ветки
} // все! осталось 1 дерево Хаффмана
}
public void makeCode() { // запускаем вычисление кодов Хаффмана
tree[0].traverse( "", this);
}
public String coder( int[] data ) { // кодирует данные строкой из 1 и 0
String str = "";
for (int i=0; i<data.length; i++) str += code[data[i]];
return str;
}
public String decoder(String data) {
String str=""; // проверяем в цикле данные на вхождение
int l = 0; // кода, если да, то отбрасываем его ...
while(data.length() > 0){
for (int c=0; c < ALPHABETSIZE; c++) {
if (weights[c]>0 && data.startsWith(code[c])){
data = data.substring(code[c].length(), data.length());
str += (char)c;
}
}
}
return str;
}
}
public class HuffmanTest { // тест и демонстрация
public static void main(String[] args) {
Huffman h = new Huffman();
String str = "to be or not to be?"; // входные данные
int data[] = new int[str.length()]; // преобразуем в массив
for (int i=0; i<str.length(); i++) data[i] = str.charAt(i);
h.growTree( data ); // растим дерево
h.makeCode(); // находим коды
str = h.coder(data);
System.out.println(str);
System.out.println(h.decoder(str));
}
}