Сжатие массива больших чисел - PullRequest
4 голосов
/ 08 апреля 2010

У меня есть приложение javascript, которое отправляет большое количество числовых данных по проводам. Эти данные затем сохраняются в базе данных. У меня проблемы с размером (слишком большая пропускная способность, слишком большая база данных). Теперь я готов пожертвовать некоторой производительностью для сжатия.

Я думал о реализации базового 62 number.toString (62) и parseInt (сжатого, 62). Это, конечно, уменьшит размер данных, но прежде чем я продолжу и сделаю это, я подумал, что я хотел бы рассказать об этом людям, поскольку я знаю, что должно быть какое-то нестандартное решение, которое я не рассматривал.

Основные характеристики: - Сжать большое количество массивов в строки для передачи JSONP (так что я думаю, что UTF отсутствует) - Будь относительно быстрым, послушай, я не ожидаю такой же производительности, как сейчас, но я также не хочу сжатия gzip.

Любые идеи будут с благодарностью.

Спасибо

Гвидо Тапиа

Ответы [ 4 ]

4 голосов
/ 08 апреля 2010

Другим способом сделать это может быть кодирование в двоичные типы, такие как целые числа со знаком / без знака, и ручное декодирование в http://snippets.dzone.com/posts/show/685, что потребует кода на стороне сервера для создания двоичных данных.

Затем можно выполнить сжатие Хаффмана или что-то подобное, например, RLE (см. http://rosettacode.org/wiki/Run-length_encoding#JavaScript для реализации, хотя в IE могут быть некоторые проблемы без изменения) для дальнейшего сжатия данных.

EDIT : В качестве альтернативы, вы можете преобразовать сами числа в основание (основание) в диапазоне некодированных символов URI (см. http://en.wikipedia.org/wiki/Percent-encoding), что должно хорошо работать, если многие числа больше 2 цифр. Я преобразовал код в http://code.activestate.com/recipes/111286-numeric-base-converter-that-accepts-arbitrary-digi/ от Python, чтобы сделать это.

В настоящее время он не обрабатывает поплавки, но это может быть сделано довольно легко:

function get_map(s) {
    d = {}
    for (var i=0; i<s.length; i++) {
        d[s.charAt(i)] = i}
    d.length = s.length
    d._s = s
    return d}

var separate_with = '~';
var encodable = get_map('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_.'); // - is reserved for negatives obviously :-P
var base10 = get_map('0123456789')

// UNCOMMENT ME for length/speed testing in a wider base!
// You may wish to experiment with the ranges for a happy medium between bandwidth and DB space :-P
/*var encodable = ''
for (var i=1; i<128; i++) {
    encodable += String.fromCharCode(i)
}
encodable = get_map(encodable)*/

function baseconvert(number, fromdigits, todigits) {
    var number = String(number)

    if (number.charAt(0) == '-') {
        number = number.slice(1, number.length)
        neg=1}
    else {
        neg=0}

    // make an integer out of the number
    var x = 0
    for (var i=0; i<number.length; i++) {
        var digit = number.charAt(i)
        x = x*fromdigits.length + fromdigits[digit]
    }

    // create the result in base 'todigits.length'
    res = ""
    while (x>0) {
        remainder = x % todigits.length
        res = todigits._s.charAt(remainder) + res
        x = parseInt(x/todigits.length)
    }

    if (neg) res = "-"+res
    return res
}

function encodeNums(L) {
    var r = []
    for (var i=0; i<L.length; i++) {
         r.push(baseconvert(L[i], base10, encodable))
    }
    return r.join(separate_with)
}

function decodeNums(s) {
    var r = []
    var s = s.split(separate_with)
    for (var i=0; i<s.length; i++) {
         r.push(parseInt(baseconvert(s[i], encodable, base10)))
    }
    return r
}

var test = [5, 654645, 24324, 652124, 65, 65289543, 65278432, 643175874158, 652754327543]
alert(encodeNums(test))
alert(decodeNums(encodeNums(test)))
2 голосов
/ 08 апреля 2010

Ну, как уже упоминалось в принятом ответе на этот вопрос , библиотека jsolait имеет реализацию сжатия LZW в JavaScript ...

0 голосов
/ 09 апреля 2010

Сейчас я играю с идеей кодирования длины числа в самом числе.Я все еще не усовершенствовал этот алгоритм, но опубликую его, как только сделаю.Но примерно это то, чего я сейчас пытаюсь достичь:

Границы:

  • Допускается потеря точности (+ - 3)
  • Максимальное число будет 3200
  • Минимальное значение равно 0 (поэтому нет отрицательных значений)
  • Без десятичного знака - число с плавающей запятой

Итак, теперь, учитывая мое максимально допустимое число, я знаю, что длина закодированной цифрыbase 62 будет иметь максимальную длину 2. Таким образом, любое закодированное число имеет длину 1 или 2 символа.Потрясающие.Так что теперь я собираюсь сделать число нечетным или четным, если его 1 или 2 символа (помните, я могу справиться с потерей точности).Это устраняет необходимость в разделителях.

Теперь я вижу сжатие на 70-80% с этим, оно очень глючное в данный момент, но я взволнован об этом, поэтому пост, чтобы поощрить обсуждение вокруг этогометодология.

0 голосов
/ 08 апреля 2010

Опции

  • Используйте библиотеку js (см. Ответ от Джоша), но следите за временем ожидания сценария
  • Используйте какой-нибудь загрузчик activex или silverlight, который также делает zip
  • Использовать плагин Java
  • Использование сжатия на основе флэш-памяти
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...