이번에 살펴볼 예제는 찢어진 문서의 파편들이 주어졌을 때에 어떻게 original 문서로 복원하는가에 대한 이야기입니다. 각 파편들은 문장 또는 단락의 일부분을 가지고 있는데요, 우리가 조립할 방법은 현재 파편들 중에서 가장 overlap이 많이 되는 두 파편을 골라서 합치고, 또 다시 가장 overlap이 많이 되는 두 파편을 찾고, …, 이런식으로 하나의 문서가 될 때까지 합쳐나가는 방법입니다.
예를들면, ['all is well', 'ell that en', 'hat end', 't ends well']
이런 4개의 파편이 주어졌을 때, 가장 많이 overlap되는 ‘ell that en’과 ‘hat end’를 합쳐서 ['all is well', 't ends well', 'ell that end']이 되고,
다시 또 합쳐서 ['all is well', 'ell that ends well']이 되고,
마지막으로 ['all is well that ends well']의 복원된 문서를 갖게 되는 것입니다.
먼저 우리가 예제로 사용할 4가지 input입니다. 파일1, 파일2, 파일3, 파일4
이 input들은 {}로 한 파편이 정의되고 있습니다. 따라서 우리는 이를 먼저 string의 list로 바꾸는 함수를 만들어서 우리가 다루기 편하게 변환하겠습니다.
def parseInput(string):
result = [] #각 파편들을 담을 list
for ch in string:
if ch == '{': #'{'는 새 파편이 시작되었음을 알리는 것입니다.
element = ""
elif ch == '}': #'}'는 현재 파편이 끝났음을 알리는 것입니다.
result.append(element) #따라서 list에 추가해줍니다.
else:
element += ch #그렇지 않으면 계속 파편의 글자들을 붙여나갑니다.
return result
>>> test_input1 = parseInput("""{all is well}
{ell that en}
{hat end}
{t ends well}""")
>>> print test_input1
['all is well', 'ell that en', 'hat end', 't ends well']Input을 잘 쪼개고 있음을 확인하실 수 있죠? :) 그럼 이제 어떻게 두 파편의 overlap을 찾을 수 있을까요?
Overlap이 되는 경우는 다음과 같은 세 가지 중의 하나입니다.
- 하나가 다른 하나에 완전히 포함될 수 있을 때
- 파편 A가 파편 B의 왼쪽에서 overlap될 때
- 파편 A가 파편 B의 오른쪽에서 overlap될 때
이를 바탕으로 최대 overlap이 되는 문자 수와 overlap시켜 붙인 문자를 리턴하는 함수를 짜볼 수 있습니다.
def overlap(str1, str2):
if len(str1)<=len(str2):
shortstr = str1
longstr = str2
else:
shortstr = str2
longstr = str1
#짧은 문자열이 긴 문자열에 속하는 경우
if shortstr in longstr:
return len(shortstr), longstr
for i in range(len(shortstr)-1, 0, -1):
#짧은 문자열이 긴 문자열의 왼쪽에서 overlap되는 경우
if shortstr[-i:]==longstr[:i]:
return i, shortstr + longstr[i:]
#짧은 문자열이 긴 문자열의 오른쪽에서 overlap되는 경우
if longstr[-i:]==shortstr[:i]:
return i, longstr + shortstr[i:]
#여기까지 왔다는 것은 overlap이 없다는 것입니다.
return 0, str1 + str2
>>> print overlap('abcde', 'bcd')
(3, 'abcde')
>>> print overlap('abc', 'bcd')
(2, 'abcd')함수가 잘 동작하는 것 같네요 :) 그럼 이제 이 overlap함수를 바탕으로 우리가 최종적으로 모든 파편들을 모아 맞추는 reassemble함수를 구현해 보겠습니다.
def reassemble(strings, verbose=False):
# 문자열이 최종적인 하나가 남을때까지 두개씩 비교하여 maximum overlap을 갖는 쌍을 합쳐서 하나씩 줄여나갑니다.
while len(strings)>=2:
if verbose:
print strings
max_overlap = -1
max_str = ""
max_i, max_j = None, None
for i in range(len(strings)-1):
for j in range(i+1, len(strings)):
ov, mstr = overlap(strings[i], strings[j])
if ov > max_overlap:
max_overlap = ov
max_str = mstr
max_i = i
max_j = j
strings.pop(max_j)
strings.pop(max_i)
strings.append(max_str)
return strings그럼 결과를 확인해 보면,
#파일1의 input에 대한 결과
>>> reassemble(allswell_frags, verbose=True)
['all is well', 'ell that en', 'hat end', 't ends well']
['all is well', 't ends well', 'ell that end']
['all is well', 'ell that ends well']
['all is well that ends well']
#파일2의 input에 대한 결과
>>> reassemble(hymm_frags)
['Where the rolling foothills rise\nUp towards mountains higher,\nWhere at eve the Coast Range lies\nIn the sunset fire,\nFlushing deep and paling,\nHere we raise our voices hailing\nThee, our Alma Mater.\nFrom the foothills to the bay\nIt shall ring,\nAs we sing,\nIt shall ring and float away.\nHail, Stanford, Hail!\nHail, Stanford, Hail!']
#파일3의 input에 대한 결과
>>> reassemble(preamble_frags)
['We the People of the United States, in Order to form a more perfect\nUnion, establish Justice, insure domestic Tranquility, provide for the\ncommon defence, promote the general Welfare, and secure the Blessings of\nLiberty to ourselves and our Posterity, do ordain and establish this\nConstitution for the United States of America.']
#파일4의 input에 대한 결과
>>> reassemble(row_frags)
['Row, row, row your boat,\nGently down the stream.\nMerrily, merrily, merrily, merrily,\nLife is but a dream.']이것은 비단 문서 복원뿐 아니라, DNA Sequencing에서도 많이 사용되는 알고리즘이니 잘 파악해 두시면 좋을 것 같습니다 :)