viterbi.java

卷积码就是一种较好的信道编码方式。这种编码方式同样是把k个信息比特编成n个比特

	states.add(st);
    }
    public void addEndState(State st) {
	state_end = states.size(); // get current index
	states.add(st);
    }

    // for debugging.
    public void showmatrix() {
	for(int i = 0; i < symbols.size(); i++) {
	    for(int j = 0; j < states.size(); j++) {
		System.out.print(matrix_maxprob[i][j]+" "+matrix_prevstate[i][j]+", ");
	    }
	    System.out.println();
	}
    }

    // initialize for decoding
    public void initialize(SymbolList syms) {
	// symbols[syms.length] should be END
	symbols = syms;
	matrix_maxprob = new double[symbols.size()][states.size()];
	matrix_prevstate = new int[symbols.size()][states.size()];
	for(int i = 0; i < symbols.size(); i++) {
	    for(int j = 0; j < states.size(); j++) {
		matrix_prevstate[i][j] = -1;
	    }
	}
	
	State start = states.get(state_start);
	for(int i = 0; i < states.size(); i++) {
	    matrix_maxprob[0][i] = start.transprob(states.get(i));
	    matrix_prevstate[0][i] = 0;
	}

	stage = 0;
	i0 = -1;
	i1 = -1;
	sequence = new IntegerList();
	status = "Ok, let's get started...";
	status2 = "";
    }
    
    // forward procedure
    public boolean proceed_decoding() {
	status2 = "";
	// already end?
	if (symbols.size() <= stage) {
	    return false;
	}
	// not started?
	if (stage == 0) {
	    stage = 1;
	    i0 = 0;
	    i1 = 0;
	    matrix_maxprob[stage][i1] = 0.0;
	} else {
	    i0++;
	    if (states.size() <= i0) {
		// i0 should be reinitialized.
		i0 = 0;
		i1++;
		if (states.size() <= i1) {
		    // i1 should be reinitialized.
		    // goto next stage.
		    stage++;
		    if (symbols.size() <= stage) {
			// done.
			status = "Decoding finished.";
			return false;
		    }
		    laststage = (stage == symbols.size()-1);
		    i1 = 0;
		}
		matrix_maxprob[stage][i1] = 0.0;
	    }
	}
	
	// sym1: next symbol
	Symbol sym1 = symbols.get(stage);
	State s0 = states.get(i0);
	State s1 = states.get(i1);

	// precond: 1 <= stage.
	double prob = matrix_maxprob[stage-1][i0];
	DecimalFormat form = new DecimalFormat("0.0000");
	status = "Prob:" + form.format(prob);

	if (1 < stage) {
	    // skip first stage.
	    double transprob = s0.transprob(s1);
	    prob = prob * transprob;
	    status = status + " x " + form.format(transprob);
	}

	double emitprob = s1.emitprob(sym1);
	prob = prob * emitprob;
	status = status + " x " + form.format(emitprob) + "(" + s1.name+":"+sym1.name + ")";

	status = status + " = " + form.format(prob);
	// System.out.println("stage: "+stage+", i0:"+i0+", i1:"+i1+", prob:"+prob);
	
	if (matrix_maxprob[stage][i1] < prob) {
	    matrix_maxprob[stage][i1] = prob;
	    matrix_prevstate[stage][i1] = i0;
	    status2 = "(new maximum found)";
	}
	
	return true;
    }

    // backward proc
    public void backward() {
	int probmaxstate = state_end;
	sequence.add(probmaxstate);
	for(int i = symbols.size()-1; 0 < i; i--) {
	    probmaxstate = matrix_prevstate[i][probmaxstate];
	    if (probmaxstate == -1) {
		status2 = "Decoding failed.";
		return;
	    }
	    sequence.add(probmaxstate);
	    //System.out.println("stage: "+i+", state:"+probmaxstate);
	}
    }
}


public class Viterbi extends Applet implements ActionListener, Runnable {
    SymbolTable symtab;
    StateTable sttab;
    HMMDecoder myhmm = null;
    HMMCanvas canvas;
    Panel p;
    TextArea hmmdesc;
    TextField sentence;
    Button bstart, bskip;
    static final String initialHMM =
    "start: go(cow,1.0)\n" + 
    "cow: emit(moo,0.9) emit(hello,0.1) go(cow,0.5) go(duck,0.3) go(end,0.2)\n" +
    "duck: emit(quack,0.6) emit(hello,0.4) go(duck,0.5) go(cow,0.3) go(end,0.2)\n";
    
    final int sleepmillisec = 100; // 0.1s

    // setup hmm
    // success:true.
    boolean setupHMM(String s) {
	myhmm = new HMMDecoder();
	symtab = new SymbolTable();
	sttab = new StateTable();
	
	State start = sttab.get("start");
	State end = sttab.get("end");
	myhmm.addStartState(start);
	
	boolean success = true;
	StringTokenizer lines = new StringTokenizer(s, "\n");
	while (lines.hasMoreTokens()) {
	    // foreach line.
	    String line = lines.nextToken();
	    int i = line.indexOf(':');
	    if (i == -1) break;
	    State st0 = sttab.get(line.substring(0,i).trim());
	    if (st0 != start && st0 != end) {
		myhmm.addNormalState(st0);
	    }
	    //System.out.println(st0.name+":"+line.substring(i+1));
	
	    StringTokenizer tokenz = new StringTokenizer(line.substring(i+1), ", ");
	    while (tokenz.hasMoreTokens()) {
		// foreach token.
		String t = tokenz.nextToken().toLowerCase();
		if (t.startsWith("go(")) {
		    State st1 = sttab.get(t.substring(3).trim());
		    // fetch another token.
		    if (!tokenz.hasMoreTokens()) {
			success = false; // err. nomoretoken
			break;
		    }
		    String n = tokenz.nextToken().replace(')', ' ');
		    double prob;
		    try {
			prob = Double.valueOf(n).doubleValue();
		    } catch (NumberFormatException e) {
			success = false; // err.
			prob = 0.0;
		    }
		    st0.addLink(st1, prob);
		    //System.out.println("go:"+st1.name+","+prob);
		} else if (t.startsWith("emit(")) {
		    Symbol sym = symtab.intern(t.substring(5).trim());
		    // fetch another token.
		    if (!tokenz.hasMoreTokens()) {
			success = false; // err. nomoretoken
			break;
		    }
		    String n = tokenz.nextToken().replace(')', ' ');
		    double prob;
		    try {
			prob = Double.valueOf(n).doubleValue();
		    } catch (NumberFormatException e) {
			success = false; // err.
			prob = 0.0;
		    }
		    st0.addSymbol(sym, prob);
		    //System.out.println("emit:"+sym.name+","+prob);
		} else {
		    // illegal syntax, just ignore
		    break;
		}
	    }

	    st0.normalize();	// normalize probability
	}
	
	end.addSymbol(symtab.intern("end"), 1.0);
	myhmm.addEndState(end);

	return success;
    }

    // success:true.
    boolean setup() {
	if (! setupHMM(hmmdesc.getText()))
	    return false;
	
	// initialize words
	SymbolList words = new SymbolList();
	StringTokenizer tokenz = new StringTokenizer(sentence.getText());
	words.add(symtab.intern("start"));
	while (tokenz.hasMoreTokens()) {
	    words.add(symtab.intern(tokenz.nextToken()));
	}
	words.add(symtab.intern("end"));
	myhmm.initialize(words);
	canvas.setHMM(myhmm);
	return true;
    }

    public void init() {
	canvas = new HMMCanvas();
	
	setLayout(new BorderLayout());
	p = new Panel();
	sentence = new TextField("moo hello quack", 20);
	bstart = new Button("  Start  ");
	bskip = new Button("Auto");
	bstart.addActionListener(this);
	bskip.addActionListener(this);
	p.add(sentence);
	p.add(bstart);
	p.add(bskip);
	hmmdesc = new TextArea(initialHMM, 4, 20);
	add("North", canvas);
	add("Center", p);
	add("South", hmmdesc);
	
    }

    void setup_fallback() {
	// adjustable
	State cow = sttab.get("cow");
	State duck = sttab.get("duck");
	State end = sttab.get("end");
	
	cow.addLink  (cow,  0.5);
	cow.addLink  (duck, 0.3);
	cow.addLink  (end,  0.2);
	duck.addLink (cow,  0.3);
	duck.addLink (duck, 0.5);
	duck.addLink (end,  0.2);	
	
	cow.addSymbol(symtab.intern("moo"), 0.9);
	cow.addSymbol(symtab.intern("hello"), 0.1);
	duck.addSymbol(symtab.intern("quack"), 0.6);
	duck.addSymbol(symtab.intern("hello"), 0.4);
    }

    public void destroy() {
        remove(p);
        remove(canvas);
    }

    public void processEvent(AWTEvent e) {
        if (e.getID() == Event.WINDOW_DESTROY) {
            System.exit(0);
        }
    }
    
    public void run() {
	if (myhmm != null) {
	    while (myhmm.proceed_decoding()) {
		canvas.repaint();
		try {
		    Thread.sleep(sleepmillisec);
		} catch (InterruptedException e) {
		    ;
		}
	    }
	    myhmm.backward();
	    canvas.repaint();
	    bstart.setLabel("  Start  ");
	    bstart.setEnabled(true);
	    bskip.setEnabled(true);
	    myhmm = null;
	}
    }

    public void actionPerformed(ActionEvent ev) {
	String label = ev.getActionCommand();

	if (label.equalsIgnoreCase("  start  ")) {
	    if (!setup()) {
		// error
		return;
	    }
	    bstart.setLabel("Proceed");
	    canvas.repaint();
	} else if (label.equalsIgnoreCase("proceed")) {
	    // next
	    if (! myhmm.proceed_decoding()) {
		myhmm.backward();
		bstart.setLabel("  Start  ");
		myhmm = null;
	    }
	    canvas.repaint();
	} else if (label.equalsIgnoreCase("auto")) {
	    // skip
	    if (myhmm == null) {
		if (!setup()) {
		    // error
		    return;
		}
	    }
	    bstart.setEnabled(false);
	    bskip.setEnabled(false);
	    Thread me = new Thread(this);
	    me.setPriority(Thread.MIN_PRIORITY);
	    // start animation.
	    me.start();
	}
    }
    
    public static void main(String args[]) {
	Frame f = new Frame("Viterbi");
	Viterbi v = new Viterbi();
	f.add("Center", v);
	f.setSize(400, 400);
	f.show();
	v.init();
	v.start();
    }
    
    public String getAppletInfo() {
        return "A Sample Viterbi Decoder Applet";
    }
}