【JavaScript】 区切記号なし連続した数値文字列の生成と復元

更新日:2022/02/07

複数の数値を区切り記号なしで文字列として出力したい。
そんなときはどうすればいいのでしょうか。
今回は、一般化可変長整数という考え方で実現してみます。

 

やりたいこと

複数の数値を文字列にして並べるとき、普通なら次のように区切り記号を入れます。

3つの数値を","を区切り記号として並べる

12345,678,999

今回は区切り記号を使わないで数値を並べて、並べた数値文字列を元の数値に分割したい。

"12345678999" → 12345 678 999

目的としては、暗号化が挙げられます。
どこで区切ったらいいのか人の目では判断できないからです。

この問題を解決する手法として、Punycodeで使用されている一般化可変長整数を利用してみます。

Punycodeの仕組みについては次の記事で簡単に解説してあります。
【JavaScript】 Punycodeの仕組みと実装

 

一般化可変長整数

一般化可変長整数は桁ごとに閾値を設定して、桁の値が閾値未満のとき最上位桁とみなします。

例えば次のような数値があるとします。

957366182

一般的な数値は上桁から下位桁に向かって数値を並べますが、この数値は下位桁から上位桁に向かって並んでいます。

上の数値は閾値を4として生成されたものとします。
先頭桁から順番に4と比較して小さければ、そこが最上位桁です。

つまり、次のように分割されます。

957366182 → 9573 661 82

この手法を利用するには前提として、下位桁が閾値以上になる必要があります。
「1000」などを思い浮かべればわかりますが、数値をそのまま出力したのではこの前提に従うことはできません。

そこで計算により前提にあう形にエンコードし、読み込み時には逆の手順でデコードします。

エンコード

数値を文字列にするとき、普通は基数で割った余りが桁の数値になります。
そして割った結果で再度基数で割るを繰り返します。
割った結果が基数より小さくなったら終了です。

123を基数10で文字列化

1234 ÷ 10 = 12 余り 3 → "3"
12 ÷ 10 = 1 余り 2 → "2"
1 < 10 → "1"

一般化可変長整数は、まず数値から閾値を減算して(基数 - 閾値) で割った余りを求めます。
その数値に閾値を加算したものが、桁の値となります。

桁の値: (数値 - 閾値) % (基数 - 閾値) + 閾値

%は、割った余りを求める演算子です。
(基数 - 閾値)で割った余りは、0から(基数 - 閾値 -1)の範囲になります。

基数10、閾値4なら 0 から 5 です。
この値に閾値4が加算されます。

つまり、最大値が9なので基数10の範囲を超えることはあります。
そして最低値が4なので、下位桁の条件を満たします。

次の桁の元となる数値は、次の式で求めます。

次桁の数値: (数値 - 閾値) ÷ (基数 - 閾値)

小数点は切り捨てます。
桁の値を求めたときは閾値を加算していますが、ここでは必要ありません。

この結果が閾値より小さければ終了です。

そうでなければ、再度桁の値を求めます。

なお閾値は、デコード時に同じ値を使うことを条件として、桁ごとに変更できます。

デコード

デコードは(基数 -閾値)を重みとして計算していきます。

基数10、閾値4なら次のようになります。

基数10、閾値4の時の重み

一桁目: 1
二桁目: 1×( 10 - 4 ) → 6
二桁目: 1×( 10 - 4 ) × ( 10 - 4 ) → 36
三桁目: 1×( 10 - 4 ) × ( 10 - 4 ) × ( 10 - 4 )  → 216
 ・・・

桁ごとに閾値が変わる場合、例えば3,4,5,6と変化する場合は次のようになります。

桁ごとに閾値が変わる場合

一桁目: 1
二桁目: 1×( 10 - 3 ) → 7
二桁目: 1×( 10 - 3 ) × ( 10 - 4 ) → 42
三桁目: 1×( 10 - 3 ) × ( 10 - 4 )  × ( 10 - 5 ) → 210
・・・

桁の値が閾値未満のとき最上位桁とみなして、数値が続くなら別の数値として処理を続けます。

 

コード例

前項の仕組みをJavaScriptで実装してみます。

まずは期数と閾値を設定します。


const BASE = 10; // 基数
const ts = [3,4,5,6,6,6,6,6,6,6,6]; // 閾値

閾値は桁ごとに変動させます。
ts[0]が一桁目です。
要素数以上の桁数が必要になったらどうするのかという問題がありますが、ここでは気にしない方向でコードを組んでいきます。

エンコード

配列にセットされた数値を、一般化可変長整数でエンコードします。


const v = [196608,32768,683981];

const result = v.reduce(
    (buf,value)=>{
        let q = value;
        let count = 0;
        while( q >= ts[count] ){
            const t = ts[count++]
            buf.push( (t + (q - t) % (BASE - t)).toString(BASE) );
            q = Math.floor((q - t) / (BASE - t) );
        }
        buf.push( q );
        return buf;
    },[]
).join("");

console.log( result ); // 665788818696970479789861

reduceはとても便利です(笑

デコード

次はデコードです。
変数resultは、前項のエンコード例の結果です。


const result2 = [...result].reduce(
    (a,b)=>{
        const digit = parseInt( b , BASE);
        a.r += digit * a.w;
        if( digit < ts[a.count]) {
            a.value.push( a.r );
            a.reset();
        }
        else a.w *= ( BASE - ts[a.count++] );
        return a;
    },{value:[],w:1,r:0,count:0,reset:function(){this.w=1;this.r=0;this.count=0;}}
).value;

console.log( result2 ); // [ 196608, 32768, 683981 ]

[...result]は、文字列を文字単位で分割して配列化しています。

更新日:2022/02/07

書いた人(管理人):けーちゃん

スポンサーリンク

記事の内容について

null

こんにちはけーちゃんです。
説明するのって難しいですね。

「なんか言ってることおかしくない?」
たぶん、こんなご意見あると思います。

裏付けを取りながら記事を作成していますが、僕の勘違いだったり、そもそも情報源の内容が間違えていたりで、正確でないことが多いと思います。
そんなときは、ご意見もらえたら嬉しいです。

掲載コードについては事前に動作確認をしていますが、貼り付け後に体裁を整えるなどをした結果動作しないものになっていることがあります。
生暖かい視線でスルーするか、ご指摘ください。

ご意見、ご指摘はこちら。
https://note.affi-sapo-sv.com/info.php

 

このサイトは、リンクフリーです。大歓迎です。