| 基于压缩后缀数组的近似字符串匹配算法 |
| |
| 引用本文： | 胥永康,杨光露,路松峰. 基于压缩后缀数组的近似字符串匹配算法[J]. 计算机工程与应用, 2015, 51(23): 139-142 |
| |
| 作者姓名： | 胥永康 杨光露 路松峰 |
| |
| 作者单位： | 1.中国工程物理研究院 计算机应用研究所，四川 绵阳 6219992.河南中烟工业有限责任公司 南阳卷烟厂，河南 南阳 4730073.华中科技大学 计算机科学与技术学院，武汉 430074 |
| |
| 摘 要： | 近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构，具有检索速度快和适用广泛的优点。利用压缩后缀数组，提出了适合近似字符串匹配搜索算法的数据结构，并在此基础上提出了一种匹配搜索算法。实验结果表明，相对于现有的算法，提出的算法在小字母表的情况下具有计算优势。
|
| 关 键 词： | 模式匹配 近似串匹配 后缀数组 压缩后缀数组 |
Approximate string matching algorithm based on compressed suffix array |
| |
| XU Yongkang,YANG Guanglu,LU Songfeng. Approximate string matching algorithm based on compressed suffix array[J]. Computer Engineering and Applications, 2015, 51(23): 139-142 |
| |
| Authors: | XU Yongkang YANG Guanglu LU Songfeng |
| |
| Affiliation: | 1.Institute of Computer Application Technology, China Academy of Engineering Physics, Mianyang, Sichuan 621999, China2.Nanyang Cigarette Factory, China Tobacco Henan Industrial CO., Ltd, Nanyang, Henan 473007, China3.School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China |
| |
| Abstract: | Approximate string matching is an important issue in the research area of pattern matching. Compressed suffix array is an index structure widely used in string matching and data compression, and it has the advantage of fast retrieval and can be widely applied. In this paper, it proposes a data structure suitable for approximate string matching searching algorithm, and based on the structure, it proposes a matching search algorithm. The result of the experiment shows that compared to the current algorithms, the algorithm proposed in this paper has computing advantage when the small alphabet exists. |
| |
| Keywords: | pattern matching approximate string matching suffix array compressed suffix array |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
|
