Loading…

Strict pattern matching under non-overlapping condition

Pattern matching(or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support(or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state...

Full description

Saved in:
Bibliographic Details
Published in:中国科学:信息科学(英文版) 2017 (1), p.5-20
Main Author: Youxi WU Cong SHEN He JIANG Xindong WU
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 20
container_issue 1
container_start_page 5
container_title 中国科学:信息科学(英文版)
container_volume
creator Youxi WU Cong SHEN He JIANG Xindong WU
description Pattern matching(or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support(or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints(or flexible wildcards) uses the number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.
format article
fullrecord <record><control><sourceid>chongqing</sourceid><recordid>TN_cdi_chongqing_primary_74708871504849554849484849</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><cqvip_id>74708871504849554849484849</cqvip_id><sourcerecordid>74708871504849554849484849</sourcerecordid><originalsourceid>FETCH-chongqing_primary_747088715048495548494848493</originalsourceid><addsrcrecordid>eNqdS90KwiAYlSho1N7BFxA03dTrKLqvi-5CNtuM7dOcBb19DnqCDpwfDucsUMFUrQnTTC9zrqUgkvPrGpXT9KAZnNOdVAWS5xRdk3AwKdkIeDSp6R10-AWtjRg8EP-2cTAhzG3joXXJedii1d0Mky1_vkH8eLjsT6TpPXTPvL2F6EYTPzcpJFVKsooKJXRVzZqZlf_3-gINwD8R</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Strict pattern matching under non-overlapping condition</title><source>Springer Nature</source><creator>Youxi WU Cong SHEN He JIANG Xindong WU</creator><creatorcontrib>Youxi WU Cong SHEN He JIANG Xindong WU</creatorcontrib><description>Pattern matching(or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support(or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints(or flexible wildcards) uses the number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.</description><identifier>ISSN: 1674-733X</identifier><identifier>EISSN: 1869-1919</identifier><language>eng</language><ispartof>中国科学:信息科学(英文版), 2017 (1), p.5-20</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Uhttp://image.cqvip.com/vip1000/qk/84009A/84009A.jpg</thumbnail><link.rule.ids>314,780,784,4024</link.rule.ids></links><search><creatorcontrib>Youxi WU Cong SHEN He JIANG Xindong WU</creatorcontrib><title>Strict pattern matching under non-overlapping condition</title><title>中国科学:信息科学(英文版)</title><addtitle>Science China(Information Sciences)</addtitle><description>Pattern matching(or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support(or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints(or flexible wildcards) uses the number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.</description><issn>1674-733X</issn><issn>1869-1919</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNqdS90KwiAYlSho1N7BFxA03dTrKLqvi-5CNtuM7dOcBb19DnqCDpwfDucsUMFUrQnTTC9zrqUgkvPrGpXT9KAZnNOdVAWS5xRdk3AwKdkIeDSp6R10-AWtjRg8EP-2cTAhzG3joXXJedii1d0Mky1_vkH8eLjsT6TpPXTPvL2F6EYTPzcpJFVKsooKJXRVzZqZlf_3-gINwD8R</recordid><startdate>2017</startdate><enddate>2017</enddate><creator>Youxi WU Cong SHEN He JIANG Xindong WU</creator><scope>2RA</scope><scope>92L</scope><scope>CQIGP</scope><scope>~WA</scope></search><sort><creationdate>2017</creationdate><title>Strict pattern matching under non-overlapping condition</title><author>Youxi WU Cong SHEN He JIANG Xindong WU</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-chongqing_primary_747088715048495548494848493</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Youxi WU Cong SHEN He JIANG Xindong WU</creatorcontrib><collection>维普_期刊</collection><collection>中文科技期刊数据库-CALIS站点</collection><collection>维普中文期刊数据库</collection><collection>中文科技期刊数据库- 镜像站点</collection><jtitle>中国科学:信息科学(英文版)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Youxi WU Cong SHEN He JIANG Xindong WU</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Strict pattern matching under non-overlapping condition</atitle><jtitle>中国科学:信息科学(英文版)</jtitle><addtitle>Science China(Information Sciences)</addtitle><date>2017</date><risdate>2017</risdate><issue>1</issue><spage>5</spage><epage>20</epage><pages>5-20</pages><issn>1674-733X</issn><eissn>1869-1919</eissn><abstract>Pattern matching(or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support(or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints(or flexible wildcards) uses the number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.</abstract></addata></record>
fulltext fulltext
identifier ISSN: 1674-733X
ispartof 中国科学:信息科学(英文版), 2017 (1), p.5-20
issn 1674-733X
1869-1919
language eng
recordid cdi_chongqing_primary_74708871504849554849484849
source Springer Nature
title Strict pattern matching under non-overlapping condition
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T21%3A08%3A15IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-chongqing&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Strict%20pattern%20matching%20under%20non-overlapping%20condition&rft.jtitle=%E4%B8%AD%E5%9B%BD%E7%A7%91%E5%AD%A6%EF%BC%9A%E4%BF%A1%E6%81%AF%E7%A7%91%E5%AD%A6%EF%BC%88%E8%8B%B1%E6%96%87%E7%89%88%EF%BC%89&rft.au=Youxi%20WU%20Cong%20SHEN%20He%20JIANG%20Xindong%20WU&rft.date=2017&rft.issue=1&rft.spage=5&rft.epage=20&rft.pages=5-20&rft.issn=1674-733X&rft.eissn=1869-1919&rft_id=info:doi/&rft_dat=%3Cchongqing%3E74708871504849554849484849%3C/chongqing%3E%3Cgrp_id%3Ecdi_FETCH-chongqing_primary_747088715048495548494848493%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_cqvip_id=74708871504849554849484849&rfr_iscdi=true