3

我想创建一个函数,它接受一个字符串并返回一个介于 0 和 1 之间的数字。当给定相同的字符串时,该函数应该始终返回相同的数字,但除此之外,结果应该没有可辨别的模式。任何大量输入字符串的输出数字都应遵循均匀分布。

此外,我需要生成多个这样的函数,即当给定字符串“abc”时,函数 A 可能始终返回 0.593927,而函数 B 始终返回 0.0162524。我需要它快速(它用于数值模拟),并且具有相当好的统计数据。

我正在使用 Python,并会接受以下形式的答案:“这是一种使用 Python 库的简单方法”或“这是一种您可以实现的算法”。如果在 Python 中没有快速的方法,我将改用 C。

我意识到以下两种方法中的任何一种都可以,但是每种方法都有缺点,这使我想寻找更优雅的解决方案。

  1. 存储一个字典
    我可以在每次给定一个新字符串时计算一个新的随机数,并将其存储在字典中,以便在我再次收到相同的字符串时检索。但是,我的应用程序很可能会生成很多只出现一次的字符串,这最终会导致必须在内存中存储一​​个非常大的字典。这也使可重复性变得更加困难,因为即使我使用相同的种子,如果我以不同的顺序接收相同的字符串,我也会生成不同的函数。由于这些原因,“动态”一致地计算随机数会更好。

  2. 使用散列函数
    我可以在字符串上调用散列函数,然后将结果转换为数字。例如,可以通过将“种子”字符串附加到每个输入字符串来解决生成多个函数的问题。然而,然后我坚持尝试找到具有适当速度和统计数据的哈希函数。Python 的内置哈希速度很快,但依赖于实现,我不知道统计数据会有多好,因为它不是为此类目的而设计的。另一方面,我可以使用诸如 md5 之类的安全散列算法,它具有良好的统计数据,但这对于我的应用程序来说太慢了。针对数据存储应用程序的哈希函数通常比像 md5 这样的加密安全函数快得多,但它们的设计目的是避免冲突,而不是产生均匀分布的输出,而且这些函数不一定在所有情况下都相同。

关于散列函数的进一步说明

为了说明避免冲突和产生统一结果是不同的事情,请考虑以下使用 Python 内置哈希函数的示例:

>>> hash("aaa") % 1000
340
>>> hash("aab") % 1000
343
>>> hash("aac") % 1000
342
>>> hash("aad") % 1000
337
>>> hash("aae") % 1000
336
>>> hash("aaf") % 1000
339
>>> hash("aag") % 1000
338
>>> hash("aah") % 1000
349
>>> hash("aai") % 1000
348
>>> hash("aaj") % 1000
351
>>> hash("aak") % 1000
350

上面的输出没有冲突,但也明显不是均匀分布的,因为它们都在336和351之间,而且第三位数也有一定的规律。我意识到我可能通过这样做可以获得更好的统计数据(hash("aaa")/HASH_MAX)*1000(假设我可以计算出HASH_MAX应该是什么),但这应该有助于说明一个好的散列函数的要求与我正在寻找的函数的要求不同.

关于问题的一些相关信息

我不确切知道该算法需要处理的字符串是什么,因为字符串将由模拟生成,但可能会出现以下情况:

  1. 它们将具有非常有限的字符集(可能只有 4 或 5 个不同的符号)。

  2. 会有很多独特或稀有的字符串和一些非常常见的长度不等的字符串。

  3. 字符串的长度没有上限,但短的可能比长的更常见。如果我从未见过超过 100 个字符的字符,我不会感到惊讶,但我不确定。其中许多只有一到三个字符,因此该算法对于短字符串的速度非常重要。(但我想我可以使用查找表来查找小于一定长度的字符串。)

  4. 通常,字符串将具有共同的大子字符串 - 通常两个字符串的不同之处仅在于在开头或结尾附加一个字符。当字符串相似时,算法不会给出相似的输出值,这一点很重要。

4

4 回答 4

3

使用一个好的随机数生成器并用字符串作为种子。

于 2013-02-05T14:09:20.687 回答
1

Lookup3被认为具有非常好的碰撞特性,这应该意味着结果的均匀分布,而且速度也很快。将它放在 Python 扩展中应该很简单。

更一般地说,如果您找到一个函数可以很好地减少哈希表冲突并具有您需要的速度属性,那么您只需要从 32 位或 64 位整数到浮点数的最终转换。网络和其他地方有许多字符串散列函数的来源。检查Knuth,对于初学者。

添加

另一件可能值得尝试的事情是首先使用像 RC4 这样的快速 1-1 算法(不安全,但仍然足够接近伪随机)加密字符串,然后运行一个简单的哈希(h = h + a * c[i ] + b) 覆盖密文。RC4 密钥是唯一标识符。

于 2013-02-05T06:46:23.263 回答
1

尝试使用指纹,例如拉宾指纹。
http://en.wikipedia.org/wiki/Fingerprint_(computing)

如果您选择 N 位指纹,您只需将结果除以 2^N。

指纹是一种散列函数,通常对计算机来说非常快(与MD5 等密码散列函数相比),但对密码应用程序不利(密钥值可以通过其指纹以某种方式恢复)

于 2013-02-05T07:05:35.987 回答
1

在关于通用散列的维基百科文章中的“散列字符串”部分中有一个算法。

或者,您可以只使用一些内置的哈希函数;您的每个随机函数都会在散列之前为字符串添加一个随机(但固定的)前缀。

于 2013-02-05T06:45:54.503 回答