[알고리즘] 스트링 편집 거리 문제

 편집 거리(edit distance)는 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도로, 철자 검사기에서 잘못된 철자를 만나면 해당 철자와 가장 근접한 다른 단어를 찾아주는 데 활용된다.

일반적으로 편집 거리는 두 문자열 사이에 편집이 필요할수록 커지는 구조이다.

 

 

---

예제 1

x='baa'와 y='aab'가 주어졌을 때 x와 y의 편집 거리를 구하시오.

단, ins=del=1, chg=2

 

 

예제 2

x='SNOWY'와 y='SUNNY'가 주어졌을 때 x와 y의 편집 거리를 구하시오.

단, ins=del=1, chg=2

 

 

---

스트링 편집 거리 알고리즘

function solution(x, y, ins, del, chg){
    const [row, col] = [x.length, y.length];
    let answer = new Array(row+1);
    for(let i=0; i<=row; i++) answer[i]=new Array(col+1);

    answer[0][0] = 0;
    for(let i=1; i<=row; i++) answer[i][0] = i;
    for(let j=1; j<=col; j++) answer[0][j] = j;
    // for(let i=1; i<=row; i++) answer[i][0] = answer[i-1][0]+del;
    // for(let j=1; j<=col; j++) answer[0][j] = answer[0][j-1]+ins;

    for(let i=1; i<=row; i++){
        for(let j=1; j<=col; j++){
            let c = x[i-1] === y[j-1] ? 0 : chg;
            let min = [answer[i-1][j]+del, answer[i][j-1]+ins, answer[i-1][j-1]+c]
            answer[i][j] = Math.min(...min);
        }
    }
    return answer[row][col];
}
console.log(solution('baa', 'aab', 1, 1, 2));
console.log(solution('SNOWY', 'SUNNY', 1, 1, 2));

 

편집 거리 테이블 만들기

const [row, col] = [x.length, y.length];
let answer = new Array(row+1);
for(let i=0; i<=row; i++) answer[i]=new Array(col+1);

x.length=1, y.length+1 크기만큼의 2차원 배열을 만듭니다.

 

 

첫 번째 열과 행의 값을 넣어주기

answer[0][0] = 0;
for(let i=1; i<=row; i++) answer[i][0] = i;
for(let j=1; j<=col; j++) answer[0][j] = j;
// for(let i=1; i<=row; i++) answer[i][0] = answer[i-1][0]+del;
// for(let j=1; j<=col; j++) answer[0][j] = answer[0][j-1]+ins;

예제 1일 경우 아래와 같이 만들어 주기 위한 과정입니다.

		a	a	b
	0	1	2	3
b	1
a	2
a	3

 

answer 2차원 배열에 각 위치에 알맞은 편집 거리 값 넣기

for(let i=1; i<=row; i++){
    for(let j=1; j<=col; j++){
        let c = x[i-1] === y[j-1] ? 0 : chg;
        let min = [answer[i-1][j]+del, answer[i][j-1]+ins, answer[i-1][j-1]+c]
        answer[i][j] = Math.min(...min);
    }
}

return answer[row][col];

c : 특정 위치의 x문자열의 문자, y문자열의 문자가 같다면 0, 아니면 chg

i-1, j-1을 넣은 이유는 i, j가 1부터 시작해서, x[i], j[j] 넣으면 x[0], j[0]값을 비교할 수 없기 때문에

 

min : del값, ins값, chg값을 변수로 담아주었습니다.

그리고 min에서 최솟값을 구하고 그 값을 answer[i][j]로 넣어주었습니다.