| 主权项 |
一种用在字符串搜索中的基于扩展有限状态机的多正则表达式联合搜索方法，所述扩展有限状态机包括有穷状态集合Q、输入字母表Vt、状态转换函数δ、始态q0、终止状态集F、状态标识集合P、状态与状态标识的映射函数ρ、状态转换函数的标识集合N和状态转换函数与状态转换函数标识的映射函数ω，其中状态标识集合P用于给状态机中的每一个状态加一个标识，状态与状态标识的映射函数ρ用于通过该映射函数计算出一个给定状态的状态标识，状态转换函数的标识集合N用于给状态机中的每一个状态转换函数引入一个唯一的标识，状态转换函数与状态转换函数标识的映射函数ω用于计算与一条状态转换函数对应的标识；所述扩展有限状态机包括扩展非确定性有限状态机和扩展确定性有限状态机，所述扩展非确定性有限状态机中的状态转换函数允许是多值的，所述扩展确定性有限状态机不接受空串作为输入且状态转换函数是单值的；该方法的特征在于：(1)构造同时识别多个正则表达式的扩展非确定性有限状态机或扩展确定性有限状态机；(2)分配一个足够大的状态转换函数标识空间S，该空间中的每一个元素用来存放一个状态转换函数标识，用变量flag标识该空间的使用状况，置flag＝0，记当前状态标识集合U＝ρ(q0)；(3)正向搜索时，每当调用一次状态转换函数δ(p，a)＝q，则自动执行下面三个步骤：U＝U∩ρ(q)，S[flag]＝ω(p，a，q)，flag＝flag+1，其中，δ(p，a)＝q表示状态p在遇到字符a时转移到状态q；(4)逆向回退字符时：(4.1)如果只沿着某个正则表达式回退，且该正则表达式的标识为i，执行如下步骤：记状态机当前状态为m，若i∈ρ(m)，则可以回退字符，否则停止回退，若可以回退字符，则查找状态转换函数标识空间对应的映射函数ω，然后把字符a回退回输入串中，同时把p设为当前状态，执行flag＝flag-1，释放标识空间，若继续回退字符，则重复本步骤，否则结束回退；(4.2)如果不沿着某个正则表达式回退，则执行如下步骤：记状态机当前状态为m，查找状态转换函数标识空间对应的映射函数ω，然后把字符a回退回输入串中，同时把p设为当前状态，执行flag＝flag-1，若继续回退字符，则重复本步骤，否则结束回退。 |
