24

我正在尝试开发一个可以将我的字符串更改为唯一整数值​​的系统，例如说“帐户”这个词的加密数值为 0891，并且没有其他词可以通过相同的转换过程转换为 0891 ，但是它不需要能够将生成的整数转换回字符串。

同时它会依赖于词的结构规则，意思是“accuracy”和“announcement”等词的生成数大于0891，“a”、“abacus”和“abbreviation”等词的生成数会大于0891。生成的数字小于 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

每个单词必须有一个唯一的独立积分等价物并具有相应的权重。

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

任何帮助将不胜感激。

4

8 回答 8

13

This is not possible with the constraints you have given, unless you impose a maximum length.

Assume that k("a") and k("b") are the codes of these two strings.

With your constraints, you are looking for a unique integer number that falls inbetween these two values, but k("a") < k("a....a") < k("b"). As there is an infinite number of strings of style "a....a" (and "akjhdsfkjhs") that would need to fit inbetween the two codes, such an order preserving general, unique, fixed-length code cannot exist for strings of arbitrary length. Because you would need as many integers as strings, and since strings are not bounded by length this cannot work.

Drop either general (so don't allow inserting new strings), unique (allow collissions - e.g. use the first four letters as code!), the unbounded length (to e.g. 3 characters) or the order-preserving property.

于 2013-05-13T12:08:08.070 回答
11

为简单起见，我假设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 开始，相对而言，一个小的差异），因为字母序列有很多可能性。

于 2013-05-13T14:42:33.140 回答
4

为了唯一性，从为字母分配素数开始： 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 开始或按顺序为字母表的字符分配质数，只要您跟踪映射即可。还要记住，这样做的结果会很快变大。

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

于 2013-05-13T11:56:33.953 回答
2

如果您对这些整数可以占用的字节数没有任何限制，那么每个字符的底层（例如 Ascii）字节码将为您提供整数表示。等效地，分配 0=A, 1=B 直到 Z=25，然后单词本身就是以 26 为底的整数。

于 2013-05-13T11:53:35.173 回答
1

以递增的顺序为每个字母分配一个唯一的素数（不需要顺序）。

请注意：由于素数的乘法是一个唯一的结果，只能乘以这些数字，它会给你每个单词的唯一值。

算法 ：

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

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

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

该算法将提供足够大的值，从而超出您的数组。

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

于 2013-05-13T11:51:37.273 回答
1

是的，但大多数情况下没有。

是的，就像随机的答案一样。通过设置基数 26（或所有 ASCII 基数 128），理论上您可以唯一地散列每个字符串。

另一方面，这是不切实际的，不仅对于大多数语言来说数字会变得太大，而且这可能是一个非常耗时的过程。此外，如果允许字符串是无限的，则可以应用一种形式的康托尔对角参数也“破坏”该算法。不可能创建一个具有基数 aleph-one（字符串）的集合到一组基数 aleph-null（整数）的一对一映射。

于 2016-09-25T17:32:12.310 回答
1

你可以这样做：

SEPARETOR = '000'
string_to_hash = "some_string"
hashed_result = int(SEPARETOR.join(list(str(ord(character)) for character in string_to_hash)))

享受！

于 2016-11-14T18:33:47.210 回答
0

s长度字符串的一般形式的函数n是：

hashCode(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

其中^表示取幂。由于 Java 使用 32 位整数来保存哈希值，因此所有值都应保持原样。

如果要将字符串散列为小整数，可以使用以下C#代码：

int StringToIntegerHash(string str)
{
  int hash = 0;
  str = GetTicketHash(str);
  for(int i=0; i<str.Length;i++)
  {
     hash +=(int) ((int)str[i]) * Math.Pow(2, str.Length - i);
  }
  return hash;
}





string GetTicketHash(string str)
{
   const string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   byte[] bytes = Encoding.UTF8.GetBytes(str);

   SHA256Managed hashstring = new SHA256Managed();
   byte[] hash = hashstring.ComputeHash(bytes);

   char[] hash2 = new char[16];

   // Note that here we are wasting bits of hash! 
   // But it isn't really important, because hash.Length == 32
   for (int i = 0; i < hash2.Length; i++)
   {
     hash2[i] = chars[hash[i] % chars.Length];
   }

   return new string(hash2);
 }
于 2021-04-06T18:13:44.940 回答