Насколько эффективен алгоритм кодирования / декодирования класса BASE64 в Java? - PullRequest
Новая
       42

Насколько эффективен алгоритм кодирования / декодирования класса BASE64 в Java?

5 голосов
/ 15 июня 2011

Я собираюсь использовать алгоритм для кодирования переменной длины, но очень длинное поле String , извлеченное из файла XML, затем эти закодированные данные должны быть сохранены в базе данных.

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

Я пробовал org.apache.commons.codec.binary.Base64 класс, у него есть 2 метода:

  1. encodeBase64(Byte[] barray)
  2. decodeBase64(String str)

, который прекрасно работает и решает мою проблему.Но он преобразует строку из 55 символов в строку из 6 символов.

Так что мне интересно, есть ли такой случай, когда этот алгоритм кодирует 2 очень большие строки, имеющие только 1 несоответствие (например) в один и тот же кодированный байтмассивы.

Я не знаю много о классе Base64, но если кто-нибудь может мне помочь, это будет очень полезно.

Если вы можете предложить какой-либо другой алгоритм, который делает короткую большую строкуфиксированной длины и решает мою задачу, я буду рад его использовать.

Заранее спасибо.

Ответы [ 2 ]

12 голосов
/ 15 июня 2011

Не очень эффективно.

Кроме того, использование классов sun.misc дает непереносимое приложение.

Проверьте следующие сравнения производительности из MiGBase64 :

enter image description here

Так что мне интересно, есть ли случай, когда этот алгоритм кодирует 2 очень большие строки и имеет только 1 несовпадение символов (например) в одну и ту же закодированнуюмассивы байтов.

Base64 - это не алгоритм хеширования, это кодировка, и поэтому он должен быть двунаправленным.Столкновения не могут быть допущены по необходимости - иначе декодирование было бы недетерминированным.Base64 предназначен для представления произвольных двоичных данных в строке ASCII.Кодирование строки Unicode в виде Base64 часто увеличивает количество кодовых точек , необходимых, так как для набора символов Unicode требуется несколько байтов.Представление Base64 строки Unicode будет варьироваться в зависимости от используемой кодировки (UTF-8, UTF-16).Например: 

Base64( UTF8( "test" ) ) => "dGVzdA=="
Base64( UTF16( "test" ) ) => "/v8AdABlAHMAdA=="

Решение 1

Использовать сжатие без потерь 

GZip( UTF8( "test" ) )

Здесь вы конвертируете строку в байтовый массиви использование сжатия без потерь, чтобы уменьшить количество байтов, которые вы должны хранить.Вы можете изменить алгоритм кодирования и сжатия символов, чтобы уменьшить количество байтов в зависимости от строк, которые вы будете хранить (т. Е. Если это в основном ASCII, то UTF-8, вероятно, будет лучшим.

Pros : без коллизий, возможность восстановления исходной строки
Минусы : байт, необходимый для хранения значения, является переменным, байт, необходимый для хранения значения, больше

Solution 2

Использование алгоритма хеширования 

SHA256( UTF8( "test" ) )

Здесь вы конвертируете строку в набор байтов фиксированной длины с функцией хэширования. Хэширование является однонаправленным и по своей природе столкновенийможет быть возможным . Однако, основываясь на профиле и количестве строк, которые вы ожидаете обработать, вы можете выбрать хеш-функцию, чтобы минимизировать вероятность коллизий

Плюсы : требуется байтфиксированное значение для хранения; количество байтов, необходимых для сохранения, мало
Минусы : возможны коллизии, восстановление исходной строки невозможно

1 голос
/ 15 июня 2011

Я только что видел ваш комментарий - кажется, вы на самом деле ищете сжатие, а не хэширование, как я изначально думал Хотя в этом случае вы не сможете получить выходные данные фиксированной длины для произвольных входных данных (подумайте об этом, бесконечное число входных данных не может быть биективно отображено на конечное число выходных данных), поэтому я надеюсь, что не было сильным требованием.

В любом случае производительность выбранного вами алгоритма сжатия будет зависеть от характеристик входного текста. В отсутствие дополнительной информации сжатие DEFLATE (которое используется входными потоками Zip, IIRC) является хорошим алгоритмом общего назначения, с которого можно начинать, и, по крайней мере, использовать в качестве основы для сравнения. Однако для простоты реализации вы можете использовать встроенный в JDK класс Deflator , который использует сжатие ZLib.

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

Эти другие вопросы могут представлять интерес:

...