Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 119 for “"string matching"”.
-
Approximate String Matching
… in practice. Second, we cover approximate string matching in bidirectional indices. To improve the running time and make higher error rates suitable for index-based searches, we introduce an integer linear program for finding optimal search strategies. We show that it is significantly …
-
Towards Faster String Matching
Exact string matching is a much studied and popular problem. The task is to find the occurrences of a string pattern in a long text. We introduce several new algorithms for online exact string matching and study their experimental performance and compare them with some earlier algorithms. Moreover, …
-
Approximate string matching with pumping
… for computing edit distances between two strings is extended to compute the distance between a string and a class of strings represented by a regular expression. The result allows arbitrary pumping of symbols and substrings. The extended algorithm has the same complexity as the …
-
Character recognition using string matching
… character image. In this work, a directly string representation of the pattern ( prototype as well as unknown input) using the histogram method, a decision procedure for classification is the well known Levenshtein distance or weighted Levenshtein distance (Wanger 1974; Hall and Dowling …
-
Sensitivity analysis of online string-matching algorithms /
String-matching is a well known and studied problem in computer science that allows us to find occurrences of a pattern inside a text. As datasets grow larger every year, it becomes more and more important to know which algorithms work better in specific situations, as there is not a single …
-
Approximate string matching for high-throughput sequencing
… DNA reads, based on state of the art approximate string matching algorithms and data structures. Read mapping is a fundamental step of any HTS data analysis pipeline in resequencing projects, where DNA reads are reassembled by aligning them back to a previously known reference genome. The …
-
String matching and indexing with suffix data structures
… text so that the occurrences of any given query string in the text can be located efficiently. An occurrence or match may be imprecise, allowing some deviations from the actual query. This gives rise to a family of interesting string matching problems like exact and approximate string matching, …
-
Rappresentazioni compatte dell'automa suffisso per lo string matching
Quello dello string matching è un problema fondamentale nell'informatica, con una miriade di problemi di applicazioni dirette in diverse aree distinte dell’informatica, comprese i sistemi di gestione e compressione dei dati, la bioinformatica, l'elaborazione del linguaggio naturale, la linguistica …
-
Using partial string matching for coding of hierarchical grammars
… data can be compressed by extracting repeated strings in the input. Therefore, the input can be expressed using a context-free grammar, where each repeated string is denoted by a rule of the grammar. Sequitur [3] is one such method that derives a context-free grammar, which generates the given …
-
Parallel approximate string matching applied to occluded object recognition
This thesis develops an algorithm for approximate string matching and applies it to the problem of partially occluded object recognition. The algorithm measures the similarity of differing strings by scanning for matching substrings between strings. The length and number of matching substrings …
-
Approximate String Matching With Dynamic Programming and Suffix Trees
The importance and the contribution of string matching algorithms to the modern society cannot be overstated. From basic search algorithms such as spell checking and data querying, to advanced algorithms such as DNA sequencing, trend analysis and signal processing, string matching algorithms form …
-
Approximate string matching methods for duplicate detection and clustering tasks
Approximate string matching methods are utilized by a vast number of duplicate detection and clustering applications in various knowledge domains. The application area is expected to grow due to the recent significant increase in the amount of digital data and knowledge sources. Despite the large …
-
A multiprocessor parallel approach to bit-parallel approximate string matching
… applied along with bit-parallel approximate string matching algorithms to solve practical bioinformatics problems. It will demonstrate that nearly optimal speedup can be achieved with a cluster of between two and eight workstations using MPI (Message Passing Interface), directly decreasing …
-
Energy Efficient Hardware Accelerators for Packet Classification and String Matching
… that implement packet classification and fixed string matching. These computationally heavy and memory intensive tasks are used by networking equipment to inspect all packets at wire speed. The constant growth in Internet usage has made them increasingly difficult to implement at core network …
-
A multiprocessor parallel approach to bit-parallel approximate string matching
… applied along with bit-parallel approximate string matching algorithms to solve practical bioinformatics problems. It will demonstrate that nearly optimal speedup can be achieved with a cluster of between two and eight workstations using MPI (Message Passing Interface), directly decreasing …
-
Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index
… to derive optimal search schemes for approximate string matching using bidirectional FM-index, and utilize them in increasing the speed of such searches. Such a problem arises in computer science with many applications. Approximate string matching problem is also central in bioinformatics where …
-
Improved algorithms for string searching problems
… practically efficient algorithms for several string searching problems, where we search for a short string called the pattern in a longer string called the text. We are mainly interested in the online problem, where the text is not preprocessed, but we also present a light indexing approach to …
Page 1 of 6