Exact String Matching Algorithms: Survey, Issues, and Future Research Directions
---
paper_title: Towards an ontology based framework for searching multimedia contents on the web

paper_content:

We live in a world where there are huge number of consumers and producers of multimedia content. In this sea of information, finding the right content is like finding a needle in a haystack. Rich annotation of multimedia content during its initial upload on the Web, and further various methodologies for framing search query can be helpful to the user in this regard. In addition to annotation of multimedia content based on the user-provided description, various approaches for annotation and indexing of multimedia files based upon the embedded contents have been presented in the literature. However, annotating multimedia files by using multiple possible sources simultaneously to generate better annotation needs further exploration. We have proposed a framework utilizing these multiple sources of information like text, audio, image, etc. This framework generates annotation based on the contents of user entered description, embedded audio, image analysis, optical character recognition and finally by gathering more information from the Web. This framework provides multiple options to search for content like search by image, audio, video, face and also provides an improved textual search. A system has been implemented based on the proposed framework and the work has also been evaluated.
---
paper_title: Stream segregation algorithm for pattern matching in polyphonic music databases

paper_content:

As music can be represented symbolically, most of the existing methods extend some string matching algorithms to retrieve musical patterns in a music database. However, not all retrieved patterns are perceptually significant because some of them are, in fact, inaudible. Music is perceived in groupings of musical notes called streams. The process of grouping musical notes into streams is called stream segregation. Stream-crossing musical patterns are perceptually insignificant and should be pruned from the retrieval results. This can be done if all musical notes in a music database are segregated into streams and musical patterns are retrieved from the streams. Findings in auditory psychology are utilized in this paper, in which stream segregation is modelled as a clustering process and an adapted single-link clustering algorithm is proposed. Supported by experiments on real music data, streams are identified by the proposed algorithm with considerable accuracy.
---
paper_title: A new split based searching for exact pattern matching for natural texts

paper_content:

Exact pattern matching algorithms are popular and used widely in several applications, such as molecular biology, text processing, image processing, web search engines, network intrusion detection systems and operating systems. The focus of these algorithms is to achieve time efficiency according to applications but not memory consumption. In this work, we propose a novel idea to achieve both time efficiency and memory consumption by splitting query string for searching in Corpus. For a given text, the proposed algorithm split the query pattern into two equal halves and considers the second (right) half as a query string for searching in Corpus. Once the match is found with second halves, the proposed algorithm applies brute force procedure to find remaining match by referring the location of right half. Experimental results on different S1 Dataset, namely Arabic, English, Chinese, Italian and French text databases show that the proposed algorithm outperforms the existing S1 Algorithm in terms of time efficiency and memory consumption as the length of the query pattern increases.
---
paper_title: The study on content based multimedia data retrieval system

paper_content:

Of late, advance in hardware and communications technology has been rapidly increasing the demand for diverse multimedia information, which, including all image, audio, video, text, numerical data, etc., should be designed to excel the existing information processing system in the functions of data storage, search, transmission, display, etc. The newest image retrieval system is gradually being converted from text-based into content-based retrieval, which uses the image content itself as features. In content-based retrieval, how to combine the color, shape, layout, texture, etc. used for describing each image or object is considered an important element. The existing method has chiefly used histogram out of the content-based image method using color information, but this has a drawback in being sensitive to brightness of light and the object size in the image. Thus, the present methods is intended to design and implement a system that can retrieve images similar to the query image from image database without losing image information in the use of color features.
---
paper_title: Hardware based String Matching Algorithms: A Survey

paper_content:

are various string matching Algorithms which are software based but some are hardware based. The main factor of string matching algorithm is depending on searching efficiency. In this paper we have discussed about the hardware based string matching algorithms such as Brute Force, KMP, and Aho-Corasicks with their applications. There are different types of string matching algorithms which are software based solution and hardware based solution. Since software-based solutions are slower and less efficient, now a day, so the hardware-based solutions are highly preferred. Hardware based approaches are more efficient in terms of speed, memory size and power consumption than software based approaches. Hardware based solutions has great importance in the real life applications. This paper focus on the hardware based solutions and describes the hardware based implementation of string matching algorithms such as Brute Force, KMP and Aho- Corasicks.
---
paper_title: On-line string matching algorithms: survey and experimental results

paper_content:

In this paper we present a short survey and experimental results for well known sequential string matching algorithms. We consider algorithms based on different approaches including classical, suffix automata, bit-parallelism and hashing. We put special emphasis on algorithms recently presented such as Shift-Or and BNDM algorithms. We compare these algorithms in terms of the number of character comparisons and the running time for four different types of text: binary alphabet, alphabet of size 8, English alphabet and DNA alphabet.
---
paper_title: Ontology matching: A literature review

paper_content:

We present a literature review regarding articles on ontology matching published in the last decade.It serves the purpose of offering an up-to-date review of the field and showing its evolution trends.Over 1600 papers have been sorted according to a classification framework that we have defined.This framework helps in identifying the distribution of the load work in the last decade.Practitioners have been consulted to contrast and validate the results of the review. The amount of research papers published nowadays related to ontology matching is remarkable and we believe that reflects the growing interest of the research community. However, for new practitioners that approach the field, this amount of information might seem overwhelming. Therefore, the purpose of this work is to help in guiding new practitioners get a general idea on the state of the field and to determine possible research lines.To do so, we first perform a literature review of the field in the last decade by means of an online search. The articles retrieved are sorted using a classification framework that we propose, and the different categories are revised and analyzed. The information in this review is extended and supported by the results obtained by a survey that we have designed and conducted among the practitioners.
---
paper_title: The exact online string matching problem: A review of the most recent results

paper_content:

This article addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.
---
paper_title: A guided tour to approximate string matching

paper_content:

We survey the current techniques to cope with the problem of string matching that allows errors. This is becoming a more and more relevant issue for many fast growing areas such as information retrieval and computational biology. We focus on online searching and mostly on edit distance, explaining the problem and its relevance, its statistical behavior, its history and current developments, and the central ideas of the algorithms and their complexities. We present a number of experiments to compare the performance of the different algorithms and show which are the best choices. We conclude with some directions for future work and open problems.
---
paper_title: Faster Filters for Approximate String Matching

paper_content:

We introduce a new filtering method for approximate string matching called the suffix filter. It has some similarity with well-known filtration algorithms, which we call factor filters, and which are among the best practical algorithms for approximate string matching using a text index. Suffix filters are stronger, i.e., produce fewer false matches than factor filters. We demonstrate experimentally that suffix filters are faster in practice, too.
---
paper_title: Tight comparison bounds for the string prefix-matching problem

paper_content:

Abstract In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string of length m that occurs starting at each position of a text string of length n . This is a natural generalization of the string matching problem where only occurences of the whole pattern are sought. The Knuth-Morris-Pratt string matching algorithm can be easily adapted to solve the string prefix-matching problem without making additional comparisons. In this paper we study the exact complexity of the string prefix-matching problem in the deterministic sequential comparison model. Our bounds do not account for comparisons made in a pattern preprocessing step. The following results are presented: 1. (1) A family of linear-time string prefix-matching algorithms that make at most ⌊( (2m−1) m )n⌋ comparisons. 2. (2) A tight lower bound of ⌊(( 2m−1) m )n⌋ comparisons for any string prefix-matching algorithm that has to match the pattern ‘ ab m −1’. We also consider the special case when the pattern and the text strings are the same string and all comparisons are accounted. This problem, which we call the string self-prefix problem, is similar to the failure function that is computed in the pattern preprocessing of the Knut-Morris-Pratt string matching algorithm and used in several other comparison efficient algorithms. By using the lower bound for the string prefix-matching problem we are able to show: 3. (3) A lower bound of 2m−⌊2 m ⌋ comparisons for the self-prefix problem.
---
paper_title: Optimal spaced seeds for faster approximate string matching

paper_content:

Filtering is a standard technique for fast approximate string matching in practice.In filtering, a quick first step is used to rule out almost all positions of a text as possible starting positions for a pattern. Typically this step consists of finding the exact matches of small parts of the pattern. In the followup step, a slow method is used to verify or eliminate each remaining position. The running time of such a method depends largely on the quality of the filtering step, as measured by its false positives rate. The quality of such a method depends on the number of true matches that it misses, that is, on its false negative rate.
---
paper_title: Bidirectional search in a string with wavelet trees and bidirectional matching statistics

paper_content:

Searching for genes encoding microRNAs (miRNAs) is an important task in genome analysis. Because the secondary structure of miRNA (but not the sequence) is highly conserved, the genes encoding it can be determined by finding regions in a genomic DNA sequence that match the structure. It is known that algorithms using a bidirectional search on the DNA sequence for this task outperform algorithms based on unidirectional search. The data structures supporting a bidirectional search (affix trees and affix arrays), however, are rather complex and suffer from their large space consumption. Here, we present a new data structure called bidirectional wavelet index that supports bidirectional search with much less space. With this data structure, it is possible to search for candidates of RNA secondary structural patterns in large genomes, for example the complete human genome. Another important application of this data structure is short read alignment. As a second contribution, we show how bidirectional matching statistics can be computed in linear time.
---
paper_title: FAST PATTERN MATCHING IN STRINGS*

paper_content:

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use, and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time. Other algorithms which run even faster on the average are also considered.
---
paper_title: A Hybrid Indexing Method for Approximate String Matching

paper_content:

We present a new indexing method for the approximate string matching problem. The method is based on a suffix array combined with a partitioning of the pattern. We analyze the resulting algorithm and show that the average retrieval time is O(n log n), for some > 0 that depends on the error fraction tolerated and the alphabet size . It is shown that < 1 for approximately < 1 e=p , where e = 2:718:::. The space required is four times the text size, which is quite moderate for this problem. We experimentally show that this index can outperform by far all the existing alternatives for indexed approximate searching. These are also the first experiments that compare the different existing schemes.
---
paper_title: Approximate String Matching Using a Bidirectional Index

paper_content:

We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of [5]. We introduce a formalism, called search schemes, to specify search strategies of this type, then develop a probabilistic measure for the efficiency of a search scheme, prove several combinatorial results on efficient search schemes, and finally, provide experimental computations supporting the superiority of our strategies.
---
paper_title: The exact string matching algorithms efficiency review

paper_content:

Exact String matching algorithms has been very significant in many applications in the last two decades. This is due to the advancement in technology that produces large volumes of data. The main factors in string matching algorithms are the number of attempts, the number of character comparison and the running time. These factors are influenced by the type of algorithm, type of data, data size and length of pattern used. In this article, we perform review for advantages and disadvantages of executing exact string matching algorithm. We conclude that the suffix automata and hybrid are the faster algorithms with the lowest number of attempts and the hashing approaches have the lower number of comparison. The bit parallelism algorithms have the similar limitations. Keyword: Exact string matching, character comparison, number of attempt, limitations;
---
paper_title: Algorithms for Finding Patterns in Strings.

paper_content:

Publisher Summary This chapter discusses the algorithms for solving string-matching problems that have proven useful for text-editing and text-processing applications. String pattern matching is an important problem that occurs in many areas of science and information processing. In computing, it occurs naturally as part of data processing, text editing, term rewriting, lexical analysis, and information retrieval. Many text editors and programming languages have facilities for matching strings. In biology, string-matching problems arise in the analysis of nucleic acids and protein sequences, and in the investigation of molecular phylogeny. String matching is also one of the central and most widely studied problems in theoretical computer science. The simplest form of the problem is to locate an occurrence of a keyword as a substring in a sequence of characters, which is called the input string. For example, the input string queueing contains the keyword ueuei as a substring. Even for this problem, several innovative, theoretically interesting algorithms have been devised that run significantly faster than the obvious brute-force method.
---
paper_title: FAST PATTERN MATCHING IN STRINGS*

paper_content:

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use, and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time. Other algorithms which run even faster on the average are also considered.
---
paper_title: ERS-A Algorithm for Pattern Matching

paper_content:

3 Abstract: Pattern matching algorithms have many applications that cover a wide range including information retrieval, text processing, DNA sequence analysis and pattern recognition. In this paper, we propose a new algorithm ERS-A, that made enhancements on both two sliding windows (TSW) and Fast Pattern Matching (RS-A) algorithms. In ERS-A and TSW algorithms two sliding windows are used to scan the text from the left and right simultaneously, but while TSW utilizes the idea of Berry Ravindran bad character shift function (BR), ERS-A adds an improvement by using the shift technique provided by RS-A algorithm. RS-A algorithm uses four consecutive characters in the text immediately following the pattern window, instead of using two consecutive characters as in BR. The experimental results show that the ERS-A has enhanced the searching process significantly.
---
paper_title: Memory-Based Architecture for Multicharacter Aho–Corasick String Matching

paper_content:

The Aho–Corasick (AC) string matching algorithm is commonly used in signature-based intrusion detection and antivirus systems. In this paper, we present a hardware implementation of the AC algorithm that can process multiple characters per cycle. State transitions are implemented using table lookup. Hence, updates to the pattern set do not require hardware reconfiguration. A fundamental issue of multicharacter AC string matching is the transition rules explosion problem. We apply the transition rule reduction strategy such that the number of transition rules can be reduced to less than two rules per state in the finite automaton. The memory cost is further optimized by implementing the rule table as near-minimal perfect hash table. We implement the proposed method on a virtex-7 FPGA for a pattern set with 2200 Snort signatures. The normalized memory cost of our design is 13.75 bytes per character of the pattern set when four characters are processed per cycle, and the FPGA can operate at 216 MHz.
---
paper_title: String Matching with Multicore CPUs: Performing Better with the Aho-Corasick Algorithm

paper_content:

Multiple string matching is known as locating all the occurrences of a given number of patterns in an arbitrary string. It is used in bio-computing applications where the algorithms are commonly used for retrieval of information such as sequence analysis and gene/protein identification. Extremely large amount of data in the form of strings has to be processed in such bio-computing applications. Therefore, improving the performance of multiple string matching algorithms is always desirable. Multicore architectures are capable of providing better performance by parallelizing the multiple string matching algorithms. The Aho-Corasick algorithm is the one that is commonly used in exact multiple string matching algorithms. The focus of this paper is the acceleration of Aho-Corasick algorithm through a multicore CPU based software implementation. Through our implementation and evaluation of results, we prove that our method performs better compared to the state of the art.
---
paper_title: A fast string searching algorithm

paper_content:

An algorithm is presented that searches for the location, “ i l” of the first occurrence of a character string, “ pat ,” in another string, “ string .” During the search operation, the characters of pat are matched starting with the last character of pat . The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first i characters of string are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of pat . For a random English pattern of length 5, the algorithm will typically inspect i /4 characters of string before finding a match at i . Furthermore, the algorithm has been implemented so that (on the average) fewer than i + patlen machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in i + patlen , assuming the availability of array space for tables linear in patlen plus the size of the alphabet. 3~
---
paper_title: Tight comparison bounds for the string prefix-matching problem

paper_content:

Abstract In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string of length m that occurs starting at each position of a text string of length n . This is a natural generalization of the string matching problem where only occurences of the whole pattern are sought. The Knuth-Morris-Pratt string matching algorithm can be easily adapted to solve the string prefix-matching problem without making additional comparisons. In this paper we study the exact complexity of the string prefix-matching problem in the deterministic sequential comparison model. Our bounds do not account for comparisons made in a pattern preprocessing step. The following results are presented: 1. (1) A family of linear-time string prefix-matching algorithms that make at most ⌊( (2m−1) m )n⌋ comparisons. 2. (2) A tight lower bound of ⌊(( 2m−1) m )n⌋ comparisons for any string prefix-matching algorithm that has to match the pattern ‘ ab m −1’. We also consider the special case when the pattern and the text strings are the same string and all comparisons are accounted. This problem, which we call the string self-prefix problem, is similar to the failure function that is computed in the pattern preprocessing of the Knut-Morris-Pratt string matching algorithm and used in several other comparison efficient algorithms. By using the lower bound for the string prefix-matching problem we are able to show: 3. (3) A lower bound of 2m−⌊2 m ⌋ comparisons for the self-prefix problem.
---
paper_title: The exact string matching algorithms efficiency review

paper_content:

Exact String matching algorithms has been very significant in many applications in the last two decades. This is due to the advancement in technology that produces large volumes of data. The main factors in string matching algorithms are the number of attempts, the number of character comparison and the running time. These factors are influenced by the type of algorithm, type of data, data size and length of pattern used. In this article, we perform review for advantages and disadvantages of executing exact string matching algorithm. We conclude that the suffix automata and hybrid are the faster algorithms with the lowest number of attempts and the hashing approaches have the lower number of comparison. The bit parallelism algorithms have the similar limitations. Keyword: Exact string matching, character comparison, number of attempt, limitations;
---
paper_title: A new approach to text searching

paper_content:

We introduce a family of simple and fast algorithms for solving the classical string matching problem, string matching with don't care symbols and complement symbols, and multiple patterns. In addition we solve the same problems allowing up to k mismatches. Among the features of these algorithms are that they are real time algorithms, they don't need to buffer the input, and they are suitable to be implemented in hardware.
---
paper_title: A fast string search algorithm for deep packet classification

paper_content:

In this paper, we propose a string search algorithm that requires reduced time complexity. It also requires a small amount of memory, and shows better performance than any other algorithm for deep packet classification based on their payload data. The proposed algorithm is based on Boyer-Moore algorithm but requires a much reduced number of operations. In addition, our algorithm's memory requirement is lower than Boyer-Moore algorithm without sacrificing its speed. We have done time complexity analysis and verified its time complexities through extensive numerical simulations. These simulations show that our algorithm's performance is better for long text, long pattern, and large alphabet set and even its worst case time complexity linearly depends on the length of the text.
---
paper_title: A fast string searching algorithm

paper_content:

An algorithm is presented that searches for the location, “ i l” of the first occurrence of a character string, “ pat ,” in another string, “ string .” During the search operation, the characters of pat are matched starting with the last character of pat . The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first i characters of string are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of pat . For a random English pattern of length 5, the algorithm will typically inspect i /4 characters of string before finding a match at i . Furthermore, the algorithm has been implemented so that (on the average) fewer than i + patlen machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in i + patlen , assuming the availability of array space for tables linear in patlen plus the size of the alphabet. 3~
---
paper_title: Speeding up two string matching algorithms

paper_content:

We show how to speed up two string-matching algorithms: the Boyer-Moore algorithm (BM algorithm), and its version called here the reverse factor algorithm (RF algorithm). The RF algorithm is based on factor graphs for the reverse of the pattern. The main feature of both algorithms is that they scan the text right-to-left from the supposed right position of the pattern. The BM algorithm goes as far as the scanned segment (factor) is a suffix of the pattern. The RF algorithm scans while the segment is a factor of the pattern. Both algorithms make a shift of the pattern, forget the history, and start again. The RF algorithm usually makes bigger shifts than BM, but is quadratic in the worst case. We show that it is enough to remember the last matched segment (represented by two pointers to the text) to speed up the RF algorithm considerably (to make a linear number of inspections of text symbols, with small coefficient), and to speed up the BM algorithm (to make at most 2 ·n comparisons). Only a constant additional memory is needed for the search phase. We give alternative versions of an accelerated RF algorithm: the first one is based on combinatorial properties of primitive words, and the other two use the power of suffix trees extensively. The paper demonstrates the techniques to transform algorithms, and also shows interesting new applications of data structures representing all subwords of the pattern in compact form.
---
paper_title: Tuning the Boyer-Moore-Horspool String Searching Algorithm

paper_content:

SUMMARY Substring search is a common activity in computing. The fastest known search method is that of Boyer and Moore with the improvements introduced by Horspool. This paper presents a new implementation which takes advantage of the dependencies between the characters. The resulting code runs 25 per cent faster than the best currently-known routine.
---
paper_title: Practical fast searching in strings

paper_content:

SUMMARY The problem of searching through text to find a specified substring is considered in a practical setting. It is discovered that a method developed by Boyer and Moore can outperform even special-purpose search instructions that may be built into the, computer hardware. For very short substrings however, these special purpose instructions are fastest-provided that they are used in an optimal way.
---
paper_title: The Boyer–Moore–Galil String Searching Strategies Revisited

paper_content:

Based on the Boyer–Moore–Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring. Preprocessing is only slightly more involved and still requires a time linear in the pattern size.
---
paper_title: A very fast substring search algorithm

paper_content:

This article describes a substring search algorithm that is faster than the Boyer-Moore algorithm. This algorithm does not depend on scanning the pattern string in any particular order. Three variations of the algorithm are given that use three different pattern scan orders. These include: (1) a “Quick Search” algorithm; (2) a “Maximal Shift” and (3) an “Optimal Mismatch” algorithm.
---
paper_title: A new split based searching for exact pattern matching for natural texts

paper_content:

Exact pattern matching algorithms are popular and used widely in several applications, such as molecular biology, text processing, image processing, web search engines, network intrusion detection systems and operating systems. The focus of these algorithms is to achieve time efficiency according to applications but not memory consumption. In this work, we propose a novel idea to achieve both time efficiency and memory consumption by splitting query string for searching in Corpus. For a given text, the proposed algorithm split the query pattern into two equal halves and considers the second (right) half as a query string for searching in Corpus. Once the match is found with second halves, the proposed algorithm applies brute force procedure to find remaining match by referring the location of right half. Experimental results on different S1 Dataset, namely Arabic, English, Chinese, Italian and French text databases show that the proposed algorithm outperforms the existing S1 Algorithm in terms of time efficiency and memory consumption as the length of the query pattern increases.
---
paper_title: A fast string matching algorithm based on lowlight characters in the pattern

paper_content:

We put forth a new string matching algorithm which matches the pattern from neither the left nor the right end, instead a special position. Comparing with the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm, the new algorithm is more flexible to pick the position for starting comparisons. The option really brings it a saving in cost.
---
paper_title: Correctness and efficiency of pattern matching algorithms

paper_content:

Abstract A few lines pattern matching algorithm is obtained by using the correctness proof of programs as a tool to the design of efficient algorithms. The new algorithm is obtained from a brute force algorithm by three refinement steps. The first step leads to the algorithm of Knuth, Morris, and Pratt that performs 2n character comparisons in the worst case and (1 + α)n comparisons in the average case (0
---
paper_title: Hybrid pattern-matching algorithm based on BM-KMP algorithm

paper_content:

Reading and reference many books and articles, and then analyze and study the KMP algorithm, BM algorithm and a variety of improved algorithms. Summarizes various of the advantages and disadvantages of the pattern matching algorithms and in-depth study the advantages of the algorithms. And on this basis, a new algorithm - KMPBS algorithm is introduced. The algorithm refers to BM algorithm, KMP algorithm and the thinking of improved algorithms. Utilize the last character of the string, the next character and the method to compare from side to side, and then advance a new hybrid pattern matching algorithm. And it adjusted the comparison direction and the order of the comparison to make the maximum moving distance of each time to reduce the pattern matching time. The algorithm reduces the comparison number and greatly reduces the moving number of the pattern and improve the matching efficiency. This algorithm achieved a better result and it works well.
---
paper_title: Generalizations of Horner's rule for polynomial evaluation

paper_content:

Polynomials are generally evaluated by use of Horner's rule, sometimes referred to as the nesting rule. This rule is sequential and affords no opportunity for parallecl omputation, i.e., completion of several of the arithmetic operations simultaneously. Two generalizations of Horner's rule which allow for parallel computation are presented here. ::: ::: Schedules and, in some cases, machine codes for evaluating a polynomial on a computer with several parallel arithmetic units are developed. Some advantages of the generalized rules in sequential computations on a computer with a single arithmetic unit are presented.
---
paper_title: The exact string matching algorithms efficiency review

paper_content:

Exact String matching algorithms has been very significant in many applications in the last two decades. This is due to the advancement in technology that produces large volumes of data. The main factors in string matching algorithms are the number of attempts, the number of character comparison and the running time. These factors are influenced by the type of algorithm, type of data, data size and length of pattern used. In this article, we perform review for advantages and disadvantages of executing exact string matching algorithm. We conclude that the suffix automata and hybrid are the faster algorithms with the lowest number of attempts and the hashing approaches have the lower number of comparison. The bit parallelism algorithms have the similar limitations. Keyword: Exact string matching, character comparison, number of attempt, limitations;
---
paper_title: Efficient randomized pattern-matching algorithms

paper_content:

We present randomized algorithms to solve the following string-matching problem and some of its generalizations: Given a string X of length n (the pattern) and a string Y (the text), find the first occurrence of X as a consecutive block within Y. The algorithms represent strings of length n by much shorter strings called fingerprints, and achieve their efficiency by manipulating fingerprints instead of longer strings. The algorithms require a constant number of storage locations, and essentially run in real time. They are conceptually simple and easy to implement. The method readily generalizes to higher-dimensional patternmatching problems.
---
paper_title: Comparison of Exact String Matching Algorithms for Biological Sequences

paper_content:

Exact matching of single patterns in DNA and amino acid sequences is studied. We performed an extensive experimental comparison of algorithms presented in the literature. In addition, we introduce new variations of earlier algorithms. The results of the comparison show that the new algorithms are efficient in practice.
---
paper_title: A FAST ALGORITHM FOR MULTI-PATTERN SEARCHING

paper_content:

A new algorithm to search for multiple patterns at the same time is presented. The algorithm is faster than previous algorithms and can support a very large number — tens of thousands — of patterns. Several applications of the multi-pattern matching problem are discussed. We argue that, in addition to previous applications that required such search, multi-pattern matching can be used in lieu of indexed or sorted data in some applications involving small to medium size datasets. Its advantage, of course, is that no additional search structure is needed.
---
paper_title: Fast exact string matching algorithms

paper_content:

String matching is the problem of finding all the occurrences of a pattern in a text. We propose a very fast new family of string matching algorithms based on hashing q-grams. The new algorithms are the fastest on many cases, in particular, on small size alphabets.
---
paper_title: A Very Fast String Matching Algorithm Based on Condensed Alphabets

paper_content:

String matching is the problem of finding all the substrings of a text which correspond to a given pattern. It’s one of the most investigated problem in computer science, mainly due to its various applications in many fields. In recent years most solutions to the problem focused on efficiency and flexibility of the searching procedure and effective techniques appeared to speed-up previous solutions. In this paper we present a simple and very efficient algorithm for string matching. It can be seen as an extension of the Skip-Search algorithm to condensed alphabets with the aim of reducing the number of verifications during the searching phase. From our experimental results it turns out that the new variant obtains in most cases the best running time when compared against the most effective algorithms in literature. This makes the new algorithm one of the most flexible solutions in practical cases.
---
paper_title: A FAST ALGORITHM FOR MULTI-PATTERN SEARCHING

paper_content:

A new algorithm to search for multiple patterns at the same time is presented. The algorithm is faster than previous algorithms and can support a very large number — tens of thousands — of patterns. Several applications of the multi-pattern matching problem are discussed. We argue that, in addition to previous applications that required such search, multi-pattern matching can be used in lieu of indexed or sorted data in some applications involving small to medium size datasets. Its advantage, of course, is that no additional search structure is needed.
---
paper_title: A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching

paper_content:

We present a new algorithm for string matching. The algorithm, called BNDM, is the bit-parallel simulation of a known (but recent) algorithm called BDM. BDM skips characters using a “suffix automaton” which is made deterministic in the preprocessing. BNDM, instead, simulates the nondeterministic version using bit-parallelism. This algorithm is 20%–25% faster than BDM, 2–3 times faster than other bit-parallel algorithms, and 10%–40% faster than all the Boyer-Moore family. This makes it the fastest algorithm in all cases except for very short or very long patterns (e.g. on English text it is the fastest between 5 and 110 characters). Moreover, the algorithm is very simple, allowing to easily implement other variants of BDM which are extremely complex in their original formulation. We show that, as other bit-parallel algorithms, BNDM can be extended to handle classes of characters in the pattern and in the text, multiple patterns and to allow errors in the pattern or in the text, combining simplicity, efficiency and flexibility. We also generalize the suffix automaton definition to handle classes of characters. To the best of our knowledge, this extension has not been studied before.
---
paper_title: Parallelization of KMP String Matching Algorithm on Different SIMD architectures: Multi-Core and GPGPU’s

paper_content:

matching is a classical problem in computer science. After the study of the Naive string search, Brute Force and the KMP algorithm, several advantages and disadvantages of the algorithms have been analyzed. Considering KMP in particular concept of parallelization has been introduced to improve the performance of the KMP algorithm. The algorithm is designed to work on SIMD parallel architecture where text is divided for parallel processing and special searching at division point is required for consistent and complete searching. This algorithm reduces the number of comparisons and parallelization improves the time efficiency. This algorithm achieves a better result as compared to the multithreaded version of the algorithm where again by text dividing, the parallelization is achieved.
---
paper_title: FAST PATTERN MATCHING IN STRINGS*

paper_content:

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use, and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time. Other algorithms which run even faster on the average are also considered.
---
paper_title: Mealy Machines Are A Better Model Of Lexical Analyzers

paper_content:

Lexical analyzers partition input characters into tokens. When ambiguities arise during lexical analysis, the longest-match rule is generally adopted to resolve the ambiguities. The longest-match rule causes the look-ahead problem in traditional lexical analyzers, which are based on Moore machines. In Moore machines, output tokens are associated with states of the automata. By contrast, because Mealy machines associate output tokens with state transitions, the look-ahead behaviors can be encoded in their state transition tables. Therefore, we believe that lexical analyzers should be based on Mealy machines, rather than Moore machines, in order to solve the look-ahead problem. We propose techniques to construct Mealy machines from regular expressions and to perform sequential and data-parallel lexical analysis with these Mealy machines.
---
paper_title: Simple Optimal String Matching Algorithm

paper_content:

We present a new string matching algorithm linear in the worst case (in O(m + n) where n is the size of the text and m the size of the searched word, both taken on an alphabet Σ) and optimal on average (with equiprobability and independence of letters, in O(m + n log|Σ| m/m)). Of all the algorithms that verify these two complexities, our is the simplest since it uses only a single structure, a suffix automaton. Moreover, its preprocessing phase is linearly dynamical, i.e. it is possible to search the words p1, then p1p2, p1p2p3, . . . , p1p2p3 . . . pi with O(Σ|pi|) total preprocessing time. Among the algorithms that verify this property (for instance the Knuth-Morris-Pratt) our algorithm is the only one to be optimal on average.
---
paper_title: Factor oracle: a new structure for pattern matching

paper_content:

We introduce a new automaton on a word p, sequence of letters taken in an alphabet ?, that we call factor oracle. This automaton is acyclic, recognizes at least the factors of p, has m+1 states and a linear number of transitions. We give an on-line construction to build it. We use this new structure in string matching algorithms that we conjecture optimal according to the experimental results. These algorithms are as efficient as the ones that already exist using less memory and being more easy to implement.
---
paper_title: EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM

paper_content:

In this article we present two efficient variants of the BOM string matching algorithm which are more efficient and flexible than the original algorithm. We also present bitparallel versions of them obtaining an efficient variant of the BNDM algorithm. Then we compare the newly presented algorithms with some of the most recent and effective string matching algorithms. It turns out that the new proposed variants are very flexible and achieve very good results, especially in the case of large alphabets.
---
paper_title: The wide window string matching algorithm

paper_content:

Generally, current string matching algorithms make use of a window whose size is equal to pattern length. In this paper, we present a novel string matching algorithm named WW (for Wide Window) algorithm, which divides the text into [n/m] overlapping windows of size 2m - 1. In the windows, the algorithm attempts m possible occurrence positions in parallel. It firstly searches pattern suffixes from middle to right with a forward suffix automaton, shifts the window directly when it fails, otherwise, scans the corresponding prefixes backward with a reverse prefix automaton. Theoretical analysis shows that WW has optimal time complexity of O(n) in the worst, O(n/m) best and O(n(logσm)/m) for average case. Experimental comparison of WW with existing algorithms validates our theoretical claims for searching long patterns. It further reveals that WW is also efficient for searching short patterns.
---
paper_title: Two Improved Single Pattern Matching Algorithms

paper_content:

In this paper, two single pattern matching algorithms are presented, each of which is composed by a smallest suffix automaton and a forward finite state automaton. Whatever the suffix automaton or the forward finite state automaton is running, the window shifts m-R characters and then the suffix automaton starts running if no pattern prefix is found (R is zero) in the first algorithm or R is not greater than half of m in the second algorithm, otherwise, the forward finite state automaton starts running. Their time complexities are all O(n) in the worst case and O(n/m) in the best case. The experimental results show that the average time complexities of two algorithms are less than that of RF and LDM for short patterns and that of BM for long patterns over small alphabets or short lengths over large alphabets.
---
paper_title: Suffix Type String Matching Algorithms Based on Multi-windows and Integer Comparison

paper_content:

In this paper, 3 classic suffix type algorithms: QS, Tuned BM and BMHq were improved by reducing the average cost of basic operations. Firstly, the multi-windows method was used to let the calculations of the jump distance run in parallel and pipelining. Secondly, the comparison unit was increased to integer to reduce the total number and the average cost of comparisons. Especially for BMHq, the jump distance was increased by good prefix rule and the operations to get the jump distance were simplified by unaligned integer read. Thus, 3 algorithms named QSMI, TBMMI and BMHqMI were presented. These algorithms are faster than other known algorithms in many cases.
---
paper_title: Efficient Online Timed Pattern Matching by Automata-Based Skipping

paper_content:

The timed pattern matching problem is an actively studied topic because of its relevance in monitoring of real-time systems. There one is given a log $w$ and a specification $\mathcal{A}$ (given by a timed word and a timed automaton in this paper), and one wishes to return the set of intervals for which the log $w$, when restricted to the interval, satisfies the specification $\mathcal{A}$. In our previous work we presented an efficient timed pattern matching algorithm: it adopts a skipping mechanism inspired by the classic Boyer--Moore (BM) string matching algorithm. In this work we tackle the problem of online timed pattern matching, towards embedded applications where it is vital to process a vast amount of incoming data in a timely manner. Specifically, we start with the Franek-Jennings-Smyth (FJS) string matching algorithm---a recent variant of the BM algorithm---and extend it to timed pattern matching. Our experiments indicate the efficiency of our FJS-type algorithm in online and offline timed pattern matching.
---
paper_title: Simple Optimal String Matching Algorithm

paper_content:

We present a new string matching algorithm linear in the worst case (in O(m + n) where n is the size of the text and m the size of the searched word, both taken on an alphabet Σ) and optimal on average (with equiprobability and independence of letters, in O(m + n log|Σ| m/m)). Of all the algorithms that verify these two complexities, our is the simplest since it uses only a single structure, a suffix automaton. Moreover, its preprocessing phase is linearly dynamical, i.e. it is possible to search the words p1, then p1p2, p1p2p3, . . . , p1p2p3 . . . pi with O(Σ|pi|) total preprocessing time. Among the algorithms that verify this property (for instance the Knuth-Morris-Pratt) our algorithm is the only one to be optimal on average.
---
paper_title: A FAST ALGORITHM FOR MULTI-PATTERN SEARCHING

paper_content:

A new algorithm to search for multiple patterns at the same time is presented. The algorithm is faster than previous algorithms and can support a very large number — tens of thousands — of patterns. Several applications of the multi-pattern matching problem are discussed. We argue that, in addition to previous applications that required such search, multi-pattern matching can be used in lieu of indexed or sorted data in some applications involving small to medium size datasets. Its advantage, of course, is that no additional search structure is needed.
---
paper_title: Alternative algorithms for bit-parallel string matching

paper_content:

We consider bit-parallel algorithms of Boyer-Moore type for exact string matching. We introduce a two-way modification of the BNDM algorithm. If the text character aligned with the end of the pattern is a mismatch, we continue by examining text characters after the alignment. Besides this two-way variation, we present a simplified version of BNDM without prefix search and an algorithm scheme for long patterns. We also study a different bit-parallel algorithm, which keeps the history of examined characters in a bit-vector and where shifting is based on this bit-vector. We report experiments where we compared the new algorithms with existing ones. The simplified BNDM is the most promising of the new algorithms in practice.
---
paper_title: Filter Based Fast Matching of Long Patterns by Using SIMD Instructions.

paper_content:

SIMD instructions exist in many recent microprocessors supporting parallel execution of some operations on multiple data simultaneously via a set of special instructions working on limited number of special registers. Although the usage of SIMD is explored deeply in multimedia processing, implementation of encryption/decryption algorithms, and on some scientific calculations, it has not been much addressed in pattern matching. This study introduces a filter based exact pattern matching algorithm for searching long strings benefiting from SIMD instructions of Intel’s SSE (streaming SIMD extensions) technology. The proposed algorithm has worst, best, and average time complexities of O(n · m), O(n/m), and O(n/m + n · m/2) respectively, while searching an m bytes pattern on a text of n bytes. Experiments on small, medium, and large alphabet text files are conducted to compare the performance of the new algorithm with other alternatives, which are known to be very fast on long string search operations. In all cases the proposed algorithm is the clear winner on the average. When compared with the nearest successor, the matching speed is improved in orders of magnitude on small alphabet sequences. The performance is 40 % better on medium alphabets, and 50 % on natural language text.
---
paper_title: Practical and Optimal String Matching

paper_content:

We develop a new exact bit-parallel string matching algorithm, based on the Shift-Or algorithm (Baeza-Yates & Gonnet, 1992). Assuming that the pattern representation fits into a single computer word, this algorithm has optimal O(n logσm / m) average running time, as well as optimal O(n) worst case running time, where n, m and σ are the sizes of the text, the pattern, and the alphabet, respectively. We also study several implementation details. The experimental results show that our algorithm is the fastest in most of the cases where it can be applied, displacing even the long-standing BNDM (Navarro & Raffinot, 2000) family of algorithms. Finally, we show how to adapt our techniques for the Shift-Add algorithm (Baeza-Yates & Gonnet, 1992), obtaining optimal time for searching under Hamming distance.
---
paper_title: A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching

paper_content:

The performance of the pattern matching algorithms based on bit-parallelism degrades when the input pattern length exceeds the computer word size. Although several divide-and-conquer methods have been proposed to overcome that limitation, the resulting schemes are not that much efficient and hard to implement. This study introduces a new fast bit-parallel pattern matching algorithm that is capable of searching patterns of any length in a common bit-parallel fashion. The proposed bit-parallel length invariant matcher (BLIM) is compared with the Shift-Or and bit-parallel non-deterministic matching (BNDM) algorithms along with the standard Boyer-Moore and Sunday's quick search, which are known to be the very fast in general. Benchmarks have been conducted on natural language, DNA sequence, and binary alphabet random texts. Besides the length invariant architecture of the algorithm, experimental results indicate that on the average BLIM is 18%, 44%, and 6% faster than BNDM, which is accepted as one of the fastest algorithms of this genre, on natural language, DNA sequence and binary random texts respectively.
---
paper_title: The exact online string matching problem: A review of the most recent results

paper_content:

This article addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.
---
paper_title: The exact string matching algorithms efficiency review

paper_content:

Exact String matching algorithms has been very significant in many applications in the last two decades. This is due to the advancement in technology that produces large volumes of data. The main factors in string matching algorithms are the number of attempts, the number of character comparison and the running time. These factors are influenced by the type of algorithm, type of data, data size and length of pattern used. In this article, we perform review for advantages and disadvantages of executing exact string matching algorithm. We conclude that the suffix automata and hybrid are the faster algorithms with the lowest number of attempts and the hashing approaches have the lower number of comparison. The bit parallelism algorithms have the similar limitations. Keyword: Exact string matching, character comparison, number of attempt, limitations;
---
paper_title: A new approach to text searching

paper_content:

We introduce a family of simple and fast algorithms for solving the classical string matching problem, string matching with don't care symbols and complement symbols, and multiple patterns. In addition we solve the same problems allowing up to k mismatches. Among the features of these algorithms are that they are real time algorithms, they don't need to buffer the input, and they are suitable to be implemented in hardware.
---
paper_title: A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching

paper_content:

We present a new algorithm for string matching. The algorithm, called BNDM, is the bit-parallel simulation of a known (but recent) algorithm called BDM. BDM skips characters using a “suffix automaton” which is made deterministic in the preprocessing. BNDM, instead, simulates the nondeterministic version using bit-parallelism. This algorithm is 20%–25% faster than BDM, 2–3 times faster than other bit-parallel algorithms, and 10%–40% faster than all the Boyer-Moore family. This makes it the fastest algorithm in all cases except for very short or very long patterns (e.g. on English text it is the fastest between 5 and 110 characters). Moreover, the algorithm is very simple, allowing to easily implement other variants of BDM which are extremely complex in their original formulation. We show that, as other bit-parallel algorithms, BNDM can be extended to handle classes of characters in the pattern and in the text, multiple patterns and to allow errors in the pattern or in the text, combining simplicity, efficiency and flexibility. We also generalize the suffix automaton definition to handle classes of characters. To the best of our knowledge, this extension has not been studied before.
---
paper_title: TVSBS: A fast exact pattern matching algorithm for biological sequences

paper_content:

The post-genomic era is witnessing a remarkable increase in the number of nucleotide and amino acid sequences. The content of biological sequence databases almost doubles frequently. Pattern matching emerges as a powerful tool in locating nucleotide or amino acid sequence patterns in the biological sequence databases. Presently, several pattern-matching algorithms are available in the literature right from the basic Brute Force algorithm to the recent SSABS. The efficiency of the various algorithms depends on faster and exact identification of the pattern in the text. In this article, we propose an exact pattern-matching algorithm for biological sequences. The proposed algorithm, TVSBS, is a combination of Berry–Ravindran and SSABS algorithms. The performance of the new algorithm has been improved using the shift of Berry–Ravindran bad character table, which leads to lesser number of character comparisons. It works consistently well for both nucleotide and amino acid sequences. The proposed algorithm has been compared with the recent algorithm, SSABS. The results show the robustness of the proposed algorithm and thus it can be incorporated in any exact pattern-matching applications involving biological sequences. The best- and worst-case time complexities of the new algorithm are also outlined.
---
paper_title: Speeding up two string matching algorithms

paper_content:

We show how to speed up two string-matching algorithms: the Boyer-Moore algorithm (BM algorithm), and its version called here the reverse factor algorithm (RF algorithm). The RF algorithm is based on factor graphs for the reverse of the pattern. The main feature of both algorithms is that they scan the text right-to-left from the supposed right position of the pattern. The BM algorithm goes as far as the scanned segment (factor) is a suffix of the pattern. The RF algorithm scans while the segment is a factor of the pattern. Both algorithms make a shift of the pattern, forget the history, and start again. The RF algorithm usually makes bigger shifts than BM, but is quadratic in the worst case. We show that it is enough to remember the last matched segment (represented by two pointers to the text) to speed up the RF algorithm considerably (to make a linear number of inspections of text symbols, with small coefficient), and to speed up the BM algorithm (to make at most 2 ·n comparisons). Only a constant additional memory is needed for the search phase. We give alternative versions of an accelerated RF algorithm: the first one is based on combinatorial properties of primitive words, and the other two use the power of suffix trees extensively. The paper demonstrates the techniques to transform algorithms, and also shows interesting new applications of data structures representing all subwords of the pattern in compact form.
---
paper_title: Alternative algorithms for bit-parallel string matching

paper_content:

We consider bit-parallel algorithms of Boyer-Moore type for exact string matching. We introduce a two-way modification of the BNDM algorithm. If the text character aligned with the end of the pattern is a mismatch, we continue by examining text characters after the alignment. Besides this two-way variation, we present a simplified version of BNDM without prefix search and an algorithm scheme for long patterns. We also study a different bit-parallel algorithm, which keeps the history of examined characters in a bit-vector and where shifting is based on this bit-vector. We report experiments where we compared the new algorithms with existing ones. The simplified BNDM is the most promising of the new algorithms in practice.
---
paper_title: A fast algorithm for order-preserving pattern matching

paper_content:

We present a new method of deciding the order-isomorphism between two strings.We show that the bad character rule can be applied to the OPPM problem.We present a space-efficient algorithm computing the shift table for text search.We present a linear-time algorithm for an integer alphabet in the worst case. Given a text T and a pattern P, the order-preserving pattern matching (OPPM) problem is to find all substrings in T which have the same relative orders as P. The OPPM has been studied in the fields of finding some patterns affected by relative orders, not by their absolute values. In this paper, we present a method of deciding the order-isomorphism between two strings even when there are same characters. Then, we show that the bad character rule of the Horspool algorithm for generic pattern matching problems can be applied to the OPPM problem and we present a space-efficient algorithm for computing shift tables for text search. Finally, we combine our bad character rule with the KMP-based algorithm to improve the worst-case running time. We give experimental results to show that our algorithm is about 2 to 6 times faster than the KMP-based algorithm in reasonable cases.
---
paper_title: GRASPm: an efficient algorithm for exact pattern-matching in genomic sequences

paper_content:

In this paper, we propose Genomic-oriented Rapid Algorithm for String Pattern-match (GRASPm), an algorithm centred on overlapped 2-grams analysis, which introduces a novel filtering heuristic - the compatibility rule - achieving significant efficiency gain. GRASPm's foundations rely especially on a wide searching window having the central duplet as reference for fast filtering of multiple alignments. Subsequently, superfluous detailed verifications are summarily avoided by filtering the incompatible alignments using the idcd (involving duplet of central duplet) concept combined with pre-processed conditions, allowing fast parallel testing for multiple alignments. Comparative performance analysis, using diverse genomic data, shows that GRASPm is faster than its competitors.
---
paper_title: Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm

paper_content:

The string matching problem, i.e. the task of finding all occurrences of one string as a substring of another one, is a fundamental problem in computer science. Recently, this problem received a great deal of attention due to numerous applications in computational biology. In this paper we address a modified version of Horspool's string matching algorithm using the probabilities of the different symbols to speed up the search. We show that the modified algorithm has a linear average running time; a precise asymptotical representation of the running time will be proven. A comparison of the average running time of the modified algorithm with well-known results for the original method shows that a substantial speed up for most of the symbol distributions has been achieved. Finally, we show that the distribution of the symbols can be approximated to a high precision using a random sample of sublinear size.
---
paper_title: Efficient string matching: an aid to bibliographic search

paper_content:

This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
---
paper_title: Bidirectional search in a string with wavelet trees and bidirectional matching statistics

paper_content:

Searching for genes encoding microRNAs (miRNAs) is an important task in genome analysis. Because the secondary structure of miRNA (but not the sequence) is highly conserved, the genes encoding it can be determined by finding regions in a genomic DNA sequence that match the structure. It is known that algorithms using a bidirectional search on the DNA sequence for this task outperform algorithms based on unidirectional search. The data structures supporting a bidirectional search (affix trees and affix arrays), however, are rather complex and suffer from their large space consumption. Here, we present a new data structure called bidirectional wavelet index that supports bidirectional search with much less space. With this data structure, it is possible to search for candidates of RNA secondary structural patterns in large genomes, for example the complete human genome. Another important application of this data structure is short read alignment. As a second contribution, we show how bidirectional matching statistics can be computed in linear time.
---
paper_title: The exact online string matching problem: A review of the most recent results

paper_content:

This article addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.
---
paper_title: A Deterministic Cost-effective String Matching Algorithm for Network Intrusion Detection System

paper_content:

Network intrusion detection systems (NIDS) are more and more important in today's network security for identifying and preventing malicious attacks over the network. This paper proposes a novel and effective string matching algorithm (named ACMS) with advantages of both compact memory and high performance. By employing the characteristics of magic states observed from the deterministic finite state automata, the proposed ACMS significantly reduces the memory requirement without sacrificing high speed no matter it is implemented in software or hardware. The ACMS algorithm also provides high flexibility that it can be tuned to fit specific performance requirement and resource constraints. The experimental results show that the performance of ACMS is over 3.5 times in hardware implementation and 21 times in software implementation better than that of the state-of-the-art studies.
---
paper_title: Practical fast searching in strings

paper_content:

SUMMARY The problem of searching through text to find a specified substring is considered in a practical setting. It is discovered that a method developed by Boyer and Moore can outperform even special-purpose search instructions that may be built into the, computer hardware. For very short substrings however, these special purpose instructions are fastest-provided that they are used in an optimal way.
---
paper_title: New string matching technology for network security

paper_content:

String matching is a comprehensive applicable key technology beyond intrusion detection systems (IDS), and many areas can benefit from faster string matching algorithm. Which can be used in IDS, firewall et al network security applications. These applications are usually deployed at choke points of a network where there is heavily traffic. Using lower efficient string matching algorithm may make these applications to become a performance bottleneck in network. So it is very necessary to develop faster and more efficient string matching algorithms in order to overcome the troubles on performance. On a basis of Boyer-Moore-Horspool algorithm, a new string matching algorithm is presented in this paper. The algorithm is described in detail. The new algorithm has been greatly improved. The algorithm is one simplification of Boyer-Moore-Horspool algorithm. Array NEXT in Preprocessing stage is redesigned. A novel generated rules are presented. Using these rules, a simple NEXT is generated. And based on the concept of reference point, all make the algorithm to have better performance and more efficient. These characteristics will be useful in all these applications. Main features of the algorithm are presented, then explained its work processes. The algorithm also passed test and is validated. The test results show that the algorithm has better performance than Boyer-Moore algorithm and Boyer-Moore-Horspool algorithm, and more simple and efficient.
---
paper_title: The exact string matching algorithms efficiency review

paper_content:

Exact String matching algorithms has been very significant in many applications in the last two decades. This is due to the advancement in technology that produces large volumes of data. The main factors in string matching algorithms are the number of attempts, the number of character comparison and the running time. These factors are influenced by the type of algorithm, type of data, data size and length of pattern used. In this article, we perform review for advantages and disadvantages of executing exact string matching algorithm. We conclude that the suffix automata and hybrid are the faster algorithms with the lowest number of attempts and the hashing approaches have the lower number of comparison. The bit parallelism algorithms have the similar limitations. Keyword: Exact string matching, character comparison, number of attempt, limitations;
---
paper_title: A New String Matching Algorithm

paper_content:

In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n . It requires only O ( m +σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.
---
paper_title: Hybrid string matching algorithm with a pivot

paper_content:

Pattern matching is important in text processing, molecular biology, operating systems and web search engines. Many algorithms have been developed to search for a specific pattern in a text, but the need for an efficient algorithm is an outstanding issue. In this paper, we present a simple and practical string matching algorithm. The proposed algorithm is a hybrid that combines our modification of Horspool's algorithm with two observations on string matching. The algorithm scans the text from left to right and matches the pattern from right to left. Experimental results on natural language texts, genomes and human proteins demonstrate that the new algorithm is competitive with practical algorithms.
---
paper_title: The Boyer–Moore–Galil String Searching Strategies Revisited

paper_content:

Based on the Boyer–Moore–Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring. Preprocessing is only slightly more involved and still requires a time linear in the pattern size.
---
paper_title: Fast Practical Multi-Pattern Matching

paper_content:

The multi-pattern matching problem consists in finding all occurrences of the patterns from a finite set X in a given textT of length n. We present a new and simple algorithm combining the ideas of the Aho‐Corasick algorithm and the directed acyclic word graphs. The algorithm has time complexity which is linear in the worst case (it makes at most 2n symbol comparisons) and has good average-case time complexity assuming the shortest pattern is sufficiently long. Denote the length of the shortest pattern bym, and the total length of all patterns by M. Assume thatM is polynomial with respect tom, the alphabet contains at least 2 symbols and the text (in which the pattern is to be found) is random, for each position each letter occurs independently with the same probability. Then the average number of comparisons is O..n=m/ logm/, which matches the lower bound of the problem. For sufficiently large values of m the algorithm has a good behavior in practice. © 1999 Elsevier Science B.V. All rights reserved.
---
paper_title: A FAST Pattern Matching Algorithm

paper_content:

The advent of digital computers has made the routine use of pattern-matching possible in various applications. This has also stimulated the development of many algorithms. In this paper, we propose a new algorithm that offers improved performance compared to those reported in the literature so far. The new algorithm has been evolved after analyzing the well-known algorithms such as Boyer-Moore, Quick-search, Raita, and Horspool. The overall performance of the proposed algorithm has been improved using the shift provided by the Quick-search bad-character and by defining a fixed order of comparison. These result in the reduction of the character comparison effort at each attempt. The best- and the worst- case time complexities are also presented in this paper. Most importantly, the proposed method has been compared with the other widely used algorithms. It is interesting to note that the new algorithm works consistently better for any alphabet size.
---
paper_title: Hybrid Approach to Reduce Time Complexity of String Matching Algorithm Using Hashing with Chaining

paper_content:

String matching is an integral part of various important areas of computer science viz search engines, DNA matching, information retrieval, security, and biological systems. String matching algorithms are used in finding a pattern in a string. In this paper, the authors have given a novel algorithm to reduce the time complexity of string matching. The proposed algorithm is based on the concept of hashing with chaining. Further, the authors have found reduced time complexity in most of the cases and equal in few.
---
paper_title: Fast-search: a new efficient variant of the Boyer-Moore string matching algorithm

paper_content:

We present a new variant of the Boyer-Moore string matching algorithm which, though not linear, is very fast in practice. ::: ::: We compare our algorithm with the Horspool, Quick Search, Tuned Boyer-Moore, and Reverse Factor algorithms, which are among the fastest string matching algorithms for practical uses. It turns out that our algorithm achieve very good results in terms of both time efficiency and number of character inspections, especially in the cases in which the patterns are very short.
---
paper_title: Trends in big data analytics

paper_content:

Abstract One of the major applications of future generation parallel and distributed systems is in big-data analytics. Data repositories for such applications currently exceed exabytes and are rapidly increasing in size. Beyond their sheer magnitude, these datasets and associated applications’ considerations pose significant challenges for method and software development. Datasets are often distributed and their size and privacy considerations warrant distributed techniques. Data often resides on platforms with widely varying computational and network capabilities. Considerations of fault-tolerance, security, and access control are critical in many applications (Dean and Ghemawat, 2004; Apache hadoop). Analysis tasks often have hard deadlines, and data quality is a major concern in yet other applications. For most emerging applications, data-driven models and methods, capable of operating at scale, are as-yet unknown. Even when known methods can be scaled, validation of results is a major issue. Characteristics of hardware platforms and the software stack fundamentally impact data analytics. In this article, we provide an overview of the state-of-the-art and focus on emerging trends to highlight the hardware, software, and application landscape of big-data analytics.
---
paper_title: Residual-based approach for authenticating pattern of multi-style diacritical Arabic texts

paper_content:

Arabic script is highly sensitive to changes in meaning with respect to the accurate arrangement of diacritics and other related symbols. The most sensitive Arabic text available online is the Digital Qur'an, the sacred book of Revelation in Islam that all Muslims including non-Arabs recite as part of their worship. Due to the different characteristics of the Arabic letters like diacritics (punctuation symbols), kashida (extended letters) and other symbols, it is written and available in different styles like Kufi, Naskh, Thuluth, Uthmani, etc. As social media has become part of our daily life, posting downloaded Qur'anic verses from the web is common. This leads to the problem of authenticating the selected Qur'anic passages available in different styles. This paper presents a residual approach for authenticating Uthmani and plain Qur'an verses using one common database. Residual (difference) is obtained by analyzing the differences between Uthmani and plain Quranic styles using XOR operation. Based on predefined data, the proposed approach converts Uthmani text into plain text. Furthermore, we propose to use the Tuned BM algorithm (BMT) exact pattern matching algorithm to verify the substituted Uthmani verse with a given database of plain Qur'anic style. Experimental results show that the proposed approach is useful and effective in authenticating multi-style texts of the Qur'an with 87.1% accuracy.
---
paper_title: Approaches for preserving content integrity of sensitive online Arabic content: A survey and research challenges

paper_content:

Abstract Trends in Internet usage and accessing online content in different languages and formats are proliferating at a considerable speed. There is a vast amount of digital online content available in different formats that are sensitive in nature with respect to writing styles and arrangement of diacritics. However, research done in the area aimed at identifying the necessary techniques suitable for preserving content integrity of sensitive digital online content is limited. So, it is a challenge to determine the techniques most suitable for different formats such as image or binary. Hence, preserving and verifying sensitive content constitutes an emerging problem and calls for timely solutions. The digital Holy Qur'an in Arabic, constitutes, one case of such sensitive content. Due to the different characteristics of the Arabic letters like diacritics (punctuation symbols), kashidas (extended letters) and other symbols, it is very easy to alter the original meaning of the text by simply changing the arrangement of diacritics. This article surveys the different approaches that are presently employed in the process of preserving and verifying the content integrity of sensitive online content. We present the state-of-the-art in content integrity verification and address the existing challenges in preserving the integrity of sensitive texts using the Digital Qur'an as a case study. The proposed taxonomy provides an effective classification and analysis of existing related schemes and their limitations. The paper discusses the recommendations of the expected efficiency of such approaches when applied for use in digital content integrity. Some of the main findings suggest unified approaches of watermarking and string matching approaches can be used to preserve content integrity of any sensitive digital content.
---
paper_title: Preserving Content Integrity of Digital Holy Quran: Survey and Open Challenges

paper_content:

In recent years, a new trend has come up, which is that of reading the digital Quran online. This text was revealed more than 1400 years ago in the Arabic language and has been protected from all possible ways of distortion until today. Unfortunately, driven by the desire to make profit or gain publicity, fraudsters have started modifying certain Quranic verses. These alterations are misleading many people who are thus deprived of the original and accurate message of the Holy Quran. This paper focuses on systematically analyzing and categorizing existing research related to preserving and verifying the content integrity of the Quran. This paper further assesses these existing studies in terms of their evaluation parameters and findings. We find that the existing studies can be classified according to their format and methods, i.e., the online formats in which the Quranic content is available, methods employed to protect the Quranic content from modification, and last methods of verification. This paper concludes with the issue of future challenges and their possible solutions.
---
paper_title: The exact online string matching problem: A review of the most recent results

paper_content:

This article addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.
---
paper_title: An efficient parallel-network packet pattern-matching approach using GPUs

paper_content:

Abstract In the past few years, the increase in interest usage has been substantial. The high network bandwidth speed and the large amount of threats pose challenges to current network intrusion detection systems, which manage high amounts of network traffic and perform complicated packet processing. Pattern matching is a computationally intensive process included in network intrusion detection systems. In this paper, we present an efficient graphics processing unit (GPU)-based network packet pattern-matching algorithm by leveraging the computational power of GPUs to accelerate pattern-matching operations and subsequently increase the overall processing throughput. According to the experimental results, the proposed algorithm achieved a maximal traffic processing throughput of over 2 Gbit/s. The results demonstrate that the proposed GPU-based algorithm can effectively enhance the performance of network intrusion detection systems.
---
paper_title: A review of recent advances on multimedia watermarking security and design implications for digital Quran computing

paper_content:

The explosion in the online propagation of digital multimedia suggests that such data is vulnerable to threats, data-manipulation and attack. This problem is further exacerbated when dealing with highly sensitive digital multimedia content such as the Holy Quran, in which the modification/corruption of a single character, diacritic or symbol would regard the entire content as invalid. Hence, the protection of sensitive data and Quran multimedia data in particular is essential to ensure that only the original non-tampered data is propagated with no distortion. Protection schemes include verifying integrity, proof-of-authenticity, tamper-detection and copyright protection. A technique in the literature used to provide the necessary security for such digital content is known as digital watermarking. This paper reviews the state-of-the-art in digital text, image and audio watermarking applicable to sensitive digital content and discusses how those approaches can achieve the required protection, measured against relevant performance metrics and set according to their respective environments and digital formats being used. The main goal of this paper is to provide an effective study by which to develop new techniques and approaches for the protection of sensitive multimedia content.
---
paper_title: Image pattern recognition in big data: taxonomy and open challenges: survey

paper_content:

Image pattern recognition in the field of big data has gained increasing importance and attention from researchers and practitioners in many domains of science and technology. This paper focuses on the usage of image pattern recognition for big data applications. In this context, the taxonomy of image pattern recognition and big data is revealed. The applications of image pattern recognition for big data, including multimedia, biometrics, and biology/biomedical, are also highlighted. Moreover, the significance of using pattern-based feature reduction in big data is discussed, and machine-learning techniques in pattern recognition applications are presented. A comparison based on the objectives of the approaches is presented to underline the taxonomy. This paper provides a novel review in exploring image recognition approaches for big data, which can be used in future research.
---
paper_title: Preserving Content Integrity of Digital Holy Quran: Survey and Open Challenges

paper_content:

In recent years, a new trend has come up, which is that of reading the digital Quran online. This text was revealed more than 1400 years ago in the Arabic language and has been protected from all possible ways of distortion until today. Unfortunately, driven by the desire to make profit or gain publicity, fraudsters have started modifying certain Quranic verses. These alterations are misleading many people who are thus deprived of the original and accurate message of the Holy Quran. This paper focuses on systematically analyzing and categorizing existing research related to preserving and verifying the content integrity of the Quran. This paper further assesses these existing studies in terms of their evaluation parameters and findings. We find that the existing studies can be classified according to their format and methods, i.e., the online formats in which the Quranic content is available, methods employed to protect the Quranic content from modification, and last methods of verification. This paper concludes with the issue of future challenges and their possible solutions.
---
paper_title: An Efficient Text Representation for Searching and Retrieving Classical Diacritical Arabic Text.

paper_content:

Abstract Due to the rapid growth of the Internet and advanced technologies, data storage and extraction of Arabic diacritical data in real time from an Arabic corpus have become a vital issue in the field of information retrieval. In this paper, we propose a new idea for representing Arabic diacritic text in the corpus such that search engines can enhance the search time of retrieving the desired text with high precision. To achieve our goal, we segment the Arabic diacritical sentences/verses into individual characters along with diacritics which are necessary for interpreting the meanings. Then, we propose a new data structure for representing data using segmented alphabets. To verify the corpus representation, the proposed approach uses the Boyer-Moore algorithm for searching given verses of Arabic diacritical data. The proposed representation of data structure reduces the search time from O(m*n) to O(1+m) in the worst case, where m denotes the diacritical verse to be searched, and n denotes the total number of diacritical verses. Experimental results on popular corpus show that the proposed method outperforms the existing search methods in terms of time complexity.
---

Title: Exact String Matching Algorithms: Survey, Issues, and Future Research Directions

Section 1: INTRODUCTION
Description 1: This section introduces the concept of string matching, its applications across different fields, and the motivation behind this survey.

Section 2: CLASSIFICATION OF STRING MATCHING ALGORITHMS
Description 2: This section provides a general classification of string matching algorithms, highlighting the main categories and their subcategories.

Section 3: ANALYSIS OF SOFTWARE-BASED SINGLE-PATTERN MATCHING ALGORITHMS
Description 3: This section explains the detailed survey work on software-based single-pattern matching algorithms, discussing fundamental algorithms like Boyer-Moore (BM), KMP, and Karp-Rabin.

Section 4: COMPARISON ANALYSIS OF SOFTWARE-BASED PATTERN STRING MATCHING ALGORITHMS
Description 4: This section contains a summary of single-pattern algorithms with their time complexity and limitations. It helps in understanding the strengths and weaknesses of the methods.

Section 5: CURRENT TRENDS, APPLICATIONS, CHALLENGES AND FUTURE SCOPE
Description 5: This section highlights the latest trends, current applications, challenges, and potential future research directions related to string matching algorithms.

Section 6: CONCLUSION
Description 6: This section provides the conclusions drawn from the survey, summarizing the key findings and the significance of the survey in guiding future research directions.