| SDFA： a Uniform Model for String Matching Algorithms |
| |
| 引用本文： | 贺龙涛,Fang Binxing,YUN Xiaochun,Hu Mingzeng.SDFA： a Uniform Model for String Matching Algorithms[J].高技术通讯(英文版),2004,10(2):34-37. |
| |
| 作者姓名： | 贺龙涛 Fang Binxing YUN Xiaochun Hu Mingzeng |
| |
| 作者单位： | ResearchCenterofComputerNetworkandSecurityTechnology,HarbinInstituteofTechnology,Harbin150001,P.R.China |
| |
| 基金项目： | SupportedbytheHighTechnologyResearchDevelopmentProgramofChinaandtheDefencePre researchProjectoftheTenthFive YearPlanofChina . |
| |
| 摘 要： | String matching algorithms play an important role in computer science. However, there is no uniform mathematical model to describe these algorithms. Thus, read-head-Skippable DFA (SDFA) is put for-ward, which is an extension of two-way DFA. It is proved that SDFA is equivalent to DFA. Furthermore,SDFA is a more natural mathematical model for string matching algorithms. After that, four types of the movement of the read head of string matching are analyzed and modeled by SDFA. Finally, the SDFA model of BMA string matching algorithms is given.
|
| 关 键 词： | 字符串匹配算法 DFA 2DFA SDFA 首读跳跃确定性有限自动机 |
SDFA:a Uniform Model for String Matching Algorithms |
| |
| He Longtao,Fang Binxing,Yun Xiaochun,Hu Mingzeng.SDFA:a Uniform Model for String Matching Algorithms[J].High Technology Letters,2004,10(2):34-37. |
| |
| Authors: | He Longtao Fang Binxing Yun Xiaochun Hu Mingzeng |
| |
| Institution: | Research Center of Computer Network and Security Technology, Harbin Institute of Technology, Harbin 150001, P.R.China;Research Center of Computer Network and Security Technology, Harbin Institute of Technology, Harbin 150001, P.R.China;Research Center of Computer Network and Security Technology, Harbin Institute of Technology, Harbin 150001, P.R.China;Research Center of Computer Network and Security Technology, Harbin Institute of Technology, Harbin 150001, P.R.China |
| |
| Abstract: | String matching algorithms play an important role in computer science. However, there is no uniform mathematical model to describe these algorithms. Thus, read head Skippable DFA (SDFA) is put forward, which is an extension of two way DFA. It is proved that SDFA is equivalent to DFA. Furthermore, SDFA is a more natural mathematical model for string matching algorithms. After that, four types of the movement of the read head of string matching are analyzed and modeled by SDFA. Finally, the SDFA model of BMA string matching algorithms is given. |
| |
| Keywords: | string matching DFA 2DFA SDFA |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
