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 38 for “"Suffix array"”.
-
Direct suffix sorting and its applications
The suffix sorting problem is to construct the suffix array for an input sequence. Given a sequence T[0... n -- 1] of size n = |T|, with symbols from a fixed alphabet Sigma, (|Sigma| ≤ n), the suffix array provides a compact representation of all the suffixes of T in a lexicographic order. …
-
Space efficient string search algorithms and data structures
… two new data structures, called the Sloppy Suffix Array and the Super Sloppy Suffix Array. These data structures are space efficient, easy to understand and implement. Sloppy suffix arrays can be built faster than suffix arrays with just one array of n integers; the search algorithms for …
-
USING SUFFIX ARRAYS FOR LEMPEL-ZIV DATA COMPRESSION
… the use of sophisticated data structures (e.g. suffix trees, binary search trees, etc) to hold the dictionary in order to boost the search time. The problem with such data structures is that the amount of memory required is variable and cannot be known in advance. Furthermore, some of these data …
-
Implementing Efficient Algorithms for Computing Runs
… following the strategy:</p> <p>1. Compute suffix array and LCP array in linear time;</p> <p>2. Using the suffix array and LCP array, compute Lempel-Ziv factorization in linear time;</p> <p>3. Using the Lempel-Ziv factorization, compute in linear time some of the runs that include all the …
-
Efficient String Algorithms with Applications in Bioinformatics
… present two algorithms to efficiently decode the Suffix Array/Inverse Suffix Array of the reveres text, by using the FM-index of the forward text. Additionally, our experimental results are competitive when compared to the standard approach of maintaining the FM-Index for both the forward and the …
-
Efficient Substring Discovery Using Suffix, LCP Array and Algorithm-Architecture Interaction
… when we preprocess the database in the form suffix array. Due to inherent organization of data in suffix array and it’s secondary data structure longest common prefix (LCP) array (Manber and Myers 1990) only a limited portion of the database is accessed during the searching operation which …
-
Parallel and scalable combinatorial string algorithms on distributed memory systems
… and the use of large computing clusters. Suffix arrays and trees are fundamental string data structures, which lie at the foundation of many string algorithms, with important applications in text processing, information retrieval, and computational biology. Conversely, the parallel …
-
Enhanced Suffix Trees for Very Large DNA Sequences
… scalable, and versatile processing of such data. Suffix tree (ST) is a data structure used for indexing genome data. This, however, comes with a price: it occupies a space that is about 10 times more than the input size. Existing disk-based ST index techniques either suffer from data skew problem, …
-
Performance comparisons of various runs algorithms
… the linear-time strategy of computing the suffix array of the string; using the suffix array it then computes the LCP array; us- ing the suffix and LCP arrays it computes the Lempel-Ziv factorization; from the Lempel-Ziv factorization all leftmost runs are computed using Main’s algorithm; …
-
Parameterized Strings: Algorithms and Data Structures
… only if prev(S) == prev(T). In order to utilize suffix data structures in terms of p-matching, we must account for the dynamic nature of the parameterized suffixes (p-suffixes) of T, namely prev(T[ i...n]) ∀ i, 1 ≤ i ≤ n.;In this work, we propose transformative approaches to the direct …
-
Optimizing Lempel-Ziv Factorization for the GPU Architecture
… We are also able to reevaluate the fastest GPU suffix array construction algorithm, which is needed to compute the LZ factorization. We are able to find speedups of up to 5x over the fastest CPU implementations.
-
Approximate String Matching With Dynamic Programming and Suffix Trees
… data structure in string algorithms, the suffix tree. The lowest common ancestor extension of the suffix tree is the key to many advanced string matching algorithms. With these tools, we are able to solve string problems that were, until recently, thought intractable by many. Another …
-
EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS
… a border that occurs only as a prefix and as a suffix of $ u $, without appearing elsewhere within $ u $. This thesis presents a fast and practical $ \mathcal{O}(n \log n) $ time algorithm to compute all $ \mathcal{O}(n^2) $ closed substrings of a string $ w[1..n] $. This is achieved by …
-
Suffix trees and suffix arrays in primary and secondary storage
… To speed up the runtime of these algorithms, suffix trees and suffix arrays are routinely used to generate a set of starting positions quickly and/or narrow down the set of possibilities need to be considered.;The first contribution of this dissertation is a linear time algorithm to sort all …
-
Parameterized Strings: Algorithms and Applications
… By handling the intricacies of the parameterized suffix, we can efficiently address complex applications with data structures also reusable in traditional matching scenarios. In this dissertation, we extend data structures for p-strings (and variants) to address sophisticated string …
-
Suffix Structures and Circular Pattern Problems
The suffix tree is a data structure used to represent all the suffixes in a string. However, a major problem with the suffix tree is its practical space requirement. In this dissertation, we propose an efficient data structure -- the virtual suffix tree (VST) -- which requires less space than other …
-
Searching, clustering and evaluating biological sequences
… to efficiently find approximate seeds using a suffix array index of the sequences. Next, we present DNACLUST; a tool for clustering millions of DNA sequence fragments. Although DNACLUST has been primarily made for clustering 16S ribosomal RNA sequences, it can be used for other tasks, such as …
-
Computing Lyndon Arrays
… et al. showed a linear co-equivalence of sorting suffixes and sorting maximal Lyndon substrings of a string (inspired by a novel suffix sorting algorithm of Baier). In 2016, Franek et al. presented a brief overview of algorithms for com- puting the Lyndon array that encodes the knowledge of …
-
An approximate search engine for structure
… include storing the paths of trees in a suffix array, employing hashing techniques to speed up retrieval, and counting the number of up-down operations to move a token from one node to another node in a tree. Various filters for accelerating a search, different strategies for …
-
Succinct Indexes
… a theorem that characterizes a permutation as a suffix array, based on which we design succinct text indexes. We design a succinct representation of ordinal trees that supports all the navigational operations supported by various succinct tree representations. In addition, this representation …
Page 1 of 2