c++ - 在不破坏多字节序列的情况下找到最长的 UTF-8 序列

Question

我需要将 UTF-8 编码的字符串截断为不超过预定义的字节大小。特定协议(protocol)还要求，截断后的字符串仍然形成有效的 UTF-8 编码，即不能拆分多字节序列。

鉴于 structure of the UTF-8 encoding ，我可以继续前进，计算每个代码点的编码大小，直到达到最大字节数。不过，O(n) 并不是很吸引人。是否有一种算法可以更快地完成，最好在(摊销的)O(1) 时间内完成？

Answer 1

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

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

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

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

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;
}

这test code

#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. 输入比请求的字节数长。在索引 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. No longer than max byte count
    if (sv.size() <= max_byte_count)
    {
        return sv.size();
    }

    // 2. Longer than byte count
    auto c0{static_cast<unsigned char>(sv[max_byte_count - 1])};
    if ((c0 & 0b10000000) == 0)
    {
        // 2.1 ASCII
        return max_byte_count;
    }

    auto c1{static_cast<unsigned char>(sv[max_byte_count])};
    if (((c1 & 0b10000000) == 0) || ((c1 & 0b11000000) == 0b11000000))
    {
        // 2.2. At end of multi-byte sequence
        return max_byte_count;
    }

    // 2.3. At start or middle of multi-byte sequence
    unsigned char c{};
    do
    {
        --max_byte_count;
        c = static_cast<unsigned char>(sv[max_byte_count]);
    } while ((c & 0b11000000) != 0b11000000);
    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;
    }
}

产生this output :

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»