리처드 카프

기타 업적

래빈-카프 알고리듬

카프가 만든 알고리듬 중에는 문자열 찾기 알고리듬도 유명하다. 프로그래밍 작업뿐만 아니라 일반 문서 작업에서도 단어 찾기는 자주 사용된다.

어떤 글에서 단어를 찾는 가장 단순무식한^brute-force 방법은 처음부터 계속 한 글자씩 뒤져나가는 것이다. 다음의 예를 보자.

우리의 소원은 통일. 꿈에도 소원은 통일. 이 정성 다해서 통일. 통일을 이루자. 이 겨레 살리는 통일. 이 나라 살리는 통일. 통일이여 어서오라. 통일이여 오라. 

위와 같은 글에서 ‘통일’이라는 단어를 찾아야 한다고 해보자. 그러면 맨 처음 글자 ‘우’에서부터 시작해서 두 글자씩 뽑아 비교해보면 된다. 만약 ‘통일이여 오라’를 찾아야 한다고 하면 역시 맨 처음 글자 ‘우’에서부터 시작해서 일곱 글자씩 뽑아 비교해보면 된다.

위의 글이 총 91글자로 이루어져 있으므로, ‘통일’을 찾을 때는 90번 비교가 이루어져야 하고 ‘통일이여 오라’를 찾을 때는 84번 비교가 이루어져야 한다. 글자 단위의 비교 회수를 따져 본다면 ‘통일’일 때는 90 x 2 번, ‘통일이여 오라’일 때는 84 x 7 번 비교가 발생한다. 결국 글자 단위의 비교 회수는 글의 길이와 찾으려는 단어의 길이에 함께 비례하는 것을 볼 수 있다. 짧은 글이라면 모르겠으나 백과사전처럼 글의 양이 많다면 단어 하나를 찾는 시간이 엄청나게 길 수 있다.

마이클 래빈과 리처드 카프는 지문^fingerprint 이라는 개념을 도입했다. 비교해야 할 데이터의 크기를 줄이는 것이다. 지문 함수^{fingerprinting function}라는 것을 만들어서 원문과 찾는 단어의 크기를 줄인다. 예를 들어 일곱 글자를 네 글자로 줄이는 지문 함수를 만들었다고 해보자. 이것을 위의 예에 적용한다면 ‘통일이여 오라’를 찾을 때 ‘갺녂됶듂’이라는 지문 값으로 바뀌어 사용되고 글 내에서도 ‘우리의 소원은 ‘, ‘리의 소원은 통’, ‘의 소원은 통일’ 등이 모두 네 자리의 지문 값으로 바뀐 후에 비교가 이루어진다.

지문 함수는 데이터의 크기를 줄이는 것이기 때문에, 서로 다른 데이터가 같은 지문을 가질 가능성이 발생한다. 그래서 지문의 비교는, 일종의 필터링 용도로 사용된다. 즉 지문이 다르면, 확실하게 다른 단어라고 보고 무시해 버리지만, 지문이 같다면 확실하게 판별하기 위해서 지문이 아니라 원래의 데이터로 다시 비교를 진행한다.

생명공학

1994년에 버클리의 교수직에서 물러난 그는 워싱턴 대학교에 자리를 구하면서 생명공학이라는 새로운 분야에 도전했다.

내가 워싱턴 대학교를 선택한 이유는 계산생물학^{computational biology}에 관심이 생겼기 때문이었습니다. 1990년대 초에 인간 게놈 프로젝트가 박차를 가하고 있었고 생물학이 다음 세대의 가장 중요한 과학이 되리라는 분위기가 형성되고 있었습니다. 그리고 나는 생물학과 관련된 조합 알고리듬에 큰 기회가 숨어 있다는 느낌이 들었습니다.^​3​

안타깝게도 카프는 계산생물학에서 의미 있는 성과를 내지 못했다. 하지만 그와 함께 연구했던 많은 후배 연구자들이 이 분야에서 중요한 역할을 하고 있다.^​2​

(c) 이재범, 2023
이 콘텐츠는 대한민국 저작권법의 보호를 받습니다. 작성된 모든 내용의 권리는 저자에게 있으며, 저자의 동의 없는 사용은 금합니다. 본 콘텐츠의 일부 혹은 전체 내용을 무단으로 전재/복제/배포하거나 2차적 저작물로 재편집하는 경우, 법적 책임을 지게 됩니다.

1 2 3 4