JavaScriptで数値文字列を0と1のビット列にエンコードする方法

問題

10進数を表す文字列を受け取り、決められたルールに従って「0」と「1」だけで構成される文字列へエンコードするJavaScript関数を実装します。

エンコードのルール

入力文字列の各桁の数字 d に対して、次の手順で符号語を作ります。

• d を2進数で表したときのビット数を k とする
• 「0」を k−1 個並べ、その後ろに「1」を1つ付けた文字列をプレフィックスとする
• 数字 d 自身を2進数の文字列として表す(最右ビットが最下位ビット)
• プレフィックスと2進表現を連結したものが d の符号語になる

最後に、すべての桁について得られた符号語を順番に連結したものが、全体のエンコード結果となります。

たとえば 2 は「0110」、3 は「0111」とエンコードされます。2 の2進表現は「10」(2ビット)なので、プレフィックス「01」と「10」を連結して「0110」になり、3 は「11」なので「01」+「11」=「0111」になる、という仕組みです。

各数字の符号語一覧

この符号化方式では、符号語の先頭パターンを見るだけで元のビット長が一意に判別できます。そのため、桁ごとに長さが異なる可変長符号でありながら、復号時に曖昧さが生じないプレフィックス符号になっているのが特徴です。

コード例

const str = '77338855';

const encodeNumString = (str = '') => {
  // 1桁の数字を符号語へ変換する関数
  const encodeDigit = (digit) => {
    const bin = Number(digit).toString(2);            // 2進表現を取得
    const prefix = '0'.repeat(bin.length - 1) + '1';  // プレフィックスを生成
    return prefix + bin;
  };

  let result = '';
  for (const ch of str) {
    result += encodeDigit(ch);
  }
  return result;
};

console.log(encodeNumString(str));

出力

001111001111011101110001100000011000001101001101

コードの解説

• Number(digit).toString(2): 各桁の数字を2進数の文字列に変換します。
• '0'.repeat(bin.length - 1) + '1': ビット数より1つ少ない個数の「0」に「1」を続けたプレフィックスを作ります。
• prefix + bin: プレフィックスと2進表現を連結して1桁分の符号語とし、これを全桁分つなげて返します。

たとえば入力「77338855」の場合、各桁は「001111」「001111」「0111」「0111」「00011000」「00011000」「001101」「001101」とエンコードされ、これらを連結したものが最終的な出力として得られます。