본문 바로가기
Computer/Etc

LCS, longest common subsequence vs longest common substring

by hexists 2014. 12. 9.
  • 여기에서는 두가지를 다룬다.
    • longest common subsequence
    • longest common substring
    • 두 개념의 약어는 모두 LCS... 이다.
      • 두 개념이 헷갈릴 수 있어서... 같이 정리해본다.
  • longest common subsequence
    • 한국어로는 최장 공통 부분 수열이라고 한다.
    • 최장 공통 부분 수열은? 두 문자열에 공통적으로 존재하는 가장 긴 부분 수열이다.
      • 여기서 주목할 점은 부분 수열이니 연속된 것이 아니라는 점이다.
    • 예제를 들어 설명해본다.

      1. 두개의 문자열이 있다.
      : bcdb, abcbdab
       
      2. 두 문자열의 최장 공통 부분 수열을 구해본다.
      그림으로 표시해보면...
       
       bc d b
      abcbdab
       
      3. 위에 보면 공통으로 존재하는 부분 수열이 {b,c,d,b}가 된다.
    • 아주 간단해보인다.

      • 하지만, 이 알고리즘은 diff 알고리즘의 근간이 된다.
        • 그만큼 중요한 알고리즘이며, 그리고... 문제를 풀때는... 간단하지도 않다. 
    • 문제를 푸는 방법
      • 식으로 정리하면

      • 최장 공통 부분 수열과 관련된 알고리즘으로는... '최장 공통 부분 수열의 길이를 구하는 로직'이다.

        예전에 풀었던 문제중 최장 공통 수열의 길이를 구하는 문제에 대한 알고리즘이다.
        1. len(a) + 1 x len(b) +1 table을 생성한다.
        2. lcs_tbl[i,j] 값은 1) a[i] == b[j] 을 때는 lcs_tbl[i-1][j-1] + 1
                             2) a[i] != b[j] 아닐 때는 lcs_tbl[i-1, j] 또는 lcs_tbl[i, j-1] 중에서 큰 값을 저장한다.
                                 * 이는 공통 문자의 경우 수열의 길이가 증가함을 의미하고
                                   공통 문자가 아닐 경우에는 이전 결과 중 공통 부분 수열이 긴 것을 가져오는 것을 의미한다.
        3. 이렇게 했을 때, lcs[len(a) + 1][len(b) + 1]의 값이 최장 공통 부분 수열의 크기이다.
        4. 문제의 조건에 따라 최장 공통 부분 수열 중 하나를 출력하기 위해서는 마지막 부터 backtracking 해서 값을 구한다.
      • 테이블을 만든다. 아래처럼... 위 식을 참고해서...(이 부분은 나중에 시간나면 정리하는 것으로...한다)

         
        0
        a
        b
        c
        b
        d
        a
        b
        0ØØØØØØØØ
        bØØbbbbbb
        cØ       
        dØ       
        bØ       
    • 참고 링크 : http://ko.wikipedia.org/wiki/최장_공통_부분_수열

 

  • longest common substring

  • 사설...
    • 문제를 어떻게 풀 수 있는지... 그리고 suffix tree를 어떤 형태로 구현하고, 또 사용할 수 있는지에 대해서도 정리하고 싶었지만... 시간 관계상 이정도 선에서 마무리한다.
    • 다음에 기회가 된다면, 좀 더 정리할 것이다.

본 글은 회사 위키에 작성한 글과 동일합니다.


'Computer > Etc' 카테고리의 다른 글

github gist  (0) 2015.01.03
Loop Invariant  (0) 2015.01.01
Excel에서 조건부 수식을 사용해서 줄단위 색 입히기  (0) 2014.12.05
long-tail vs short head  (0) 2014.12.03
svn에서 다른 리비전간에 diff 하기  (0) 2014.11.25