Случайные строки высокой плотности в Javascript - PullRequest
Новая
       34

Случайные строки высокой плотности в Javascript

7 голосов
/ 06 августа 2011

В настоящее время я генерирую UUID в Javascript с помощью этой функции ( Создать GUID / UUID в JavaScript? ): 

lucid.uuid = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

Я понимаю, что вся случайность исходит только из JavascriptФункция Math.random (), и мне все равно, соответствует ли она RFC для UUID.Я хочу упаковать как можно больше случайности в как можно меньшее количество байтов в строке Javascript.Вышеуказанная функция дает около 128 бит случайности.Какую маленькую строку (измеренную в байтах UTF8, передаваемых по проводам в HTTP POST) я могу разместить в 128 битах в Javascript?И как мне сгенерировать такую ​​строку?

Редактировать: эта строка будет частью объекта JSON при отправке на сервер, поэтому символы, которые необходимо экранировать в строке, не очень полезны.

Ответы [ 3 ]

2 голосов
/ 06 августа 2011

Вот одна потенциальная функция, которую я придумал.Начальная строка - это набор незарезервированных символов URL (66 из них).Я добавляю к случайности метки времени с разрешением примерно в 1 секунду, что полезно, поскольку пространство столкновений для моего конкретного приложения заполняется достаточно медленно с течением времени (только при МОСТах несколько сотен таких генерируется в секундукрайний случай). 

uuidDense = function() {
    var seed = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_.~';

    //Start the UUID with 4 digits of seed from the current date/time in seconds
    //(which is almost a year worth of second data).
    var seconds = Math.floor((new Date().getTime())/1000);

    var ret = seed[seconds % seed.length];
    ret += seed[Math.floor(seconds/=seed.length) % seed.length];
    ret += seed[Math.floor(seconds/=seed.length) % seed.length];
    ret += seed[Math.floor(seconds/=seed.length) % seed.length];

    for(var i = 0; i < 8; i++)
        ret += seed[Math.random()*seed.length|0];

    return ret;
}

Мысли?

0 голосов
/ 03 мая 2013

Ваш вопрос несколько противоречив. Строки Javascript используют UCS-2 (фиксированные 16-битные символы) для своего внутреннего представления. Однако UTF-8 имеет переменную ширину, но для целей кодирования я считаю, что наиболее компактной формой будет использование 1-байтовых символов UTF8, для которых требуется, чтобы только самый старший бит был равен нулю. То есть Вы можете упаковать 128 бит в 128 * 8/7 = 147 бит.

Преобразование в байты и округление, вы можете сделать это в 19 символов.

0 голосов
/ 06 августа 2011

128 битов = 16 байтов -> base64 -> 16 * 3/2 = даст вам строку из 24 символов (против 36 символов, которые у вас есть)

Вы также можете использовать base85 для лучшей плотности, но для этого потребуется кодирование URL, что может привести к худшим результатам, чем у вас.

...