弦楽器学の宝石

『文字列学の宝石：テキストアルゴリズム』は、文字列におけるパターンマッチングアルゴリズムと関連問題について解説した書籍です。マキシム・クロシュモアとヴォイチェフ・リッターによって執筆され、2003年にワールド・サイエンティフィック社から出版されました。

本書の最初のトピックは、完全に一致する部分文字列を見つけるための 2 つの基本的な文字列検索アルゴリズム、Knuth–Morris–Pratt アルゴリズムとBoyer–Moore 文字列検索アルゴリズムです。次に、一致する部分文字列を素早く検索するためのインデックスであるサフィックス ツリーと、それを構築するための 2 つのアルゴリズムについて説明します。本書の他のトピックには、パターン認識のための決定論的有限オートマトンの構築、文字列内の繰り返しパターンの発見、定数空間文字列マッチング アルゴリズム、および文字列の可逆圧縮が含まれます。近似文字列マッチングは、編集距離や最長共通部分列問題など、いくつかのバリエーションで扱われています。本書は、2 次元パターンマッチング、パターンマッチングのための並列アルゴリズム、最短共通スーパーストリング問題、パラメータ化パターンマッチングと重複コード検出、およびRabin–Karp アルゴリズムなどの高度なトピックで締めくくられています。^{[ 1 ]}

本書は、アルゴリズムの設計と分析に精通しているが、必ずしも文字列アルゴリズムに精通しているわけではない読者を対象として書かれている。^{[ 1 ]}レビュアーのロルフ・クラインは、本書は多くの学生にとって難しすぎるが、同じ著者の以前の著書『テキストアルゴリズム』（1994年）ほど専門家向けの深みを提供していないと評価しており、対象読者が限られている可能性があると指摘している。^{[ 2 ]}

書評家のショシャナ・マーカスは、本書に収録されているアルゴリズムは「優雅でありながら基本的」だが、より一般的なアルゴリズムの教科書では見落とされがちだと述べている。彼女は、本書自体がこの分野の研究者にとって貴重な参考書となるべきであり、学部生や大学院生のアルゴリズムの授業教材の補足としても使用できると述べている。^{[ 1 ]}書評家のリカルド・バエザ＝イェーツは、本書にビットレベルの並列プログラミング技術が省略されているのは、実践的な方法よりも理論的な方法に偏っていることを反映しているが、それでも大学院の授業に適しているという点には同意していると述べている。^{[ 3 ]}