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

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

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

12345,678,999

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

"12345678999" → 12345 678 999

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

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

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

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

957366182

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

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

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

957366182 → 9573 661 82

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

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

エンコード

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

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なら次のようになります。

一桁目： 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]は、文字列を文字単位で分割して配列化しています。