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

问题描述 投票：1回答：3

我想将任何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使其工作。此外，我意识到该函数可以被记忆以加速后续执行，但我在初始执行后性能提高。

java string sorting hash clojure
3个回答
8
投票

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

为了了解为什么这一般是不可能的，考虑一组长度的随机字符串，比如1000只由[A-Za-z0-9]组成。每个字母有62个可能的值，称之为6位数据（稍微向上舍入）。因此，可能的不同值的数量大约是621000，或大约101792.如何计划在哈希函数中对这些值进行编码？保留顺序，以便您可以正确排序"[999 random characters]A"和"[same 999 random characters]B"将需要至少6000位长的哈希码。

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

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

小区（LOG2（AL））

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

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

小区（LOG2（A））

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

0
投票

这个应用程序在JDK中由类java.text.CollationKey涵盖。 CollationKey表示某些字符串（Unicode）归类顺序。

因此，如果您使用的是Java平台，则可以轻松获取校对键并直接对其进行比较 - 这就是它们的用途：

(def root-collator (java.text.Collator/getInstance java.util.Locale/ROOT))

(defn collation-key [s]
  (.getCollationKey root-collator s))

(compare (collation-key "a") (collation-key "b"))  ; => -1

CollationKey有一个toByteArray方法，它返回一个表示键的字节数组。由于这些字节数组可以直接相互比较，因此如果必须，可以将它们的内容倒入大整数：

(defn bigint-key [s]
  (-> s collation-key .toByteArray bigint))

;; these all pass:
(assert (< (bigint-key "a") (bigint-key "b")))
(assert (< (bigint-key "a") (bigint-key "aa")))
(assert (< (bigint-key "aa") (bigint-key "ab")))

（我不是100％确定bigint-key是正确的。整理关键字节数组是无符号的，但java.math.BigInteger字节数组是二进制补码表示;可能需要一些处理符号的腿部工作。）

你强调你对空间/性能有一些限制，所以我不确定这个解决方案是否有用。尽管如此，知道在JDK中存在诸如CollationKey之类的东西并且可以用最少量的代码应用于这个问题是很好的。

0
投票

我不知道Clojure或Java如何处理与C的接口，但这听起来像C标准库的strxfrm函数。也就是说，strxfrm的结果只有在两个字符串都使用相同的LC_COLLATE设置进行转换时才有效。换句话说，将德语单词与法语单词进行比较是没有意义的，因为这些语言对如何对单词进行排序有不同的规则。

如果您可以使用字节串比较的排序规则（这涵盖了我需要的所有时间），那么strxfrm就是您所需要的。但如果你真的需要数字比较，那么你必须做更多。

如果你确实需要数字比较，那么你必须涉及任意精度整数（比如Java的BigInteger;你不需要BigDecimal）。毕竟，你不能将两个七字符串作为64位整数进行比较（通过鸽子原理）。

在这种情况下，最好的办法是将生成的字节字符串解释为任意精度的大端数字。换句话说，如果字节串的长度是七个字节，则需要将结果数构建为(byte_string[0]<<64) + (byte_string[1]<<56) + … + (byte_string[6]<<0)（其中每个字节左移一个总长度减去其位置* 8位）。

我实际上并没有遇到这样一种情况，即以保持校对的方式将字符串转换为任意精度数字非常有用，就像你在这里尝试做的那样。通常，我发现我需要将Unicode字符串转换为字节字符串，在类似memcmp的比较下保留整理顺序。然而，当然可能有一些数据库层需要你要求的东西（大概是使用Elias伽玛编码之类的东西来获得任意精度的数字）。如果这就是你所拥有的，那么使用strxfrm后跟任意精度的大端解释（正如我在这里所描述的）可能就是你所需要的。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.