◈ 이 책의 대상 독자 ◈
자료 구조와 알고리듬에 관한 대학원 수업을 가르치는 교수자는 수강생을 위해 이 책의 원하는 부분을 어디든지 선택할 수 있다. 하지만 기초 교재는 아니며, 연구원, 박사과정 또는 석사과정 대학원생과 문자열 알고리듬에 직접적인 연관이 없더라도 알고리듬 수업을 강의해야 하는 학자들을 위한 참고자료로 집필했다. 이 책은 이 분야의 표준 교재에 대한 참고자료라고 생각해야 한다. 문제에 포함된 설명은 이 주제에 대한 깊은 배경지식을 요구하지 않고 그 이해와 해법에 대한 빠른 접근을 제공한다.
◈ 이 책의 구성 ◈
이 책은 7개의 장으로 구성된다.
1장, ‘문자열학의 기초’는 다음 장을 위한 용어, 기본 개념, 기본 도구를 소개하며 준비하는 장으로, 이 분야의 여섯 가지 큰 줄기를 반영한다.
2장, ‘조합론적 퍼즐’은 단어에 대한 조합 문제에 대한 장으로, 많은 알고리듬이 그 입력의 조합론적 성질에 기반하기 때문에 중요한 주제다.
3장, ‘패턴 찾기’에서는 가장 고전적인 주제인 문서 탐색과 문자열 일치를 다룬다.
4장, ‘효율적 자료 구조’는 문서 색인을 위한 자료 구조에 대해 다룬다. 이 자료 구조는 문서와 관련된 특수한 배열이나 나무와 같은 여러 알고리듬에서 기본적 도구로 사용한다.
5장, ‘단어의 정규성’에서는 단어에서 나타나는 정규성, 특히 반복과 대칭성에 대해 다루며, 알고리듬의 효율성에 큰 영향을 준다.
6장, ‘문자열 압축’은 무손실 문서 압축에서 실질적으로 중요한 영역의 몇 가지 기법을 주로 다룬다.
7장, ‘그 외의 다양한 알고리듬’은 이전 장에 어울리진 않지만, 확실히 알릴 가치가 있는 다양한 문제를 소개한다.
◈ 옮긴이의 말 ◈
컴퓨터는 대량의 자료를 자동으로 처리하기에 적합한 장치이며 처리할 수 있는 자료는 본질적으로 문자열, 또는 수열이다. 문자열이란 말 그대로 문자를 늘어놓은 것으로, 인류가 만들어낸 모든 정보는 문자열이다. 예를 들면 우리가 흔히 접하는 신문 기사, 소설과 같이 자연어로 이뤄진 것이 있고, 컴퓨터에 작업을 지시하기 위해 정해진 규칙에 의해 만들어진 프로그램 코드와 같은 인공어가 있다. 이외에도 유전 정보를 담고 있는 DNA 서열, 단백질을 구성하는 아미노산 순서, 음악을 표현하는 음표의 길이와 순서 등 생각보다 다양한 곳에 문자열이 숨어 있다.
이와 같은 문자열을 컴퓨터를 사용해 다루려면 문자열에 숨어 있는 패턴을 탐구해 그 특성에 맞는 알고리듬을 사용할 필요가 있다. 최근에는 컴퓨터 성능의 개선과 인공지능의 발달로 문자열 처리를 알고리듬 수준에서 다뤄야 할 필요성이 줄어들었다고 생각할 수도 있겠지만, 컴퓨터가 다뤄야 하는 자료가 문자열로 돼 있는 한 문자열 알고리듬의 중요성은 결코 줄지 않는다. 특히 컴퓨터의 발달에 힘입어 아무리 머신러닝을 통해 임의의 문자열을 처리할 수 있다고 하더라도, 주어진 문자열을 목적에 적합하게 처리하는 알고리듬이 존재한다면 그 알고리듬을 사용하는 편이 더 효율적인 경우가 많다. 따라서 문자열 알고리듬을 공부하고 연구하는 것은 인공지능의 시대에도 여전히 중요한 문제다.
이 책에서는 컴퓨터를 사용해 문자열을 다루기 위해 필요한 기본 지식부터 패턴 매칭, 문자열 압축과 같은 고급 알고리듬에 이르는 다양한 기법을 구체적인 문제를 통해 살펴보고 있다. 이 책에서 다루는 문제는 앞서 언급한 자연어나 인공어의 처리, 유전 정보 해석, 음악 분석 등에서 널리 사용되는 알고리듬과 관련이 있다. 관심 있는 독자라면 각 알고리듬이 어디에서 쓰이고 있는지 눈치챌 수 있을 것이다. 독자는 이 책에서 제시하는 문제를 하나씩 해결하면서 지적인 즐거움을 얻을 수 있고, 더 나아가 새로운 문자열 처리 알고리듬을 발견할 수 있을지도 모른다. 더 자세한 내용에 대해서는 참고문헌을 찾아서 공부해보는 방법도 좋을 것이다.
개인적으로는 이 책을 번역하면서 컴퓨터 과학의 본질적인 흥미를 다시 느낄 수 있었다. 가령 압축 알고리듬으로 쓰이는 LZW 알고리듬이나 RLE 알고리듬을 수업 시간에 배울 땐 별다른 감흥이 없었다. 하지만 이 책을 번역하면서 기초 개념부터 다시 한번 살펴본 바로는 이러한 알고리듬을 개발하기 위해 고민을 거듭했던 무수한 선배 과학자의 노력이 엿보였다.
