有效地将任何字符串映射到表示字符串的字典顺序的唯一数字

Question

我想将任何unicode字符串转换为唯一的数字(在Clojure或Java中).我希望生成的数字具有以下属性: - 它对于该字符串是唯一的 - 当一组这样的数字被排序并映射回原始字符串时,字符串将按排序顺序出现.字符串并非事先都知道.

可以这样做的一种方法是:

(defn strval [^String s]
    (bigdec (reduce #(str %1 (format "%05d" (int %2))) "0." s)))

我们可以通过以下方式验证排序顺序是否正确

(assert (< (strval "a") (strval "b")))
(assert (< (strval "a") (strval "aa")))
(assert (< (strval "aa") (strval "ab")))

(忽略,如果你喜欢"int"不一定是获得单个角色的排序顺序的最佳方式.)

对于那些不熟悉Clojure的人,这个算法:

1. 将字符串转换为字符序列
2. 获取一个字符的整数值
3. 将此整数转换为字符串并用零填充它,以便它生成一个包含五个字符的字符串.
4. 将此字符串追加到以"0"开头的结果字符串.
5. 如果有更多字符则返回步骤2,否则返回步骤2
6. 将结果字符串转换为Java BigDecimal

但是,以这种方式创建BigDecimal的过程是次优的:

1. 它依赖于数字和字符串之间的转换,然后返回到最终的数字.
2. 用零填充每个值不会产生最紧凑的表示.

有哪些替代方案可以加速它并尽可能减少生成的数量,同时保留上述的唯一性和排序属性？

注意:该解决方案没有生成BigDecimal,它只需要生成一个数字,但我不知道如何使用BigInteger使其工作.此外,我意识到该函数可以被记忆以加速后续执行,但我在初始执行后性能提高.

Answer 1

一般情况下不可能,但如果事先知道整个字符串的范围,则可能.您要求的是一个保留字典排序顺序的哈希函数.为了做到这一点,哈希函数必须为每个可能的字符串产生一个唯一值 - 即一个哈希函数,在所有可能的输入上没有冲突.在这种情况下,散列值的长度具有等于输入中的信息的位数的下限.

要想知道为什么这一般是不可能的,考虑一组长度的随机字符串,比如1000只包含[A-Za-z0-9].每个字母有62个可能的值,称之为6位数据(稍微向上舍入).因此,可能的不同值的数量约为62 ¹⁰⁰⁰,或约10 ¹⁷⁹².如何计划在哈希函数中编码这些值？保留顺序,以便您可以正确排序"[999 random characters]A","[same 999 random characters]B"并且需要至少6000位长的哈希码.

如果事先知道所有可能的字符串,您可以对列表进行排序并按递增顺序分配哈希值,但这可能不是您想要的.

此外,如果字符串的最大长度有界(即所有字符串都小于某个合理的值),您可能会想出一个有效的编码.您需要确定编码所有可能值所需的总位数,这将是

ceil(log ₂(AL))

其中L是字符串的最大长度,A是字母表的大小,即在最大长度字符串的每个位置可能出现的不同字符的数量.因此,例如,对于最大长度为10和由其组成的字母表[A-Z],所需的位数将是26 ¹⁰的基数2对数,向上舍入为48.

设计适合最佳48位的保持顺序的哈希可能会非常困难.稍微不太理想的方法是计算每个符号所需的位数,即

ceil(log ₂(A))

在你的情况下是5位.将每个8位字节编码为5位,将这些位打包成二进制字符串并将其作为字节流写出.