文字列処理のアルゴリズム

要点と定義

文字列処理では、文字やビットの並びを決められた順に調べ、照合・置換・検査などの結果を得ます。設計時には、走査の開始位置、位置の数え方、一致条件、終了条件を明確にします。文字列照合では候補位置ごとにパターンを比べ、最初の一致を求める場合は一致した時点で探索を終えます。

ビット列の一部を置換するには、まずマスクを使って対象範囲を消し、位置を合わせた置換値を論理和で重ねます。対象外のビットを保ちながら、対象内は置換値のビットにできます。論理積だけで置換値を重ねると、元が0で置換値が1の箇所を1にできません。

対象が複数の語にまたがる場合、全体の位置と各語の中の位置を分けて扱います。二語目の先頭位置が16なら、全体位置 p にある対象の二語目内の位置は p−16 です。例えば p=14、長さ5なら対象は一語目に2ビット、二語目に3ビットかかります。二語目用のマスクは、二語目の該当範囲に合わせてシフトします。16ビットの論理左シフトでは空いた下位ビットを0で埋め、左端から出たビットは語の外へ出ます。

重み付き剰余による検査文字は、文字を数値に対応させ、末尾からの位置に応じて値を変換・加算して作ります。ここで扱う方式では、生成時は元の文字列の末尾を1番目として、奇数番目の値 x を「2xをNで割った商と余りの和」に変換し、偶数番目はそのまま加算します。総和を S とすると、検査文字の値は (N − (S mod N)) mod N です。

例えば N=30で、末尾から見た元の文字の値が5、8、12なら、寄与は順に10、8、24です。24は、2×12=24を30で割った商0と余り24の和です。総和42の剰余は12なので、検査文字の値は18です。値22の場合は、2×22=44を30で割ると商1、余り14となり、寄与は15です。

検証では検査文字を含む文字列の末尾から数えます。この方式では偶数番目を同じ商と余りの和に変換し、奇数番目はそのまま加算します。総和がNで割り切れると、この方式は誤りなしと判定します。これは検査規則に基づく判定であり、元の文字列が必ず正しいという証明ではありません。複数箇所の誤りが剰余上で打ち消し合えば、見逃すことがあります。

適用条件と例

単純な部分文字列照合は、連続した範囲を探す方法です。長さ32ビットの列から長さnのパターンを探すなら、候補の開始位置は0から32−nまでです。候補を一つずつ進めて同じ長さを比較すれば、先頭側にある一致から順に見つけられます。データが大きいと、候補ごとに比較を繰り返すため処理量が増えることがあります。