Сжатие строк в Java

Question

Я написал фрагмент кода, который сжимает строки нецифровых символов. например, «aabccccaaa» будет сжиматься до a2b1c4a3. Мне было интересно, способ, которым я достигаю этого, имеет эффективную асимптотику времени выполнения. Есть ли более эффективный способ достижения?

Код указано ниже:

public static String Compress(String s) 
{ 
    if(s.length()<=2) 
    { 
     return s; 
    } 
    int org_length=s.length(); 
    String comp=""; 
    int i=0; 
    while(i<org_length) 
    { 
     Integer lc=1; 
     while(i+1<org_length && s.charAt(i)==s.charAt(i+1)) 
     { 
      lc++; 
      i++; 

     } 
     if(i>=org_length){ 
      comp=comp+s.charAt(s.length()-1)+1; 
     } 
     else{ 
     comp=comp+s.charAt(i)+lc.toString(); 
     } 

     i++; 
    } 
    if(s.length()<=comp.length()) 
    { 
     return s; 
    } 
    return comp; 
} 

Answer 1

Счетчик в то время как следует сравнить запуск из-группы символов до тех пор, пока не изменится или конец строки будет достигнута. Затем просто напишите символ начала группы и захваченную длину. Сложность должна быть O (n).

public String rleCompress (String str) { 
    StringBuilder res = new StringBuilder(); 
    int len = str.length(); 
    for (int i = 0; i < len;) { 
     char c = str[i]; 
     int l = 0; 
     // Always will loop at least once. 
     while (i < len && str[i] == c) { 
     l++; 
     i++; 
     } 
     res.append(c); 
     res.append(l); 
    } 
    return res.toString(); 
} 

(Это «чище» реализация, в основном потому, что она изолирует граничное значение, но имеет ту же общую сложность, предполагая, что строка конкатенации постоянна - надеюсь, понятно, что он читает через строку ровно один раз .)

Однако Run-Length Encoding (RLE) хорош только в особых случаях - в основном, когда одно значение повторяется для много раз. Как и в случае с представленными данными, он сжимается до 80%, но «ababababab» «сжимает» до 200% оригинала!

Для очень коротких (~ 4 + charactes) строк SMAZ может быть уместно: «Smaz - это простая библиотека сжатия, подходящая для сжатия очень коротких строк ». (Он подходит для «текста на английском языке», поэтому он не подходит для этих данных.)

Для коротких строк (~ 60 + символов) реализация zlib/DEFLATE может быть более практичной. (Некоторые реализации DEFLATE будут создавать бесполезный большой словарь, если это не требуется, убедитесь, что он действительно «сжатый» размер, и разрешите альтернативный режим или без сжатия.)