Вопрос по text, math, string, algorithm – Кодирование строк имени в уникальный номер

4

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

Что такое умный способ кодирования этого? Я знаю, что легко пометить каждый алфавит имени в соответствии с его положением в наборе алфавитов (a-> 1, b-> 2 и т. Д.), Поэтому такое имя, как Deepa, получит - & gt; 455161, но, опять же, здесь я не могу разобрать, если '16'; действительно 16 или комбинация 1 и 6.

Итак, я ищу умный способ кодирования имен.

Кроме того, кодировка должна быть такой, чтобы количество цифр в выходной цифре для любого имени имело фиксированное количество цифр, то есть оно не должно зависеть от длины. Это возможно?

Спасибо Абхишек С

Вы должны объяснить больше о вашей мотивации для этого. Наивно, вы можете просто трактовать представление имени utf-8 как (очень большое) число base-256; переводите на любую базу, которую вы предпочитаете, но это довольно бесполезно. Если вам просто нужен уникальный идентификатор для каждого имени, база данных, вероятно, ваш лучший вариант. Nick Johnson
Цель состоит в том, чтобы иметь возможность нанести имена на одно из измерений в трехмерном пространстве измерений, где два других измерения уже имеют числовой характер. Итак, поскольку имена носят текстовый характер, нам нужно преобразовать имена в числовые, прежде чем наносить их на график. London guy
Это не решит проблему фиксированной длины, но вы могли бы закодировать каждую букву в виде двух цифр: a = 01, b = 02 .... j = 10, k = 11 ... z = 26. В чем смысл делать это преобразование? Там могут быть лучшие решения. Кроме того, любая функция хеширования, которую вы можете придуматьwill иметь столкновения в некоторой точке (т.е. не строго 1: 1). Почему вы не можете просто использовать таблицу базы данных с порядковым номером в качестве ключа, с которым вы связываете имя? По мере появления новых имен просто ищите их, чтобы найти их ключ, если нет, то добавьте их. NealB

Ваш Ответ

6   ответов
0

http://en.wikipedia.org/wiki/Huffman_coding , Это стандартный подход.

0

если каждый символ (плюс, по крайней мере, пробел) займет позицию.

Поэтому ABC, который составляет 1,2,3, должен быть переведен в

1*(2*26+1)² + 2*(53) + 3

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

2

что вы пытаетесь сделать, это на самом деле хеширование (по крайней мере, если у вас фиксированное количество цифр). Есть несколько хороших алгоритмов хеширования с небольшим количеством коллизий. Попробуйте, например, sha1, что он хорошо протестирован и доступен для современных языков (см.http://en.wikipedia.org/wiki/Sha1) - кажется, это достаточно хорошо для мерзавца, так что это может сработать для тебя.

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

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

(улучшенный ответ после обдумывания и прочтения первых комментариев)

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceedednotError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

очень похожее на предложенное вами, и вот что я придумал:

def hash_string(value):
    score = 0
    depth = 1
    for char in value:
        score += (ord(char)) * depth
        depth /= 256.
    return score

Если вы не знакомы с Python, вот что он делает.

The score is initially 0 and the depth are set to 1 For every character add the ord value * the depth The ord function returns the UTF-8 value (0-255) for each character Then it's multiplied by the 'depth'. Finally the depth is divided by 256.

По сути, способ, которым это работает, заключается в том, что начальные персонажи добавляют больше к счету, в то время как более поздние персонажи дают все меньше и меньше. Если вам нужно целое число, умножьте конечную оценку на 2 ** 64. В противном случае у вас будет десятичное значение от 0 до 256. Эта схема кодирования работает для двоичных данных, так как в байте / символе есть только 256 возможных значений.

Этот метод отлично работает для небольших строковых значений, однако, для более длинных строк вы заметите, что десятичное значение требует большей точности, чем может обеспечить обычный double (64-битный). В Java вы можете использовать «BigDecimal». и в Python используйте «десятичный» модуль для дополнительной точности. Преимущество использования этого метода заключается в том, что возвращаемые значения расположены в отсортированном порядке, поэтому их можно искать «эффективно».

2

BigInteger для кодирования произвольных строк, например:

BigInteger bi = new BigInteger("some string".getBytes());

И для возврата строки используйте:

String str = new String(bi.toByteArray());
9

разве вы не можете просто заполнить нулями слева?

Некоторые варианты:

Sort them. Count them. The 10th name is number 10. Treat each character as a digit in a base 26 (case insensitive, no digits) or 52 (case significant, no digits) or 36 (case insensitive with digits) or 62 (case sensitive with digits) number. Compute the value in an int. EG, for a name of "abc", you'd have 0 * 26^2 + 1 * 26^1 + 2 * 20^0. Sometimes Chinese names may use digits to indicate tonality. Use a "perfect hashing" scheme: http://en.wikipedia.org/wiki/Perfect_hash_function This one's mostly suggested in fun: use goedel numbering :). So "abc" would be 2^0 * 3^1 * 5^2 - it's a product of powers of primes. Factoring the number gives you back the characters. The numbers could get quite large though. Convert to ASCII, if you aren't already using it. Then treat each ordinal of a character as a digit in a base-256 numbering system. So "abc" is 0*256^2 + 1*256^1 + 2*256^0.

Если вам нужно время от времени обновлять список имен и номеров, № 2, № 4 и № 5 должны работать. № 1 и № 3 будут проблемы. # 5, вероятно, больше всего подходит для будущего, хотя в какой-то момент вам может понадобиться юникод.

Я считаю, что вы могли бы сделать Unicode как вариант # 5, используя полномочия 2 ^ 32 вместо 2 ^ 8 == 256.

Error: User Rate Limit Exceeded

Похожие вопросы