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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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

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

字节

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

msg7086

2013-06-14 04:26:45 +08:00

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

013231

2013-06-14 05:58:20 +08:00

輸入字符串按兩字節一組分成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-06-14 06:51:48 +08:00

源字符串里, 可打印字符的码点不超过 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-06-14 09:23:14 +08:00 via iPhone

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

zorceta

2013-06-14 12:13:32 +08:00

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

solos

2013-06-16 08:50:27 +08:00

MurmurHash or Google CityHash