如何把最多16字节的字符串映射成64位的唯一字符串?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 4699 天前的主题，其中的信息可能已经有所发展或是发生改变。

最多16字节那个,长度可以是1-16字节,每字节可以是所有95个可打印字符.
64字节那个,长度固定64字节,每字节可以是64个可打印字符中的一个,并且每字节在字符串里唯一.

看起来是个比UUID更复杂的活儿......不过确实要用到啊.
没学过算法.

字节

6 条回复 1970-01-01 08:00:00 +08:00

msg7086

2013 年 6 月 14 日

每字节在字符串里唯一？本来我想说base64就行了

013231

2013 年 6 月 14 日

入字符串按字一分成8, 每可能有95^2 = 9025.
出字符串可如此造:
可出在出字符串的64字符排序,然後每8字一, 分成8. 每中的字符按不同序排列, 可表示fatorial(8) = 40320中不同. 40320中出9025, 入字符串每分的9025成一映射表, 直接查表即可.
表看上去大概是子:
第一的表:
'AA' -> 'ABCDEFGH'
'AB' -> 'ABCDEFHG'
'AC' -> 'ABCDEHFG'
...
第二的表:
'AA' -> 'IJKLMNOP'
'AB' -> 'IJKLMNPO'
'AC' -> 'IJKLMPNO'
...
共8的表, 大小(2 + 10) * 9025 * 8 = 722,000字.

luikore

2013 年 6 月 14 日

源字符串里, 可打印字符的码点不超过 127, 故每 2 个字节可以对应成1个unsigned short, 而且不超过 127*256 = 32512

目标字符串里, 8 个不同的字符有 8! = 40320 种排列 > 32512

所以每 2 字节映射到一个无符号 16 位整数, 然后作为下标在预先计算好的, 大小为 40320 的全排列表中查找就可以了

ruby 代码 (to 看不懂的: unpack 就和 php/perl/python 的 unpack 差不多, each 和 each_with_index 相当于 for 循环, to_a 是把range/迭代器转换成数组)

---

CHARS64 = [*'a'..'z', *'A'..'Z', *'0'..'9', '+', '=']
PTABLE = (0..7).to_a.permutation.to_a

s = "hello world" # 源字符串
s_len16 = s.ljust 16, "\0" # 给不足 16 字节的部分补上 nul
r = '' # 目标字符串
s_len16.unpack('S*').each_with_index do |c16, i|
PTABLE[c16].each{|e| r << CHARS64[e + i * 8] }
end
print(r) #=> fbadghcenlmjoikprvuqxwtsDCBEFAzyLJKHNGIMOPQVRUSTWXYZ0123456789+=

xatest

2013 年 6 月 14 日 via iPhone

http://zh.wikipedia.org/zh/Murmur%E5%93%88%E5%B8%8C

zorceta

2013 年 6 月 14 日

@msg7086 其实是改造的b64...
@013231 @luikore 这个想法我其实想过不过当时卡住了一解释明白多了~
@xatest 这个听说过...我慢慢看算法吧.

solos

2013 年 6 月 16 日

MurmurHash or Google CityHash