5

プロジェクトの一環として、0から3までの数字の文字列があります。例： 2030000000000000000030000000000000000003333212111221121301

この文字列をURLに渡したいので、各数値はそれぞれ最大2ビットしか使用しないため、ビットフィールドを使用してみることができると考えました。このような文字列をデータのビットフィールドとして使用される整数の配列との間で変換するために、クラスで次の関数を作成しました。

makeBuildBitfield: function(build) {
var b = build.split('');
var f = [3, 0]; // the "3" is there for future purposes
var i = 1;
var j = 0;

for (var t in b) {
    if (j < 14) {
        f[i] |= b[t];
        f[i] = f[i] << 2;
        ++j;
    } else {
        f[i] |= b[t];
        ++i;
        f[i] = 0;
        j = 0;
    }
}

return f.join('.');
},

getBuildFromBitfield: function(bitfield) {
b = bitfield.split('.');

var ba = [];
for (var x = 1; x < b.length; ++x) { //start from 1 to skip the "3"
    ba[x] = [];
    var n = b[x];
    for (var y = 14; y >= 0; --y) {
        ba[x][y] = n & 3;
        n = n >>> 2;
    }
}

build = '';
for (var a in ba) build += ba[a].join('');
return build;
},

それらは機能しているように見えますが...完全ではありません。最初に例の文字列を渡すと、次のようになります。

2030000000000000000030000000000000000003333212111221121301

次の出力が得られます。

3.587202560.786432.4089.156916164

ただし、これを元に戻すことになっている関数に渡すと、次のようになります。

203000000000000000003000000000000000000333321021112211213010

2番目の文字列の余分なゼロに注意してください。今、私はビットを操作するのは初めてで、これは初めての試みですが、このテーマについて見つけた記事を探して読んだり、紙に書き留めたりしようとしました。ループが進行するときのビットの状態は、何が起こっているのかを理解しようとしますが、なぜそれがうまくいかないのか、そしてそれらの余分なゼロがそこで何をしているのか理解できないようです。私のstring->bitfield機能がオフになっているか、他の機能がオフになっているか、あるいはその両方である可能性があります。しかし、私は本当にそれを理解することができないので、それがうまくいかないことが何であれ、私がどのように修正できるかについて誰かが何か提案がありますか？

前もって感謝します！

4

3 に答える 3

7

これは、ビットフィールドをベース36の文字列に縮小する短いアプローチです。10進数の文字列でも機能しますが、これはもう少し凝縮されています。また、ビットフィールドの先行ゼロでも機能します。

function shrink (s) {
  for (var p=0, l=s.length, r=''; p<l; p+=25) { 
    r+=parseInt('1'+s.substring(p,p+25),4).toString(36); 
  }
  return r;
}

function expand (s) {
  for (var p=0, l=s.length, r=''; p<l; p+=10) { 
    r+=parseInt(s.substring(p,p+10), 36).toString(4).substring(1);
  }
  return r;
}

編集-あなたの目標はビットフィールドを縮小し、URLを介して送信し（GETリクエスト）、反対側で拡張することだと思います。これにより、それを行うことができますが、縮小されたデータを転送して展開する以外に、縮小されたデータで役立つことは何もできなくなります。

編集2-これは「ドットなし」のバリエーションになりました。テストは次のとおりです。

var bits =  "0000000000000000000000000000000032222000" +
            "0000000000000000000000000000000031111300" +
            "0000000000000000000002111300000002111200" +
            "0000000000000000000003111120000003111130" +
            "0000000000000000000000021111200000111120" +
            "0000000000000320000000000211112000311110" +
            "0000000000002111123000000031111130011113" +
            "0000000000000321111111230000311112031111" +
            "0000000000000000032111111123002112200000" +
            "0000000032223300000000021111112000000000" +
            "0000000021111111112233000332130000000000" +
            "0330000000033322111111111111003330000000" +
            "2112000000000000000003222112001113000000" +
            "2112000111111111111112222220001113000000" +
            "2112000222222111111111111120001113000000" +
            "2112000000000000000033222230001113000000" +
            "2112003111111111111111111120001113000000" +
            "2112000000000000000000000000001113000000" +
            "2112333333333333333333333333331113000000" +
            "2111111111111111111111111111111113000000" ;

var shrunk = shrink(bits);
// b33j9ynrb4b34c70cb9cb33j9ynrclf2iv9lsx6ocpgnayh8n4b33j9ys...

var restored = expand(shrunk);

alert ( "Worked: " + (bits===restored) + ", orig size: " 
      + bits.length + ", shrunk size: " + shrunk.length);

// Worked: true, orig size: 800, shrunk size: 320
于 2010-07-26T05:13:35.320 に答える
1

いくつかの問題があります：

  1. 配列を反復処理するときは、「for（var x iny）」タイプのループを使用しないでください。常にインデックスを使用してください。

  2. ビットフィールド文字列に最後に追加されたものは、必ずしも元の数字から15桁を表すとは限りません。「get」関数は、各ビットフィールドコンポーネントの桁数が同じであると常に想定しています。

  3. varローカル変数宣言の一部を省略しました。

これが私のバージョンで、少なくともサンプル入力で機能します。

  makeBuildBitfield: function(build) {
    var b = build.split('');
    var f = [3, 0]; // the "3" is there for future purposes
    var i = 1, j = 0;;

    for (var t = 0; t < b.length; ++t, ++j) {
        if (j === 15) {
          f[++i] = 0;
          j = 0;
        }
        f[i] = (f[i] << 2) + (b[t] & 3);
    }

    f[0] = j === 0 ? 15 : j;
    return f.join('.');
  },

  getBuildFromBitfield: function(bitfield) {
    var b = bitfield.split('.');

    var ba = [];
    for (var x = 1; x < b.length; ++x) { //start from 1 to skip the "3"
        ba[x] = [];
        var n = b[x];
        for (var y = (x === b.length - 1 ? parseInt(b[0], 10) : 15); --y >= 0; ) {
            ba[x][y] = n & 3;
            n = n >>> 2;
        }
    }

    var build = '';
    for (var a = 1; a < ba.length; ++a) {
      build += ba[a].join('');
    }
    return build;
  }

最後のエントリのサイズとして「f[0]」を盗みましたが、値はどこにでも置くことができます。

于 2010-07-25T20:28:04.857 に答える
1

私はすでにいくつかのビットマップコードをすでに書いているので、これを使用した解決策があります。

Bitmap.js

function Bitmap (vals) {
  this.arr = [];
  this.length = 0;
  if (vals) {
    for (var i = vals.length - 1; i >= 0; --i) {
      if (vals [i]) {
        this.set (i);
      }
      else {
        this.clear (i);
      }
    }
  }
}

Bitmap.prototype = {
    constructor: Bitmap

  , toString: function () {
      vals = [];
      for (var i = this.length - 1; i >= 0; --i) {
        vals [i] = this.get (i) ? "1" : "0";
      }
      return vals.join ("");
    }

  , clear: function (i) {
      if (i >= this.length) {
        this.length = i + 1;
      }
      var pos = i / 32 | 0;
      this.arr [pos] = this.arr [pos] & ~(1 << i % 32);
    }

  , get: function (i) {
      return (this.arr [Math.floor (i / 32 | 0)] & 1 << i % 32) > 0;
    }

  , serialize: function () {
      var str = "";
      for (var i = 0; i < this.arr.length; ++i) {
        var num = this.arr [i];
        str += num < 0
          ? (-num).toString (36) + Bitmap.NEGATIVE_DELIM
          : num.toString (36) + Bitmap.POSITIVE_DELIM
          ;
      }
      var trailingLength = this.length % 32;
      if (trailingLength == 0) {
        trailingLength = 32;
      }
      if (this.length == 0) {
        trailingLength = 0;
      }
      return str + trailingLength.toString (36);
    }

  , set: function (i) {
      if (i >= this.length) {
        this.length = i + 1;
      }
      var pos = i / 32 | 0;
      this.arr [pos] = this.arr [pos] | 1 << i % 32;
    }

  , size: function () {
      return this.length;
    }

};

Bitmap.POSITIVE_DELIM = ".";
Bitmap.NEGATIVE_DELIM = "!"

Bitmap.deserialize = (function () {
  var MATCH_REGEX = new RegExp (
      "[A-Za-z0-9]+(?:"
      + Bitmap.POSITIVE_DELIM
      + "|"
      + Bitmap.NEGATIVE_DELIM
      + ")?"
    , "g");
  return function (str) {
    var bm = new Bitmap ();
    var arr = str.match (MATCH_REGEX);
    var trailingLength = parseInt (arr.pop (), 36);
    for (var i = 0; i < arr.length; ++i) {
      var str = arr [i];
      var sign = str.charAt (str.length - 1) == Bitmap.POSITIVE_DELIM ? 1 : -1;
      bm.arr [i] = parseInt (str, 36) * sign;
    }
    bm.length = Math.max ((arr.length - 1) * 32 + trailingLength, 0);
    return bm;
  };
}) ();

Test.js

function toBits (numStr, numBitsToExtract) {
  var numChars = numStr.split ("");
  var bits = [];
  for (var i = 0; i < numChars.length; ++i) {
    var num = numChars [i] - 0;
    for (var j = numBitsToExtract - 1; j >= 0; --j) {
      bits.push (num & 1 << j ? 1 : 0);
    }
  }
  return bits;
}

function fromBits (bitStr, numBitsToExtract) {
  var bitChars = bitStr.split ("");
  var nums = [];
  for (var i = 0; i < bitChars.length; ) {
    var num = 0;
    for (var j = numBitsToExtract - 1; j >= 0; ++i, --j) {
      num |= bitChars [i] - 0 << j;
    }
    nums.push (num);
  }
  return nums.join ("");
}

var numStr = "2030000000000000000030000000000000000003333212111221121301";
var bits = toBits (numStr, 2);
var serialized = new Bitmap (bits).serialize (); // "1d.lc.ou00e8!ci3a.k"
var recoveredNumStr = fromBits (Bitmap.deserialize (serialized).toString (), 2);
于 2010-07-26T03:21:03.277 に答える