Top

125가지 문자열 알고리듬

  • 원서명125 Problems in Text Algorithms: with Solutions (ISBN 9781108835831)
  • 지은이막심 크로슈모르(Maxime Crochemore), 티에리 르크로크(Thierry Lecroq), 보이체흐 리터(Wojciech Rytter)
  • 옮긴이남기환
  • ISBN : 9791161758398
  • 35,000원
  • 2024년 04월 30일 펴냄
  • 페이퍼백 | 436쪽 | 188*235mm
  • 시리즈 : 프로그래밍 언어

책 소개

요약

문자열 처리에 널리 사용되는 알고리듬을 구체적인 문제를 통해서 소개하고, 그 풀이 과정을 통해서 학습할 수 있도록 돕는 책이다. 문자열 처리 알고리듬은 문자열의 패턴 매칭, 자료 압축, 반복 탐색과 같은 작업에 사용되며, 이를 위한 기초 지식부터 고급 문자열 알고리듬까지 다루고 있다. 독자들은 이 책에서 문자열 알고리듬을 탐구하는 지적인 즐거움을 얻고 더 높은 수준으로 올라가기 위한 기반을 닦을 수 있을 것이다.

이 책의 대상 독자

자료 구조와 알고리듬에 관한 대학원 수업을 가르치는 교수자는 수강생을 위해 이 책의 원하는 부분을 어디든지 선택할 수 있다. 하지만 기초 교재는 아니며, 연구원, 박사과정 또는 석사과정 대학원생과 문자열 알고리듬에 직접적인 연관이 없더라도 알고리듬 수업을 강의해야 하는 학자들을 위한 참고자료로 집필했다. 이 책은 이 분야의 표준 교재에 대한 참고자료라고 생각해야 한다. 문제에 포함된 설명은 이 주제에 대한 깊은 배경지식을 요구하지 않고 그 이해와 해법에 대한 빠른 접근을 제공한다.

이 책의 구성

이 책은 7개의 장으로 구성된다.
1장, ‘문자열학의 기초’는 다음 장을 위한 용어, 기본 개념, 기본 도구를 소개하며 준비하는 장으로, 이 분야의 여섯 가지 큰 줄기를 반영한다.
2장, ‘조합론적 퍼즐’은 단어에 대한 조합 문제에 대한 장으로, 많은 알고리듬이 그 입력의 조합론적 성질에 기반하기 때문에 중요한 주제다.
3장, ‘패턴 찾기’에서는 가장 고전적인 주제인 문서 탐색과 문자열 일치를 다룬다.
4장, ‘효율적 자료 구조’는 문서 색인을 위한 자료 구조에 대해 다룬다. 이 자료 구조는 문서와 관련된 특수한 배열이나 나무와 같은 여러 알고리듬에서 기본적 도구로 사용한다.
5장, ‘단어의 정규성’에서는 단어에서 나타나는 정규성, 특히 반복과 대칭성에 대해 다루며, 알고리듬의 효율성에 큰 영향을 준다.
6장, ‘문자열 압축’은 무손실 문서 압축에서 실질적으로 중요한 영역의 몇 가지 기법을 주로 다룬다.
7장, ‘그 외의 다양한 알고리듬’은 이전 장에 어울리진 않지만, 확실히 알릴 가치가 있는 다양한 문제를 소개한다.

저자/역자 소개

지은이의 말

이 책은 알고리듬 문자열학(algorithmic stringology)이라고 하는 문자열 알고리듬에 관한 책이다. 문자열(단어, 문자열, 수열)은 비구조적 자료형의 하나로, 컴퓨터과학의 매우 중요한 주제다.
이 주제는 다용도인데, 여러 분야의 과학, 특히 컴퓨터과학과 컴퓨터공학에서 기본적인 수요가 있기 때문이다. 비구조적 자료의 처리는 매우 생동적인 영역으로, 운영체제의 엄청나게 반복적인 명령과 디지털 네트워크와 장비에서 분석돼야 하는 대량의 자료 모두에게 효율적 방법이 필요하다. 후자는 대량의 자료를 그들의 데이터 센터에서 관리하는 정보기술 회사에 대해서 당연한 이야기이며, 또한 컴퓨터과학을 넘어서는 대부분의 과학 분야에 대해서도 성립한다.
이 책은 문자열학에서 가장 흥미롭고 대표적인 문제를 모아서 제시한다. 각 문제는 짧고 가벼운 방식으로 소개되며, 더 고급 주제로 향하는 문을 열어준다. 이 문제들은 수백 편의 중요한 과학 출간물에서 뽑아냈다. 그중 어떤 문제는 100년을 넘은 것도 있고, 최근의 신선한 문제도 있다. 이 문제들의 대부분은 연관된 응용 분야가 있지만, 어떤 것들은 보다 추상적이다. 입문을 위한 몇 가지 조합론 문제를 제외하면 대부분은 그 핵심에 기발하고 간단한 알고리듬 풀이가 있다.
이 책은 이 주제를 다루는 새로운 단편일 뿐만 아니라 문제를 순서대로 제시한다(퍼즐과 연습 문제). 문자열 알고리듬이라는 주제를 더 학술적이고 종합적으로 다루는 전문 서적을 보충해준다. 그러나 대부분의 개념은 이 책에 포함돼 그 간극을 채우며 이 분야의 첫 번째 문제 풀이 교재로써 학생과 교사에게 특히 기대되고 필요하다.

지은이 소개

막심 크로슈모르(Maxime Crochemore)

구스타프 에펠 대학(Université Gustave Eiffel)과 킹스 칼리지 런던(King’s College London)의 명예교수다. 헬싱키 대학(University of Helsinki)에서 명예박사를 받았다. 문자열 알고리듬과 그 응용에 관한 200편 이상의 논문 저자이며, 이 주제에 관한 여러 책을 공동 저술했다.

티에리 르크로크(Thierry Lecroq)

프랑스 루앙 노르망디 대학(University of Rouen Normandy)의 컴퓨터과학과 교수다. 현재 컴퓨터과학, 정보 처리, 시스템 연구실의 생물학과 건강의 정보처리연구 팀의 수장이다. 프랑스 국립과학연구센터의 문자열학의 실무 담당자 중 한 사람으로 10년 이상 재직했다.

보이체흐 리터(Wojciech Rytter)

바르샤바 대학(University of Warsaw)의 수학, 정보학, 역학학부 교수다. 자동자, 형식 언어, 병렬 알고리듬, 문자열 알고리듬에 대한 많은 출판물의 저자다. 『Efficient Parallel Algorithms』(Cambridge University Press, 1988), 『Analysis of Algorithms and Data Structures』(Addison-Wesley, 1991), 『Text Algorithms』(Oxford University Press, 1994) 등 이 주제에 관한 여러 책을 저술했다. 유럽 학술원의 일원이다.

옮긴이의 말

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

옮긴이 소개

남기환

중앙대학교에서 물리학과 수학을 전공하고 한국방송통신대학교에서 컴퓨터과학, 영어영문학을 전공했다. 중앙대학교에서 입자물리학 석사를 취득하고, 카이스트 물리학과 박사과정을 중퇴했다. 광주과학기술원 고등광기술연구소를 거쳐 현재 광통신 관련 업체에서 연구원으로 재직 중이다.

목차

목차
  • 1장. 문자열학의 기초

  • 2장. 조합론적 퍼즐
    • 1 페르마의 작은 정리의 문자열학적인 증명
    • 2 부호성 검사의 간단한 경우
    • 3 마방진과 투에 - 모스 단어
    • 4 올덴버거 - 콜라코스키 수열
    • 5 제곱이 없는 게임
    • 6 피보나치 단어와 피보나치 기수법
    • 7 와이트호프의 게임과 피보나치 단어
    • 8 서로 다른 주기적 단어
    • 9 투에 - 모스 단어의 친척
    • 10 투에 - 모스 단어와 거듭제곱의 합
    • 11 단어의 켤레와 회전
    • 12 켤레 회문
    • 13 많은 회문을 갖는 많은 단어
    • 14 순열의 짧은 초단어
    • 15 순열의 짧은 초수열
    • 16 스콜렘 단어
    • 17 랭포드 단어
    • 18 린던 단어에서 드 브루인 단어로

  • 3장. 패턴 찾기
    • 19 경계표
    • 20 가장 짧은 덮개
    • 21 짧은 경계
    • 22 접두어 표
    • 23 최대 접미어로 향하는 경계표
    • 24 주기성 검사
    • 25 엄격한 경계
    • 26 순차적 문자열 탐색의 지연
    • 27 희박한 탐색 자동자
    • 28 효율적으로 비교하는 문자열 탐색
    • 29 피보나치 단어의 엄격한 경계표
    • 30 싱글톤 변수를 갖는 단어
    • 31 순서 보존 패턴
    • 32 매개변수화된 탐색
    • 33 좋은 접미어 표
    • 34 보이어-무어 알고리듬의 최악의 경우
    • 35 초고속 BM 알고리듬
    • 36 와일드카드를 갖는 문자열 탐색
    • 37 순환적 등가
    • 38 간단한 최대 접미어 계산
    • 39 자기최대 단어
    • 40 최대 접미어와 그 주기
    • 41 단어의 임계 위치
    • 42 린던 단어 접두어의 주기
    • 43 지민 단어를 찾아서
    • 44 불규칙적인 2차원 패턴 검색

  • 4장. 효율적 자료 구조
    • 45 최단 덮개에 대한 리스트 알고리듬
    • 46 최장 공통 접두어 계산
    • 47 접미어 배열에서 접미어 나무로
    • 48 선형 접미어 트라이
    • 49 삼진 검색 트라이
    • 50 두 단어의 최장 공통 인자
    • 51 부분문자열 자동자
    • 52 부호성 검사
    • 53 최장 기존 인자 표
    • 54 투에-모스 단어의 접미어 정렬
    • 55 앙상한 접미어 나무
    • 56 피보나치 단어의 접미어 비교
    • 57 이진 단어의 회피 가능성
    • 58 단어 집합 회피하기
    • 59 최소 유일 인자
    • 60 최소 부재 단어
    • 61 욕심쟁이 초문자열
    • 62 짧은 단어의 최단 공통 초단어
    • 63 길이에 의한 인자 수 세기
    • 64 위치를 덮는 인자 수 세기
    • 65 최장 공통 홀짝성 인자
    • 66 기본 인자 사전과 단어의 제곱없음 검사
    • 67 인자방정식의 일반 단어
    • 68 무한 단어에서 탐색하기
    • 69 완벽한 단어
    • 70 빽빽한 이진 단어
    • 71 인자 오라클

  • 5장. 단어의 정규성
    • 72 3개의 제곱 접두어
    • 73 거듭제곱 단어의 출현에 대한 딱 맞는 한계
    • 74 일반 알파벳에서 런 계산하기
    • 75 이진 단어에서 겹침 검사
    • 76 겹침없음 게임
    • 77 정박된 제곱 단어
    • 78 제곱 단어가 거의 없는 단어들
    • 79 제곱 단어가 거의 없는 이진 단어
    • 80 제곱 단어가 없는 긴 단어 만들기
    • 81 제곱 단어 없음 함수의 검사
    • 82 표지가 붙은 나무에서 제곱 인자의 수
    • 83 선형 시간 내에 빗에 있는 제곱 단어 세기
    • 84 세제곱 런
    • 85 짧은 제곱 단어와 국소적 주기
    • 86 런의 개수
    • 87 정렬된 알파벳에 대한 런 계산
    • 88 주기성과 인자 복잡도
    • 89 함수적 단어의 주기성
    • 90 단순한 반-지수
    • 91 회문의 회문적 연결
    • 92 회문 나무
    • 93 회피할 수 없는 패턴

  • 6장. 문자열 압축
    • 94 투에-모스 단어의 BW 변환
    • 95 균형 단어의 BW 변환
    • 96 제자리 BW 변환
    • 97 렘펠-지프 인자분해
    • 98 렘펠-지프-웰치 복호화
    • 99 허프만 부호의 비용
    • 100 길이가 제한된 허프만 부호화
    • 101 실시간 허프만 부호화
    • 102 런 길이 부호화
    • 103 빽빽한 인자 자동자
    • 104 피보나치 단어에서 압축된 일치
    • 105 일부분 일치에 의한 예측
    • 106 접미어 배열 압축하기
    • 107 욕심쟁이 초문자열의 압축률

  • 7장. 그 외의 다양한 알고리듬
    • 108 이진 파스칼 단어
    • 109 자기 재생 단어
    • 110 인자의 가중치
    • 111 문자 출현 횟수 차이
    • 112 경계가 없는 접두어로 인자분해
    • 113 단항 연장에 대한 원시성 검사
    • 114 부분적으로 교환 가능한 알파벳
    • 115 최대 고정밀도 목걸이
    • 116 등가-주기 이진 단어
    • 117 드 브루인 단어의 실시간 생성
    • 118 드 브루인 단어의 재귀적 생성
    • 119 변수의 길이가 주어진 단어 방정식
    • 120 세 문자 알파벳으로 이뤄진 다양한 인자
    • 121 가장 긴 증가하는 부분문자열
    • 122 린던 단어를 통한 회피 불가능한 집합
    • 123 단어 동기화하기
    • 124 금고 열림 단어
    • 125 짧아진 순열의 초단어

도서 오류 신고

도서 오류 신고

에이콘출판사에 관심을 가져 주셔서 고맙습니다. 도서의 오탈자 정보를 알려주시면 다음 개정판 인쇄 시 반영하겠습니다.

오탈자 정보는 다음과 같이 입력해 주시면 됩니다.

(예시) p.100 아래에서 3행 : '몇일'동안 -> 며칠동안