查找最长的UTF-8序列而不会破坏多字节序列

Question

我需要截断UTF-8编码的字符串，以使其不超过以字节为单位的预定义大小。特定协议还要求截断的字符串仍然形成有效的UTF-8编码，即，不得拆分多字节序列。

给定UTF-8编码的结构，我可以继续前进，计算每个代码点的编码大小，直到达到最大字节数为止。O（n）并不是很吸引人。有没有一种算法可以更快地完成，最好在（摊销）O（1）时间内完成？

Answer 1

更新2019-06-24： 经过一夜的睡眠，这个问题似乎比我第一次尝试看起来要容易得多。由于历史原因，我在下面留下了先前的答案。

UTF-8编码是自同步的。这使得可以确定符号流中的任意选择的代码单元是否是代码序列的开始。UTF-8序列可以在代码序列开头的左侧拆分。

代码序列的开头可以是ASCII字符（0xxxxxxxb），也可以11xxxxxxb是多字节序列中的前导字节（）。尾随字节遵循模式10xxxxxxb。UTF-8编码的开头满足条件(code_unit & 0b11000000) != 0b10000000，换句话说：它不是尾随字节。

通过应用以下算法，可以在恒定时间（O（1））中确定不超过请求字节数的最长UTF-8序列：

1. 如果输入不超过请求的字节数，则返回实际的字节数。
2. 否则，循环到开头（在请求的字节数之后开始一个代码单元），直到找到序列的开头。将字节计数返回到序列开头的左侧。

输入代码：

#include <string_view>

size_t find_max_utf8_length(std::string_view sv, size_t max_byte_count)
{
    // 1. Input no longer than max byte count
    if (sv.size() <= max_byte_count)
    {
        return sv.size();
    }

    // 2. Input longer than max byte count
    while ((sv[max_byte_count] & 0b11000000) == 0b10000000)
    {
        --max_byte_count;
    }
    return max_byte_count;
}

这个测试代码

#include <iostream>
#include <iomanip>
#include <string_view>
#include <string>

int main()
{
    using namespace std::literals::string_view_literals;

    std::cout << "max size output\n=== ==== ======" << std::endl;

    auto test{u8"€«test»"sv};
    for (size_t count{0}; count <= test.size(); ++count)
    {
        auto byte_count{find_max_utf8_length(test, count)};
        std::cout << std::setw(3) << std::setfill(' ') << count
                  << std::setw(5) << std::setfill(' ') << byte_count
                  << " " << std::string(begin(test), byte_count) << std::endl;
    }
}

产生以下输出：

max size output
=== ==== ======
  0    0 
  1    0 
  2    0 
  3    3 €
  4    3 €
  5    5 €«
  6    6 €«t
  7    7 €«te
  8    8 €«tes
  9    9 €«test
 10    9 €«test
 11   11 €«test»

该算法仅对UTF-8编码进行操作。它不会尝试以任何方式处理Unicode。尽管它将始终产生有效的UTF-8编码序列，但是编码的代码点可能无法形成有意义的Unicode字素。

该算法在恒定时间内完成。不管输入大小如何，如果每个UTF-8编码的当前限制为4个字节，则最终循环最多旋转3次。万一更改了UTF-8编码以允许每个编码的代码点最多5或6个字节，该算法将在恒定时间内继续工作并完成。

先前的答案

可以通过将问题分解为以下情况在O（1）中完成：

1. 输入不超过请求的字节数。在这种情况下，只需返回输入即可。
2. 输入的长度大于请求的字节数。在index处找出编码内的相对位置max_byte_count - 1：
   1. 如果这是一个ASCII字符（未设置最高位0xxxxxxxb），则我们处于自然边界，可以在其后立即截断该字符串。
   2. 否则，我们将位于多字节序列的开头，中间或结尾。要找出位置，请考虑以下字符。如果它是ASCII字符（0xxxxxxxb）或多字节序列的开头（11xxxxxxb），则我们位于多字节序列的末尾，即自然边界。
   3. 否则，我们将处于多字节序列的开头或中间。迭代到字符串的开头，直到找到多字节编码（11xxxxxxb）的开头。在该字符之前剪切字符串。

给定最大字节数，以下代码将计算截断字符串的长度。输入需要形成有效的UTF-8编码。

#include <string_view>

size_t find_max_utf8_length(std::string_view sv, size_t max_byte_count)
{
    // 1. Input no longer than max byte count
    if (sv.size() <= max_byte_count)
    {
        return sv.size();
    }

    // 2. Input longer than max byte count
    while ((sv[max_byte_count] & 0b11000000) == 0b10000000)
    {
        --max_byte_count;
    }
    return max_byte_count;
}

以下测试代码

#include <iostream>
#include <iomanip>
#include <string_view>
#include <string>

int main()
{
    using namespace std::literals::string_view_literals;

    std::cout << "max size output\n=== ==== ======" << std::endl;

    auto test{u8"€«test»"sv};
    for (size_t count{0}; count <= test.size(); ++count)
    {
        auto byte_count{find_max_utf8_length(test, count)};
        std::cout << std::setw(3) << std::setfill(' ') << count
                  << std::setw(5) << std::setfill(' ') << byte_count
                  << " " << std::string(begin(test), byte_count) << std::endl;
    }
}

产生以下输出：

max size output
=== ==== ======
  0    0 
  1    0 
  2    0 
  3    3 €
  4    3 €
  5    5 €«
  6    6 €«t
  7    7 €«te
  8    8 €«tes
  9    9 €«test
 10    9 €«test
 11   11 €«test»