作 者:吴信东 等 著
定 价:98
出 版 社:科学出版社
出版日期:2016年03月01日
页 数:192
装 帧:精装
ISBN:9787030474100
●Preface
●Chapter 1Introduction
●1.1The Aim and Focus of This Book
●1.2Overview
●1.3Basic Concepts
●Chapter 2The SAIL and SAIL-APPROX Algorithms
●2.1Introduction
●2.2The SAILAlgorithm
●2.2.1The Significance of the One-off Condition
●2.2.2Issues for Considerations
●2.2.3Algorithm Design
●2.2.4A Running Example
●2.2.5Correctness Analysis
●2.2.6Completeness Analysis
●2.2.7Time and Space Complexities
●2.2.8Discussions
●2.3The SAIL-APPROX Algorithm
●2.3.1Problem Definition
●2.3.2Algorithm Design
●2.3.3Correctness Analysis
●部分目录
为了打破必须固定通配符间隔约束的,实现可以根据实际问题灵活的指定通配符位置以及长度约束,成为了很近几年研究的热点。本书介绍目前具有代表性的带有灵活通配符的模式匹配算法。首先,给出了一个很早解决局部长度约束和全局长度约束的模式匹配算法SAIL,该算法采用很左很优的策略,只要在文本中找到模式的出现,就输出匹配位置。该算法不仅能够处理灵活的通配符,还引入了具有重要的理论和实际应用价值的one-off条件(模式的任意两次出现都不能共享文本中同一位置的字符)。第二,为了提高解决带灵活通配符约束的模式匹配算法的有效性,给出了一种基于位并行的方法,提高了该问题的时空效率。第三,如果模式中有重复字符时,在线的算法可能会出现丢解,给出了一种新的启发式算法。该算法基于一种新的非线性数据结构-WOW。理论分析和实验结果表面了该方法的有效性和完备性。第四,考虑到在不处理one-off条件下,解的数目有可能是指数级等