UTF-8验证

Question

我最近解决了"UTF-8验证“LeetCode问题：

UTF8中的字符可以从1字节长到4字节，受以下规则约束:对于1字节字符，第一位是0，然后是它的unicode代码。对于n字节字符，第一个n位都是一个人的，n+1位是0，其次是n-1字节，最重要的2位是10。这就是UTF-8编码的工作方式: Char。编号范围: UTF-8八进制序列(十六进制)x(二进制) --------------------+--------------------------------------------- 0000-0000 007F =0xxxxxxxx 0000 0080-0000 07 UTF=110 range 10 0xxxxxxx 0000 0800-0000 FFFF \1110xxxxx 10xxxxxx 10xxxxx0001 0000-0010 FFFF 11110xxxxxx10xxxxx10 xxxxxxxxxxxxx10xxxxx10xxxxx 10 10xxxxxx给出一个表示数据的整数数组，返回是否为有效的utf-8编码。注意:输入是一个整数数组。仅使用每个整数中最小的8位来存储数据。这意味着每个整数只代表1字节的数据。示例1：data = [197, 130, 1]，它表示八进制序列：11000101 10000010 00000001。返回真。它是2字节字符的有效utf-8编码，后面是1字节字符.示例2：data = [235, 140, 4]，它表示八进制序列：11101011 10001100 00000100。还假。前3位都是一个人的，第4位是0，这意味着它是一个3字节字符。下一个字节是以10开头的连续字节，这是正确的。但是第二个连续字节不以10开头，因此它是无效的。

该守则行得通，并为司法部所接受：

NUMBER_OF_BITS_PER_BLOCK = 8
MAX_NUMBER_OF_ONES = 4


class Solution(object):
    def validUtf8(self, data):
        """
        :type data: List[int]
        :rtype: bool
        """
        index = 0
        while index < len(data):
            number = data[index] & (2 ** 7)
            number >>= (NUMBER_OF_BITS_PER_BLOCK - 1)
            if number == 0:  # single byte char
                index += 1
                continue

            # validate multi-byte char
            number_of_ones = 0
            while True:  # get the number of significant ones
                number = data[index] & (2 ** (7 - number_of_ones))
                number >>= (NUMBER_OF_BITS_PER_BLOCK - number_of_ones - 1)
                if number == 1:
                    number_of_ones += 1
                else:
                    break

                if number_of_ones > MAX_NUMBER_OF_ONES:
                    return False  # too much ones per char sequence

            if number_of_ones == 1:
                return False  # there has to be at least 2 ones

            index += 1  # move on to check the next byte in a multi-byte char sequence

            # check for out of bounds and exit early
            if index >= len(data) or index >= (index + number_of_ones - 1):
                return False  

            # every next byte has to start with "10"
            for i in range(index, index + number_of_ones - 1):
                number = data[i]

                number >>= (NUMBER_OF_BITS_PER_BLOCK - 1)
                if number != 1:
                    return False
                number >>= (NUMBER_OF_BITS_PER_BLOCK - 1)
                if number != 0:
                    return False

                index += 1

        return True

我一直在努力记住位操作技巧，并且试图在不查看它们的情况下解决这个问题--因此，我认为代码重载了左、右移位和两次乘法的幂。

我是不是把问题弄得太复杂了？在拟议的解决方案中，您会改进什么？有更好的办法吗？

Answer 1

这比使用位迭代器要复杂得多。将一个数字更改为一个位列表非常简单，创建一个迭代器也相当简单。这可以通过以下方式实现：

def to_bits(bytes):
    for byte in bytes:
        num = []
        exp = 1 << NUMBER_OF_BITS_PER_BLOCK
        while exp:
            exp >>= 1
            num.append(bool(byte & exp))
        yield num

在这之后，你只需要做问题中的检查，问题的布局方式。首先，检查所做的单个字节是否正确。在此之后，您可以找到您需要循环通过的数量，对这个数字进行检查，然后继续循环通过减去一项，并检查它们是否正常。

这可以很容易地更改为使用按位运算符，而不是切片运算符，但我发现它们很难理解。

class Solution(object):
    def validUtf8(self, data):
        """
        :type data: List[int]
        :rtype: bool
        """
        bits = to_bits(data)
        for byte in bits:
            # single byte char
            if byte[0] == 0:
                continue

            # multi-byte character
            amount = sum(takewhile(bool, byte))
            if amount <= 1:
                return False
            if amount >= MAX_NUMBER_OF_ONES:
                return False

            for _ in range(amount - 1):
                try:
                    byte = next(bits)
                except StopIteration:
                    return False
                if byte[0:2] != [1, 0]:
                    return False
        return True

Answer 2

我想是的，你太复杂了。

按位运算是用来挤压机器的每一点性能的，但是使用它，像Python这样的解释语言就会完全失败。

如果您想加快速度，那么您应该使用C，如果您想使用Python，您最好使这个习惯用法而不用担心性能，这样您就可以使用这个脚本来甲骨文测试您编写的C脚本。

简而言之，使用内置的字符串操作工具使这个问题变得简单：

def valid_unicode(blocks):
    """
    A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

    For 1-byte character, the first bit is a 0, followed by its unicode code.

    For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

    Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

    Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

    >>> valid_unicode([197, 130, 1])
    True
    >>> valid_unicode([235, 140, 4])
    False

    """
    successive_10 = 0
    for b in blocks:
        b = bin(b).replace('0b','').rjust(8, '0')
        if successive_10 != 0:
            successive_10 -= 1
            if not b.startswith('10'):
                return False
        elif b[0] == '1':
                successive_10 = len(b.split('0')[0]) - 1
    return True

只有10行逻辑，而不是31行，令人惊讶的是(可能是因为您的函数包含了一些冗余的检查)--我的版本也快了一点：

# valid_unicode2 is your function
print( timeit.timeit(lambda: valid_unicode2([197, 130, 1])))
print( timeit.timeit(lambda: valid_unicode([197, 130, 1])) )

给予：

6.9072500330003095
6.539016634000291

因此，为正确的工作使用正确的工具，Python不是C，最快的不是您所期望的(所以您不应该像用C编写那样用Python编写)，最好将它作为一种原型语言使用，或者性能不重要的地方。