극대 증가 부분서열을 찾는 선형 알고리즘
Linear-time algorithms for computing a maximal increasing subsequence
4
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최장 증가 부분서열(longest increasing subsequence)은 컴퓨터 과학 분야에서 오랫동안 연구되어온 주요 문제이다. 본 논문에서는 최장 조건을 극대로 완화한 극대 증가 부분서열(maximal increasing subsequence) 문제를 고려한다. 본 논문에서는 두 가지 버전의 증가 개념(단조증가, 순증가)에 대해, 알파벳 에 대한 서열의 극대 증가 부분서열을 구하는 선형시간 알고리즘을 제안한다. 극대 단조증가 부분서열을 구하는 알고리즘은 공간을 사용하고, 극대 순증가 부분서열을 구하는 알고리즘은 공간을 사용한다.
Abstract
The longest increasing subsequence is a fundamental problem which has been studied for a long time in computer science. In this paper, we consider the maximal increasing subsequence problem where the constraint is released from the longest to the maximal. For two kinds of increasing (monotone increasing and strictly increasing), we propose linear-time algorithms computing a maximal increasing subsequence of an input sequence from an alphabet . Our algorithm for computing a maximal monotone increasing subsequence requires space and our algorithm for computing a maximal strictly increasing subsequence requires space.
참고문헌 (16)
- C. Schensted, "Longest increasing and decreasing subsequences", Canadian Journal of Mathematics, 13, pp.179~191 (1961)
- 이인복, "Mining Regular Expression Rules based on q-grams", 스마트미디어저널, 8(3), pp.17~22 (2019), (사)한국스마트미디어학회[DOI]
- M. L. Fredman, "On computing the length of longest increasing subsequences", Discrete Mathematics, 11(1), pp.29~35 (1975)
- J.W. Hunt, "A fast algorithm for computing longest common subsequences", Communications of ACM, 20(5), pp.350~353 (1977)
- D. Aldous, "Longest increasing subsequences : from patience sorting to the Baik-Deift-Johansson theorem", Bulletin of the American Mathematical Society, 36(4), pp.413~432 (1999)
- M. Crochemore, "Fast computation of longest increasing subsequences and application", Information and computation, 208(9), pp.1054~1059 (2010)
- D. Gusfield, "Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology" (1997), Cambridge University Press
- 이인복, "k개의 오차를 허용하는 순위 패턴 매칭", 스마트미디어저널, 9(2), pp.33~38 (2020), (사)한국스마트미디어학회[DOI]
- 박승현, "한글 편집거리 알고리즘을 이용한 한국어 철자오류 교정방법", 스마트미디어저널, 6(1), pp.16~21 (2017), (사)한국스마트미디어학회
- R.A. Wagner, "The string-to-string correction problem", Journal of the ACM, 21(1), pp.168~173 (1974)
- I.-H. Yang, "A fast algorithm for computing a longest common increasing subsequence", Information Processing Letters, 93(5), pp.249~253 (2005)
- A. Agrawal, "A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem", Proc. of International Symposium on Algorithms and Computation (ISAAC), 4 (2020)
- Y. Sakai, "Maximal common subsequence algorithms", Theoretical Computer Science, 793, pp.132~139 (2019)
- 이동엽, "유사도 측정에 대한 극대 공통 부분 서열의 효용성", 한국차세대컴퓨팅학회 논문지, 18(3), pp.53~61 (2022), 한국차세대컴퓨팅학회[DOI]
- 이동엽, "더 긴 극대 공통 부분 서열을 찾기 위한 알고리즘", 정보과학회논문지, 49(7), pp.507~513 (2022), 한국정보과학회[DOI]
- M.J. Atallah, "An Efficient Algorithm for Maxdominance, with Applications", Algorithmica, 4, pp.221~236 (1989)