实现一个函数来检查字符串/字节数组是否遵循utf-8格式

Question

我正在努力解决这个面试问题.

在明确定义了UTF-8格式之后.例如:1字节:0b0xxxxxxx 2字节:....要求编写一个函数来验证输入是否有效UTF-8.输入将是字符串/字节数组,输出应为是/否.

我有两种可能的方法.

首先,如果输入是一个字符串,因为UTF-8最多是4个字节,在我们删除前两个字符"0b"之后,我们可以使用Integer.parseInt(s)来检查字符串的其余部分是否在范围0到10FFFF.此外,最好检查字符串的长度是否为8的倍数,以及输入字符串是否首先包含全0和1.所以我将不得不经历两次字符串,复杂性将是O(n).

其次,如果输入是字节数组(如果输入是字符串,我们也可以使用此方法),我们检查每个1字节元素是否在正确的范围内.如果输入是一个字符串,首先检查字符串的长度是8的倍数然后检查每个8字符的子字符串是否在该范围内.

我知道有很多关于如何使用Java库检查字符串的解决方案,但我的问题是我应该如何根据问题实现该功能.

非常感谢.

Answer 1

让我们首先看一下UTF-8设计的直观表示.

现在让我们恢复我们要做的事情.

• 循环遍历字符串的所有字符(每个字符都是一个字节).
• 我们需要根据代码点对每个字节应用一个掩码,因为x字符代表实际的代码点.&如果两个操作数都存在,我们将使用二进制AND运算符()将结果复制到结果中.
• 应用掩码的目的是删除尾随位,以便将实际字节作为第一个代码点进行比较.我们将使用0b1xxxxxxx其中1将出现"序列中的字节"时间,其他位将为0 来执行按位操作.
• 然后我们可以与第一个字节进行比较以验证它是否有效,并确定实际字节是什么.
• 如果输入的字符均不包括,则表示该字节无效,我们返回"否".
• 如果我们可以离开循环,这意味着每个字符都是有效的,因此字符串是有效的.
• 确保返回true的比较对应于预期长度.

该方法如下所示:

public static final boolean isUTF8(final byte[] pText) {

    int expectedLength = 0;

    for (int i = 0; i < pText.length; i++) {
        if ((pText[i] & 0b10000000) == 0b00000000) {
            expectedLength = 1;
        } else if ((pText[i] & 0b11100000) == 0b11000000) {
            expectedLength = 2;
        } else if ((pText[i] & 0b11110000) == 0b11100000) {
            expectedLength = 3;
        } else if ((pText[i] & 0b11111000) == 0b11110000) {
            expectedLength = 4;
        } else if ((pText[i] & 0b11111100) == 0b11111000) {
            expectedLength = 5;
        } else if ((pText[i] & 0b11111110) == 0b11111100) {
            expectedLength = 6;
        } else {
            return false;
        }

        while (--expectedLength > 0) {
            if (++i >= pText.length) {
                return false;
            }
            if ((pText[i] & 0b11000000) != 0b10000000) {
                return false;
            }
        }
    }

    return true;
}

编辑:实际的方法不是原始方法(几乎,但不是),并从这里被盗.根据@EJP评论原来的那个没有正常工作.

Answer 2

嗯，我很感谢您的评论和答案。首先，我必须承认这是“另一个愚蠢的面试问题”。确实，在 Java 中 String 已经被编码了，所以它总是与 UTF-8 兼容。检查它的一种方法是给定一个字符串：

public static boolean isUTF8(String s){
    try{
        byte[]bytes = s.getBytes("UTF-8");
    }catch(UnsupportedEncodingException e){
        e.printStackTrace();
        System.exit(-1);
    }
    return true;
}

但是，由于所有可打印字符串都是 unicode 形式，所以我没有机会得到错误。

其次，如果给定一个字节数组，它将始终在 -2^7(0b10000000) 到 2^7(0b1111111) 范围内，因此它始终在有效的 UTF-8 范围内。

我对这个问题的最初理解是，给定一个字符串，比如“0b11111111”，检查它是否是有效的UTF-8，我想我错了。

此外，Java确实提供了将字节数组转换为字符串的构造函数，如果您对decode方法感兴趣，请查看这里。

另一件事是，如果使用另一种语言，上述答案将是正确的。唯一的改进可能是：

2003年11月，RFC 3629限制UTF-8以U+10FFFF结尾，以匹配UTF-16字符编码的限制。这删除了所有 5 字节和 6 字节序列，以及大约一半的 4 字节序列。

所以4个字节就足够了。

我绝对同意这一点，所以如果我错了请纠正我。多谢。