Journal of Guangdong University of Technology ›› 2017, Vol. 34 ›› Issue (05): 56-59.doi: 10.12052/gdutxb.160157

Previous Articles     Next Articles

A Digital Order-Preserving-Matching Algorithm Based on Binary Coding Processing

Luo Guo-hui, Lin Sui, Jiang Wen-chao   

  1. School of Computers Science, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2016-12-07 Online:2017-09-09 Published:2017-07-10

HTML

PDF (PC)

2857

Abstract: Giving a digital text T and a number of text paragraphs P, and then finding in T all the same order with P-related sub-string is called the digital order preserving and matching. Digital order-matching is the focus of research on similarity and prediction trend, widely used in stock forecast, fund trend and weather forecast. Aiming at the efficiency of preserving and matching algorithm in digital matching, a character matching method based on binary coding has been proposed. Firstly, the binary characters are preprocessed before the order matching. Then the four main algorithms are used to achieve the order-preserving and matching, and the matching time and complexity are compared and analyzed. The experimental results show that the proposed method effectively improves the efficiency of digital character matching while maintaining a low time complexity.

Key words: order-preserving, binary-coding, time complexity, character matching algorithm

CLC Number: 

  • TP301
[1] NAVARRO G, RAFFINOT M. Flexible Pattern Matching in String Practical On-line Search Algorithms for Texts and BiologicalSequences[M]. Cambridge:Cambridge University Press, 2002. 23-28. [2] FARO S, LECROQ T. The exact online string matching problem:A review of the most recent results[J]. ACM Computing Surveys, 2013, 45(2):13-13. [3] KNUTH D E, MORRIS J H, PRATT V R. Fast pattern matchingin string[J]. SIAM Journalon Computing, 1977, 20(6):323-350. [4] BOYER R S, MOORE J S. A fast string searching algorithm[J]. Communications of the ACM, 1977, 20(10):762-772. [5] 苏德福, 钟诚. 计算机算法设计与分析[M]. 2版. 北京:清华大学出版社, 2001. 57-59. [6] DANIEL M S. Very fast substring search algorithm[J]. Communications of the ACM, 1990, 33(8):132-142. [7] AHMED M, KAYKOBAD M, CHOWDHURY R A. A new string matching algorithm[J]. Computer Mathematics, 2003, 80(7):825-834. [8] 赵森严, 黄伟, 李阳铭. 一种改迚的KMP入侵检测的模式匹配算法[J]. 井冈山大学学报(自然科学版), 2013, 34(1):55-58.ZHAO S Y, HUANG W, LI Y M. Improved model matching algorithm for KMP Intrusion detection[J]. Journal of Jinggangshan University:Natural Science, 2013, 34(1):55-58. [9] AMIR A, FARACH M. Efficient 2-dimensional approximate matching of halfrectangular figures[J]. Information and Computation, 2010, 118(1):1-11. [10] 欧嵬, 吴纯青. 几种字符串匹配算法的分析和比较[J]. 微处理机, 2007, 28(4):59-62.OU W, WU C Q. Analysis and comparison of several string matching algorithms[J]. Microprocessors, 2007, 28(4):59-62. [11] 杨俊丽, 吕晓燕, 满晰. 基于改进的KMP算法的词频统计[J]. 微计算机信息, 2010, 26(9):161-162.YANG J L, LYU X Y, MAN X. Based on improved KMP algorithm for word frequency statistics[J]. Microcomputer Information, 2010, 26(9):161-162. [12] 李莉, 江育娥, 林劼, 等. 基于KMP算法的改进算法KMPP[J]. 计算机工程与应用, 2016, 52(8):33-37.LI L, JIANG Y E, LIN J, et al. Improved algorithm KMPP based on KMP[J]. Computer Engineering and Applications, 2016, 52(8):33-37. [13] CLIFFORD R, ILIOPOULOS C S. Approximate string matching for music analysis[J]. Soft Computing, 2004, 8(9):597-603. [14] 陈文伟, 赵侠, 黄金才. 进化创新的绕行变换[J]. 广东工业大学学报, 2017, 34(1):1-5.CHEN W W, ZHAO X, HUANG J C. Modeling transformation of evolutionary innovation[J]. Journal of Guangdong University of Technology, 2017, 34(1):1-5.
[1] Zhang Rui, Lyu Jun. Single-channel Speech Separation Based on Separated SI-SNR Regression Estimation and Adaptive Frequency Modulation Network [J]. Journal of Guangdong University of Technology, 2023, 40(02): 45-54.
[2] Liu Dong-ning, Wang Zi-qi, Zeng Yan-jiao, Wen Fu-yan, Wang Yang. Prediction Method of Gene Methylation Sites Based on LSTM with Compound Coding Characteristics [J]. Journal of Guangdong University of Technology, 2023, 40(01): 1-9.
[3] Xu Wei-feng, Cai Shu-ting, Xiong Xiao-ming. Visual Inertial Odometry Based on Deep Features [J]. Journal of Guangdong University of Technology, 2023, 40(01): 56-60,76.
[4] Liu Dong-ning, Zheng Chu-chu. Task Allocation under Cool Down Time Constraints via the Many to Many Assignment [J]. Journal of Guangdong University of Technology, 2021, 38(05): 10-15.
[5] Zhang Wei, Tong Ru, Wu Shi-jue, Wang Zi-qi, Teng Shao-hua. Group Role Assignment Based on KD45 Closure [J]. Journal of Guangdong University of Technology, 2021, 38(04): 26-34.
[6] Lyu Shu-yuan, Liu Fu-chun, Zhao Rui, Deng Xiu-qin, Cui Hong-gang. A Research on Patterns Fault Prediction of Decentralized Discrete Event Systems [J]. Journal of Guangdong University of Technology, 2021, 38(01): 54-63.
[7] Hao Zhi-feng, Li Yi-ting, Cai Rui-chu, Zeng Yan, Qiao Jie. A Research on Users’ Shopping Behaviors in Social Network Based on Causal Model [J]. Journal of Guangdong University of Technology, 2020, 37(03): 1-8.
[8] Hong Ying-han, Hao Zhi-feng, Mai Gui-zhen, Chen Ping-hua. Learning Causal Skeleton by Using Lower Order Conditional Independent Tests [J]. Journal of Guangdong University of Technology, 2019, 36(05): 14-19.
[9] Chen He-feng, Wu Nai-qi. Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net [J]. Journal of Guangdong University of Technology, 2019, 36(04): 1-9.
[10] Lei Rui-sheng, Ling Bingo Wing-Kuen. A Heart Rate Variability Analysis via Modified Multi-time Scale Permutation Entropy [J]. Journal of Guangdong University of Technology, 2019, 36(03): 32-38.
[11] Shi Cong-cong, Liu Fu-chun. A Pattern-Based Failure Diagnosis of Fuzzy Discrete-Event Systems [J]. Journal of Guangdong University of Technology, 2019, 36(01): 35-41.
[12] Huang Tian-an, Cheng Liang-lun, Huang Si-meng. A Research of Fluctuation Analysis Method on Process Flow of Production Process Based on Internet of Manufacturing Things [J]. Journal of Guangdong University of Technology, 2019, 36(01): 57-62.
[13] Liu Dong-ning, Liu Tong-wu, Song Jing-jing, Hou Yan. Multiple Assignment in Task Allocation of Communication Base Stations [J]. Journal of Guangdong University of Technology, 2018, 35(06): 69-76.
[14] Ye Bin-bin, Liu Fu-chun. Failure Predictability of Stochastic Discrete Event Systems [J]. Journal of Guangdong University of Technology, 2018, 35(06): 83-89.
[15] Zheng San-qiang, Han Xiao-zhuo. A Simulation of Cellular Automata Based on the SIR Infectious Disease Model with Multifactorial Constraints [J]. Journal of Guangdong University of Technology, 2018, 35(05): 51-59.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © 2017 Journal of Guangdong University of Technology
Add：729 East Dongfeng RD., Guangzhou PRC. Postcode: 510090
Tel：020-37626653,020-37626139,020-37626396
Email：xbzrb@gdut.edu.cn
Supported:Beijing Magtech