6

我有一大堆名字（数百万）。他们每个人都有一个名字、一个可选的中间名和一个姓氏。我需要将这些名称编码为唯一代表名称的数字。编码应该是一对一的，即一个名字只能和一个数字相关联，一个数字只能和一个名字相关联。

对此进行编码的聪明方法是什么？我知道根据其在字母集中的位置（a-> 1、b->2.. 等等）标记名称的每个字母很容易，因此像 Deepa 这样的名称会得到 -> 455161，但又一次在这里，我无法确定“16”是否真的是 16 或 1 和 6 的组合。

所以，我正在寻找一种编码名称的智能方法。

此外，编码应该使得任何名称的输出数字中的位数应该具有固定的位数，即，它应该与长度无关。这可能吗？

谢谢阿布舍克 S

4

6 回答 6

9

要获得相同的宽度数字，你不能在左边填零吗？

一些选项：

  1. 对它们进行排序。数一数。第 10 个名字是 10 号。
  2. 将每个字符视为 26（不区分大小写，无数字）或 52（有效，无数字）或 36（数字不区分大小写）或 62（数字区分大小写）数字中的数字。计算 int 中的值。例如，对于“abc”的名称，您将有 0 * 26^2 + 1 * 26^1 + 2 * 20^0。有时中文名称可能会使用数字来表示音调。
  3. 使用“完美哈希”方案：http ://en.wikipedia.org/wiki/Perfect_hash_function
  4. 这主要是在乐趣中建议的：使用 goedel 编号:)。所以“abc”将是 2^0 * 3^1 * 5^2 - 它是素数幂的乘积。考虑数字可以让您恢复字符。不过，这些数字可能会变得很大。
  5. 如果您还没有使用它，请转换为 ASCII。然后将字符的每个序数视为 base-256 编号系统中的数字。所以“abc”是 0*256^2 + 1*256^1 + 2*256^0。

如果您需要能够不时更新您的姓名和号码列表，#2、#4 和#5 应该可以工作。#1 和 #3 会有问题。#5 可能是最具前瞻性的，尽管您可能会发现在某些时候需要 unicode。

我相信您可以使用 2^32 而不是 2^8 == 256 的幂来将 unicode 作为 #5 的变体。

于 2012-04-26T19:50:48.057 回答
3

你在那里尝试做的实际上是散列（至少如果你有固定的位数）。有一些很好的散列算法很少发生冲突。例如，试试 sha1，它经过了良好的测试并且可用于现代语言（参见http://en.wikipedia.org/wiki/Sha1）——它似乎对 git 来说已经足够好了，所以它可能对你有用。

当然，对于两个不同的名称，相同的哈希值的可能性很小，但是对于哈希来说总是如此，并且可以处理。使用 sha1 等，您不会在名称和 ID 之间建立任何明显的联系，这可能是好事也可能是坏事，具体取决于您的问题。

如果您确实想要唯一的 ID，您将需要执行 NealB 建议的操作，自己创建 ID 并在数据库中连接名称和 ID（您可以随机创建它们并检查冲突或增加它们，从 0000000000001 左右开始） .

（经过深思熟虑并阅读第一条评论后改进了答案）

于 2012-04-26T17:51:16.823 回答
2

您可以BigInteger像这样使用编码任意字符串：

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

并且为了得到字符串回来使用：

String str = new String(bi.toByteArray());
于 2016-12-01T14:40:09.583 回答
1

我一直在寻找与您提出的问题非常相似的问题的解决方案，这就是我想出的：

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

如果你对 Python 不熟悉，那么它就是这样做的。

  1. 分数最初为 0，深度设置为 1
  2. 为每个字符添加ord值 * 深度
    1. 该ord函数返回每个字符的 UTF-8 值 (0-255)
    2. 然后乘以“深度”。
  3. 最后深度除以 256。

从本质上讲，它的工作方式是最初的角色增加了更多的分数，而后来的角色越来越少。如果您需要整数，请将最终分数乘以 2**64。否则，您将有一个介于 0-256 之间的十进制值。这种编码方案适用于二进制数据，并且一个字节/字符中只有 256 个可能的值。

此方法适用于较小的字符串值，但是，对于较长的字符串，您会注意到十进制值需要比常规双精度（64 位）所能提供的更高的精度。在 Java 中，您可以使用“BigDecimal”，而在 Python 中，可以使用“decimal”模块来提高精度。使用此方法的一个好处是返回的值是按排序顺序排列的，因此可以“有效地”搜索它们。

于 2013-01-30T06:14:50.357 回答
1

看看https://en.wikipedia.org/wiki/Huffman_coding。这是标准方法。

于 2012-04-26T18:01:59.077 回答
0

你可以翻译它，如果每个字符（至少加上空白）都会占据一个位置。

因此 ABC，即 1,2,3 必须翻译成

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

这样，您可以对任意字符串进行编码，但如果输入的长度不受限制（以及应该如何限制？），则不能保证长度有上限。

于 2012-04-26T18:01:49.117 回答