Создание идентификатора из имени и адресных данных. Hash / Дайджест

Question

Моя проблема:

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

Другими словами, каков наилучший способ реализовать следующую функцию, чтобы возвращаемое значение было одинаковым для одного и того же ввода, коллизии маловероятны, а идентификаторы были бы менее 20 символов?

>>> make_fake_id(fname = 'Oscar', lname = 'Grouch', stnum = '1', stname = 'Sesame', zip = '12345')
N1743123734

Контекст приложения (для тех, кто заинтересован):

Это будет использоваться для приложения связывания записей . Учитывая имя и адрес ввода, мы ищем в очень большой базе данных лучшее совпадение и возвращаем идентификатор базы данных и другие данные (как мы это делаем, здесь не важно). Если совпадения нет, мне нужно сгенерировать этот псевдо / сгенерированный / производный идентификатор из входных данных поиска (имя и адрес объекта). Каждая поисковая запись должна приводить к выходной записи с реальным (фактический идентификатор базы данных, полученный в результате совпадения / ссылки) или сгенерированным псевдо / сгенерированным / полученным идентификатором. Идентификатор псевдо будет иметь префикс с символом (например, N), чтобы отличить его от реального идентификатора.

Answer 1

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

Answer 2

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

Простой способ сделать это: хэшировать данные, кодировать в base64, удалять все не буквенно-цифровые символы, усекать.

N_HASH_CHARS = 11
import hashlib, re
def digest(name, address):
  hash = hashlib.md5(name + "|" + address).digest().encode("base64")
  alnum_hash = re.sub(r'[^a-zA-Z0-9]', "", hash)
  return alnum_hash[:N_HASH_CHARS]

Сколько буквенно-цифровых символов вы должны сохранить? Каждый персонаж дает вам около 5,95 бит энтропии (log (62,2)). 11 символов дают вам 65,5 битов энтропии, чего должно быть достаточно, чтобы избежать столкновения для первых 2 ** 32,7 пользователей (около 7 миллиардов).

Answer 3

Я согласен с другим постером, предлагающим серийные номера. OTOH, если вы действительно очень хотите сделать что-то еще:

Создайте хеш SHA1 из данных и сохраните его в таблице с полем серийного номера.

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

Answer 4

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

Answer 5

Интересно, намереваетесь ли вы «назначить» эти идентификаторы пользователям? Если это так, я ожидаю, что ваши пользователи будут ненавидеть все, что вы предлагаете; кто хотел бы получить идентификатор пользователя "AAAAA01"?

Итак, если эти идентификаторы видны пользователю, то вам следует просто позволить им выбрать то, что им нравится, и проверить их на уникальность (легко). Если они не видны пользователю (например, внутренний первичный ключ), просто сгенерируйте их последовательно, используя соответствующую технику, такую ​​как Oracle Sequence или SQL Server AutoNumber (также легко).

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

РЕДАКТИРОВАТЬ: Теперь, когда я лучше понимаю проблемное пространство, основываясь на ваших изменениях, я думаю, что весьма маловероятно, что ваш алгоритм (пока) поймает большинство совпадений. Помимо моего предложения о канонизации входных данных, я рекомендую вам рассмотреть подход, который приводит к ранжированному списку нескольких возможных совпадений (которые должны быть разрешены человеком, если это возможно), а не к попытке "все или ничего" в одном совпадении , Другими словами, я рекомендую подход поиска, а не поиск.

Возможно ли это в вашей ситуации?

Answer 6

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

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

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

You could use AAAAA01  for first person at first address,
              AAAAA02 for second person at first address,
              AAAAB07 for the seventh resident at the second adresss, etc.

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