문자열 차이점 탐지 알고리즘

'블렉스 이야기' 시리즈문자열 차이점 탐지 알고리즘

baealex

소비적인 일보단 생산적인 일을 좋아합니다.

Sign in to view email

깃허브를 사용하면서 단 한 번도 버전관리가 '어떻게' 작동하고 있는지 관심을 가지지 않았다. 그저 "변경된 '무언가'를 감지하겠지"라는 생각 뿐이었다. 그러다 깃처럼 우리의 블로그에도 버전관리를 넣어보면 어떨까 싶었다. 변경된 점을 유지하기 위함이 아니라 다른 사용자가 내 글에 참여할 수 있는 기능을 위해서 말이다. 그러기 위해선 버전관리라는 시스템에 대해서 이해해야했다.


Git, 대체 어떻게 작동하지?

인터넷에 'Git의 원리'라고 검색하면 깃이 어떻게 작동하고 있는지 알려준다. add를 하고 commit을 하고 push를 하면 어떻게 동작하는지 말이다. 내가 궁금한 것은 그런게 아니라 더 깊은 내용이다. 하지만 검색 키워드를 도통 찾을 수 없어 직접 개발해야 할 것 같다. 이 글은 아마 그 작업에 대한 실험과 고찰이 될 것이다. 우선은 문자열을 가지고 장난쳐 봐야겠다.


문자열 변경 감지
old_text = ["안녕하세요, 배준호입니다.", 0]
new_text = ["안녕하세요, 배진오입니다!", 1]

먼저 위와같은 문자열을 두자. 현재는 테스트를 위해서 배열의 첫번째 인덱스엔 문자열을 두번째엔 정수를 넣었지만 실제로는 정수가 들어갈 부분에 시간을 넣어서 비교할 생각이다. 우선 위 문자가 똑같은지 다른지 비교를하자. 달라진 게 없다면 버전을 관리할 필요가 없으니까.

기본적인 방법으로 길이 혹은 사이즈로 구분하면 위 문자열의 경우 변경되었는지 전혀 분간할 수 없으므로 우선 성능이 제일 빠를 것 같은 길이로 먼저 비교한 뒤 집합으로 변경하여 차집합을 구하도록 하였다.

def is_change(old_text, new_text):
    if len(old_text) == len(new_text):
        if len(set(old_text) - set(new_text)) == 0:
            return False
    return True
old_text = ["안녕하세요, 배준호입니다.", 0]
new_text = ["안녕하세요, 배진오입니다!", 1]

print(is_change(old_text[0], new_text[0])) # True
old_text = ["가", 0]
new_text = ["가가가가가", 1]

print(is_change(old_text[0], new_text[0])) # True
old_text = ["가다", 0]
new_text = ["가다", 1]

print(is_change(old_text[0], new_text[0])) # False

의도한 대로 동작한다.

변경된 지점 탐색
  • 가장 쉽게 버전관리 하는 방법 : 위와같이 다르다는게 입증되면 그냥 데이터베이스에 때려박아 놨다가 사용자가 병합하면 합쳐버리고 데이터를 지운다.
    • 용량이 너무 아까움
    • 사용자한테 바뀐 지점 보여주려면 2번 일해야 됨
    • 자바스크립트보단 파이썬으로 하고 싶음

아마도 해당 함수를 만든다면 아래와 같은 입력에서 다음과 같은 출력을 만들고 싶다.

안녕하세요. 배준호입니다.

BLEX는 모두를 위한 블로그 서비스입니다.
언제까지나 무료입니다.

감사합니다. 배준호입니다.
안녕하세요. 배진오입니다.

BLEX는 모두를 위한 블로그 서비스는 맞지만...
부분유료화가 될지도 모르죠?

감사합니다. 배진오입니다.
[
    [0, "준호", "진오"],
    [1, "입니다", "는 맞지만.."]
    [0, "언제까지나 무료입니다.", "부분유료화가 될지도 모르죠?"]
    [1, "준호", "진오"]
]

첫번째 인덱스의 의미는 인덱스다. '배준호'라는 문장은 2번 나오는데 그중에 첫번째 단어라는 의미이다. (이거 보다는 탐색중인 위치를 기록하는게 여러모로 편리할 듯) 두번째 인덱스의 의미는 원문 세번째 인덱스의 의미는 수정문이다. 일단 다음과 같이 탐색하면 되지 않을까?

원문과 변경글을 순차적으로 탐색하다가 다른 지점을 감지한다. 그 순간부터 배열에 차곡차곡 쌓는다. 그리고 다시 같아지는 지점으로 넘어가면 결과 배열에 넣어준다.

def changed_list(old_text, new_text):
    point = 0
    data = {
        'results': list(),
    }

    new_list = {
        'point': int(),
        'old': str(),
        'new': str()
    }
    while True:
        if not old_text[point] == new_text[point]:
            new_list['point'] = point
            new_list['old'] += old_text[point]
            new_list['new'] += new_text[point]
            break
        point += 1
    data['results'].append(new_list)
    return data

# {'results': [{'new': '\xa7', 'old': '\xa4', 'point': 22}]}

만들다가 급작스런 뇌정지가 발생했다. 고려할 점이 너무나 많았다. 특히 글자 갯수가 다른 경우 어디부터 어디까지 구분시킬지 판단할 수가 없었다. 그리고 길이가 다른 경우 다시 같아지는 지점을 찾는 것은 매우 극악이다. 성능도 너무 구려지고... 우선 공통되는 부분을 전체적으로 삭제하는 방식으로 접근하면 어떨까 싶었다.

import re
def remove_common(old_text, new_text):
    old_word_lists = re.split(' |\n', old_text)
    new_word_lists = re.split(' |\n', new_text)
    return {
        'old': set(old_word_lists) - set(new_word_lists),
        'new': set(new_word_lists) - set(old_word_lists), 
    }

for i in remove_common(old_text[0], new_text[0])['new']:
    print(i)
print('-----')
for i in remove_common(old_text[0], new_text[0])['old']:
    print(i)

"""
부분유료화가
될지도
모르죠?
배진오입니다.
맞지만...
서비스는
-----
무료입니다.
서비스입니다.
배준호입니다.
언제까지나
"""

공통 부분을 제거했다. 이제 이 부분을 원문에서 위치를 감지하고 원레 출력하고자 하는 결과물로 출력하고자 하였다. 다만 또 문제는 어떤 부분이 어떤 문자에서 변형된 것인지 알 방도가 없다. 그냥 수정을 허용하는 사용자에게 원문과 수정문을 보여주고 어떤 부분이 변경되었는지 어떤 부분이 추가되었는지 두개의 분활된 화면으로 보여주면 될 것 같다! 역시 난 똑똑해!

데이터 베이스엔 변경되기 전 부분의 [포인트, 문장]과 변경된 후 부분의 [포인트, 문장]을 저장하자. 중복되는 문장은 어떻게 처리하지? 결국 가장 하고 싶지 않았던 방법인 데이터 통째로 때려넣기를 사용해야 할 것 같다. 아... 점점 산으로 가는구나.

변경사항 적용하기

첫번째 인덱스엔 위치가 있고 두번째 인덱스엔 원문이 있으므로 첫번째 인덱스에서 원문의 길이만큼을 변경문으로 변경하면 된다. 다만 길이가 다른 문자열로 변경되면 첫번째 인덱스의 위치의 의미가 무색해진다. 따라서 변경한 지점의 다음 배열들의 첫번째 인덱스의 값을 변경문과 원문의 길이 차이만큼 더해주어야 한다.

baealex
3개월, 1주전

이 길은 내 길이 아니었다...

로그인된 사용자만 댓글을 작성할 수 있습니다.