Как однозначно идентифицировать набор строк, используя целое число

Question

Вот моя постановка задачи:

• У меня есть набор строк, которые соответствуют регулярному выражению. допустим, он соответствует [A-Z] [0-9] {3} (т. е. 1 буква и 3 цифры).
• я могу иметь любое число строк от 1 до 30. Для примера я мог бы иметь:
  • {A123}
  • {A123, B456}
  • {Z789, D752, E147, ... , Q665}
  • ...
• мне нужно генерировать целое число (на самом деле можно использовать 256 бит), который был бы уникальным для любого набора строк, независимо от количества элементов (хотя количество элементов могут быть использованы для генерации интуиции r)

Какой алгоритм я мог использовать?

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

Любое предложение?

Answer 1

У вас есть 2^333 возможных входных набора ((26 * 10^3) выберите 30).

Это означает, что для представления всех возможностей вам понадобится целое число 333 бит. У вас будет максимум 256 бит, поэтому будут столкновения.

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

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

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

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

• хэшей однозначно идентифицировать произвольные входы, как CityHash и SpookyHash предназначены для быстрого перемешивания и столкновения свободной идентификации.

SpookyHash кажется хорошим кандидатом для вашего случая использования. Это 128 бит в ширину, что означает, что вам нужно 2^64 разных входа, чтобы получить 50% -ный шанс одиночного столкновения.

Это также быстро: три байта за цикл на порядок быстрее, чем md5 или sha1.SpookyHash доступен в общественном достоянии (см. Ссылку выше).

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

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

Answer 2

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

Для письма у вас есть 90 - 65 = 25 различных значений, поэтому вы можете использовать 5 бит для представления буквы.

3-значное число имеет 1000 различных значений, поэтому для этого вам нужны 10 бит.

Если вы объединяете эти биты, у вас есть уникальное отображение от входа к 15-битовому номеру.

---

Этот подход прост, но он может расточать некоторые бит. Если выход должен быть как можно короче, можно отобразить следующим образом:

output = (L - 'A')*1000 + N 

где L это значение буквы, 'A' это значение буквы А, N является 3-значное число. Затем вы можете использовать как несколько бит, сколько необходимо для представления полного диапазона output, что составляет 25 * 1000 - 1 = 24999. Здесь снова 15 бит, поэтому простой подход не теряет места.

---

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

общего назначение хэш-функция не может различать входные биты, потому что он ничего не знает об их значении.
Для 256 выходных бит, после хеширования значений 5.7e38, вероятность столкновения составляет 75%. Источник: Birthday Attack.

5.7e38 кажется огромным, но ему соответствует только 129 бит (2^129 = 6.8e38). В этом случае это означает, что есть вероятность превышения 75%, что существует пара строк с (129/15 = 8,6) Элементы, которые сталкиваются.

С другой стороны, если использовать очень простую функцию отображения как:

• усечение вход на 256 битов (использовать первые 17 элементов 15 бит каждый)
• сделать 256 битное значение XOR всех 15-битных элементы

вы можете Гарантийный лист нет столкновений между любыми двумя строками с максимально 17 элементами.

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

Заключение: Если большая часть входных строк имеет менее 17 элементов, я бы предпочел бы это сделать хэш.