Получение int-представления String

Question

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

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

Любая другая идея, касающаяся более быстрого сравнения строк, также будет оценена по достоинству ...

Answer 1

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

Существует 4294967296 возможных значений для целого числа (2 ^ 32). Если у вас есть строка, содержащая более 4 символов ASCII или более двух символов Unicode, то возможных строковых значений больше, чем возможных целочисленных. Вы не можете иметь уникальное целочисленное значение для каждой возможной 5-символьной строки. Длинные значения имеют больше возможных значений, но они предоставляют уникальное значение для каждой возможной строки из 8 символов ASCII.

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

Answer 2

Разве вы не можете просто начать с хеш-кода, и, если хеш-коды совпадают, сделать посимвольное сравнение?

Answer 3

Как долго струны? Если они очень короткие, то уникальный идентификатор можно сгенерировать, считая символы в виде цифр в базе 36 (26 + 10), которые образуют число n -значений, где n - это длина строки С другой стороны, если строки достаточно короткие, чтобы позволить это, прямое сравнение в любом случае не будет проблемой.

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

Могут быть и другие способы найти такую ​​функцию. Кнут назвал это «довольно забавной… загадкой» в TAoCP, но он также не дает алгоритм.

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

Answer 4

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

Не встречающееся число, которое позволяет быстро сравнивать строки, будет обязательно расти экспоненциально с длиной строки.

Таким образом, вы first должны выбрать самую длинную строку, которую вы ожидаете сравнить. Предполагая, что длина N символов, и если вам нужны ТОЛЬКО заглавные буквы и цифры 0-9, вам нужно целочисленное представление, которое может достигать 36 ^ N

Для строки длиной 25 (поле общего имени) вам понадобится двоичное число со 130 битами.

Если вы скомпонуете это в 32-разрядные числа, вам понадобится 4. Затем вы можете сравнить каждое число (четыре сравнения целых чисел не должны занимать время по сравнению с обходом строки). Я бы порекомендовал большую библиотеку чисел, но для этого специализированного случая я уверен, что вы можете написать свою собственную и получить лучшую производительность.

Если вы хотите обработать 72 возможных значения на символ (прописные, строчные, цифры, знаки пунктуации ...) и вам нужно 10 символов, тогда вам потребуется 62 бита - два 32-битных целых числа (или одно 64-битное, если вы Вы находитесь в системе, которая поддерживает 64-битные вычисления)

Если, однако, вы не можете ограничить числа в строке (т. Е. Это может быть любая из 256 букв / цифр / символов / и т. Д.) И не можете определить размер строки, тогда сравниваете прямой путь - единственный путь, но есть быстрый путь.

Приведите указатель строки к 32-битному массиву целых чисел без знака и сравните строку 4 байта за раз (или 64 бита / 8 байт за раз на 64-битном процессоре). Это означает, что для 100-символьной строки требуется только 25 сравнений, чтобы найти большее значение.

Вам может потребоваться переопределить набор символов (и преобразовать строки), чтобы символам с более высоким приоритетом присваивались значения ближе к 0, а значениям с более низким приоритетом ближе к 255 (или наоборот, в зависимости от того, как вы сравнивая их).

Удачи!

-Adam

Answer 5

Возможно:

String y = "oiu291981u39u192u3198u389u28u389u";
BigInteger bi = new BigInteger(y, 36);
System.out.println(bi);

Answer 6

Пока это хеш-функция, будь то String.hashCode (), MD5 или SHA1, столкновение неизбежно, если у вас нет фиксированного ограничения длины строки. Математически невозможно иметь однозначное отображение из бесконечной группы в конечную группу.

Отступая, необходимо ли предотвращение столкновений абсолютно необходимо?

Answer 7

Несколько вопросов в начале:

1. Вы проверяли, что простое сравнение строк слишком медленное?
2. Как выглядит сравнение ('ABC' == 'abc' или 'ABC'! = 'Abc')?
3. Сколько строк вы должны сравнить?
4. Сколько сравнений нужно сделать?
5. Как выглядят ваши строки (длина, регистр букв)?

Насколько я помню, String в Java - это объект, и две идентичные строки указывают на один и тот же объект.

Так что, может быть, этого будет достаточно для сравнения объектов (возможно, сравнение строк уже реализовано таким образом).

Если это не поможет, вы можете попытаться использовать реализацию строкового объекта на языке Pascal, когда длина первого элемента равна длине, а если строки имеют различную длину, это должно сэкономить некоторое время процессора.

Answer 8

Длина строки может варьироваться, но скажем, 10 символов на данный момент.

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

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

Answer 9

Почему бы вам не сделать что-то вроде 1stChar + (10 x 2ndChar) + 100 x (3rdChar) ...., где вы используете простое целочисленное значение каждого символа, т.е. или просто целочисленное значение, если это не буква. Это даст уникальное значение для каждой строки, даже для 2 строк, которые являются одинаковыми буквами в другом порядке.

Конечно, если становится сложнее, если вам нужно беспокоиться о Unicode, а не только о ASCII, и числа могут стать большими, если вам нужно использовать длинную строку.

Являются ли стандартные функции сравнения строк Java определенно недостаточно эффективными?

Answer 10

Казалось бы, хэш MD5 будет работать нормально. Риск столкновения с хешем был бы крайне маловероятным. В зависимости от длины вашей строки, хеш, который генерирует int / long, очень быстро столкнется с проблемами максимального значения.