2-11 文字列処理アルゴリズム

文字列表現

文字列の表現は、配列に1文字1要素で格納する。

文字列照合

今までは数値や1文字を探索の対象としていたが、文字列も探索することができる。

ある文字列の中から、特定の文字列(パターン)を探し出すアルゴリズム

ナイーブ法を例とする。
1文字ずつ確認していく方法である。

他の文字列照合の方法は、bm法・kmp法がある。ナイーブ法のよりも効率が良い。詳しくは

文字列圧縮

文字列のデータを圧縮する

いくつか方法があるが、今回はランレングス法を説明する。
簡単に言うと、連続する文字を圧縮するアルゴリズムである。

他にはハフマン圧縮があり、

ハフマン圧縮は、文字の出現回数に応じて、効率よく区別できるようなビットパターンを与えて効率化する。その時、区別できるかどうかをハフマン木を使って考えることができる。

体感的には、ランレングス法、BM法、ハフマン法をよく見る。