2

我正在寻找一种可以将字符串转换为数字的算法、函数或技术。我希望算法或函数具有以下属性：

  1. 相同的字符串产生相同的计算值

  2. 相似的字符串会产生相似的值（相似可以定义为含义相似或组成相似）

  3. 能够处理可变长度的字符串

几年前我读过一篇文章，让我希望可以实现这一目标。不幸的是，我一直无法回忆起这篇文章的出处。

4

5 回答 5

3

非严肃答案：将所有内容映射到 0

属性1：检查。属性2：检查。属性3：检查。

但我认为您也希望不同的字符串获得不同的值。那么问题是，什么是相似的，什么不是。

本质上，您正在寻找一个散列函数。

有许多针对不同目标设计的哈希函数。用于示例的加密哈希计算起来非常昂贵，因为您希望很难回溯甚至预测输入的更改如何影响输出。因此，他们非常努力地违反您的条件 2。还有更简单的哈希函数，主要尝试传播数据。他们大多试图确保关闭的输入值之后不会彼此接近（但如果它是可预测的就可以了）。

您可能想阅读维基百科：

https://en.wikipedia.org/wiki/Hash_function#Finding_similar_substrings

（是的，它有一个关于“通过散列查找相似的子字符串”的部分）

维基百科也有一个哈希函数列表：

https://en.wikipedia.org/wiki/List_of_hash_functions

有几个相关的东西给你。例如可以使用minhash 。这是一种受 minhash 启发的方法：定义字母表中所有字母的一些随机列表。假设我只有这个例子的字母“abcde”。在这个例子中，我只使用两个列表。然后我的清单是：

p1 = "abcde"
p2 = "edcba"

设为我f1(str)的测试词中第一个字母在 p1 中的索引，f2(str)即 p2 中的第一个字母。所以“bababa”这个词将映射到0,3。“ababab”一词也。“dada”这个词会变成 0,1，而“ce”会映射到 2,0。请注意，此映射对于单词排列是不变的（因为它将它们视为集合），对于长文本，它将收敛到“0,0”。然而，通过一些微调，它可以让您有相当快的机会找到更仔细检查的候选人。

于 2012-10-16T06:23:35.843 回答
3

类似的构图很容易，我会让其他人解决这个问题。

意思相似要困难得多，但很有趣 :)，我记得读过一篇关于如何训练神经网络来构建一大堆英语单词的 2D“语义图”的文章，其中两个单词之间的距离表示如何“相似”它们的含义，只是通过在维基百科文章上进行训练。

你可以做同样的事情，但是把它做成一维的，这会给你一个连续的数字，其中相似的词将彼此接近。

于 2012-10-16T01:05:16.823 回答
2

模糊散列（上下文触发的分段散列）可能是您正在寻找的。

实现： ssdeep

算法说明：使用上下文触发的分段散列识别几乎相同的文件

于 2012-10-16T05:58:20.760 回答
2

正如许多海报所说，我认为您可能正在使用哈希函数。然而，类似的含义也是可能的，通过一种方式：使用诸如潜在狄利克雷分配或潜在语义分析之类的东西将你的单词映射到多维空间，相对于在大量文本集合上训练的模型（这些预训练模型可以是如果您无法访问您感兴趣的文本类型的代表性样本，请下载）。如果你需要一个标量值而不是多维向量（很难说，你没有说你想要什么），你可以尝试一些事情，比如最可能主题的概率，维度的平均值, 最可能主题的索引等.

于 2012-10-16T10:12:16.380 回答
0 
num = 0
for (byte in getBytes(str))
    num += UnsignedIntValue(byte)

这将满足所有 3 个属性（对于 #2，这适用于字符串二进制组合）。

于 2012-10-16T00:57:45.010 回答