Генерация уникального идентификатора из нескольких значений с отказоустойчивостью - PullRequest
Новая
       7

Генерация уникального идентификатора из нескольких значений с отказоустойчивостью

1 голос
/ 06 декабря 2010

Учитывая некоторые значения, я бы хотел (довольно чертовски) уникальный результат.

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plnmjfys'));
//now $unique1 == "sqef3452y";

Мне также нужно что-то, что достаточно близко, чтобы вернуть тот же результат.В этом случае 20% значений отсутствует.

$unique2 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8'));
//also $unique2 == "sqef3452y";

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

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

Было бы неплохо иметь весовой коэффициент, при котором можно сказать, что «значение 1 важнее, чем значение 3».Это потребует многомерного массива для ввода вместо одного измерения.

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

Ответы [ 2 ]

1 голос
/ 06 декабря 2010

Ваши два требования кажутся немного противоречивыми.Если последние 20% массива несущественны (т.е. вы хотите получить тот же результат, если он равен '0plnmjfys' или он нулевой), то почему вы хотите включить его в первую очередь?

Первый шаг - уточнить, что вы хотите устранить неоднозначность.Если это несущественно, просто отбросьте его.

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

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plnmjfys'));
//now $unique1 == "sqef3452y";

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plSsa45'));
//now $unique1 == "sqef3452k";

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

Если вы хотите обеспечить уникальность и не хотите, чтобы в ваших результатах была «закрытость», просто вычислите хеш сцепленной строки или хеш для каждой входной строки и объедините хеш-коды.

Если вы хотите присвоить привилегию «близости», вы можете вычислить хэши для наиболее важных частей и применить алгоритм Soundex или что-то подобное для остальных менее важных частей.

Просто запомнитеу вас есть противоречивые требования в этом: уникальные идентификаторы очень стараются дать (дико) разные коды для строк, даже если единственная разница - один символ в 1000-chars строка.

Близость (эта строка «более или менее совпадает» с этой второй строкой) пытается сделать прямо противоположное и, будем надеяться, вернет один и тот же код для двоих: цитирование википедии об алгоритме Soundex:

Используя этот алгоритм, оба «Роберт» и «Руперт» возвращают одну и ту же строку «R163», а «Рубин» возвращает «R150».«Ashcraft» и «Ashcroft» оба дают «A261».

Итак ... что это?Считаете ли вы, что использование хэшей для первых 4 элементов (в вашем примере) и Soundex для наименее значимых 20% в вашем примере работает?

Это может привести (возвращаясь к вашему примеру) к чему-то вроде:

$unique2 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8',));
//now $unique2 == "AB67R45-000000";

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plSsa45'));
//now $unique2 == "AB67R45-012000";
0 голосов
/ 06 декабря 2010

Я предлагаю вам ознакомиться с генераторами случайных чисел (RNG), начальными значениями и степенями случайности.

Как правило, большинство программных RNG используют значение, называемое начальным числом, для инициализации алгоритма.После этого каждое сгенерированное случайное число используется в качестве начального числа для следующей итерации.Это означает, что если вы всегда используете одно и то же начальное число (например, 1 или 42), вы всегда получите одну и ту же последовательность «случайных» чисел.Таким образом, эти типы RNG часто называют «псевдослучайными».В целях безопасности значение начального числа часто выбирается с использованием чего-то вроде текущего системного времени в миллисекундах или аппаратного устройства рандомизации, чтобы уменьшить шансы выбора одного и того же начального числа дважды за любой разумный период времени.

То, что вы предлагаете - это ГСЧ, который может принимать несколько строк, возможно, с весами, и использовать некоторую формулу для вычисления начального числа.Затем вы используете засеянный ГСЧ для случайного выбора символов для создания новой строки.Это интересно, но, к сожалению, на самом деле это не будет в конечном итоге более случайным, чем просто начало с числового начального числа и существующего ГСЧ, как описано выше.Хотя это может быть забавным упражнением!

http://en.wikipedia.org/wiki/Random_number_generation

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

...