逆さまの文字列を得るのに「ブロック交換」のアルゴリズムを使う

今日は「逆の文字列を得る処理」を書く必要があったので、自分で考えたり友人とブレストしたりして手法を考えました。

ここでの「逆さまの文字列を得る処理」とは「あいうえお」から「おえういあ」を得る処理のこと、とします。

このような処理は様々なプログラミング言語の標準ライブラリに含まれていることがありますが、今回は C 言語で実装する必要がありました。、せっかくだから答えをみないで頭を悩ませることにしました。


実装に採用したアイディアは、ランチのときに小林さんからいただいた「それは各文字のバイトを逆順にして、後ろから読めば良いんじゃね?」という意見です。

「珠玉のアルゴリズム」か「奥村先生のアルゴリズム本」に手法が乗っているとのことでしたが、正解は両方に載っていました。とくに奥村先生のアルゴリズム本249ページの「ブロック交換」のためのアルゴリズムにおける説明が詳しいです。

UTF-8の文字列は1バイトから4バイトの文字で構成されています。たとえば「A」は1バイトで「あ」は3バイトです。

このように各文字ごとにバイト長がバラバラの可能性がある文字で構成された文字列は、単純に文字列の一番後ろから固定長バイトずつ先頭に追ってきても、逆さまの文字列にはなりません。また、各文字のバイト数を固定長な文字列にするために、バイト数を揃えた領域を扱うのは余分な計算が必要になるので避けたいです。

「ブロック交換」のアルゴリズムを使うと、たとえば各文字が3バイトな文字列「あいう」を逆さまにする際には以下のような様子になります。



例:ブロック交換アルゴリズムで「あいう」を「ういあ」にする


0. 初期状態

あ-1, あ-2, あ-3, い-1, い-2, い-3, う-1, う-2, う-3

1, 各文字を構成するバイト列を逆さまにする

あ-3, あ-2, あ-1, い-3, い-2, い-1, う-3, う-2, う-1

2, 文字列の一番後ろから先頭方向に向けて読み込んだバイトをそのまま順次出力する

う-1, う-2, う-3, い-1, い-2, い-3, あ-1, あ-2, あ-3

以上。



この手法だと、バイト長の違う文字同士の入れかえや、文字をスタックに積み込んだりしないので、大変シンプルな実装になります。

ただし日本語の UTF-8 文字列の場合には、実際にバイトを入れ替えたりするコード以外にも「UTF-8 な文字の長さを算出するコード」や「UTF-8 で任意の位置からN文字取得するコード」などを書く必要はあるでしょう。

手元のコードは後日公開します。というか、そろそろ最近書いてきた実装ずみなコードを順番に出していきたいな。いま家で実装してるものがあるので、それが終わったらかな。

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

[Amazonで詳細を見る]

C言語による最新アルゴリズム事典

[Amazonで詳細を見る]


投稿者:としのり  日時:23:59:59 | コメント | トラックバック |
blog comments powered by Disqus