125가지 문자열 알고리듬

막심크로슈모어,티에리르크로,보이첵리터

저자:막심크로슈모르
구스타프에펠대학(UniversiteGustaveEiffel)과킹스칼리지런던(King’sCollegeLondon)의명예교수다.헬싱키대학(UniversityofHelsinki)에서명예박사를받았다.문자열알고리듬과그응용에관한200편이상의논문저자이며,이주제에관한여러책을공동저술했다.

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

저자:보이체흐리터
바르샤바대학(UniversityofWarsaw)의수학,정보학,역학학부교수다.자동자,형식언어,병렬알고리듬,문자열알고리듬에대한많은출판물의저자다.『EfficientParallelAlgorithms』(CambridgeUniversityPress,1988),『AnalysisofAlgorithmsandDataStructures』(Addison-Wesley,1991),『TextAlgorithms』(OxfordUniversityPress,1994)등이주제에관한여러책을저술했다.유럽학술원의일원이다.

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

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장.단어의정규성
__723개의제곱접두어
__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짧아진순열의초단어

이책의대상독자

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

이책의구성

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