带有通配符和长度约束的模式匹配

图书信息

作者：吴信东等著

出版社：科学出版社

定价：98.00

ISBN：9787030474100

出版时间：2016-03-01

分类：图书,行业职业,计算机,工具书

商品介绍

目录

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

2.3.4Time and Space Complexities

2.4Conclusions

2.5Other Algorithms and References

Chapter 3Pattern Matching Based on Bit-parallelism

3.1Introduction

3.2The BPBM Algorithm

3.2.1Pattem Searching with Two Automata

3.2.2Extending Bit-parallelism Operation for Flexible Pattern with Multiple Wildcards

3.2.3On-line Sequential PaRem Matching

3.2.4Off-line Occurrence Pruning

3.2.5ComplexityAnalysis

3.2.6Experiments

3.3Multiple-pattern Matching

3.3.1Basic Concept

3.3.2Prefix NFA and SuffiX NFA

3.3.3Bit Mask

3.3.4Occurrence Verification

3.3.5Occurrence Printing

3.3.6BWW and FWW Algorithms

3.3.7Complexity Analysis

3.3.8Experiments

3.4PaRem Matching with Arbitrary-length Wildcards

3.4.1Problem Definition

3.4.2Bit-parallelism with Arbitrary-length Wildcards

3.4.3Algorithm Design

3.4.4Time and Space Complexities

3.4.5Global Length Constraint

3.4.6Experiments

3.5Conclusions

3.6OtherAlgorithms and References

Chapter 4Efficient Algorithms for Counting the Number of Occurrences

4.1Introduction

4.2The PAIG Algorithm

4.2.1Problem Definition

4.2.2An Illustration Example

4.2.3Algorithm Description

4.2.4ComplexityAnalysis

4.2.5Algorithm Enhancements

4.2.6Global Length Constraints

4.2.7Pattern Matching Frequency

4.2.8Experiments

4.3The NAMEIC Algorithm Based on Nettree

4.3.1The Definition of Netffee

4.3.2The NAMEIC Algorithm

4.3.3Correctness

4.3.4An Illustration Example

4.3.5Analysis

4.3.6Experiments

4.4Conclusions

4.5OtherAlgorithms and References

Chapter 5Pattern Matching with General Gaps

5.1Introduction

5.2Strict Pattem Matching with General Gaps

5.2.1Problem Definition and Theoretical Analysis

5.2.2Subnettree

5.2.3The SETS Algorithm Design

5.2.4Complexity and Completeness Analysis

5.2.5A Running Example

5.2.6Experiments

5.3Approximate Pattem Matching with General Gaps

5.3.1Problem Definition andAnalysis

5.3.2Subnettree for SAP

5.3.3The SETAAlgorithm

5.3.4Analysis

5.3.5A Running Example

5.3.6Experiments

5.4Conclusions

5.5Other Algorithms and References

Chapter 6The WoW Algorithm

6.1Introduction

6.2Nettree（P，S） and Degree

6.2.1Nettree（P，S）

6.2.2Centrality-degree

6.2.3Subtree

6.3Weighted Centralization Measure

6.4Algorithm Design.l

6.4.1WOW Algorithm

6.4.2Theorems

6.4.3ComplexityAnalysis

6.5Experiments

6.5.1Experiments on DNA Sequences

6.5.2Experiments on Artificial Data

6.5.3Experiments on Parameter ξ

6.6Conclusions

6.7OtherAlgorithms and References

Chapter 7The RBCTAlgorithm

7.1Introduction

7.2Left-most Strategy

7.3Problem Definition

7.4CluTree

7.4.1The Structure and Property of the Clullree

7.4.2Path Selection and Pruning

7.5RBCT Algorithm

7.5.1Algorithm Description

7.5.2Complexity Analysis

7.5.3A Running Example

7.6ImprovingAlgorithm Performance

7.7Experiments

7.8Conclusions

7.9OtherAlgorithms and References

References

内容简介

为了打破必须固定通配符间隔约束的，实现可以根据实际问题灵活的指定通配符位置以及长度约束，成为了很近几年研究的热点。本书介绍目前具有代表性的带有灵活通配符的模式匹配算法。首先，给出了一个很早解决局部长度约束和全局长度约束的模式匹配算法SAIL，该算法采用很左很优的策略，只要在文本中找到模式的出现，就输出匹配位置。该算法不仅能够处理灵活的通配符，还引入了具有重要的理论和实际应用价值的one-off条件（模式的任意两次出现都不能共享文本中同一位置的字符）。第二，为了提高解决带灵活通配符约束的模式匹配算法的有效性，给出了一种基于位并行的方法，提高了该问题的时空效率。第三，如果模式中有重复字符时，在线的算法可能会出现丢解，给出了一种新的启发式算法。该算法基于一种新的非线性数据结构-WOW。理论分析和实验结果表面了该方法的有效性和完备性。第四，考虑到在不处理one-off条件下，解的数目有可能是指数级的情况，给出了一种只计算模式在文本中出现次数的方法，该方法在序列模式挖掘中得到了应用。很后，我们把该问题推广到近似模式匹配和多模式匹配中，并给出了算法的设计和正确性分析。