编写LZ78算法代码遇IndexOutOfBoundsException错误求助

你好！看到你在实现LZ78算法时遇到了数组越界的问题，我来帮你分析一下原因并给出修复方案。

首先，先明确你遇到的错误：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 20, Size: 20

接下来看你的代码：

public class LZ88 { 
    ArrayList input = new ArrayList(); 
    ArrayList stored = new ArrayList(); 
    Iterator counter = input.iterator(); 
    int count=0; 
    int lz78(String x) { 
        int length=x.length(); 
        for(int i=0;i<x.length();i++) { 
            input.add(x.charAt(i)); 
        } 
        for(int i=0;i<=input.size(); i++) { 
            if(stored.contains(input.get(i))==true) { 
                String str ; 
                StringBuilder sb = new StringBuilder(); 
                sb.append(input.get(i)); 
                sb.append(input.get(++i)); 
                str=sb.toString(); 
                while(stored.contains(str)==true) { 
                    sb.append(input.get(++i)); 
                    str=sb.toString(); 
                } 
                stored.add(str); 
                System.out.println(stored); 
            } else { 
                stored.add(x.charAt(i)); 
                System.out.println(stored); 
            } 
        } 
        return 0; 
    } 
    public static void main(String[] args) { 
        String x ="abaababaababbbbbbbba"; 
        LZ88 ob = new LZ88(); 
        ob.lz78(x); 
    } 
}

错误原因分析 #

• 循环边界错误：外层for循环的条件是i<=input.size()，但ArrayList的索引从0开始，最大有效索引是input.size()-1。当i等于input.size()时，调用input.get(i)必然触发越界，这就是你看到Index:20, Size:20的核心原因（你的输入字符串长度为20，input的容量也是20，索引20超出了有效范围）。
• 循环变量被非法修改：在if分支里，你多次使用++i来获取下一个字符，这会直接打乱外层循环的索引节奏。当i已经走到最后一个有效索引时，执行++i会让它超出input的容量，此时再调用input.get(i)就会报错。
• else分支的索引不匹配：else分支里你直接使用x.charAt(i)，但此时i可能已经被内层的++i修改过，和input列表的索引不再对应，甚至可能超出原字符串的长度范围。

修复后的代码 #

针对这些问题，我调整了代码逻辑，既修复了越界问题，也修正了LZ78算法的核心逻辑：

import java.util.ArrayList;

public class LZ78 { 
    ArrayList<String> stored = new ArrayList<>(); 

    void lz78(String x) { 
        int i = 0;
        int length = x.length();
        
        while (i < length) {
            StringBuilder sb = new StringBuilder();
            sb.append(x.charAt(i));
            
            // 寻找最长的已存在于字典中的前缀
            while (i + 1 < length && stored.contains(sb.toString() + x.charAt(i + 1))) {
                sb.append(x.charAt(++i));
            }
            
            String currentStr = sb.toString();
            // 若当前字符串不在字典中，添加进去
            if (!stored.contains(currentStr)) {
                stored.add(currentStr);
            }
            
            System.out.println(stored);
            i++;
        }
    } 

    public static void main(String[] args) { 
        String x = "abaababaababbbbbbbba"; 
        LZ78 ob = new LZ78(); 
        ob.lz78(x); 
    } 
}

修复说明 #

1. 改用while循环控制索引：避免for循环中变量被意外修改导致的索引混乱，更灵活地控制遍历节奏。
2. 严格边界检查：每次获取下一个字符前，先判断i+1是否小于字符串长度，确保不会访问超出范围的索引。
3. 规范LZ78算法逻辑：按照算法思想，每次寻找最长的已存在前缀，再将新的字符串（前缀+下一个字符）加入字典，符合LZ78的编码规则。
4. 添加泛型约束：给ArrayList指定String泛型，避免类型转换隐患，让代码更健壮。

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