(メモ) 文字コード変換、探索、素数階段

  • 10
    Like
  • 6
    Comment
More than 1 year has passed since last update.

こないだ、シェル芸勉強会の第19回のQ6を Scheme で解こおとした時に、文字コードを Shift JIS からユニコードに変換する標準的な仕組みが Scheme には無いことを知った(「lambda を隠した書き方 (32) - 2進数の文字コード列を文字列に」)。で、自分でそうゆう関数を作ろうとしてたら、SaitoAtsushi さんが、そおゆうのを作ってくれた(「Shift_JIS Converter for R7RS Scheme」)。

ユニコードのコードポイントから Shift JIS への対応関係には全く規則性がない。だから、ユニコードのコードポイントを与えられてそれを Shift JIS に変換したい時に、そのコードポイントが対応表に存在するかどうかの検索は簡単にはできなくて、(作ってもらったプログラムでもやってるけど)二分探索法を使うとかの工夫が必要だ。

で、「これをもっと速くできないだろか?任意の文字コード間でも使える一般的な方法で・・・。」と考えてみて、思いついたアイデアをメモしとく。

問題

やりたいのは要するに、入力されたコード(整数値)が文字コード対応表に定義されているかどうかを調べて、定義がある場合はそれに紐付いた文字コードを返すこと。

$$
\begin{array}\newline
{\tt type\ \color{blue}{TranslatePair}\ =\ record}\newline
{\tt \hspace{1em}\color{blue}{from}\ :\ Integer\ ;}\newline
{\tt \hspace{1em}\color{blue}{to}\ \ \ \ \ :\ Integer}\newline
{\tt end\ ;}\newline
\newline
{\tt type\ \color{blue}{TranslateArray}\ =\ array\ of\ \color{blue}{TranslatePair}\ ascending\ sorted\ by\ \color{blue}{from}\ ;}
\end{array}
$$

で、このコードでゆうと、from にはユニコードのコードポイントが、to には Shift JIS のコードが入るとゆうことになる。で、TranslateArray のデータは from 値で昇順に並んでいるものとする。でも from の数値は連続的に変化をするわけではない。つまり、この配列の要素を一つずつ順に見ていったとしても、from 値は必ずしも1ずつ増えるわけでなくて所々で数値が2以上増える。

何か Shift JIS コードに変換したいユニコードのコードポイントがある時、TranslateArrayfrom 部分を探していくのけど、それをいかに速くやるかってこと。で、見つかってしまえば後は、そのレコードの to を見るだけ。

要するに、

昇順に並んではいるものの、不連続な(=必ずしも1ずつ増えるわけではない)整数値列の中から特定の数値が存在する場所を(あるいは、どこにも存在しないとゆう事実を)いかに速く見つけ出すか
これに尽きる。

素数階段、関数近似

で色々考えてて、思い出したのはガウスの「素数階段」とゆうやつ。素数も不規則に不連続にしか存在しない整数だからだ。で、素数階段ってのは、数を 1、2、3、… と順に数えていって、素数を見つけたら、一段上がるような階段状のグラフ。

これを今回、横軸は from 側の文字コードで、縦軸は TranslateArray データの添字ということになる。名づけて「文字コード階段」。イメージはこんな感じ。(数学のグラフだから本当は曲線のグラフけど、分かりやすいから棒グラフにしてみた。)

文字コード階段

階段が一段上った場合はその文字コードは from 側の文字コードとして定義されてて、なおかつ、その文字に対応する文字が to 側の文字集合にも存在することを意味する(要するに、変換表にエントリーがあるってこと)。このグラフの場合、文字コード値 6~10、14~16 では階段が上がってないから、その文字コードは定義されていない、またはその文字コード値で表される文字が to 側の文字集合には含まれていないので変換テーブルにエントリーがない、という意味になる。(そもそもユニコードで定義された範囲を超えるコードポイントとか、Shift JIS には含まれないヘブライ文字とかタミル文字とかを表すコードポイントについては、Shift JIS には変換できないから、変換表にエントリーがないってゆーこと。)

…で、これをどうするかってゆーと、このグラフを適切なモデル関数を想定してその関数で近似関数 getInitialIndex :: Integer -> Real を求める。どうゆうモデル関数がいいのかは分からないけど、単調増加だから、普通に冪級数べききゅうすう展開がいいのかもしれない。

$${\tt getInitialIndex} (c) = \sum_n{a_nc^n}$$

関数形は別に冪級数でなくても何でもいいのけど、何であれ近似関数を求めておく。もっとも、近似関数の正確さが、このアルゴリズムの鍵かもしれないから、最も近似できる形にするべきだろおけど。

文字コードを探すには

…で、実際に文字コードを探すにはどうしたらいいかとゆーと、事前に求めた近似関数に探してる文字コード codePoint を入れて求まる実数 real_index_0 = getInitialIndex (codePoint) を適切に整数化(四捨五入か切り捨てか切り上げかどれが良いのかわからないけど)して、それを検索の最初の添字 index_0 = round (real_index_0) にすればいいのだ。

で、TranslateArray データの中で、index_0 が指し示す箇所を見て、

  • 運良くそこの from 値と探してる文字コード codePoint とがズバリ一致していればそれで終了で、
  • from 値が codePoint よりも小さい値であれば、index_0 + 1index_0 + (codePoint - from) の間に存在する可能性があるから、その区間を二分法などで探せば良いし、
  • from 値が codePoint よりも大きい値であれば、index_0 - (from - codePoint)index_0 - 1 の間に存在する可能性があるから、その区間を二分法などで探せば良い、

とゆーアイデア。

文字処理とか記号処理的なものに普通は使わない実数の数学関数を使うとゆうところがチョット面白いかも。でも実際、本当に実用的なものなんだろか。どうなんだろ?まぁ、思いつきのアイデアだし…。もぉ少し考えてみても良いねっ。 (・∀・)