Finite State Machine And Its Application

The content of this article is to introduce finite state machine, study finite state machineand implement its application in address recognition. This paper first introduces thetheoretical knowledge and the working mechanism of deterministic finite machine,Non-deterministic Finite State Machines and Probabilistic finite state machine, so incorporatethis three model into an integrated theoretical frame. Then apply these theoretical knowledgeto address recognition. In the process of applying finite state machine to address recognition,this paper used the method is differ from previous method which make the single text as finitestate machine arc weights. This paper make the administrative unit name as finite statemachine arc weights, because address is make up of administrative unit name. This methodnot only reduce the space complexity of the algorithm but also increase the execution speed ofthe algorithm. In order to achieve the purpose of address recognition, when the basic unit isadministrative unit. This paper use the ICTCLAS segmentation system to do the work ofaddress segmentation, then make the segmentation unit sequentially input the finite statemachine go to identification. In the initialization phase of the identification, this thesis makeand implement a make finite state machine algorithm. In this method the node is nested instate point, so make the finite state machine’s conversion is sorted by some law. This methodimprove the query speed because the conversion is sorter. In the identification process, thispaper implement recognition algorithm using index lookup. This recognition algorithm havinga small search, a small amount of matching the advantages based on the created finitestatemachine. So it can improve the recognition speed. To verify the accuracy and rapidity of thealgorithm, ultimately this article use all at or above the county level administrative units asinput set, then establish a finite state machine and go to address recognition. The results show,rapid address recognition can be achieved through the finite state machine. First to achievethe verification of the address recognition is strict matching. Introduce the law of addressrecognition that using probabilistic finite state machine at the end of the article. So we canrecognize the address which have wrong writing rules or wrong word.