字符串到唯一整数散列

Question

我正在尝试开发一个系统,可以将我的字符串更改为唯一的整数值,这意味着例如单词"account"具有加密的数值0891,并且没有其他字可能转换为0891具有相同的转换过程,它不但是需要能够产生的整数转换回字符串.

同时它将依赖于单词结构规则,意味着诸如"准确性"和"公告"之类的单词将具有大于0891的生成数字,并且诸如"a","abacus"和"abbreviation"之类的单词将具有生成的数字小于0891.

此应用程序的目的是提供类似于索引或主键的服务.我没有使用增量索引的原因是出于安全目的,并且是由于索引依赖于集合中的数据数量

(例如)

[0] A, [1] B, [2] C, [3] D, [4] E, [5] F

上面的字母有各自对应的索引,E的索引为4

但是,如果数据突然增加或减少,则排序

[0] A, [1] AA, [2] AAB, [3] C, [4] D, [5] DA, [6] DZ, [7] E, [8] F

E现在的指数为7

每个单词必须具有唯一的独立整数等价物并具有相应的权重.

我需要知道是否存在可以执行上述操作的算法.

任何帮助将不胜感激.

Answer 1

除非您施加最大长度,否则这对您给出的约束是不可能的.

假设k("a")并且k("b")是这两个字符串的代码.

使用约束,您正在寻找一个介于这两个值之间的唯一整数,但是k("a") < k("a....a") < k("b").由于存在无限数量的样式"a....a"(和"akjhdsfkjhs")字符串需要适合两个代码,因此对于任意长度的字符串,不能存在保留通用,唯一,固定长度代码的顺序.因为你需要尽可能多的整数作为字符串,并且因为字符串不受长度限制,所以这不起作用.

删除一般(所以不允许插入新字符串),唯一(允许碰撞 - 例如使用前四个字母作为代码!),无限长度(例如3个字符)或保留顺序属性.

Answer 2

为简单起见,我假设a,以z允许在单词中的字符.

让我们分配长度为2个字符串的数字:

String Value
a      0
aa     1
ab     2
...
az     26
b      27
ba     28
bb     29
...
bz     53
c      54
...

现在,通过观察,您应该能够理解,为了确定任何给定的较短长度字符串的偏移量,您需要允许的最大长度.我们假设我们知道这个数字.

为了简化算法,我们宁愿从27开始:(随意尝试从0开始计算出来,你需要一些特殊情况)

String Value
a      27
aa     28
ab     29
...

因此,基本上,最左边的字符贡献一个值27*(1-26)(对于az),右边的下一个字符(如果存在)为1-26(对于az)贡献一个字符串的值.

现在可以概括地说,最左边的数字会贡献(1-26)*27^(len-1),下一个(1-26)*27^(len-2),依此类推,直到(1-26)*27^0.

这引出了一些Java代码:

long result = 0;
for (int i = 0; i < s.length(); i++)
   result += pow(27, MAX_LENGTH - i - 1)*(1 + s.charAt(i) - 'a');

测试输出:

a                    =   150094635296999121
aa                   =   155653695863554644
aaa                  =   155859586995649293
aaaa                 =   155867212593134280
aaaaa                =   155867495022670761
abacus               =   161447654121636735
abbreviation         =   161763445236432690
account              =   167509959568845165
accuracy             =   167554723653128367
announcement         =   230924421746611173
z                    =  3902460517721977146

在线演示.

是的,这些是一些相当大的数字,只有长达13个字符串,但是,如果没有按顺序为实际字典中的单词分配数字,你就不能做得更好(除了你可以从0开始,相对而言,一个小的差异),因为有很多可能的字母序列.

Answer 3

为了唯一性，首先为字母指定素数： A -> 2, B -> 3, C -> 5, D -> 7等等。

要计算单词中给定字母的“键”，请计算素数的单词中位置索引次方。要获得整个单词的“键”，请将所有字母键相乘。

例如单词 CAB：

C -> 5 ^ 1 = 5
A -> 2 ^ 2 = 4
B -> 3 ^ 3 = 81
CAB -> 5 * 4 * 81 =  1620.

没有其他词可以给你 1620 作为密钥。

注意：只要您跟踪映射，您不必从 A -> 2 开始，也不必按顺序为字母表中的字符分配素数。还要记住，这样做的结果会很快变得很大。

但是，请记住有关安全性的其他评论 - 这不是一个特别安全的算法。

Answer 4

按升序为每个字母表分配一个唯一的素数（顺序不是必需的）。

请注意：由于素数相乘是一个唯一的结果，只能与这些数字相乘，因此它将为每个单词提供唯一的值。

算法 ：

int hash = 0;
forEach (int i = 0 ; i < word.length ; i++)
{ 
   hash *= (prime[c[i]] ** (length - i)); 
}

prime - 一个数组，用于存储每个对应的质数

赋给 (length - 1) 为该字符出现的位置赋予值以维持字典顺序。

该算法将给出足够大的值，从而导致数组溢出。

另外：长度较小的单词可能会比某些长度较大的单词给出较低的值，并且可能会影响您的字典顺序，但我不确定为什么您需要字典顺序，因为这里将保持唯一性。