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

string searching algorithms revisited

Workshop on algorithms and Data Structures, WADS 1989

作者： Baeza-Yates, Ricardo A. Data Structuring Group Department of Computer Science University of Waterloo WaterlooONN2L 3G1 Canada

ISBN: (纸本)9783540515425

We present bounds for the average case of the Knuth-Morris-Pratt (KMP) algorithm and the Boyer-Moore-Horspool (BMH) algorithm for random text. Experimental results in both random and English text suggests that the bounds are tight. We also present a hybrid algorithm which combines the KMP and BMH algorithms, and which, in practice, is faster than the Boyer-Moore algorithm. © Springer-Verlag Berlin Heidelberg 1989.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Analysis of Boyer-Moore-type string searching algorithms 1

引用

1st Annual ACM-SIAM Symposium on Discrete algorithms, SODA 1990

作者： Baeza-Yates, Ricardo A. Gonnet, Gaston H. Régnier, Mireille Depto. de Ciencias de la Computación Universidad de Chile Casilla 2777 Santiago Chile Dept. of Computer Science University of Waterloo WaterlooONN2L 3G1 Canada ETH Zurich Canada INRIA-78 153 Le Chesnay France

ISBN: (纸本)0898712513

We study Boyer-Moore-type string searching algorithms. First, we analyze the Horspool's variant. The searching time is linear. An exact expression of the linearity constant is derived and is proven to be asymptotically i/c, where c is the cardinality of the alphabet. We exhibit a stationary process and reduce the problem to a word enumeration. The same technique applies to other variants of the Boyer-Moore algorithm. We also study Boyer-Moore automata, a notion that we formalize. This approach appears to be faster than any other known algorithm, in both, the worst and average case number of inspections. A lower bound in the maximal number of states of these automata is presented, and the concept of potential of a transition is introduced to improve the worst and average case behaviour of these machines. We show that looking at the rightmost unknown character, as suggested by Knuth et al, is not necessarily optimal.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms 19

Combined string searching algorithm based on knuth-morris- p...

引用

19th International Scientific Conference Reshetnev Readings 2015

作者： Tsarev, R Yu Chernigovskiy, A.S. Tsareva, E.A. Brezitskaya, V.V. Nikiforov, A Yu Smirnov, N.A. Siberian Federal University 79 Svobodny Prospect Krasnoyarsk Russia Siberian State Aerospace University 31 Krasnoyarskiy Rabochiy prospect Krasnoyarsk660037 Russia

The string searching task can be classified as a classic information processing task. Users either encounter the solution of this task while working with text processors or browsers, employing standard built-in tools, or this task is solved unseen by the users, while they are working with various computer programmes. Nowadays there are many algorithms for solving the string searching problem. The main criterion of these algorithms' effectiveness is searching speed. The larger the shift of the pattern relative to the string in case of pattern and string characters' mismatch is, the higher is the algorithm running speed. This article offers a combined algorithm, which has been developed on the basis of well-known Knuth-Morris-Pratt and Boyer-Moore string searching algorithms. These algorithms are based on two different basic principles of pattern matching. Knuth-Morris-Pratt algorithm is based upon forward pattern matching and Boyer-Moore is based upon backward pattern matching. Having united these two algorithms, the combined algorithm allows acquiring the larger shift in case of pattern and string characters' mismatch. The article provides an example, which illustrates the results of Boyer-Moore and Knuth-Morris- Pratt algorithms and combined algorithm's work and shows advantage of the latter in solving string searching problem. © Published under licence by IOP Publishing Ltd.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel string Matching with Linear Array, Butterfly and Divide and Conquer Models

引用

Annals of Data Science 2018年第2期5卷 181-207页

作者： Raju, S. Viswanadha Reddy, K.K.V.V.S. Rao, Chinta Someswara Department of CSE JNTUHCEJ JNT University Hyderabad HyderabadTelangana India Rayalasheema University KurnoolAndhra Pradesh India Department of CSE SRKR Engineering College BhimavaramAndhra Pradesh India

string Matching is a technique of searching a pattern in a text. It is the basic concept to extract the fruitful information from large volume of text, which is used in different applications like text processing, information retrieval, text mining, pattern recognition, DNA sequencing and data cleaning etc.,. Though it is stated some of the simple mechanisms perform very well in practice, plenty of research has been published on the subject and research is still active in this area and there are ample opportunities to develop new techniques. For this purpose, this paper has proposed linear array based string matching, string matching with butterfly model and string matching with divide and conquer models for sequential and parallel environments. To assess the efficiency of the proposed models, the genome sequences of different sizes (10–100 Mb) are taken as input data set. The experimental results have shown that the proposed string matching algorithms performs very well compared to those of Brute force, KMP and Boyer moore string matching algorithms. © 2017, Springer-Verlag GmbH Germany.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Realizing a sub-linear time string-matching algorithm with a hardware accelerator using bloom filters

引用

IEEE Transactions on Very Large Scale Integration (VLSI) Systems 2009年第8期17卷 1008-1020页

作者： Lin, Po-Ching Lin, Yin-Dar Lai, Yuan-Cheng Zheng, Yi-Jun Lee, Tsern-Huei Department of Computer Science National Chiao Tung University Hsinchu 300 Taiwan Department of Information Management National Taiwan University of Science and Technology Taipei 106 Taiwan Department of Communication Engineering National Chiao Tung University Hsinchu 300 Taiwan

Many network security applications rely on string matching to detect intrusions, viruses, spam, and so on. Since software implementation may not keep pace with the high-speed demand, turning to hardware-based solutions becomes promising. This work presents an innovative architecture to realize string matching in sub-linear time based on algorithmic heuristics, which come from parallel queries to a set of space-efficient Bloom filters. The algorithm allows skipping characters not in a match in the text, and in turn simultaneously inspect multiple characters in effect. The techniques to reduce the impact of certain bad situations on performance are also proposed: the bad-block heuristic, a linear worst-case time method and a non-blocking interface to hand over the verification job to a verification module. This architecture is simulated with both behavior simulation in C and timing simulation in HDL for antivirus applications. The simulation shows that the throughput of scanning Windows executable files for more than 10000 virus signatures can achieve 5.64 Gb/s, while the worst-case performance is 1.2 Gb/s if the signatures are properly specified. © 2006 IEEE.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Nested Counters in Bit-Parallel string Matching

Nested Counters in Bit-Parallel String Matching

引用

3rd International Conference on Language and Automata Theory and Applications

作者： Fredriksson, Kimmo Grabowski, Szymon Univ Kuopio Dept Comp Sci POB 1627 FIN-70211 Kuopio Finland Tech Univ Lodz Comp Engn Dept PL-90924 Lodz Poland

ISBN: (纸本)9783642009815

Many algorithms. e.g. in the field of string matching, are based on handling many counters, which can be performed in parallel, even on a sequential machine, using bit-parallelism. The recently presented technique of nested counters (Matryoshka counters) [1] is to handle small counters most of the time, and refer to larger counters periodically, when the small counters may g et full, to prevent overflow. In this work, we present several non-trivial applications of Matryoshka counters in string matching algorithms, improving their worst- or average-case time complexities. The set of problems comprises (delta, alpha)-matching, matching with k insertions, episode matching, and matching under Levenshtein distance.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

A Compressed Enhanced Suffix Array Supporting Fast string Matching

A Compressed Enhanced Suffix Array Supporting Fast String Ma...

引用

16th International Symposium on string Processing and Information Retrieval

作者： Oblebusch, Enno Gog, Simon Univ Ulm Inst Theoret Comp Sci D-89069 Ulm Germany

ISBN: (纸本)9783642037832

Index structures like the suffix tree or the suffix array are of utmost importance in stringology, most notably in exact string matching. In the last decade, research on compressed index structures has flourished because the main problem in many applications is the space consumption of the index. It is possible to simulate the matching of a pattern against a suffix tree on an enhanced suffix array by using range minimum queries or the so-called child table. In this paper, we show that the Super-Cartesian tree of the LCP-array (with which the suffix array is enhanced) very naturally explains the child table. More important, however, is the fact that the balanced parentheses representation of this tree constitutes a very natural compressed form of the child table which admits to locate all occ occurrences of pattern P of length m in O(m log vertical bar Sigma vertical bar + occ) time, where Sigma is the underlying alphabet. Our compressed child table uses less space than previous solutions to the problem. An implementation is available.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

INFERENCE OF EDIT COSTS USING PARAMETRIC string-MATCHING 11

INFERENCE OF EDIT COSTS USING PARAMETRIC STRING-MATCHING

引用

Conference B: Pattern Recognition Methodology and Systems, at the 11th IAPR International Conference on Pattern Recognition

作者： BUNKE, H CSIRIK, J UNIV BERN INST INFORMAT & ANGEW MATHCH-3012 BERNSWITZERLAND

ISBN: (纸本)0818629150

string matching is a useful concept in pattern recognition that is constantly receiving attention from both theoretical and practical points of view. In this paper we propose a generalized version of the string matching algorithm by Wagner and Fischer [1]. It is based on a parametrization of the edit cost. We assume constant cost for any delete and insert operation, but the cost for replacing a symbol is given as a parameter r. For any two given strings A and B, our algorithm computes the edit distance of A and B in terms of the parameter r. We give the new algorithm and study some of its properties. Its time complexity is O(n²-m), where n and m are the lengths of the two strings to be compared and n ≤ m. We also discuss potential applications of the new string distance to pattern recognition. Finally, we present some experimental results. © 1992 Institute of Electrical and Electronics Engineers Inc. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

string-MATCHING UNDER A GENERAL MATCHING RELATION 12th

STRING-MATCHING UNDER A GENERAL MATCHING RELATION

引用

12TH CONF ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE

作者： MUTHUKRISHNAN, S RAMESH, H Courant Institute New York University United States

ISBN: (纸本)3540562877

In standard string matching, each symbol matches only itself. In other string matching problems, e.g., the string matching with “don’t-cares” problem, a symbol may match several symbols. In general, an arbitrary many-to-many matching relation might hold between symbols. We consider a general string matching problem in which such a matching relation is specified and those text positions are sought at which the pattern matches under this relation. Depending upon the existence of a simple, easily recognizable property in the given matching relation, we show that string matching either requires time linear in the text and pattern lengths or is at least as hard as boolean multiplication. Since the existence of a linear time algorithm for boolean multiplication has been a long-standing open question, designing linear time algorithms for matching relations in the latter category appears to be hard. As an application, we show that the matching relations of several independently studied string matching problems do indeed fall into the latter (hard) category. We also initiate the study of a generic string matching algorithm that works for any matching relation. We give an algorithm that given any matching relation, pattern and text runs in O(n(sm)^1/3 polylog(m)), where n and m are the sizes of the text and the pattern respectively, and s is a factor related to the size of the given matching relation. This complexity is o(nm) except for very dense matching relations. © 1992, Springer Verlag. All rights reserved.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient string matching on coded texts 6th

Efficient string matching on coded texts

引用

6th Annual Symposium on Combinatorial Pattern Matching (CPM 95)

作者： Breslauer, D Gasieniec, L UNIV QUEBEC DEPT INFORMAT HULL PQ J8X 3X7 CANADA UNIV WARSAW INST INFORMAT PL-02097 WARSAW POLAND CNR IST ELABORAZIONE INFORMAZ I-56126 PISA ITALY

ISBN: (纸本)3540600442

The so called ''four Russians technique'' is often used to speed up algorithms by encoding several data items in a single memory cell. Given a sequence of n symbols over a constant size alphabet, one can encode the sequence into O(n/lambda) memory cells in O(log lambda) time using n/ log lambda processors. This paper presents an efficient CRCW-PRAM string-matching algorithm for coded texts that takes O(log log(m/lambda)) time(4) making only O(n/lambda) operations, an improvement by a factor of lambda = O(log n) on the number of operations used in previous algorithms. Using this string-matching algorithm one can test if a string is square-free and find all palindromes in a string in O(log log n) time using nl log log n processors.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：