The Factors Analysis and Algorithm Implementation of Single-pattern Matching

By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing order of using frequency, utilizing already-matched pattern suffix information, utili...

Full description

Saved in:
Bibliographic Details
Published in:Shanghai jiao tong da xue xue bao 2009-06, Vol.14 (3), p.331-337
Main Author: 刘功申 朱圣军
Format: Article
Language:English
Subjects:
Architecture
Computer Science
Electrical Engineering
Engineering
Life Sciences
Materials Science
匹配模式
因素影响
字符串
学习算法
快速搜索算法
时间复杂度
模式匹配算法
算法实现
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c1829-71b34e47ec4bd9ab9d9f768cb161c7144ec0c36cad1b5d889a4334c9a83a78a43
container_end_page 337
container_issue 3
container_start_page 331
container_title Shanghai jiao tong da xue xue bao
container_volume 14
creator 刘功申 朱圣军
description By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing order of using frequency, utilizing already-matched pattern suffix information, utilizing already-matched pattern prefix information, utilizing the position factor which is absorbed from quick search algorithm, and utilizing the continue-skip idea which is originally proposed by this paper. Combining all the five factors, a new single pattern matching algorithm is implemented. It＇s proven by the experiment that the efficiency of new algorithm is the best of all algorithms.
doi_str_mv 10.1007/s12204-009-0331-9
format article
fullrecord <record><control><sourceid>crossref_sprin</sourceid><recordid>TN_cdi_crossref_primary_10_1007_s12204_009_0331_9</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><cqvip_id>30993645</cqvip_id><sourcerecordid>10_1007_s12204_009_0331_9</sourcerecordid><originalsourceid>FETCH-LOGICAL-c1829-71b34e47ec4bd9ab9d9f768cb161c7144ec0c36cad1b5d889a4334c9a83a78a43</originalsourceid><addsrcrecordid>eNp9kEtPAyEUhYnRxFr9Ae6Ie5Q70BlYNo3VJjUurGvCMMyjzkAFXPTfS1PXru4j57s35yB0D_QRKK2eIhQF5YRSSShjQOQFmoGUCyJAiMvcZxEBqIprdBPjnlKeZXKGtrve4rU2yYeIl06PxzhErF2Dl2Pnw5D6CW-mw2gn65JOg3fYt_hjcN1oyUGnZIPDbzqZPq9u0VWrx2jv_uocfa6fd6tXsn1_2ayWW2JAFJJUUDNueWUNrxupa9nItiqFqaEEUwHn1lDDSqMbqBeNEFJzxriRWjBdiTzMEZzvmuBjDLZVhzBMOhwVUHVyqs5xqByHOsWhZGaKMxOz1nU2qL3_Cdlw_Bd6-HvUe9d9Z07V2ny1w2gVo1Kyki_YLwfvbmU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>The Factors Analysis and Algorithm Implementation of Single-pattern Matching</title><source>Springer Nature:Jisc Collections:Springer Nature Read and Publish 2023-2025: Springer Reading List</source><creator>刘功申 朱圣军</creator><creatorcontrib>刘功申 朱圣军</creatorcontrib><description>By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing order of using frequency, utilizing already-matched pattern suffix information, utilizing already-matched pattern prefix information, utilizing the position factor which is absorbed from quick search algorithm, and utilizing the continue-skip idea which is originally proposed by this paper. Combining all the five factors, a new single pattern matching algorithm is implemented. It＇s proven by the experiment that the efficiency of new algorithm is the best of all algorithms.</description><identifier>ISSN: 1007-1172</identifier><identifier>EISSN: 1995-8188</identifier><identifier>DOI: 10.1007/s12204-009-0331-9</identifier><language>eng</language><publisher>Heidelberg: Shanghai Jiaotong University Press</publisher><subject>Architecture ; Computer Science ; Electrical Engineering ; Engineering ; Life Sciences ; Materials Science ; 匹配模式 ; 因素影响 ; 字符串 ; 学习算法 ; 快速搜索算法 ; 时间复杂度 ; 模式匹配算法 ; 算法实现</subject><ispartof>Shanghai jiao tong da xue xue bao, 2009-06, Vol.14 (3), p.331-337</ispartof><rights>Shanghai Jiaotong University and Springer-Verlag GmbH 2009</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c1829-71b34e47ec4bd9ab9d9f768cb161c7144ec0c36cad1b5d889a4334c9a83a78a43</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Uhttp://image.cqvip.com/vip1000/qk/85391X/85391X.jpg</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>刘功申 朱圣军</creatorcontrib><title>The Factors Analysis and Algorithm Implementation of Single-pattern Matching</title><title>Shanghai jiao tong da xue xue bao</title><addtitle>J. Shanghai Jiaotong Univ. (Sci.)</addtitle><addtitle>Journal of Shanghai Jiaotong university</addtitle><description>By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing order of using frequency, utilizing already-matched pattern suffix information, utilizing already-matched pattern prefix information, utilizing the position factor which is absorbed from quick search algorithm, and utilizing the continue-skip idea which is originally proposed by this paper. Combining all the five factors, a new single pattern matching algorithm is implemented. It＇s proven by the experiment that the efficiency of new algorithm is the best of all algorithms.</description><subject>Architecture</subject><subject>Computer Science</subject><subject>Electrical Engineering</subject><subject>Engineering</subject><subject>Life Sciences</subject><subject>Materials Science</subject><subject>匹配模式</subject><subject>因素影响</subject><subject>字符串</subject><subject>学习算法</subject><subject>快速搜索算法</subject><subject>时间复杂度</subject><subject>模式匹配算法</subject><subject>算法实现</subject><issn>1007-1172</issn><issn>1995-8188</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><recordid>eNp9kEtPAyEUhYnRxFr9Ae6Ie5Q70BlYNo3VJjUurGvCMMyjzkAFXPTfS1PXru4j57s35yB0D_QRKK2eIhQF5YRSSShjQOQFmoGUCyJAiMvcZxEBqIprdBPjnlKeZXKGtrve4rU2yYeIl06PxzhErF2Dl2Pnw5D6CW-mw2gn65JOg3fYt_hjcN1oyUGnZIPDbzqZPq9u0VWrx2jv_uocfa6fd6tXsn1_2ayWW2JAFJJUUDNueWUNrxupa9nItiqFqaEEUwHn1lDDSqMbqBeNEFJzxriRWjBdiTzMEZzvmuBjDLZVhzBMOhwVUHVyqs5xqByHOsWhZGaKMxOz1nU2qL3_Cdlw_Bd6-HvUe9d9Z07V2ny1w2gVo1Kyki_YLwfvbmU</recordid><startdate>200906</startdate><enddate>200906</enddate><creator>刘功申 朱圣军</creator><general>Shanghai Jiaotong University Press</general><scope>2RA</scope><scope>92L</scope><scope>CQIGP</scope><scope>W92</scope><scope>~WA</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>200906</creationdate><title>The Factors Analysis and Algorithm Implementation of Single-pattern Matching</title><author>刘功申 朱圣军</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c1829-71b34e47ec4bd9ab9d9f768cb161c7144ec0c36cad1b5d889a4334c9a83a78a43</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Architecture</topic><topic>Computer Science</topic><topic>Electrical Engineering</topic><topic>Engineering</topic><topic>Life Sciences</topic><topic>Materials Science</topic><topic>匹配模式</topic><topic>因素影响</topic><topic>字符串</topic><topic>学习算法</topic><topic>快速搜索算法</topic><topic>时间复杂度</topic><topic>模式匹配算法</topic><topic>算法实现</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>刘功申 朱圣军</creatorcontrib><collection>中文科技期刊数据库</collection><collection>中文科技期刊数据库-CALIS站点</collection><collection>中文科技期刊数据库-7.0平台</collection><collection>中文科技期刊数据库-工程技术</collection><collection>中文科技期刊数据库- 镜像站点</collection><collection>CrossRef</collection><jtitle>Shanghai jiao tong da xue xue bao</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>刘功申 朱圣军</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The Factors Analysis and Algorithm Implementation of Single-pattern Matching</atitle><jtitle>Shanghai jiao tong da xue xue bao</jtitle><stitle>J. Shanghai Jiaotong Univ. (Sci.)</stitle><addtitle>Journal of Shanghai Jiaotong university</addtitle><date>2009-06</date><risdate>2009</risdate><volume>14</volume><issue>3</issue><spage>331</spage><epage>337</epage><pages>331-337</pages><issn>1007-1172</issn><eissn>1995-8188</eissn><abstract>By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing order of using frequency, utilizing already-matched pattern suffix information, utilizing already-matched pattern prefix information, utilizing the position factor which is absorbed from quick search algorithm, and utilizing the continue-skip idea which is originally proposed by this paper. Combining all the five factors, a new single pattern matching algorithm is implemented. It＇s proven by the experiment that the efficiency of new algorithm is the best of all algorithms.</abstract><cop>Heidelberg</cop><pub>Shanghai Jiaotong University Press</pub><doi>10.1007/s12204-009-0331-9</doi><tpages>7</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1007-1172
ispartof Shanghai jiao tong da xue xue bao, 2009-06, Vol.14 (3), p.331-337
issn 1007-1172
1995-8188
language eng
recordid cdi_crossref_primary_10_1007_s12204_009_0331_9
source Springer Nature:Jisc Collections:Springer Nature Read and Publish 2023-2025: Springer Reading List
subjects Architecture
Computer Science
Electrical Engineering
Engineering
Life Sciences
Materials Science
匹配模式
因素影响
字符串
学习算法
快速搜索算法
时间复杂度
模式匹配算法
算法实现
title The Factors Analysis and Algorithm Implementation of Single-pattern Matching
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-23T05%3A02%3A57IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_sprin&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20Factors%20Analysis%20and%20Algorithm%20Implementation%20of%20Single-pattern%20Matching&rft.jtitle=Shanghai%20jiao%20tong%20da%20xue%20xue%20bao&rft.au=%E5%88%98%E5%8A%9F%E7%94%B3%20%E6%9C%B1%E5%9C%A3%E5%86%9B&rft.date=2009-06&rft.volume=14&rft.issue=3&rft.spage=331&rft.epage=337&rft.pages=331-337&rft.issn=1007-1172&rft.eissn=1995-8188&rft_id=info:doi/10.1007/s12204-009-0331-9&rft_dat=%3Ccrossref_sprin%3E10_1007_s12204_009_0331_9%3C/crossref_sprin%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c1829-71b34e47ec4bd9ab9d9f768cb161c7144ec0c36cad1b5d889a4334c9a83a78a43%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=30993645&rfr_iscdi=true