检索结果-内蒙古大学图书馆

2013 IEEE Conference on Open Systems, ICOS 2013

作者： Ong, Wenmei Baskaran, Vishnu Monn Chong, Poh Kit Ettikan, K.K. Yong, Keh Kok Faculty of Engineering Multimedia University Cyberjaya Campus Selangor Malaysia Faculty of Engineering and Science University Tunku Abdul Rahman Petaling Jaya Selangor Malaysia Accelerative Technology Lab MIMOS Berhad Kuala Lumpur Malaysia

ISBN: (纸本)9781479902859

This paper analyzes the underlying architecture of a serial Bloom filter string searching algorithm to identify the performance impact of this algorithm for large datasets. Then, a parallel multi-core driven Bloom filter algorithm using software application threads is studied as benchmark. Experimental results suggest that for a set of 10 million strings, this algorithm exhibits speedups of up to 3.3× against a serial Bloom filter algorithm, when using an 8-logical processor multi-core architecture. To further improve the speedup, a many-core driven parallel Bloom filter algorithm is proposed using the Compute Unified Device Architecture (CUDA) parallel computing platform. The proposed algorithm segments the string list into blocks of words and threads in generating the bit table for the string searching process, which maximizes computational performance and sustains consistent string searching results. Experimental results suggest that the proposed algorithm extends the speedup to 5.5× against a serial Bloom filter algorithm, when using a 256-core CUDA graphics processing unit architecture. © 2013 IEEE.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Speeding Up Double-Array Trie Construction for string Matching

Speeding Up Double-Array Trie Construction for String Matchi...

引用

International Conference on Trustworthy Computing and Services, ISCTCS 2012

作者： Niu, Shuai Liu, Yanbing Song, Xinbo Institute of Computing Technology Chinese Academy of Sciences Beijing China Institute of Information Engineering Chinese Academy of Sciences Beijing China Gruduate School of Chinese Academy of Sciences Beijing China

ISBN: (纸本)9783642357947

Double-Array Trie is presented as a data structure for Trie which has advantages both in the compactness and access speed. Thus Double Array Trie structure is broadly adopted by many string matching algorithms. However, the Double Array Trie construction process is faced with problems of huge temporary peak of memory consumption and low construction speed when applied to large scale sets of strings. It's hard to meet the requirement of detecting high speed network flow in real time. This paper presents two optimization strategies in the Double Array Trie construction process to avoid the temporary peak of memory consumption and reduce the construction time. The first is to generate the Trie recursively. The second is to take different methods in finding current node's base value process according to the number of child nodes. We applied the improved strategy to Aho-Corasick algorithm and tested with different large-scale sets of strings. From the results, it turned out that the space consumption and the construction time are both significantly improved on the premise of same search efficiency. © Springer-Verlag Berlin Heidelberg 2013.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast string matching algorithm based on the skip algorithm

Fast string matching algorithm based on the skip algorithm

引用

2012 International Conference on Emerging Technologies for Information Systems, Computing, and Management, ICM 2012

作者： Wu, Wenqing Fan, Hongbo Liu, Lijun Huang, Qingsong Department of Computer Science Kunming University of Science and Technology Yunnan Key Laboratory of Computer Technology Applications Kunming China Department of Biomedical Engineering Kunming University of Science and Technology Kunming China

ISBN: (纸本)9781461470090

string matching is a fundamental problem in computer science. In order to gain higher performance online exact single pattern string matching algorithms, the authors improved the Skip algorithm which is a comparison based exact single pattern string matching algorithm. By introducing the q-grams method in the sliding window and the comparing window of Skip respectively, the branch prediction failure and the average branch cost are reduced. Meanwhile, the greedy jump method is introduced in Skip. Greedy jump is a common accelerating method for string matching, while there are some waste reads for algorithms with unfixed jump distance. Since Skip has fixed jump distance, greedy jump is more suitable for Skip. Therefore, the authors presented the HGQS algorithm. Experiments results have indicated that HGQS has higher practical performance and it is more efficient in some cases than other known algorithms in many cases on the platform. © 2013 Springer Science+Business Media New York.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Identification of all exact and approximate inverted repeats in regular and weighted sequences

Communications in Computer and Information Science

引用

Communications in Computer and Information Science 2013年 384卷 11-19页

作者： Barton, Carl Iliopoulos, Costas S. Mulder, Nicola Watson, Bruce King's College London Dept. of Informatics London WC2R 2LS United Kingdom Computational Biology Group University of Cape Town Cape Town South Africa Fastar Group University of Pretoria Pretoria South Africa

The detection of various types of repeats is a fundamental and well studied problem in stringology. In this paper we present extensions to this problem with applications to bioinformatics. In this paper we consider the detection of all exact and approximate inverted repeats, as well as all exact and approximate weighted inverted repeats and give efficient algorithms for their computation. © Springer-Verlag Berlin Heidelberg 2013.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

XAn Efficient Parallel string Matching Algorithm Based on DFA

XAn Efficient Parallel String Matching Algorithm Based on DF...

引用

作者： Fan, Yujian Zhang, Hongli Liu, Jiahui Xu, Dongliang School of Computer Science and Technology Harbin Institute of Technology Harbin China

ISBN: (纸本)9783642357947

The classical string matching algorithms are facing a great challenge on speed due to the rapid growth of information on Internet. Meanwhile, multi-core CPU has been widespread on computers. But classical string matching algorithms does not apply to multi-core CPU flexibly. It not only affects the run-time speed, but also makes a waste of the resource on CPU. In this paper, we proposed a parallel string matching algorithm based on DFA, it solved the problem effectively. By classification on the first letter of each pattern, all CPU cores could work at the same time, which do not conflict. Experiments demonstrate whether the hit rate is high or low, the algorithm has an ideal performance. © Springer-Verlag Berlin Heidelberg 2013.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

The application of a kind of duplex layer KMP algorithm within flow filtering technology

引用

Journal of Chemical and Pharmaceutical Research 2013年第9期5卷 515-521页

作者： Li, Lei Gu, Yuwan Chen, Yan Sun, Yuqiang ChangZhou University International Institute of Ubiquitous Computing Jiangsu Changzhou China JiangSu University College of Electronic and Information Engineering Jiang Su Zhenjiang China

This paper analyses the theory of KMP algorithm, using the irrelevant mismatching feature of main string and substring, proposed a kind of duplex layer structure hierarchical nesting string matching algorithm, and apply the improved algorithm to flow filtering technology. Under the condition of "large text - big Mode" string matching, the improved algorithm solves the problem of strong dynamic memory share and time-consuming about calculating the next value in the KMP algorithm. The experimental results suggest that the algorithm has higher matching efficiency under the condition of large data sets matching.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

On-line construction of position heaps

On-line construction of position heaps

引用

作者： Kucherov, Gregory Université Paris-Est CNRS Laboratoire d'Informatique Gaspard Monge 5 Bd Descartes 77454 Marne-la-Vallée France Department of Computer Science Ben-Gurion University of the Negev Be'er Sheva Israel

We propose a simple linear-time on-line algorithm for constructing a position heap for a string (Ehrenfeucht et al., 2011 [8]). Our definition of position heap differs slightly from the one proposed in Ehrenfeucht et al. (2011) [8] in that it considers the suffixes ordered in the descending order of length. Our construction is based on classic suffix pointers and resembles Ukkonen's algorithm for suffix trees (Ukkonen, 1995 [17]). Using suffix pointers, the position heap can be extended into the augmented position heap that allows for a linear-time string matching algorithm (Ehrenfeucht et al., 2011 [8]). © 2012 Elsevier B.V. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding pseudo-repetitions

Finding pseudo-repetitions

引用

30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013

作者： Gawrychowski, Pawel Manea, Florin Mercas, Robert Nowotka, Dirk Tiseanu, Catalin Max-Planck-Institut Für Informatik Saarbrücken Germany Christian-Albrechts-Universität zu Kiel Institut Für Informatik D-24098 Kiel Germany Otto-von-Guericke-Universität Magdeburg Fakultät Für Informatik PSF 4120 D-39016 Magdeburg Germany University of Maryland at College Park Computer Science Department A.V. Williams Bldg. College Park MD 20742 United States

ISBN: (纸本)9783939897507

Pseudo-repetitions are a natural generalization of the classical notion of repetitions in sequences. We solve fundamental algorithmic questions on pseudo-repetitions by application of insightful combinatorial results on words. More precisely, we efficiently decide whether a word is a pseudorepetition and find all the pseudo-repetitive factors of a word.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Q-gram variation for EBOM

Q-gram variation for EBOM

引用

2012 International Conference on Information Technology and Software Engineering, ITSE 2012

作者： Fan, Hongbo Yao, Nianmin Department of Computer Science and Technology Harbin Engineering University Harbin China

ISBN: (纸本)9783642345210

EBOM is one of the fastest exact single pattern string matching algorithms for short patterns and large alphabet. It is a 2-grams BOM type algorithm. However, only 2-grams is not enough in many case. EBOM is hardly to extend to q-grams because the space complexity of q-grams is exponential. In this article, we presented a q-grams method for BOM which just add one state and applied it on EBOM. Therefore, we presented BOMq algorithm. Experimental results indicated that BOMq is faster than other known algorithms for long patterns and random text of alphabet size 16 on our platform. © 2013 Springer-Verlag.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Tuning the EBOM algorithm with suffix jump

Tuning the EBOM algorithm with suffix jump

引用

2012 International Conference on Information Technology and Software Engineering, ITSE 2012

作者： Fan, Hongbo Yao, Nianmin Department of Computer Science and Technology Harbin Engineering University Harbin China

ISBN: (纸本)9783642345210

EBOM is one of the fastest exact single pattern string matching algorithms for short patterns and large alphabet. In this article, a suffix jump method based on the automaton of EBOM (Factor Oracle) is presented. After the suffix jump method applied, an additional jump which the distance is similar with 2-grams bad-char rule is gained and the additional jump distance can be calculated together with the factor method based on Factor Oracle. We combined the suffix jump method with the factor method of EBOM and presented an improved algorithm of EBOM called SufOM2. Experimental results indicated that SufOM2 is very fast for large alphabet and short patterns on our platform. © 2013 Springer-Verlag.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：