Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Small alphabet). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


NSYSU

1. Ho, Wen-chuan. A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet.

Degree: Master, Computer Science and Engineering, 2017, NSYSU

Given three sequences A, B and C with lengths of m, n and r, respectively, the constrained longest common subsequence (CLCS) problem is to find 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. Advisors/Committee Members: Kuo-Tsung Tseng (chair), Kuo-Si Huang (chair), Hsing-Yen Ann (chair), Chang-Biau Yang (committee member), Yi-Hsing Chang (chair).

Subjects/Keywords: Small alphabet; Dynamic Programming; Similar; CLCS; LCS

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Ho, W. (2017). A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet. (Thesis). NSYSU. Retrieved from http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0023117-160730

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Ho, Wen-chuan. “A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet.” 2017. Thesis, NSYSU. Accessed November 14, 2019. http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0023117-160730.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Ho, Wen-chuan. “A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet.” 2017. Web. 14 Nov 2019.

Vancouver:

Ho W. A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet. [Internet] [Thesis]. NSYSU; 2017. [cited 2019 Nov 14]. Available from: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0023117-160730.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Ho W. A Fast Algorithm for the Constrained Longest Common Subsequence Problem with Small Alphabet. [Thesis]. NSYSU; 2017. Available from: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0023117-160730

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.