广东工业大学学报 ›› 2017, Vol. 34 ›› Issue (05): 56-59.doi: 10.12052/gdutxb.160157

• 综合研究 • 上一篇    下一篇

一种基于二进制编码处理的数字保序匹配算法

罗国辉, 林穗, 姜文超   

  1. 广东工业大学 计算机学院, 广东 广州 510006
  • 收稿日期:2016-12-07 出版日期:2017-09-09 发布日期:2017-07-10
  • 通信作者: 林穗(1972-),女,副教授,硕士生导师,主要研究方向为云计算、数据挖掘.E-mail:1393010714@qq.com E-mail:1393010714@qq.com
  • 作者简介:罗国辉(1991-),男,硕士研究生,主要研究方向为大数据及云计算.
  • 基金资助:
    广州市科技计划项目（2017010160012）

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

摘要： 给出一个数字文本T跟一个数字文本段落P，在T中找出所有跟P相同关联顺序的子串称之为数字保序匹配问题.数字保序匹配问题是检测相似度和预测趋势领域的研究重点，在股票预测、基金走势、天气预报等方面有广泛应用.针对保序匹配算法在数字匹配中的效率问题，提出了基于二进制编码的数字字符匹配方法.首先，在保序匹配前先对数字字符进行二进制编码预处理；然后使用4种主流算法实现了保序匹配，并对匹配时间和复杂度进行对比分析.实验结果表明：该处理方法有效提高了数字字符匹配效率，同时保持了较低的时间复杂度.

关键词: 保序匹配, 二进制编码, 时间复杂度, 字符匹配算法

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

中图分类号: 

  • 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] 张锐, 吕俊. 基于分离结果信噪比估计与自适应调频网络的单通道语音分离技术[J]. 广东工业大学学报, 2023, 40(02): 45-54.
[2] 刘冬宁, 王子奇, 曾艳姣, 文福燕, 王洋. 基于复合编码特征LSTM的基因甲基化位点预测方法[J]. 广东工业大学学报, 2023, 40(01): 1-9.
[3] 徐伟锋, 蔡述庭, 熊晓明. 基于深度特征的单目视觉惯导里程计[J]. 广东工业大学学报, 2023, 40(01): 56-60,76.
[4] 刘冬宁, 郑楚楚. 冷却时间约束多对多任务分配及其优化[J]. 广东工业大学学报, 2021, 38(05): 10-15.
[5] 张巍, 仝茹, 吴诗珏, 王子奇, 滕少华. 基于KD45闭包的群组角色指派研究[J]. 广东工业大学学报, 2021, 38(04): 26-34.
[6] 吕舒园, 刘富春, 赵锐, 邓秀勤, 崔洪刚. 分布式离散事件系统的模式故障预测研究[J]. 广东工业大学学报, 2021, 38(01): 54-63.
[7] 郝志峰, 黎伊婷, 蔡瑞初, 曾艳, 乔杰. 基于因果模型的社交网络用户购物行为研究[J]. 广东工业大学学报, 2020, 37(03): 1-8.
[8] 洪英汉, 郝志峰, 麦桂珍, 陈平华. 基于低阶条件独立测试的因果网络结构学习方法[J]. 广东工业大学学报, 2019, 36(05): 14-19.
[9] 陈鹤峰, 伍乃骐. 基于Petri网可达性和结构的最大许可控制器设计[J]. 广东工业大学学报, 2019, 36(04): 1-9.
[10] 雷瑞生, 凌永权. 基于改进的多时间尺度特征排列熵的心率变异性分析研究[J]. 广东工业大学学报, 2019, 36(03): 32-38.
[11] 石聪聪, 刘富春. 模糊离散事件系统基于模式的故障诊断[J]. 广东工业大学学报, 2019, 36(01): 35-41.
[12] 黄田安, 程良伦, 黄思猛. 制造物联网生产过程工序流波动分析方法研究[J]. 广东工业大学学报, 2019, 36(01): 57-62.
[13] 刘冬宁, 刘统武, 宋静静, 侯艳. 面向基站代维人员分工协作优化的多重指派研究[J]. 广东工业大学学报, 2018, 35(06): 69-76.
[14] 叶彬彬, 刘富春. 随机离散事件系统的故障预测[J]. 广东工业大学学报, 2018, 35(06): 83-89.
[15] 郑三强, 韩晓卓. 多因素制约下的SIR传染病模型的元胞自动机仿真模拟研究[J]. 广东工业大学学报, 2018, 35(05): 51-59.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发