0

我有一个关于使用位向量方法来查找字符串是否具有唯一字符的问题。我已经看到那些解决方案（其中之一）适用于 ASCII 和 UTF-16 字符集。

但是，相同的方法将如何适用于 UTF-32？Java中最长的连续位向量可以是长变量吗？UTF-16 需要 1024 个这样的变量。如果我们采用相同的方法，它将需要 2^26 个长变量（我认为）。是否可以使用位向量来解决如此大的字符集？

4

2 回答 2

3

我认为你在这里遗漏了一些重要的东西。UTF-32 是 Unicode 的编码。Unicode 实际上适合 21 位空间。正如Unicode 常见问题解答所述：

“Unicode 标准对 U+0000..U+10FFFF 范围内的字符进行编码，相当于 21 位代码空间。”

任何在 Unicode 代码空间之外的 UTF-32 “字符”都是无效的……而且您永远不应该在 UTF-32 编码中看到它们String。所以 2^15 长应该就足够了。

在实践中，您不太可能在基本语言平面（平面 0）之外看到代码点。因此，对 BMP 使用位图（即最高 65535 的代码）和HashSet<Integer>对其他窗格使用稀疏数据结构（例如 a ）是有意义的。

您也可以考虑使用orBitSet代替“滚动您自己的”位集数据结构。longlong[]

最后，我不应该认为您链接到的问答中的某些代码不适合在 UTF-16 中查找唯一字符，原因如下：

  • 使用 N 个类型的变量long和一个 switch 语句的想法无法扩展。switch 语句的代码变得庞大且难以管理……并且可能超出 JVM 规范所能处理的范围。（编译方法的最大大小是 2^16 - 1 个字节的字节码，因此对于所有 Unicode 代码空间实现位向量显然是不可行的。）

    使用数组long并摆脱对 ... 的需求是一个更好的主意，因为您有 N 个不同的变量switch，所以它确实存在。long

  • 在 UTF-16 中，每个代码单元（16 位值）编码 1 个代码点（字符）或半个代码点。如果您只是创建代码单元的位图，您将无法正确检测到唯一字符。

于 2015-03-15T01:59:25.187 回答
2

嗯，along包含 64 位信息，而 UTF-32 字符集包含大约 2^21 个元素，这需要 2^21 位信息。如果 UTF-32 数据集使用所有位，则需要 2^26 个长变量是对的。但是，实际上，您只需要 2^13 个long变量（仍然很多）。

如果您假设字符均匀分布在数据集中，则这种低效率是不可避免的，最好的解决方案是使用其他东西，例如 aSet<Long>或 something。但是，英语纯文本的大部分字符往往在 ASCII 范围 (0-127) 内，并且大多数西方语言都相当受限于特定范围，因此您可以对高频区域使用位向量和一个Set或其他与订单无关的高效contains数据结构来表示其余区域。

于 2015-03-15T01:49:18.007 回答