第6章: アルゴリズムにおける文字列

文字列はコンピューターサイエンスの基本的なデータ型であり、文字列の並びを表します。文字列の処理アルゴリズムとデータ構造の研究は、コンピューターサイエンスのカリキュラムの重要な部分です。この章では、文字列ソート、トライ木、部分文字列検索、正規表現、データ圧縮など、いくつかの重要な文字列処理アルゴリズムを探ります。これらのアルゴリズムは、テキスト編集、文書検索、バイオインフォマティクス、自然言語処理など、多くの実用的な応用分野を持っています。

文字列ソート

ソートは、コンピューターサイエンスの基本的な操作の1つであり、文字列のソートは多くのアプリケーションで一般的な課題です。クイックソートやマージソートなどの一般的なソートアルゴリズムを使って文字列をソートできますが、文字列の特性を活かしたより効率的なアルゴリズムがあります。

基数ソート(キー索引カウンティング)

基数ソート(キー索引カウンティング)は、小さな文字集合から成る文字列をソートするための単純で効率的なアルゴリズムです。基本的な考え方は、各文字の出現頻度を数え、その情報を使って各文字列の位置を決定するというものです。

以下は、基数ソート(キー索引カウンティング)の例です:

入力:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
出力: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

このアルゴリズムは以下の手順で動作します:

各文字の出現頻度を数える
各文字の開始インデックスを計算する
頻度情報を使って、文字列を並べ替えた配列にコピーする

基数ソート(キー索引カウンティング)の時間計算量は O(n + R) で、n は文字列の総文字数、R は文字集合の大きさ(異なる文字の数)です。これにより、小さな文字集合から成る文字列をとても効率的にソートできます。

LSD基数ソート

最下位桁優先(LSD)基数ソートは、基数ソート(キー索引カウンティング)の拡張版です。以下は、与えられたマークダウンファイルの日本語翻訳です。コードの部分は翻訳せず、コメントのみ翻訳しています。

文字列の長さが等しく、大きなアルファベットを持つ文字列を並べ替えることができる数え上げソート。基本的なアイデアは、最後の文字から始めて、最初の文字に向かって文字ごとに文字列を並べ替えることです。

LSDラジックソートの例:

入力:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
出力: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

アルゴリズムの動作は以下の通りです:

最後の文字を使ってキーインデックスカウンティングで文字列を並べ替える。
1の手順を、最初の文字に向かって繰り返す。

LSDラジックソートの時間計算量はO(w * n)で、wは文字列の長さ、nは文字列の数です。これは固定長の文字列を効率的に並べ替えられる選択肢です。

MSDラジックソート

最上位桁優先(MSD)ラジックソートは、可変長の文字列を扱えるラジックソートの再帰的な変種です。クイックソートのように、MSDラジックソートは独立して並べ替えられるサブ配列に配列を分割します。

MSDラジックソートの例:

入力:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
出力: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

アルゴリズムの動作は以下の通りです:

各文字列の最初の文字に基づいて配列をサブ配列に分割する。
各サブ配列を再帰的に並べ替える。

MSDラジックソートの最悪時間計算量はO(n * w)ですが、実際には可変長の文字列に対してLSDラジックソートよりも高速な場合があります。

Tries

Trie(トライ)は、接頭辞マッチングや文字列検索を効率的に行うことができる木構造のデータ構造です。Trieの各ノードは1文字を表し、ルートからノードへの経路が文字列の接頭辞を表します。文字列がトライに格納されている

以下は、"sea"、"sells"、"she"、"shells"、"shore"の文字列がトライに格納されている例です:

     (root)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

トライでは以下の操作がサポートされています:

文字列をトライに挿入する
トライ内の文字列を検索する
トライから文字列を削除する
指定のプレフィックスを持つ文字列をすべて見つける

これらの操作の時間計算量は O(w) で、w は挿入、検索、削除する文字列の長さです。これにより、トライは文字列関連のタスクに非常に効率的なデータ構造となります。

部分文字列検索

部分文字列検索は、より大きなテキスト文字列の中で、パターン文字列のすべての出現箇所を見つける問題です。これは、テキスト編集、バイオインフォマティクス、多くの他の分野で応用されるきわめて基本的な文字列処理の問題です。

ブルートフォース検索

部分文字列検索の最も単純なアプローチはブルートフォースアルゴリズムで、テキスト内のすべての可能な位置でパターンとの一致を確認します。

ブルートフォース検索の例:

Text:    "abacadabrabracabracadabrabrabracad"
Pattern: "abracadabra"
Output:  [13]

ブルートフォースアルゴリズムの最悪時間計算量は O(n * m) で、n はテキストの長さ、m はパターンの長さです。実装は簡単ですが、大きなテキストやパターンでは非効率的になる可能性があります。

Knuth-Morris-Pratt アルゴリズム

Knuth-Morris-Pratt (KMP) アルゴリズムは、不要な比較を避けるために事前に計算された "失敗関数" を使用する効率的な部分文字列検索アルゴリズムです。

失敗関数は、これまでにマッチした部分文字列のプレフィックスのうち、最長の適切なサフィックスの長さを教えてくれます。これにより、不一致が見つかったときにテキストを後退せずに前に進むことができます。

KMP アルゴリズムの例:

Text:    "abacadabrabr
```acabracadabrabrabracad"
パターン: "abracadabra"
出力: [13]

KMPアルゴリズムの実行時間はO(n + m)であり、大きなテキストとパターンに対して、ブルートフォース法よりも効率的です。

Boyer-Moore アルゴリズム

Boyer-Moore アルゴリズムは、パターン文字列を事前に処理することで効率的なサブストリング検索アルゴリズムです。KMPとは異なり、Boyer-Mooreはパターンの末尾から比較を開始し、逆方向に進みます。

Boyer-Mooreの主なアイデアは、「good suffix」関数と「bad character」関数の2つの事前計算された関数を使うことです。これらの関数を使うことで、不一致が見つかった場合にテキストを飛ばすことができ、KMPと同様の効果を得られます。

以下に、Boyer-Mooreアルゴリズムの例を示します:

テキスト: "abacadabrabracabracadabrabrabracad"
パターン: "abracadabra"
出力: [13]

Boyer-Mooreの最良の場合の実行時間はO(n/m)、最悪の場合の実行時間はO(n * m)ですが、実際には大きなアルファベットに対して最も高速なサブストリング検索アルゴリズムです。

正規表現

正規表現は、文字列のパターンを記述するための強力なツールです。簡潔で柔軟な表記法を提供し、テキストの照合、検索、操作を可能にします。

正規表現は、文字列のパターンを表す文字列です。最も単純な形式は、"hello"のような文字列リテラルで、正確に"hello"に一致します。しかし、正規表現にはより複雑なパターンを表現するための特殊文字や構造も含まれています:

. (ドット) は任意の1文字に一致します。
* (アスタリスク) は、前の文字または群が0回以上出現することに一致します。
+ (プラス) は、前の文字または群が1回以上出現することに一致します。
? (疑問符) は、前の文字または群が0回または1回出現することに一致します。
^ (キャレット) は行頭に一致します。
$ (ドル) は行末に一致します。
[] (角括弧) は文字クラスを定義し、その中の任意の1文字に一致します。以下は、この Markdown ファイルの日本語訳です。コードの部分は翻訳せず、コメントのみ翻訳しています。

正規表現の例とそのパターンのマッチング:

a.b は "a" で始まり "b" で終わる3文字の文字列にマッチします。例: "acb"、"a5b"、"a b"。
a*b は "b"、"ab"、"aab"、"aaab" のように、0個以上の "a" の後に "b" が1個続く文字列にマッチします。
a+b は "ab"、"aab"、"aaab" のように、1個以上の "a" の後に "b" が1個続く文字列にマッチしますが、"b" にはマッチしません。
a?b は "ab" または "b" にマッチします。
^a は "a" で始まる文字列にマッチします。
a$ は "a" で終わる文字列にマッチします。
[aeiou] は単一の母音文字にマッチします。

正規表現は Java、Python、grep、sedなどの多くのプログラミング言語やツールでサポートされており、データ検証、テキスト処理、ログ解析などに広く使用されています。

データ圧縮

データ圧縮とは、元のデータ表現よりも少ないビット数でデータを表現する過程です。これにより、ストレージ容量の削減や送信時間の短縮が可能になります。圧縮には大きく分けて無損失圧縮と有損圧縮の2種類があります。無損失圧縮では、圧縮されたデータから元のデータを完全に復元できますが、有損圧縮では情報の一部が失われる代わりに、より高い圧縮率が得られます。

ランレングス符号化

ランレングス符号化(RLE)は、同一の記号が連続して出現する部分(ラン)を、その記号と出現回数で表す簡単な無損失圧縮手法です。

例:

入力:  "AAAABBBCCCDDDEEE"
出力: "4A3B3C3D3E"

RLEは単純な画像データなど、ランが長い場合に効果的ですが、ランが少ない場合は逆に圧縮率が悪化する可能性があります。

ハフマン符号化

ハフマン符号化は、無損失圧縮アルゴリズムの1つで、記号の出現頻度に応じて可変長のコードを割り当てます。こちらは日本語訳です。コードの部分は翻訳していません。コメントのみ翻訳しています。

入力データの中の文字の頻度に基づいて、より頻繁に現れる記号には短いコードが、より頻繁でない記号には長いコードが割り当てられます。

このアルゴリズムは、ボトムアップで構築されるバイナリツリー、いわゆるハフマンツリーを使って動作します。各リーフノードは記号とその頻度を表し、各内部ノードはその子ノードの頻度の合計を表します。ツリーは、最も低い頻度を持つ2つのノードを繰り返し統合することで構築されます。

ツリーが構築されると、各記号のコードは、ルートからその葉ノードへの経路によって決まります。左分岐は"0"、右分岐は"1"を表します。

ハフマン符号化の例:

入力:  "AAAABBBCCCDDDEEE"
出力: "000010011001011100101"

ハフマンツリー:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

この例では、"A"には"00"、"B"には"01"、"C"には"10"、"D"には"110"、"E"には"111"のコードが割り当てられています。圧縮された出力は、入力の各記号をその対応するコードに置き換えることで得られます。

ハフマン符号化は最適なプレフィックスコードであり、どのコードも他のコードのプレフィックスにはなりません。これにより、圧縮データの明確な復号が可能になります。ハフマン符号化は、JPEG、MP3、ZIPなどのさまざまなファイル形式や圧縮ツールで広く使用されています。

LZW圧縮

Lempel-Ziv-Welch (LZW)圧縮は、辞書ベースの圧縮アルゴリズムで、入力を圧縮しながら辞書(コードブック)を構築します。LZWは、ファイル圧縮ユーティリティで広く使用されており、GIF画像フォーマットでも使用されていました。

LZWの主な考え方は、文字列をシングルコードに置き換えることです。入力文字列を文字単位で読み取り、固定長コードを可変長コードに置き換えることで、圧縮された表現を生成します。文字列が長いほど、単一の数値としてエンコードすることで、より多くのスペースを節約できます。

以下は、LZW圧縮の例です。以下は、LZW圧縮の仕組みを説明するマークダウンファイルの日本語訳です。コードの部分は翻訳していません。

LZW圧縮の仕組み:

辞書に全ての単一文字列を初期化する。
現在の入力に一致する辞書内の最長の文字列Wを見つける。
Wの辞書インデックスを出力に出力し、Wを入力から削除する。
Wに次の入力記号を追加して辞書に追加する。
ステップ2に戻る。

例として、文字列"ABABABABA"をLZW圧縮する場合を考えてみましょう。

辞書に"A"と"B"を初期化する。
最長一致は"A"です。インデックス(0)を出力し、入力から削除します。辞書には"A"、"B"、"AB"が含まれます。
最長一致は"B"です。インデックス(1)を出力し、入力から削除します。辞書には"A"、"B"、"AB"、"BA"が含まれます。
最長一致は"AB"です。インデックス(2)を出力し、入力から削除します。辞書には"A"、"B"、"AB"、"BA"、"ABA"が含まれます。
最長一致は"ABA"です。インデックス(4)を出力し、入力から削除します。辞書には"A"、"B"、"AB"、"BA"、"ABA"、"ABAB"が含まれます。
最長一致は"BA"です。インデックス(3)を出力します。入力は空になりました。

"ABABABABA"の圧縮表現は、インデックスの列[1]です。これはオリジナルのASCII表現よりも少ないビット数で表現できます。

復号化は逆の手順で行います:

辞書に全ての単一文字列を初期化する。
入力からコードXを読み取る。
辞書からXの文字列を出力する。
前のコードが存在する場合、前の文字列にXの先頭文字を連結して辞書に追加する。
ステップ2に戻る。

LZW圧縮は簡単で高速なため、多くのアプリケーションに適しています。ただし、辞書のサイズが大きくなり、メモリを大量に消費する可能性があります。また、入力ブロックごとに辞書がリセットされるため、小さなファイルの圧縮率が低下する可能性があります。

これらの制限はありますが、LZW圧縮は依然として有用な圧縮アルゴリズムです。以下は、提供されたマークダウンファイルの日本語překladu版です。コードについては、コメントのみ翻訳しています。

結論

このチャプターでは、文字列ソート、トライ、部分文字列検索、正規表現、データ圧縮など、重要な文字列処理アルゴリズムについて探りました。これらのアルゴリズムは、多くの実世界のアプリケーションの基礎をなしており、テキストデータを扱うプログラマにとって不可欠なツールです。

まず、文字列ソートについて説明しました。文字列ソートは、文字列の特性を活かして最適化されたソートアルゴリズムです。キーインデックスカウンティング、LSD基数ソート、MSD基数ソートは、個々の文字に基づいて文字列をソートする効率的な方法を提供します。

次に、文字列を格納および検索するためのツリー状のデータ構造であるトライについて見てきました。トライは、プレフィックス一致を高速に行うことができ、自動補完やIPルーティングテーブルなどのアプリケーションで広く使用されています。

Knuth-Morris-Pratt アルゴリズムやBoyer-Moore アルゴリズムなどの部分文字列検索アルゴリズムを使うと、より大きな文字列の中でパターンを効率的に検索できます。これらのアルゴリズムは、テキスト編集、計算生物学、情報検索などで多数の用途があります。

正規表現は、文字列パターンを記述する強力で柔軟な方法を提供します。正規表現の基本的な構文と、さまざまなプログラミング言語やツールでのパターンマッチングや文字列操作への活用について説明しました。

最後に、データ圧縮アルゴリズムについて取り上げました。これらのアルゴリズムは、入力データ内の冗長性やパターンを活用して、データサイズを縮小します。ランレングス符号化、ハフマン符号化、Lempel-Ziv-Welch圧縮について、それぞれの長所と用途を紹介しました。

これらの文字列処理アルゴリズムとデータ構造を理解することは、テキストデータを扱う上で不可欠です。非構造化データの量が増え続ける中で、効率的に操作、検索、圧縮する能力は重要となっています。以下は、提供された Markdown ファイルの日本語翻訳です。コードについては、コメントのみを翻訳しています。

文字列は今後ますます価値が高まるでしょう。この章で説明した技術を習得することで、自分のプロジェクトやアプリケーションにおける幅広い文字列処理の課題に対処できるようになります。

Chapter 5 Graphs Chapter 7 Context