Строка для уникального цельного хэширования

Ответ 1

Это невозможно с ограничениями, которые вы указали, если вы не наложили максимальную длину.

Предположим, что k("a") и k("b") являются кодами этих двух строк.

С вашими ограничениями вы ищете уникальное целое число, которое попадает между этими двумя значениями, но k("a") < k("a....a") < k("b"). Поскольку существует бесконечное количество строк стиля "a....a" (и "akjhdsfkjhs"), которые должны были бы вписываться между двумя кодами, такой порядок, сохраняющий общий, уникальный, фиксированный код длины, не может существовать для строк произвольной длины. Поскольку вам понадобится столько целых чисел, сколько строк, и поскольку строки не ограничены длиной, это не сработает.

Отбросить либо общий (так что не разрешить вставлять новые строки), уникальный (разрешить коллизии - например, использовать первые четыре буквы в качестве кода!), неограниченную длину (например, 3 символа) или свойство сохранения порядка.

Ответ 2

Для простоты я предполагаю, что a to z являются единственными символами, допускаемыми в словах.

Пусть присваиваются номера длиной до 2 строк:

String Value
a      0
aa     1
ab     2
...
az     26
b      27
ba     28
bb     29
...
bz     53
c      54
...

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

Для алгоритмической простоты мы предпочли бы начать с 27: (не стесняйтесь пытаться понять это, начиная с 0, вам понадобятся специальные случаи)

String Value
a      27
aa     28
ab     29
...

Таким образом, по сути, самый левый символ присваивает значение 27*(1-26) (для az), а следующий символ справа, если таковой существует, атрибуты 1-26 (для az) соответствуют значению для строки.

Теперь это можно обобщить, чтобы сказать, что самое левое число будет относить (1-26)*27^(len-1), следующий (1-26)*27^(len-2) и т.д. до (1-26)*27^0.

Что приводит меня к некоторому Java-коду:

long result = 0;
for (int i = 0; i < s.length(); i++)
   result += (long)Math.pow(27, MAX_LENGTH - i - 1)*(1 + s.charAt(i) - 'a');

Тестируемый выход:

a                    =   150094635296999136
aa                   =   155653695863554659
aaa                  =   155859586995649308
aaaa                 =   155867212593134295
aaaaa                =   155867495022670776
abacus               =   161447654121636750
abbreviation         =   161763445236432705
account              =   167509959568845180
accuracy             =   167554723653128382
announcement         =   230924421746611188
z                    =  3902460517721977536

Тест (проверка ошибок не упрощает).

Да, это некоторые достаточно большие числа для строки длиной до 13 строк, но без последовательного присвоения чисел словам в реальном словаре, вы не можете сделать лучше (за исключением того, что вы можете начать с 0, что, относительно говоря, небольшое различие), так как существует много возможностей последовательности букв.

Ответ 3

Если у вас нет ограничений на количество байтов, которые могут занимать эти целые числа, то базовые (например, Ascii) байтовые коды для каждого символа дадут вам целочисленное представление. Эквивалентно присваивать 0 = A, 1 = B до Z = 25, а затем само слово является целым числом в базе 26.

Ответ 4

Для уникальности, начните с присвоения простых чисел буквам: A -> 2, B -> 3, C -> 5, D -> 7 и т.д.

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

Например, слово CAB:

C -> 5 ^ 1 = 5
A -> 2 ^ 2 = 4
B -> 3 ^ 3 = 81
CAB -> 5 * 4 * 81 =  1620.

Ни одно другое слово никогда не даст вам 1620 в качестве ключа.

Примечание: вам не нужно начинать с A → 2 или присваивать простые символы символам алфавита, пока вы отслеживаете отображение. Также имейте в виду, что результаты этого будут очень большими.

Однако помните о других комментариях о безопасности - это не особо безопасный алгоритм.

Ответ 5

Назначьте уникальное основное значение для каждого алфавита в порядке возрастания (порядок не требуется).

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

Алгоритм:

int hash = 0;
forEach (int i = 0 ; i < word.length ; i++)
{ 
   hash *= (prime[c[i]] ** (length - i)); 
}

prime - массив для хранения простых значений, соответствующих каждому

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

Этот алгоритм даст достаточно большие значения, которые будут превышать ваш массив.

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

Ответ 6

Да, но в основном нет.

Да, как в стохастическом ответе. Установив базу 26 (или базу 128 для всех ASCII), вы теоретически можете хэшировать каждую строку однозначно.

С другой стороны, это непрактично, и не только цифры будут слишком большими для большинства языков, но и это, вероятно, будет невероятно потребляющим процессом. Кроме того, если строки разрешены бесконечно, тогда форма диагонального аргумента Кантора может быть применена также "нарушением" этого алгоритма. Невозможно создать взаимно однозначное отображение набора с мощным алеф-1 (строки) на набор мощности aleph-null (ints).

Ответ 7

Вы можете сделать это:

SEPARETOR = '000'
string_to_hash = "some_string"
hashed_result = int(SEPARETOR.join(list(str(ord(character)) for character in string_to_hash)))

Наслаждайтесь!