靳超艳 刘靖宇



具有间隙约束的模式匹配的研究进展

靳超艳 刘靖宇

河北工业大学计算机科学与软件学院，天津 300401

模式匹配（也称为字符串匹配）是计算机科学的经典问题之一，也是众多交叉学科解决技术问题的关键。具有间隙约束的序列模式匹配已成为模式匹配问题中的研究热点，在很多领域有着广泛应用，如生物学中DNA序列的研究、音乐领域音符信息的检索以及目前研究火热的大数据领域等，因此具有间隙约束的模式匹配问题是诸多领域的基础，具有很高的研究价值和意义。因此，总结了近年来具有间隙约束的模式匹配的成果和进展，对具有间隙约束的模式匹配的发展趋势进行了展望，以便对具有间隙约束的模式匹配问题做进一步研究。

模式匹配；间隙约束；研究进展

引言

近年来，随着科学技术的迅猛发展，人类进入了信息社会。人类社会产生的数据量与日俱增，在很多领域涌现出大量的序列数据。如何对这些序列数据进行分析和挖掘以提取有价值的信息，是目前人们比较关注的问题。数据挖掘技术的基础就是模式匹配问题。

模式匹配也称为字符串匹配。此问题描述的是从序列串中找到与模式串P相匹配的出现的个数或者出现的位置。其中，序列串S和模式串来自同一个字符集。具有间隙的模式匹配问题的研究较早，所研究的模式串间隙都是单个可变间隙，例如Manber等人[1]为解决单个可变间隙的模式匹配问题提出了有效算法。……