Rust中CharRange与ByteRange高效转换方案问询

问题背景 #

我使用的一个外部库，其字符串表示等价于&[char]，该库的部分编辑接口接受type CharRange = Range<usize>类型的范围输入（基于char的偏移量）；而其他Rust库采用type ByteRange = Range<usize>（基于u8的偏移量）。

目前我用的是O(n)复杂度的转换算法，但存在性能瓶颈，想知道有没有高效的数据结构能实现二者间的转换。原转换代码如下：

type CharRange = Range<usize>;
type ByteRange = Range<usize>;

fn byte_range_to_char_range(text: &str, byte_range: ByteRange) -> CharRange {
    let start = text[..byte_range.start].chars().count();
    let end = text[..byte_range.end].chars().count();
    start..end
}

fn char_range_to_byte_range(text: &str, char_range: CharRange) -> ByteRange {
    let start = text.char_indices().nth(char_range.start).map(|(i, _)| i).unwrap_or(0);
    let end = text.char_indices().nth(char_range.end).map(|(i, _)| i).unwrap_or(text.len());
    start..end
}

高效转换方案 #

核心思路是预构建偏移映射表，利用字符串内容固定时（或修改频率远低于转换频率时）的特性，将O(n)的单次转换开销分摊到初始化阶段，后续转换操作可做到O(1)或O(log n)时间复杂度。

1. 全映射数组版本（O(1)转换，O(n)内存） #

预先遍历字符串一次，构建两个数组：记录每个字节位置对应的字符索引，以及每个字符起始的字节位置。

use std::ops::Range;

type CharRange = Range<usize>;
type ByteRange = Range<usize>;

struct StringOffsetMap {
    // 索引=字节位置，值=对应字符索引
    byte_to_char: Vec<usize>,
    // 索引=字符索引，值=对应起始字节位置
    char_to_byte: Vec<usize>,
    total_bytes: usize,
    total_chars: usize,
}

impl StringOffsetMap {
    fn new(text: &str) -> Self {
        let mut byte_to_char = vec![0; text.len()];
        let mut char_to_byte = Vec::new();
        let mut current_char_idx = 0;

        for (char_start_byte, c) in text.char_indices() {
            char_to_byte.push(char_start_byte);
            // 填充当前字符覆盖的所有字节位置对应的字符索引
            let char_len = c.len_utf8();
            for offset in 0..char_len {
                if let Some(entry) = byte_to_char.get_mut(char_start_byte + offset) {
                    *entry = current_char_idx;
                }
            }
            current_char_idx += 1;
        }

        StringOffsetMap {
            byte_to_char,
            char_to_byte,
            total_bytes: text.len(),
            total_chars: current_char_idx,
        }
    }

    fn byte_range_to_char_range(&self, byte_range: ByteRange) -> CharRange {
        let start = if byte_range.start >= self.total_bytes {
            self.total_chars
        } else {
            self.byte_to_char[byte_range.start]
        };
        let end = if byte_range.end >= self.total_bytes {
            self.total_chars
        } else {
            self.byte_to_char[byte_range.end]
        };
        start..end
    }

    fn char_range_to_byte_range(&self, char_range: CharRange) -> ByteRange {
        let start = self.char_to_byte.get(char_range.start).copied().unwrap_or(self.total_bytes);
        let end = self.char_to_byte.get(char_range.end).copied().unwrap_or(self.total_bytes);
        start..end
    }
}

2. 紧凑前缀和版本（O(log n)转换，O(k)内存，k为字符数量） #

如果字符串超大、内存紧张，可改用前缀和数组存储每个字符的结束字节位置，通过二分查找实现转换，大幅降低内存占用：

use std::ops::Range;

type CharRange = Range<usize>;
type ByteRange = Range<usize>;

struct CompactStringOffsetMap {
    // 每个字符的结束字节位置（即下一个字符的起始位置）
    char_end_bytes: Vec<usize>,
    total_bytes: usize,
    total_chars: usize,
}

impl CompactStringOffsetMap {
    fn new(text: &str) -> Self {
        let mut char_end_bytes = Vec::new();
        let mut current_byte = 0;
        for c in text.chars() {
            current_byte += c.len_utf8();
            char_end_bytes.push(current_byte);
        }
        CompactStringOffsetMap {
            char_end_bytes,
            total_bytes: text.len(),
            total_chars: char_end_bytes.len(),
        }
    }

    fn byte_to_char(&self, byte_pos: usize) -> usize {
        if byte_pos >= self.total_bytes {
            return self.total_chars;
        }
        // 二分查找第一个大于byte_pos的结束位置，索引即为字符索引
        self.char_end_bytes.partition_point(|&end| end <= byte_pos)
    }

    fn byte_range_to_char_range(&self, byte_range: ByteRange) -> CharRange {
        let start = self.byte_to_char(byte_range.start);
        let end = self.byte_to_char(byte_range.end);
        start..end
    }

    fn char_to_byte(&self, char_pos: usize) -> usize {
        match char_pos {
            0 => 0,
            pos if pos >= self.total_chars => self.total_bytes,
            _ => self.char_end_bytes[char_pos - 1],
        }
    }

    fn char_range_to_byte_range(&self, char_range: CharRange) -> ByteRange {
        let start = self.char_to_byte(char_range.start);
        let end = self.char_to_byte(char_range.end);
        start..end
    }
}

使用说明 #

• 若字符串内容固定，初始化一次映射表后，所有转换操作均为常数或对数时间，适合高频转换场景。
• 若字符串频繁修改，需权衡初始化开销与转换收益：当转换操作远多于修改操作时，仍能显著提升性能。

内容的提问来源于stack exchange，提问作者Aster