文字列操作について

はじめに

　いろいろとプログラムを作っていると、時に非常に大きな文字列を操作する必要が出てくる場合がある。ここでは、そのような場合に起こりうる問題と打開策をまとめてみた。

　まずは通常の文字列操作を考えてみる。通常、文字列の操作は各種言語ごとにその機能が提供されている。

　例　ＶＢ

    Dim a As String    ' 文字列型aを定義する
    Dim b As String    ' 文字列型bを定義する
    Dim c As String    ' 文字列型cを定義する
    a = "abc"          ' 文字列型aに文字列"abc"を格納
    b = "def"          ' 文字列型bに文字列"def"を格納
    c = a + b          ' 文字列型cにaとbを連結して格納
    MsgBox c           ' cの内容を表示する

　ＶＢでは可変長の文字列型をサポートしており、非常に容易に文字列を操作することがでる。上記のごとく「変数に値を格納する」「変数どうして加算する」などといったことができる。

　例　Ｃ

    char a[100];    /* 文字型の配列aを定義 */
    char b[100];    /* 文字型の配列bを定義 */
    char c[100];    /* 文字型の配列cを定義 */
    strcpy( a, "abc" );    /* 文字型の配列aに"abc"をコピーする。 */
    strcpy( b, "def" );    /* 文字型の配列bに"def"をコピーする。 */
    strcpy( c, a );        /* 文字型の配列cにaの内容をコピーする。 */
    strcat( c, b );        /* 文字型の配列cに、その末尾からbの内容をコピーする。 */
    printf( "%s\n", c );   /* 内容を表示する。 */

　Ｃ言語では文字列型というものをサポートしていないため、すべての処理を「文字型の配列」で行う必要がある。後は「文字列の末尾にはNULL文字が格納されている」ことを前提としたライブラリ関数が提供されているのみである。

　Ｃ＋＋ではその強力な言語の機能からVB並に文字列を操作できるクラスライブラリが提供されている。しかし、その内部ではＣでの文字列操作と同様のことが行われている。

問題点

　上記の「言語が提供する機能」では一般に配列を用いて文字列型を実装している。Ｃ／Ｃ＋＋は明白としてもその内部が隠蔽されているＶＢでもどうやら配列を用いているだろうと推測される。

　それは配列を用いて処理を行えば通常使用する範囲内では問題ない性能を実現できるからだ。

　だが、配列での操作には決定的な問題ある。

　それは文字列の追加・削除にO(n)に比例する時間がかかるということだ。Ｃ言語の例を参照して頂ければ分かり易いが、処理するのに文字数に比例した時間がかるため、文字数が多くなるに従い処理時間が増大して実用的な時間半以内で応答できなくなるというものだ。

　文字列の挿入・削除を行うのに、後半部分を移動しなくてはいけないのは明白だ。当然、処理時間は操作を行う位置に依存する。つまり、文字列の末尾に対しての追加・削除は非常に短時間で処理が終わるが、先頭に対する処理は非常に時間を要することとなる。これは、プログラムの性能を管理する上では極めて良くない特質である。

　そしてもう一つ、決定的にまずいのは配列はメモリ上に連続して存在する必要があるということだ。

　上記の絵の青い部分を操作対象とした場合、この文字列を拡張することを考えてみる。上記の絵では、青い部分の右側にいくらか余裕があるから、拡張可能である。ところが、ある程度拡張してしまうと右側の小さな赤い領域にぶつかってしまう。赤い部分を、「すでに割り当てられた領域」とした場合、大変困ったこととなる。

　通常、領域の拡張を行う場合はＯＳにその処理を依頼する。そうした場合ＯＳは下記のようにあいている領域にデータを移動する。

　当然のことながら、領域のコピーには非常に時間がかかる。また、コピーしている瞬間は最低でも元の文字列の２倍の領域が必要となる（この問題は「配列長を２倍に拡張する」アルゴリズムで極小化することができるが、それにも限界がある）。

　だが、配列を用いることによるメリットもある。それは値の参照が高速であるということだ。配列の先頭のアドレスとそこから何番目の値を参照したいのかが分かっていれば、参照すべきアドレスが算出可能であるため、直接値を取得することができる。つまりO(1)の時間で参照できるのだ。

　この参照の性能を極力そぐことなく、追加・削除の性能を極力向上するのが、このページの目的である。

バッファを使用する

　一般的に、上記のような問題に対しては「バッファリング」という手法を用いる。

　原理は簡単だ。

　上記の様に黄色い部分を設ければ、追加・挿入に際して、文字列を移動する量を削減することができる。

　また、メモリ移動の問題も解決される。まず、移動するメモリが減少する。それどころか、「一度に確保する領域」を固定長にすれば、「連続した領域」の拡張を行う必要が無くなる。また、各メモリのブロックが並んでいる必要がないため（そもそも空間を空けた時点で並んでいない状態である）、文字列が増大した場合も、短いメモリブロックを適当な部分に確保すればよく、文字列全体の移動という事態には陥らない。そのことから、メモリの使用効率も向上する。

リンクを配列にする

　上記のようなバッファリングを実現するにはどうすればいいのか。

　まずは固定長のバッファと、各バッファのアドレスを保持する配列を用意することを考える。

　これなら、バッファがメモリ上のどこにあろうが迷子にはならない。

　だが、この構造で各文字を参照するにはどうしたらいいのだろうか。

　指定された位置に存在する文字を参照するためには、バッファのアドレスを記録した配列を参照し、先頭から各バッファを走査する。そして、各バッファ内に存在する文字数をカウントして、該当する文字が存在するバッファを見つける。そしてそのバッファ内を配列として参照する。

　つまり、この構造では参照にO(n)の計算量を要する。しかし、いくらか最適化することができる。それは、各バッファが保持している文字数を別の配列に保持しておき、その配列を二分探索で検索することだ。そうすれば参照時の計算量はO(logn)になる。

　しかし、文字列の追加や削除に伴うバッファの追加・削除が行われた場合には、配列の追加・削除を行う必要があるため、結局O(n)の計算量を必要とする。

　こういう言い方をするとなんか悪そうに聞こえるが、追加・削除も参照もバッファ単位で行われるため、実際には直接配列で取り扱う場合に比較して劇的に性能は向上する。

バッファをリストでつなぐ

　とりあえず、配列をリンクリストにすれば、バッファの追加・削除に要する計算量をO(1)にすることができる。（とは言っても、追加・削除を行う位置を特定するのに結局O(n)の計算量を要するのだが）

　これぐらいの構造を構築すれば、かなりの量の文字列を取り扱うことが可能となる。解決すべき問題にもよるのだろうが、現実的にはこの程度で手を打つことなるだろう。

実装

　リストの構造と操作方法は上図から明白だろうが、バッファ内にどのように文字列を格納するべきだろうか。ただ闇雲にデータを格納してもだめなのは当然である。つまり、最悪のメモリ使用効率を保証し、最悪の処理時間を保証する必要がある。

　このような場合、バッファの操作には以下のアルゴリズムが有効である。

　文字列の追加（バッファの増加）

　文字列を追加することによってバッファを分割する場合は、バッファ内の文字列と追加する文字列を結合し、２つのバッファに半分ずつ格納する。

　また、追加する文字列が長かった場合は、適当な量ごとに区切りバッファを複数作成する。この場合、１つのバッファに含める量は半分にしておくのがアルゴリズム上簡単となる。しかし、もっと比率を多くすればメモリ使用効率が向上する。

　文字列の削除（バッファの減少）

　文字列を削除することで、あるバッファ内の文字列が、半分を下回ってしまった場合は、当該のバッファと、その隣にあるバッファとを連結し、１つのバッファにまとめる。　左右どちらのバッファと連結したとしても結果は同じであるため、実装上容易なほうを選択して構わない。

　また、連結対象のバッファの使用率が高く、２つのバッファの文字列を結合したときに、バッファ内に入りきらないことが考えられる（つまり、左右両方のバッファがいっぱいだった場合）。そのような場合は２つのバッファの文字列を連結して、その文字列を半分に分割して２つのバッファに格納する。

　こうすることで、各バッファには常に半分以上データが含まれていることとなり、メモリ使用効率の最低値が保証されることとなる。

性能の向上

　上記の連結リストの方法における最大の問題点は「参照にかかる計算量がO(n)に比例する」ことにある。そして追加・削除を行うためには参照する必要があることから、追加・削除の計算量も連鎖的に大きくなることとなる。

　これをさらに性能向上を図ってみる。

　上述の問題の原因は「インデックスの構造が悪い」ことに尽きる。ならば、より優秀な構造にすればいい。

　ランダムに参照が行われ、ランダムにデータの追加・削除が行われる場合に特に高い性能を発揮するのはツリー構造か拡張ハッシュである。だが、拡張ハッシュは実装が難しい。よって、ここではツリー構造について考察してみる。

２分木

　まず、ツリーといって思い浮かぶのが２分木である。

　上記の絵は文字数をキーとした二分木である。二分木の実装方法は大きな問題ではないのだが、ここで１つだけ、この問題に特有の大きな制約がある。それは、「各文字には意味が無く、キーとなりうるのは文字数または各文字の出現位置のみである」ということだ。なにを言いたいのかというと、各データ（ここでは文字）単体にはキーとなる要素は無く、識別するのはその出現位置のみであるということだ。

　そして、それは通常のインデックスのアルゴリズムが想定していない重大な問題を引き起こす。それは、文字が追加・挿入された場合はそれ以降の各文字の出現位置を示す番号が変化するといことだ。なにやら回りくどい言い方をしているが、難しいことではない。要は３文字あったとして、先頭の１文字が削除されれば、２文字目のものが１文字目に来て、３文字目のものが２文字目に来る、というだけだ。

　実はこのことを言い換えると「あるデータが追加・削除された場合、ほかのデータの主キーを書き換えることになる」ということだ。当然、インデックス付けを行うアルゴリズムは、各データが持つ主キーを当てにして検索を行うように考えられている。そして当然のことながら主キーが変わることなど想定していない。ましてやほとんど全ての要素の主キーがまとめて変化するなどというのは問題外である。

　そのことがどのような影響を及ぼすのかを、上記の二分木で考察してみる。そこで、上記の絵の一番左側のバッファから１文字削除してみる。すると以下のようになる。

　上記の絵の内、インデックスの値が変化した部分は赤く縁取りしている。見て分かると思うが、大部分のインデックスが変更されている。はっきり言って、インデックスの再構築という事態である。インデックスの値のみを更新する場合でもO(n)の計算量がかかり、再構築となればさらに悪くなる。

　もし、二分木の実装にSTLのmapを用いた場合は、キーの更新を許していないため、すべてのインデックスを破棄し、１から作り直さなくてはいけない。それもこれもすべて「主キーが変わる」ことが原因である。

　では、主キーが変わらないようにすることができればいいと思われるだろうが、いい術が思いつかない。それもそうだ。ここで重要なのはそれぞれ単体のデータではなく、それらが出現する順番そのものだからだ。

　つまり、こういうことを考えてみる。たとえば各文字すべてにGUIDみたいなものを振り出し、それを主キーとしてインデックス付けを行ってはどうだろうか。しかしそれでは「各文字の順番」が失われてしまう。また、各文字に飛び番の番号を振り出して、その番号でインデックス付けを行ってはどうだろうか。つまり番号のバッファリングだ。そうすれば、文字の追加・削除が行われても被害を局所化することができる。

　良さそうに思えるが、その管理を行うのはあまりにも煩雑である。というか、いい方法が思いつかない。それにそもそも「たかだか８ビットか１６ビットのデータ」に対して、複雑な属性を設けて管理しようとする時点で破綻するのは目に見えている。

　ということで、上記の方法を見直すこととする。

　さっきと、大して変わってない様に見えるが、実際には大幅に改善されている。それは、「インデックス内で保持している値が、ほかの部分木の内容に依存していない」ということだ。上記の絵の「４８」のインデックスは、その子のバッファの文字数にのみ依存しており、２０文字と１０文字のバッファの内容には影響を受けない。よって、２０文字のバッファが１９文字になったとしても、影響を受けるのは「２０」と「３０」と「７８」のインデックスのみである。このことでインデックスの更新にかかる計算量はO(logn)にまで削減できる。

　だが、失ったものもある。それは「既存のクラスライブラリが使用できない」ということだ。もちろん、上記のようなアルゴリズムを実装することが可能な二分木のクラスライブラリの実装が存在すれば何の問題も無い訳なのだが。しかし、おそらくもっとも汎用的に使えるであろうSTLのmapやsetでは実現できない。mapやsetに直接手を加えて私家版mapや私家版setを構築すれば不可能ではないが、それは非常に行儀が悪い。（というか、mapやsetのソースコードに手を入れるなどという修行僧のようなことはやりたくない。）

　つまり、二分木を自分で実装する必要があるということだ。

　軽く言ってしまったが、効率のよい二分木を実装することがいかに困難なことかは今更論じることでもないだろう。

Ｂ＋木

　ということで、Ｂ＋木の使用を考える。その前にＡＶＬ木という選択肢もあるのだが、ＡＶＬ木のアルゴリズムも結構複雑なので、割愛させて頂く。

　Ｂ＋木とは、バッファを双方向リストで連結したものに対して、Ｂ木によるインデックス付けを行ったものだ。アルゴリズム上の優位点は、通常は「局所参照性」を高めることができる為ディスクアクセスを高速化することができる、ということが挙げられる。だが、Ｂ木にはそれ以外に「常に検索効率のよい状態が維持される」という特質も併せ持つ。　これは、木を常に下からボトムアップ的に拡張することによる。

　Ｂ＋ツリーの構造については、ほかのサイトでも紹介されていることでもあるため、ここでは「テキスト操作に関連したＢ＋ツリー」について説明する。

　上記は典型的なＢ＋木を示している。何度も言うが、Ｂ＋木の構造自体については他のサイトか本で調べて頂きたい。また、上記の絵ではバッファがただ横に並んでいるだけのように描かれているが、本当はリストでつながれている。ただ、ここではそのインデックスの構造を問題としているため、バッファの構造については略記している。

　さて、問題となるのはインデックスに使用する値だが、この場合は「自分（インデックスの１要素）が保持する値は、その隣のインデックスが保持する値＋自分の左側の部分木内に存在する総文字数」となっている。

　わかりにくいので、もう少し説明する。たとえば、左から３つ目のインデックス（63とかかれている）に着目して欲しい。この６３という値は隣の「４５」と「６３」と「４５」の間にあるバッファの文字数「１８」を合計したものとなっている。そして、上にあるインデックスの右側「１４９」は、左側にあるバッファ全ての文字数を示している。（１４９＝２０＋２５＋１８＋２２＋１９＋２６＋１９）

　さて、ここで、一番左端のバッファから１文字削除してみた。その場合影響を受けるのは赤く示したインデックスである。先の二分木と比較して多いような気がするが、インデックスは固定長であるため、演算量としてはO(logn)のままである。

　ここでは、インデックス内で、その子の保持している文字数を累計してゆく方法をとっているが、必ずしもそのようにする必要はない。たとえば、常に左側の子が保持している文字数をインデックスとして保持するという方法も考えられる。

　そうすればインデックスの更新の範囲が小さくなる。しかし、参照する際にインデックス内を順次探索しなくてはいけなくなる。インデックス内で累計で保持するようにすれば、探索に二分探索を用いることができる。が、更新する際には上記のように影響範囲が大きくなる。

　結局、参照と更新のいずれについて最適化するかという問題に帰着する。この設計については各自でベンチマークをとって決定して頂きたい。

操作

　バッファの追加・削除に伴う、インデックスの操作については純粋にＢ木のアルゴルズムに従う。よって、ここではその説明は省略させて頂く。

　だが、インデックスの分割と併合については、バッファの分割と併合に関するアルゴリズムそのままであり、うまくすれば同一のプログラムを利用することも可能と考えられる。

イテレータ

　ところで、文字列を格納していると言うことは、当然のことながら「先頭から１文字ずつアクセスしたい」という要望も出てくる。もちろん、１文字ずつ参照位置を指定してアクセスしてもいいのだが、そうすると毎回毎回インデックスを辿ってアクセスすることとなる為、O(logn)の時間を要し非常に効率が悪い。

　そういう場合はイテレータを用意して、リストを辿らせればよい。そもそも、イテレータとは「単独でアクセスされる可能性のあるオブジェクトを複数格納するコンテナクラスにおいて、その内部構造を隠匿したままアクセスできるようにするオブジェクト」のことであり、一般にイテレータは、そのコンテナクラスの内部構造に依存しても構わないとされている。

　だったら、イテレータにはバッファのリストへの参照と、バッファ内のインデックスを保持させておき、「現在参照している位置の隣を参照させるメソッド」では、ただ保持しているインデックスを加算させるのみ、としておくのが最良である。

性能測定

　一応ここまで御託を並べてきたのだから、その性能のほどを示そうと思う。

　性能の測定対象となるバッファ管理の手法には、1.単純な配列、2.B+ツリーインデックス、の二つを用いる。

　性能測定の処理内容としては、A.文字列の挿入、B.文字列の削除、C.シーケンシャルなアクセス、D.ランダムなアクセスの４つを行う。

　具体的には、

1. 規定の文字数まで文字列を追加する。
2. ランダムに文字列の追加もしくは削除を行う。
3. シーケンシャルアクセスとランダムアクセスを行う。
4. 2と3を100回繰り返す。
5. 性能の測定結果を出力する。

　である。なお、テキストの文字数は上限と下限を定め、その範囲内で追加・削除を行うものとする。

　性能測定に用いたマシンは

　である。また、バッファ管理ルーチンはCOMコンポーネント化したものを用いている。

　で、結果

　なお、A,B,C,Dの結果は、一文字あたりの処理時間で、単位はμ秒である。

　グラフにすると、

　となる。やはり、挿入と削除はかなりよい性能を出しているが、アクセスは単純配列にはかなわないと見える。当然だが。

　で、いくつか補足。

• B+ツリーにおける挿入・削除の処理時間の変化について
  これは、グラフでは一定な様に見えるが、しかし、確実に文字数に比例して悪化している。残念ながら。
• 単純配列におけるシーケンシャルアクセスとランダムアクセスについて
  処理の内容としては同じである。要は配列要素へのアクセスである。
  しかし、シーケンシャルとランダムとで、アクセス時間にかなりの開きがあるのはキャッシュのヒット率の問題かと思われる。また、ランダムアクセスにおいて、文字数に比例してアクセス時間が悪化しているのも、ヒット率が変化するためと考えられる。
• B+ツリーインデックスにおけるシーケンシャルアクセスとランダムアクセスについて
  B+ツリーインデックス方式における文字へのアクセスにはイテレータを用いている。よって、シーケンシャルアクセスの場合は、各文字をインデックスを使用せずに参照することが可能である。（つまり、「現在の文字」から「次の文字」へ移動する、というアクセス方法が可能である。）なので、シーケンシャルアクセスの場合は、文字数によらず一定時間でアクセスすることができる。しかし、ランダムアクセスの場合は、アクセスする都度インデックスを参照しているため、アクセス時間がO(logn)に比例している。
• 挿入・削除に要する時間とアクセスに要する時間
  この二つの時間は一概には比較できない。B+ツリーインデックスでの挿入・削除は配列へのアクセスと同じぐらい早いのか、といったらそれは間違いである。
  挿入・削除では複数文字をmemcpyやmemmoveでまとめて処理しているのに対して、アクセスでは一文字ずつ参照しているため、その処理効率にはかなりの開きがある。よって、挿入・削除の時間とアクセスの時間との比較には意味がない

補足　Ｂ＋のインデックスの更新について

　一応ここまで書いたのだから、バッファ数が増減した際の、Ｂ＋のインデックスを更新するアルゴリズムについても記述したほうがよさそうなので、補足しておく。

　当然だが、バッファ数が増減した場合には、インデックスの一番下段のブロックの要素も増減することとなる。

　その際、要素が増減したインデックスのブロックの使用率が100%を超えたり、50%を下回ったりしなければ、特に何の問題はない。そのまま処理を終了していい。

　で、その困ったことが起きた場合には、以下のように対策を行う。

１．要素の追加

　要素が追加され、ブロックが溢れた場合には、ブロックの分割を行う。

　ブロックの分割自体はバッファの時と同様の操作となるのだが、一つ異なる部分がある。それは、そのブロックの真ん中の要素（つまり、二つに分けるところの切れ目の部分にある要素）を一つ上の段のインデックスに押し上げるという必要があるということだ。 これはつまり、インデックスのブロックが増加したことにより、そのインデックスのブロックを参照しているインデックス内の要素が増加することを意味している。

また、上図の黄色いブロックを追加したことにより、上の段のインデックスのブロックが溢れた場合には、今度はそのブロックの分割が行われることとなる。つまり、要素の増加が上の段へと連鎖的に影響を及ぼしてゆくこととなる。 よって、一番上の段のインデックスが分割される時には、Ｂ＋ツリーインデックスの段数が増えることとなる。また、そのことから、ルートのインデックスのブロックは、その利用率が50%から100%の範囲に収まるとか限らないと言うことができる。

２．要素の削除

　要素が削除されブロックの利用率が50%を下回った場合には、バッファに対するのと同様に、ブロックの連結または再分配が行われる。

　この場合、要素の追加と同様に上の段のインデックスの要素を一緒に操作する必要がある。

　再分配する場合は、上段にある黄色い要素（再分配対象の二つのブロックの間を示す要素）も、再分配対象に含めて処理を行う。この場合では、黄色い要素は左側のブロックに移動し、黄色い要素があった位置には新たに右側のブロックから要素が選ばれ配置されている。

　連結する場合は、連結対象の二つのブロック内にある要素（赤と青）以外に、黄色いブロックも連結後のブロックに格納されることとなる。 そして、黄色いブロックは上の段のインデックスから削除される。

　この際、上の段のブロックの利用率が50%を下回った場合には、今度はそのブロックの連結や再分配が行われる。そして、連結がさらに上の段まで波及していってルートのインデックスブロックが空になってしまった時には、Ｂ＋ツリーインデックスが一段低くなる事となる。

　なお、上述でインデックスの要素が「移動」されるという表現をしているが、これは、通常のＢ＋ツリーに於いてはあっているのだが、このページで述べている文字列操作におけるＢ＋ツリーの場合には単純な移動とはならない。 つまり、インデックスの要素として保持している値を、このページで述べているアルゴリズムに於いて矛盾の無い様に更新しなくてはいけない場合も起こりうる。

　以上