[algorithm] edit distance and longest common substring

edit distance

• edit distance 설명

  • 약간 코드의 오류가 있지만 가장 좋은 설명
  • src -> dst transform 한다고 가정
  • empty symbol까지 포함한 matrix 세팅
    • (N+1)x(M+1) matrix
  • initialize
    • up most, left most 초기화
      • 오른쪽은 src에 insert, 아래쪽은 src에서 delete 비용
    • i,j index for loop 돌면서
      • 현재 문자 비교해서
        • 같으면, 대각선 값으로 세팅
        • 다르면 min(왼쪽, 대각선, 위쪽) + 1 세팅
  • back tracking
    • (N, M) 위치에서 시작
    • s = min(왼쪽, 대각선, 위쪽)
    • s가 현재와 같으면 대각선 방향
      • 아무 연산 없음
    • s가 현재보다 작다면
      • s가 왼쪽
        • dst char insert
      • s가 위쪽
        • src char delete
      • s가 대각선
        • src char -> dst char replace
    • back tracking 결과를 뒤집어서, empty symbol에 대해 그대로 적용하면 dst 문자열이 생성됨

• sample code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b, int c)
{
    int m;
    if( a < b ) m = a;
    else m = b;
    if( c < m ) m = c;
    return m;
}

int edit_distance(char* src, char* dst)
{
    int n,m,i,j;
    int** matrix;
    int distance;

    n = strlen(src) + 1; // with start symbol
    m = strlen(dst) + 1; // with start symbol

    // create matrix
    matrix = (int**)malloc(n * sizeof(int*));
    for( i = 0; i < n; i++ ) {
        matrix[i] = (int*)malloc(m * sizeof(int));
    }

    // initialize matrix
    for( i = 0; i < n; i++ ) {
        matrix[i][0] = i;
    }
    for( j = 0; j < m; j++ ) {
        matrix[0][j] = j;
    }

    // compute distance matrix
    for( i = 1; i < n; i++ ) {
        for( j = 1; j < m; j++ ) {
            if( src[i] == dst[j] ) {
                matrix[i][j] = matrix[i-1][j-1];
            } else {
                matrix[i][j] = min(matrix[i][j-1], matrix[i-1][j-1], matrix[i-1][j]) + 1;
            }
        }
    }

    distance = matrix[n-1][m-1];

    // destroy matrix
    for( i = 0; i < n; i++ ) {
        free(matrix[i]);
    }
    free(matrix);

    return distance;
}

int main(int argc, char** argv)
{
    char* src = "azced";
    char* dst = "abcdef";
    int distance;

    distance = edit_distance(src, dst);

    fprintf(stdout, "distance(%s, %s) = %d\n", src, dst, distance);

    return 0;
}

longest common substring

• longest common substring은 두개의 문자열 A(n), B(m)가 주어졌을 때, 가장 긴 공통 부분 문자열의 길이를 알아내거나, 그 문자열을 알아내는 문제로 볼 수 있다.
  • 이 문제를 brute force 방법으로 해결하려면, 간단하게 A의 모든 부분 문자열을 구하고, 각각의 부분문자열에 대해서 B에 존재하는 지 체크하면서, 가장 긴 부분문자열을 저장해두는 방식일 것이다.
    • time complexity : O(n^2 * m)
  • 스마트하게 문제를 해결하는 방법을 생각해보자.
  • edit distance에서 사용했던 distance matrix 기법을 응용해 볼 수 있다.
    • matrix[i][j]를 현재 공통 부분문자열 길이라고 가정하자. 그러면 matrix[i+1][j+1]은 둘 중 하나다.
    • A[i+1] = B[j+1]인 경우, matrix[i+1][j+1] = matrix[i][j] + 1
    • A[i+1] != B[j+1]인 경우, matrix[i+1][j+1] = 0
    • matrix에 값을 채우면서, 최대값 혹은 해당 i값을 기억해두면 된다.
    • time complexity : O(n * m)
    • space complexity : O(n * m)
  • sample code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* compute_lcs(char* A, char* B)
{
    int n,m,i,j;
    int** matrix;

    int max;
    int max_i;
    char* lcs = NULL;

    n = strlen(A) + 1; // with start symbol
    m = strlen(B) + 1; // with start symbol

    // create matrix
    matrix = (int**)malloc(n * sizeof(int*));
    for( i = 0; i < n; i++ ) {
        matrix[i] = (int*)malloc(m * sizeof(int));
    }

    // initialize matrix
    for( i = 0; i < n; i++ ) {
        matrix[i][0] = 0;
    }
    for( j = 0; j < m; j++ ) {
        matrix[0][j] = 0;
    }

    // compute lcs matrix
    max = 0;
    max_i = 0;
    for( i = 1; i < n; i++ ) {
        for( j = 1; j < m; j++ ) {
            if( A[i] == B[j] ) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
                if( max < matrix[i][j] ) {
                    max = matrix[i][j];
                    max_i = i;
                }
            } else {
                matrix[i][j] = 0;
            }
        }
    }

    // get lcs
    if( max == 0 ) {
        lcs = NULL;
    } else {
        lcs = (char*)malloc(max + 1); // max + 1
        memcpy(lcs, &A[max_i - max + 1], max);
        lcs[max] = '\0';
    }

    // destroy matrix
    for( i = 0; i < n; i++ ) {
        free(matrix[i]);
    }
    free(matrix);

    return lcs;
}

int main(int argc, char** argv)
{
    char* A = "abcdefg";
    //char* A = "1234567";
    //char* A = "";
    char* B = "xzubcdkko";
    char* lcs;

    lcs = compute_lcs(A, B);

    fprintf(stdout, "lcs(%s, %s) = %s\n", A, B, lcs);

    if( lcs ) free(lcs);

    return 0;
}

• 별도의 추가 공간 없이 문제를 해결할 수 있을까? for loop 두번으로도 처리가 가능하다.

for i in n :
  k = i
  for j in m :
    if k < n and A[k] == B[j] :
      count += 1
      k += 1
    else :
      k = i
    longest = max(longest, count)

• sample code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* compute_lcs(char* A, char* B)
{
    int n,m;
    int i,j,k;

    int count;
    int max;
    int max_i;
    char* lcs = NULL;

    n = strlen(A);
    m = strlen(B);

    max = 0;
    max_i = 0;
    // compute max, max_i
    for( i = 0; i < n; i++ ) {
        k = i;
        count = 0;
        for( j = 0; j < m; j++ ) {
            if( k < n && A[k] == B[j] ) {
                count += 1;
                if( max < count ) {
                    max = count;
                    max_i = k;
                    fprintf(stderr, "A[%d] = %c, B[%d] = %c\n", k, A[k], j, B[j]);
                }
                k += 1;
            } else {
                k = i;
                count = 0;
            }
        }
    }

    fprintf(stderr, "max, max_i = %d, %d\n", max, max_i);

    // get lcs
    if( max == 0 ) {
        lcs = NULL;
    } else {
        lcs = (char*)malloc(max + 1); // max + 1
        memcpy(lcs, &A[max_i - max + 1], max);
        lcs[max] = '\0';
    }

    return lcs;
}

int main(int argc, char** argv)
{
    char* A = "abcdefg";
    //char* A = "1234567";
    //char* A = "";
    char* B = "xzubcdkko";
    char* lcs;

    lcs = compute_lcs(A, B);

    fprintf(stdout, "lcs(%s, %s) = %s\n", A, B, lcs);

    if( lcs ) free(lcs);

    return 0;
}

A[1] = b, B[3] = b
A[2] = c, B[4] = c
A[3] = d, B[5] = d
max, max_i = 3, 3
lcs(abcdefg, xzubcdkko) = bcd