Application of Improved BM Algorithm in String Approximate Matching

被引：4

作者：

Duan, Ying ^{[1
]}

Long, Hua ^{[1
]}

Qu, Yu Quan ^{[1
]}

机构：

[1] Kunming Univ Sci & Technol, Fac Informat Engn & Automat, Kunming 650000, Yunnan, Peoples R China

来源：

PROCEEDINGS OF THE 3RD INTERNATIONAL CONFERENCE ON MECHATRONICS AND INTELLIGENT ROBOTICS (ICMIR-2019) | 2020年 / 166卷

关键词：

BM algorithm; approximate search; pattern matching;

D O I：

10.1016/j.procs.2020.02.017

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

In the paper, we will propose a new algorithm to improve the error tolerance and flexibility of the exact matching by combining the bad characters and good suffix rules in Boyer-Moore algorithm. First of all, using the binary sequence function to control the output range of the target segment; secondly, matching the target segment with partial similar features. The experimental results show that the improved algorithm can improve the accuracy of the target segment and the number of segments matched can be increased to more than 7 times of the exact matching segment. (C) 2020 The Authors. Published by Elsevier B.V.

引用

页码：576 / 581

页数：6

共 11 条

[1]

Al-Khamaiseh K., 2014, Journal of Engineering Research and Applications, V4, P144

[2] FAST STRING SEARCHING ALGORITHM [J].

BOYER, RS ;

MOORE, JS .

COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772

[3]

Charras C., Exact String Matching Algorithms

[4]

Chen Li, 2004, J WUHAN U TECHNOLOGY, V28, P137

[5] PRACTICAL FAST SEARCHING IN STRINGS [J].

HORSPOOL, RN .

SOFTWARE-PRACTICE & EXPERIENCE, 1980, 10 (06) :501-506

[6]

Liu Wei-Qin, 2008, RES NETWORK SENSITIV

[7]

Lu Hongwei, 2006, Journal of Huazhong University of Science and Technology, V34, P41

[8]

Min Lian-Ying, 2006, J WUHAN U TECHNOLOGY, P528

[9]

[孙文静 Sun Wenjing], 2013, [计算机科学, Computer Science], V40, P174

[10]

Yang Wei, 2014, P 19 NAT YOUTH COMM

← 1 2 →