COMP9318 (14S1) PROJECT DUE DATE: 23:59 21 MAY 2014 (WED) 1. Objective In this project, you will implement and extend the Viterbi algorithm for parsing Aus- tralian address data. Note that it will take you quite some time to complete this project even if you are familiar with Java programming and have good programming experience. Therefore, we earnestly recommend that you start working on this project as early as possible. 2. Background We have talked about the standard Hidden Markov Model (HMM) and the Viterbi algorithm in the class. More information can be found in Section 5 of A Revealing Introduction to Hidden Markov Models” by Mark Stamp. There are a few dierences or additions required for this specic project, and they will be introduced shortly. 3. Task I: Standard Viterbi Your rst task is to write a Java class named Proj1, which receives three command line arguments: STATE FILE: it is the le that stores part of the HMM model. Its detailed format will be described shortly. SYMBOL FILE: it is the le that stores the other part of the HMM model. Its detailed format will be described shortly. QUERYFILE: the le that contains addresses to be parsed. Its format will be de- scribed shortly. k: species the top-k state sequence to be output for each address in the QUERYFILE. Your program should read in the HMM model from STATE FILE and SYMBOL FILE, and then nd best (i.e., top-1) state sequences and its corresponding probability for each of the addresses in the QUERYFILE. You can always assume the model les are correct, i.e., you do not need to deal with possible errors/inconsistencies in the le, though you should check everywhere in production code, especially in light of the recent heartbleed bug. 1
2 DUE DATE: 23:59 21 MAY 2014 (WED) 3.1. HMM Model File Format. The STATE FILE is a plain text le, where each line carries some information, as specied below: The rst line is an integer N, which is the number of states. The next N lines are the descriptive names of the…