Получение международного представления Строки
См. этот пример: https://jsfiddle.net/pqhdce2L/
function b64toBlob(b64Data, contentType, sliceSize) {
contentType = contentType || '';
sliceSize = sliceSize || 512;
var byteCharacters = atob(b64Data);
var byteArrays = [];
for (var offset = 0; offset < byteCharacters.length; offset += sliceSize) {
var slice = byteCharacters.slice(offset, offset + sliceSize);
var byteNumbers = new Array(slice.length);
for (var i = 0; i < slice.length; i++) {
byteNumbers[i] = slice.charCodeAt(i);
}
var byteArray = new Uint8Array(byteNumbers);
byteArrays.push(byteArray);
}
var blob = new Blob(byteArrays, {type: contentType});
return blob;
}
var contentType = 'image/png';
var b64Data = Your Base64 encode;
var blob = b64toBlob(b64Data, contentType);
var blobUrl = URL.createObjectURL(blob);
var img = document.createElement('img');
img.src = blobUrl;
document.body.appendChild(img);14 ответов
Если Ваша строка не ограничена в длине, Вы не можете избежать коллизий.
Существует 4294967296 возможных значений для целого числа (2^32). Если у Вас есть строка больше чем 4 символов ASCII или больше чем двух unicode символов, то существуют более возможные строковые значения, чем возможные целочисленные значения. У Вас не может быть уникального целочисленного значения для каждых возможных 5 символьных строк. Длинные значения имеют более возможные значения, но они только обеспечили бы уникальное значение для каждой возможной строки 8 символов ASCII.
Хэш-коды полезны как два процесса шага: увидьте в первый раз, если хэш-код соответствует, то проверьте целую строку. Для большинства строк, которые не соответствуют, только необходимо сделать первый шаг, и это действительно быстро.
Длина строки может варьироваться, но скажем, 10 символов на данный момент.
В этом случае для гарантии уникальности, необходимо было бы использовать своего рода большое целочисленное представление. Я сомневаюсь, что выполнение сравнений на больших целых числах было бы существенно быстрее, чем выполнение сравнений строк во-первых. Я буду второй, что других сказали здесь, используйте своего рода хеш, затем в случае проверки соответствия хеша исходные строки для избавлений от любых коллизий.
В любом случае, Если Ваши строки являются приблизительно 10 символами, я сомневаюсь, что сравнение, скажем, набора хешей на 32 бита будет всем этим намного быстрее, чем прямые сравнения строк. Я думаю, что необходимо спросить себя, если это - это действительно стоящий дополнительной сложности.
Почему Вы не делаете чего-то как 1stChar + (10 x 2ndChar) + 100 x (3rdChar)...., где Вы используете простое целочисленное значение каждого символа, т.е. = 1, b = 2 и т.д., или просто целочисленное значение, если это не буква. Это даст уникальное значение для каждой строки, даже для 2 строк, которые являются просто теми же буквами в другом порядке.
Конечно, если становится более сложным, если необходимо волноваться о Unicode, а не просто ASCII и числа могли бы стать большими, если необходимо использовать длинную строку.
Определенно не достаточно эффективны стандартные функции сравнения строк Java?
Казалось бы, что хеш MD5 будет хорошо работать. Риск хэш-коллизии был бы крайне маловероятен. В зависимости от длины Вашей строки хеш, который генерирует международное/длинное, столкнулся бы с макс. проблемами значения очень быстро.
Если Вы не хотите коллизий, попробуйте что-то безумное как SHA-512. Я не могу гарантировать, что не будет коллизий, но я не думаю, что они нашли любого все же.
Какой длины Ваши строки? Если Вы не выбираете международное представление, это длиннее, чем строка, коллизии всегда будут возможны, какое преобразование Вы используете. Таким образом, при использовании целого числа на 32 бита можно только исключительно представить строки до 4 байтов.
Принятие "алфавитно-цифрового" означает буквы и числа, Вы могли рассматривать каждую букву/число как основу 36 цифр. К сожалению, большие строки заставят число расти быстро, и необходимо было бы обратиться к большим целым числам, которые едва эффективны.
Если Ваши строки обычно отличаются при создании сравнения (т.е. поиск определенной строки), хеш мог бы быть наилучшим вариантом. После того как Вы получаете потенциальный хит, можно сделать сравнение строк, чтобы быть уверенными. Хорошо разработанный хеш сделает коллизии чрезвычайно редкими.
Насколько большой Ваши строки? Произвольно длинные строки не могут быть сжаты в формат на 32/64 бита.
Несколько вопросов в начале:
- Вы тестировали то сравнение простой строки, является слишком медленным?
- Как сравнение похоже ('ABC' == 'abc' или 'ABC'! = 'abc')?
- Сколько строки необходимо сравнить?
- Сколько сравнения необходимо сделать?
- Как Ваши строки похожи (длина, регистр)?
Насколько я помню, что Строка в Java является объектом, и две идентичных строки указывают на тот же объект.
Так, возможно, было бы достаточно сравнить объекты (вероятно, сравнение строк уже реализовано таким образом).
Если не помогает, что можно попытаться использовать реализацию Паскаля строкового объекта, когда первый элемент является длиной и если строки имеют различную длину, это должно сохранить некоторое процессорное время.
Возможно:
String y = "oiu291981u39u192u3198u389u28u389u";
BigInteger bi = new BigInteger(y, 36);
System.out.println(bi);
В конце дня единственный буквенно-цифровой знак имеет по крайней мере 36 возможных значений. При включении пунктуации, нижнего регистра, и т.д. затем можно легко передать 72 возможных значения.
Не сталкивающееся число, которое позволяет Вам быстро сравнивать строки, обязательно выросло бы экспоненциально с длиной строки.
Таким образом, сначала необходимо выбрать самую длинную строку, которую Вы ожидаете сравнивать. Для принятия это - символы N в длине и принятие Вас ТОЛЬКО, нужны прописные буквы и цифры 0-9 затем, у Вас должно быть целочисленное представление, которое может быть настолько же высоко как 36^N
Для строки длины 25 (поле общего названия) затем Вы заканчиваете тем, что нуждались в двоичном числе с 130 битами.
При создании этого в числа на 32 бита Вам будет нужно 4. Затем можно сравнить каждое число (четыре целых числа выдерживают сравнение, должен занять время, по сравнению с обходом строки). Я рекомендовал бы крупную библиотеку числа, но для этого специализированного случая я вполне уверен, можно записать собственное и получить лучшую производительность.
Если Вы захотите обработать 72 возможных значения на символ (верхний регистр, нижний регистр, цифры, пунктуация...), и Вам нужны 10 символов, то Вам будут нужны целые числа на 62 бита - два 32 бита (или 64 бита, если Вы будете в системе, которая поддерживает вычисления 64 битов),
Если, однако, Вы не можете ограничить числа в строке (т.е., могла быть любая из 256 букв/чисел/символов/и т.д.), и Вы не можете определить размер строки, то сравнение строк непосредственно является единственным способом пойти, но существует ярлык.
Бросьте указатель строки к массиву беззнаковых целых чисел на 32 бита и сравните строку 4 байта за один раз (или 64 bits/8bytes за один раз на процессоре на 64 бита). Это означает, что 100 символьных строк только требуют 25, сравнивает максимум для нахождения, который больше.
Вы, возможно, должны переопределить набор символов (и преобразовать строки) так, чтобы символам с более высоким приоритетом присвоили значения ближе 0, и более низкий приоритет оценивает ближе 255 (или наоборот, в зависимости от того, как Вы сравниваете их).
Удачи!
- Adam
Вы не можете только запустить с хэш-кода, и если хэш-коды соответствуют, делают символ по символьному сравнению?
Какой длины строки? Если они очень коротки, то уникальный идентификатор может быть сгенерирован путем рассмотрения символов как цифры в основе 36 (26 + 10), которые формируют число n-цифр, где n является длиной строки. С другой стороны, если строки будут достаточно коротки для разрешения этого, то прямое сравнение не будет проблемой так или иначе.
Иначе необходимо будет генерировать хеш без коллизий, и это может только быть сделано, когда полное пространство задач известно заранее (т.е. если Вы знаете все строки, которые могут возможно произойти). Вы захотите взглянуть на идеальное хеширование, хотя единственный выполнимый алгоритм для нахождения идеальной хеш-функции, которую я знаю, является вероятностным, таким образом, коллизии все еще теоретически возможны.
Могли бы быть другие способы найти такую функцию. Knuth назвал это “довольно забавной загадкой …” в TAoCP, но он не дает алгоритм также.
В целом Вы даете слишком немногим информацию для нахождения алгоритма, который не требует зондирования целого пространства задач некоторым способом. Это действительно неизменно означает, что проблема имеет экспоненциальное время выполнения, но могла быть решена с помощью эвристики машинного обучения. Я не уверен, желательно ли это в Вашем случае.
Пока это - хеш-функция, быть этим String.hashCode (), MD5 или SHA1, коллизия неизбежна, если у Вас нет закрепленного предела на длину строки. Математически невозможно иметь непосредственное отображение от бесконечной группы к конечной группе.
Отстранение, действительно ли предотвращение коллизий абсолютно необходимо?