字符串重复字符计数压缩（Run-Length Encoding）原理
字符串重复字符计数压缩（run-length encoding, rle）是一种简单的数据压缩算法，其核心思想是将字符串中连续重复出现的字符序列替换为字符本身加上其重复的次数。例如，字符串 "aaabbc" 经过rle压缩后变为 "a3b2c"。这种方法在处理包含大量连续重复字符的数据时非常有效。
常见实现思路与陷阱
实现RLE通常涉及遍历字符串，统计连续相同字符的个数。当遇到不同的字符或到达字符串末尾时，将之前统计的字符和其计数添加到结果字符串中。然而，在这个过程中，一个常见的陷阱是未能正确处理字符串末尾的字符序列。
考虑以下一个尝试实现RLE的Java代码片段：
public class Test12CompressString {
public static String getCompressedString(String str) {
String newString = ""; // 使用String进行拼接效率较低
int count = 1;
int len = str.length()-1; // 最后一个字符的索引
for (int i = 0; i <= len ; i++) {
if(i != len) { // 避免越界访问str.charAt(i+1)
// System.out.println(i); // 调试输出
if(str.charAt(i) == str.charAt(i+1)) {
count++;
continue; // 继续统计
}
// 字符不同时，将之前的字符和计数添加到结果
if(count == 1) {
newString = newString+str.charAt(i);
} else {
newString = newString+str.charAt(i)+count;
}
// 这里的条件判断是多余的，且可能导致逻辑混乱
if ( str.charAt(i) != str.charAt(i+1)) {
count = 1; // 重置计数
continue; // 继续下一轮循环
}
}
}
return newString;
}
public static void main(String[] args) {
String str = "abbbccccc";
String ans = getCompressedString(str);
System.out.print(ans); // 预期输出: ab3c4, 实际输出: ab3
}
}上述代码尝试压缩 "abbbccccc"，但实际输出是 "ab3"，丢失了末尾的 "c4"。其根本原因在于：
- 循环条件与边界处理不当： for (int i = 0; i
- 依赖字符变化触发添加： 代码逻辑中，字符及其计数的添加 (newString = newString+str.charAt(i)+count;) 发生在 str.charAt(i) != str.charAt(i+1) 时。对于字符串末尾的字符序列（如 "ccccc"），当循环处理到最后一个 c 时，由于后面没有字符来触发“字符变化”的条件，这个 c 及其统计的 count 永远不会被添加到 newString。
为了解决这个问题，我们需要确保无论字符是否发生变化，或者是否到达字符串末尾，当前累积的字符和计数都能够被正确地添加到结果中。
立即学习“Java免费学习笔记（深入）”；
I-Shop购物系统
下载
部分功能简介：商品收藏夹功能热门商品最新商品分级价格功能自选风格打印结算页面内部短信箱商品评论增加上一商品，下一商品功能增强商家提示功能友情链接用户在线统计用户来访统计用户来访信息用户积分功能广告设置用户组分类邮件系统后台实现更新用户数据系统图片设置模板管理CSS风格管理申诉内容过滤功能用户注册过滤特征字符IP库管理及来访限制及管理压缩，恢复，备份数据库功能上传文件管理商品类别管理商品添加/修改/
正确的实现方法
一种更健壮的RLE实现方法是，在循环中始终检查当前字符与下一个字符的关系。如果它们相同，则继续计数；如果不同或已到达字符串末尾，则将当前字符和其计数添加到结果中，并重置计数器。
import java.lang.StringBuilder; // 导入StringBuilder类
public class StringCompressor {
/**
* 对给定字符串执行Run-Length Encoding (RLE) 压缩。
* 将连续重复的字符替换为字符本身及其重复次数。
* 例如："abbbccccc" -> "ab3c4"
*
* @param str 待压缩的原始字符串。
* @return 压缩后的字符串。
*/
public static String compressString(String str) {
// 处理空字符串或null输入
if (str == null || str.isEmpty()) {
return "";
}
// 使用StringBuilder提高字符串拼接效率
StringBuilder compressedString = new StringBuilder();
int count = 1; // 记录当前字符的连续重复次数
// 遍历字符串的每个字符
for (int i = 0; i < str.length(); i++) {
// 检查当前字符是否与下一个字符相同，并且确保i+1不会越界
if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) {
count++; // 如果相同，则增加计数
} else {
// 如果字符不同，或者已经到达字符串的末尾
// 将当前字符添加到结果中
compressedString.append(str.charAt(i));
// 如果计数大于1，则将计数也添加到结果中
if (count > 1) {
compressedString.append(count);
}
// 重置计数器为1，准备统计下一个字符序列
count = 1;
}
}
return compressedString.toString(); // 返回最终的压缩字符串
}
public static void main(String[] args) {
// 测试用例
String str1 = "abbbccccc";
System.out.println("Original: \"" + str1 + "\", Compressed: \"" + compressString(str1) + "\""); // 预期: "ab3c4"
String str2 = "aabbcc";
System.out.println("Original: \"" + str2 + "\", Compressed: \"" + compressString(str2) + "\""); // 预期: "a2b2c2"
String str3 = "abc";
System.out.println("Original: \"" + str3 + "\", Compressed: \"" + compressString(str3) + "\""); // 预期: "abc"
String str4 = "aaaaa";
System.out.println("Original: \"" + str4 + "\", Compressed: \"" + compressString(str4) + "\""); // 预期: "a5"
String str5 = "";
System.out.println("Original: \"" + str5 + "\", Compressed: \"" + compressString(str5) + "\""); // 预期: ""
String str6 = "z";
System.out.println("Original: \"" + str6 + "\", Compressed: \"" + compressString(str6) + "\""); // 预期: "z"
}
}代码解析
- 空字符串/Null处理： 函数首先检查输入字符串是否为 null 或空，如果是，则直接返回空字符串，避免后续操作的错误。
- StringBuilder： 使用 StringBuilder 而不是 String 的 + 运算符进行字符串拼接。这是因为 String 的 + 运算会创建大量中间字符串对象，导致性能下降，而 StringBuilder 可以在原有对象上进行修改，效率更高。
- 循环遍历： for (int i = 0; i
-
条件判断：
- if (i + 1
- 如果相同，说明是连续重复的字符，count 递增。
- else 块：如果字符不同，或者 i 已经是字符串的最后一个索引（此时 i + 1
- compressedString.append(str.charAt(i))：将当前字符添加到结果中。
- if (count > 1) { compressedString.append(count); }：如果 count 大于1，说明字符重复了多次，将重复次数也添加到结果中。如果 count 等于1，则不添加数字（例如，"a" 压缩后仍为 "a"，而不是 "a1"）。
- count = 1;：重置 count 为1，为下一个字符序列的统计做准备。
这种实现方式能够正确处理所有情况，包括字符串末尾的字符序列。
注意事项
- 边界条件测试： 在开发任何字符串处理函数时，务必测试各种边界条件，包括空字符串、单字符字符串、所有字符都相同、所有字符都不同等情况。
- 性能优化： 对于频繁的字符串拼接操作，应优先考虑使用 StringBuilder 或 StringBuffer（线程安全版本），而不是 String 的 + 运算符。
- 算法复杂度： 此RLE算法的时间复杂度为O(N)，其中N是字符串的长度，因为它只需要单次遍历字符串。空间复杂度为O(N)（最坏情况下，没有字符重复，结果字符串与原字符串长度相同）。
- 字符集： 此算法适用于任何字符集，因为它只是比较和拼接字符。
总结
实现字符串的重复字符计数压缩（RLE）是一个常见的编程练习，它强调了在循环中正确处理边界条件的重要性。通过仔细设计循环逻辑，特别是在字符序列结束或到达字符串末尾时如何处理累积的字符和计数，可以避免常见的逻辑错误。同时，采用 StringBuilder 进行字符串构建是Java中优化字符串操作的良好实践。掌握这些原则有助于编写出高效且健壮的字符串处理代码。
