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"”.

  1. 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. …

    wvu Repository record for Direct suffix sorting and its applications (opens in a new tab)

  2. 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 …

    colostate Repository record for Space efficient string search algorithms and data structures (opens in a new tab)

  3. 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 …

    mcmaster Repository record for USING SUFFIX ARRAYS FOR LEMPEL-ZIV DATA COMPRESSION (opens in a new tab)

  4. 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 …

    mcmaster Repository record for Implementing Efficient Algorithms for Computing Runs (opens in a new tab)

  5. 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 …

    ucf Repository record for Efficient String Algorithms with Applications in Bioinformatics (opens in a new tab)

  6. 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 …

    lsu-thes Repository record for Efficient Substring Discovery Using Suffix, LCP Array and Algorithm-Architecture Interaction (opens in a new tab)

  7. 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 …

    gatech Repository record for Parallel and scalable combinatorial string algorithms on distributed memory systems (opens in a new tab)

  8. 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, …

    concordia Download PDF for Enhanced Suffix Trees for Very Large DNA Sequences (opens in a new tab)

  9. 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; …

    mcmaster Repository record for Performance comparisons of various runs algorithms (opens in a new tab)

  10. 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 …

    wvu Repository record for Parameterized Strings: Algorithms and Data Structures (opens in a new tab)

  11. 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.

    calpoly Repository record for Optimizing Lempel-Ziv Factorization for the GPU Architecture (opens in a new tab)

  12. 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 …

    unf Repository record for Approximate String Matching With Dynamic Programming and Suffix Trees (opens in a new tab) Download PDF for Approximate String Matching With Dynamic Programming and Suffix Trees (opens in a new tab)

  13. 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 …

    mcmaster Repository record for EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS (opens in a new tab)

  14. 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 …

    iastate Repository record for Suffix trees and suffix arrays in primary and secondary storage (opens in a new tab)

  15. 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 …

    wvu Repository record for Parameterized Strings: Algorithms and Applications (opens in a new tab)

  16. 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 …

    wvu Repository record for Suffix Structures and Circular Pattern Problems (opens in a new tab)

  17. 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 …

    maryland Repository record for Searching, clustering and evaluating biological sequences (opens in a new tab)

  18. 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 …

    mcmaster Repository record for Computing Lyndon Arrays (opens in a new tab)

  19. 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 …

    njit Repository record for An approximate search engine for structure (opens in a new tab)

  20. 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 …

    waterloo Repository record for Succinct Indexes (opens in a new tab)

Page 1 of 2