Альтернативы традиционным алгоритмам кодирования UUIDS (например, Base32, Base62) - PullRequest
Новая
       6

Альтернативы традиционным алгоритмам кодирования UUIDS (например, Base32, Base62)

3 голосов
/ 07 июля 2011

Нам нужно преобразовать огромное количество UUIDS в xml-совместимые строки.Если мы используем алгоритм Base32 (который отображает каждые 5 битов на один из 32 символов), это приводит к 26 строкам символов, если мы используем алгоритм Base62 (который итеративно делит 128-битное целое число на 62 и записывает модуль как один из 62 символов)) это приводит к 22 символьным строкам.В то время как base62 возвращает более короткие строки, это намного более интенсивно использует процессор, поэтому мы застряли с Base32 (Base64 не вариант из-за xml).

Знаете ли вы какие-либо другие типы алгоритмов кодирования, которые могут помочь нам здесь?Существуют ли варианты Base32-подобных алгоритмов кодирования битовых комбинаций, которые можно использовать с базами, не имеющими степени 2?Или есть гибридные алгоритмы, которые сочетают подходы первого с подходами второго алгоритма?Мы хотели бы уменьшить строки символов до менее 26, если это возможно.

Ответы [ 2 ]

3 голосов
/ 07 июля 2011

Вы упомянули 62, что говорит о том, что вы ограничиваете свой алфавит до A-Z (заглавные и строчные) и цифры 0-9. Почему бы не добавить еще пару символов, совместимых с XML, в этот список, например +, ., ~ или !, чтобы довести это число до 64? Вы сможете выполнять сдвиг битов, а не деление, что должно сделать алгоритм таким же быстрым, как и Base32, и уменьшить размер строк.

Редактировать: Поскольку существует ограничение на то, что эти символы также доступны для других , пока еще не определенных языков, вам может понадобиться экранировать некоторые из ваших символов для представления 64 вариантов. Если вы используете, например, _ в качестве escape-символа, вы могли бы иметь _1 и _2, представляющие опции 63 и 64. Статистика, упомянутая в исходном вопросе, предполагает, что UUIDS 128-битные, поэтому наш Base64 даст нам 22 символа, если нет экранирования и, если экранировано до 4 предметов, остается в пределах ваших 26 символов.

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

Википедия предлагает две версии Base64, которые можно использовать в пространствах имен XML.

http://en.wikipedia.org/wiki/Base64#XML. Я написал следующую JAVA, которая следует для выполнения URLSafe, UUID в Java (вызовите theObjectReturned.toString (), чтобы получить его в виде строки guid).

Я видел другой код для Java, который должен быть очень быстрым и может быть легко изменен, чтобы сделать безопасные варианты XML:

http://iharder.sourceforge.net/current/java/base64/

код следует. Сохранить в файл с именем UUIDUtil.java 

public class UUIDUtil{
public static UUID combUUID(){
    private UUID srcUUID = UUID.randomUUID();;
    private java.sql.Timestamp ts = new java.sql.Timestamp(Calendar.getInstance().getTime().getTime());

    long upper16OfLowerUUID = this.zeroLower48BitsOfLong( srcUUID.getLeastSignificantBits() );
    long lower48Time = UUIDUtil.zeroUpper16BitsOfLong( ts );
    long lowerLongForNewUUID = upper16OfLowerUUID | lower48Time;
    return new UUID( srcUUID.getMostSignificantBits(), lowerLongForNewUUID );
}   
public static base64URLSafeOfUUIDObject( UUID uuid ){
    byte[] bytes = ByteBuffer.allocate(16).putLong(0, uuid.getLeastSignificantBits()).putLong(8, uuid.getMostSignificantBits()).array();
    return Base64.encodeBase64URLSafeString( bytes );
}
public static base64URLSafeOfUUIDString( String uuidString ){
    UUID uuid = UUID.fromString( uuidString );
    return UUIDUtil.base64URLSafeOfUUIDObject( uuid );
}
private static long zeroLower48BitsOfLong( long longVar ){
    long upper16BitMask =  -281474976710656L;
    return longVar & upper16BitMask;
}
private static void zeroUpper16BitsOfLong( long longVar ){
    long lower48BitMask =  281474976710656L-1L;
    return longVar & lower48BitMask;
}

}

...