针对传统序列模式挖掘(SPM)不考虑模式重复性且忽略各项的效用(单价或利润)与模式长度对用户兴趣度影响的问题,提出一次性条件下top-k高平均效用序列模式挖掘(TOUP)算法。TOUP算法主要包括两个核心步骤:平均效用计算和候选模式生成。首...针对传统序列模式挖掘(SPM)不考虑模式重复性且忽略各项的效用(单价或利润)与模式长度对用户兴趣度影响的问题,提出一次性条件下top-k高平均效用序列模式挖掘(TOUP)算法。TOUP算法主要包括两个核心步骤:平均效用计算和候选模式生成。首先,提出基于各项出现位置与项重复关系数组的CSP(Calculation Support of Pattern)算法计算模式支持度,从而实现模式平均效用的快速计算;其次,采用项集扩展和序列扩展生成候选模式,并提出了最大平均效用上界,基于该上界实现对候选模式的有效剪枝。在5个真实数据集和1个合成数据集上的实验结果表明,相较于TOUP-dfs和HAOP-ms算法,TOUP算法的候选模式数分别降低了38.5%~99.8%和0.9%~77.6%;运行时间分别降低了33.6%~97.1%和57.9%~97.2%。TOUP的算法性能更优,能更高效地挖掘用户感兴趣的模式。展开更多
带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-...带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.展开更多
带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹...带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即One-Off条件。提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描。通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响。展开更多
带有灵活通配符和One-Off条件的模式匹配问题(Pattern Matching with flexible Wildcards and One-off Condition,PMWOC)在生物信息学、文本检索和数据流等领域都有着广泛的应用.给定带灵活通配符的模式和文本,在one-off条件下,已有算...带有灵活通配符和One-Off条件的模式匹配问题(Pattern Matching with flexible Wildcards and One-off Condition,PMWOC)在生物信息学、文本检索和数据流等领域都有着广泛的应用.给定带灵活通配符的模式和文本,在one-off条件下,已有算法不能得到模式在文本中的完备解,即模式在文本中最大的出现数目.为此,设计一个求解该问题的算法:首先,利用动态规划的思想去获得模式的所有出现及匹配位置;然后,根据模式的完备解至少包含任意一次出现中的一个位置的思想获得模式解的集合.通过DNA数据进行实验,实验结果显示相对于已有的算法,该算法能够获得最多的出现解.展开更多
研究了带有灵活通配符和长度约束的近似模式匹配问题(approximate pattern matching with wildcards and length constraint,APMWL);为避免文本字符重复使用造成解的指数级增长,引入了一次性使用原则one_off条件,提出了一种后向构造编...研究了带有灵活通配符和长度约束的近似模式匹配问题(approximate pattern matching with wildcards and length constraint,APMWL);为避免文本字符重复使用造成解的指数级增长,引入了一次性使用原则one_off条件,提出了一种后向构造编辑距离矩阵的BAPM(backward approximate pattern matching)算法。该算法在one_off条件、灵活通配符和长度约束条件的基础上,可同时处理插入、替换和删除三种编辑操作。与同类算法Sail_Approx进行实验对比,结果表明BAPM算法获取解的平均增长率可达18.99%,具备良好的解优势。展开更多
文摘针对传统序列模式挖掘(SPM)不考虑模式重复性且忽略各项的效用(单价或利润)与模式长度对用户兴趣度影响的问题,提出一次性条件下top-k高平均效用序列模式挖掘(TOUP)算法。TOUP算法主要包括两个核心步骤:平均效用计算和候选模式生成。首先,提出基于各项出现位置与项重复关系数组的CSP(Calculation Support of Pattern)算法计算模式支持度,从而实现模式平均效用的快速计算;其次,采用项集扩展和序列扩展生成候选模式,并提出了最大平均效用上界,基于该上界实现对候选模式的有效剪枝。在5个真实数据集和1个合成数据集上的实验结果表明,相较于TOUP-dfs和HAOP-ms算法,TOUP算法的候选模式数分别降低了38.5%~99.8%和0.9%~77.6%;运行时间分别降低了33.6%~97.1%和57.9%~97.2%。TOUP的算法性能更优,能更高效地挖掘用户感兴趣的模式。
文摘带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.
文摘带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即One-Off条件。提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描。通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响。
文摘带有灵活通配符和One-Off条件的模式匹配问题(Pattern Matching with flexible Wildcards and One-off Condition,PMWOC)在生物信息学、文本检索和数据流等领域都有着广泛的应用.给定带灵活通配符的模式和文本,在one-off条件下,已有算法不能得到模式在文本中的完备解,即模式在文本中最大的出现数目.为此,设计一个求解该问题的算法:首先,利用动态规划的思想去获得模式的所有出现及匹配位置;然后,根据模式的完备解至少包含任意一次出现中的一个位置的思想获得模式解的集合.通过DNA数据进行实验,实验结果显示相对于已有的算法,该算法能够获得最多的出现解.
