Title page for etd-0023117-160730


[Back to Results | New Search]

URN etd-0023117-160730
Author Wen-chuan Ho
Author's Email Address No Public.
Statistics This thesis had been viewed 5350 times. Download 4 times.
Department Computer Science and Engineering
Year 2016
Semester 1
Degree Master
Type of Document
Language English
Title A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet
Date of Defense 2017-01-16
Page Count 89
Keyword
  • Small alphabet
  • Dynamic Programming
  • Similar
  • CLCS
  • LCS
  • Abstract Given three sequences A, B and C with lengths of m, n and r, respectively,
    the constrained longest common subsequence (CLCS) problem is to fi
    nd the LCS of
    A and B which contains C as the subsequence of the answer. The dynamic program-
    ming (DP) for solving CLCS, proposed by Chin et al., calculates two-dimensional
    lattices layer by layer. We
    find that the values of most corresponding CLCS lattice
    cells are identical in two consecutive layers when |∑| is small, where |∑| denotes the
    alphabet size. In this thesis, we clarify which lattice cells need to be calculated, and
    which lattices need not be calculated, since the calculation is redundant if two cells
    are equal in two consecutive layers. Accordingly, our algorithm calculates only some
    special boundary cells, instead of the whole 3-dimensional lattice in most cases. Our
    algorithm still requires O(mnr) time and O(mn) space to solve the CLCS problem
    in the worst case. In 2010, Deorowicz and Obstoj showed that the algorithm of Chin
    et al. has good performance when |∑| ≤ 20. As our experimental results show, our
    algorithm is faster than Chin's algorithm when |∑| ≤ 20. So our algorithm is better
    than most of the previous CLCS algorithms when |∑| is small.
    Advisory Committee
  • Yi-Hsing Chang - chair
  • Hsing-Yen Ann - co-chair
  • Kuo-Tsung Tseng - co-chair
  • Kuo-Si Huang - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0023117-160730.pdf
  • Indicate in-campus at 0 year and off-campus access at 3 year.
    Date of Submission 2017-02-07

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys