有限元状态机

什么是有限状态机

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

可以表示为：

img img

简单来说，有限状态机是一个特殊的有向图，它包括一些状态（节点）和连接这些状态的有限弧，他有一个开始状态和一个终止状态，以及若干中间状态，每个弧上带有一个状态进入下一个状态的条件。

例如：

识别地址的有限状态机

代码实现有限状态机查找地址：

#!/usr/bin/env Python
# coding=utf-8
import os,sys



'''
状态转移器，开始状态，中间状态，结束状态。
'''
class StateMachine:
    def __init__(self):
        self.handlers = {}
        self.startState = None
        self.endStates = []

    def add_state(self, name, handler, end_state=0):
        '''
        增加状态的名字、函数；以及结束状态可选输入
        name:state name,
        handler:transfer function,
        end_state:true/false end state,
        '''
        name = name.upper()
        self.handlers[name] = handler
        if end_state:
            self.endStates.append(name)

    def set_start(self, name):
        '''
        :param name: 定义了开始
        :return:
        '''
        self.startState = name.upper()

    def run(self, cargo):
        '''

        :param cargo: 传入字符串进来
        :return:
        '''
        try:#检测一下是否有开始状态
            handler = self.handlers[self.startState]
        except:
            raise InitializationError("must call .set_start() before run()")
        if not self.endStates:
            raise InitializationError("at least one state must be an end_state")

        while True:#检查最新的状态是否在结束状态中，假如不是，执行状态转义
            newState, cargo = handler(cargo)
            if newState.upper() in self.endStates:
                print("reached ", newState)
                break
            else:
                handler = self.handlers[newState.upper()]

positive_adjectives = ['great', 'super', 'fun', 'entertaining', 'easy']
negative_adjectives = ['boring', 'difficult', 'ugly', 'bad']

def start_transitions(txt):
    splitted_txt = txt.split(None, 1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt, "")
    if word == 'Python':
        newState = 'Python_state'
    else:
        newState = 'error_state'
    return (newState, txt)

def python_state_transitions(txt):
    splitted_txt = txt.split(None, 1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt, "")
    if word == 'is':
        newState = 'is_state'
    else:
        newState = 'error_state'
    return (newState, txt)

def is_state_transitions(txt):
    splitted_txt = txt.split(None, 1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt, "")
    if word == 'not':
        newState = 'not_state'
    elif word in positive_adjectives:
        newState = 'pos_state'
    elif word in negative_adjectives:
        newState = 'neg_state'
    else:
        newState = 'error_state'
    return (newState, txt)

def not_state_transitions(txt):
    splitted_txt = txt.split(None, 1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt, "")
    if word in positive_adjectives:
        newState = 'neg_state'
    elif word in negative_adjectives:
        newState = 'pos_state'
    else:
        newState = 'error_state'
    return (newState, txt)

if __name__ == '__main__':
    m = StateMachine()
    m.add_state('Start', start_transitions)
    m.add_state('Python_state', python_state_transitions)
    m.add_state('is_state', is_state_transitions)
    m.add_state('not_state', not_state_transitions)
    m.add_state('neg_state', None, end_state=1)
    m.add_state('pos_state', None, end_state=1)
    m.add_state('error_state', None, end_state=1)

    m.set_start('Start')
    m.run('Python is great')
    m.run('Python is not great')
    m.run('Python is bad')
    m.run('Python is not bad')
    m.run('python is great')

• 其他应用
  在语音识别和自然语言的理解中有着非常重要的作用，特别是加权的有限状态机传感器（Weighted Finite State Transducer，简称WFST），和离散的马尔科夫链模型一致
  WFST的特殊性在于：有限状态机中的每个状态由输入和输出符号定义

  
  image.png

WFST中的每一条路径就是一个候选句子，概率最大的句子就是识别结果，算法的原理就是动态规划