Java String Compression – How to Compress a String to a Fixed Length in Java

algorithmcompressionjavastring

I need to achieve string compression to a certain length.

The input is a string consisting of 3 to 16 characters, which can include the English alphabet in lowercase, numbers (0-9), and underlines (or regex: ^[a-z0-9_]{3,16}$).

The English alphabet in any case, numbers, underlines, brackets, and other various utf8 characters can be used to compress the original string. The compressed string must support the reverse process: from the compressed string to the original string.

In my case, the specific length of the compressed string is 6. However, I do not know if it is possible to compress a 16-character string into a "6-character code". If this is not possible, then I suggest increasing it to 7-8 characters.

Example:
input: bestnickname
output: D_1(oP

I've been trying to find various algorithms to solve this problem, but I haven't found one.

Best Answer

If, instead of UTF-8 (as specified in the question), the OP really wants to encode into UTF-16, which is how characters are encoded in Java (since the type char is referenced in the comments and the question is tagged "Java"), then indeed the specified 3 to 16 symbols where each symbol takes one of 37 values can be encoded into six 16-bit values constrained to valid UTF-16, with no surrogate values required, i.e. the old UCS-2. In fact, only 14 bits need to be encoded into each UTF-16 character, so a subset of characters can be chosen to be more readable.

To implement the encoder, first choose 16,384 Unicode characters within the valid code points 0x0000 to 0xffff (which excludes 0xd800 to 0xdfff) to permit in the encoded form. Make a map of 0..16383 to your chosen Unicode characters. Then assign an integer to each 3 to 16 37-value sequence. The calculation can be done using the BigInteger class. This result is an 84-bit integer. Break the 84-bit integer into six 14-bit pieces (fits perfectly!), and write the corresponding code point for each of the 14-bit pieces from your map.

Related Solutions

Java – How to Read and Convert an InputStream into a String

To summarize the other answers, I found 11 main ways to do this (see below). And I wrote some performance tests (see results below):

Ways to convert an InputStream to a String:

Using IOUtils.toString (Apache Utils)

 String result = IOUtils.toString(inputStream, StandardCharsets.UTF_8);

Using CharStreams (Guava)

 String result = CharStreams.toString(new InputStreamReader(
       inputStream, Charsets.UTF_8));

Using Scanner (JDK)

 Scanner s = new Scanner(inputStream).useDelimiter("\\A");
 String result = s.hasNext() ? s.next() : "";

Using Stream API (Java 8). Warning: This solution converts different line breaks (like \r\n) to \n.

 String result = new BufferedReader(new InputStreamReader(inputStream))
   .lines().collect(Collectors.joining("\n"));

Using parallel Stream API (Java 8). Warning: This solution converts different line breaks (like \r\n) to \n.

 String result = new BufferedReader(new InputStreamReader(inputStream))
    .lines().parallel().collect(Collectors.joining("\n"));

Using InputStreamReader and StringBuilder (JDK)

 int bufferSize = 1024;
 char[] buffer = new char[bufferSize];
 StringBuilder out = new StringBuilder();
 Reader in = new InputStreamReader(stream, StandardCharsets.UTF_8);
 for (int numRead; (numRead = in.read(buffer, 0, buffer.length)) > 0; ) {
     out.append(buffer, 0, numRead);
 }
 return out.toString();

Using StringWriter and IOUtils.copy (Apache Commons)

 StringWriter writer = new StringWriter();
 IOUtils.copy(inputStream, writer, "UTF-8");
 return writer.toString();

Using ByteArrayOutputStream and inputStream.read (JDK)

 ByteArrayOutputStream result = new ByteArrayOutputStream();
 byte[] buffer = new byte[1024];
 for (int length; (length = inputStream.read(buffer)) != -1; ) {
     result.write(buffer, 0, length);
 }
 // StandardCharsets.UTF_8.name() > JDK 7
 return result.toString("UTF-8");

Using BufferedReader (JDK). Warning: This solution converts different line breaks (like \n\r) to line.separator system property (for example, in Windows to "\r\n").

 String newLine = System.getProperty("line.separator");
 BufferedReader reader = new BufferedReader(
         new InputStreamReader(inputStream));
 StringBuilder result = new StringBuilder();
 for (String line; (line = reader.readLine()) != null; ) {
     if (result.length() > 0) {
         result.append(newLine);
     }
     result.append(line);
 }
 return result.toString();

Using BufferedInputStream and ByteArrayOutputStream (JDK)

BufferedInputStream bis = new BufferedInputStream(inputStream);
ByteArrayOutputStream buf = new ByteArrayOutputStream();
for (int result = bis.read(); result != -1; result = bis.read()) {
    buf.write((byte) result);
}
// StandardCharsets.UTF_8.name() > JDK 7
return buf.toString("UTF-8");

Using inputStream.read() and StringBuilder (JDK). Warning: This solution has problems with Unicode, for example with Russian text (works correctly only with non-Unicode text)
```
StringBuilder sb = new StringBuilder();
for (int ch; (ch = inputStream.read()) != -1; ) {
    sb.append((char) ch);
}
return sb.toString();
```

Warning:

Solutions 4, 5 and 9 convert different line breaks to one.
Solution 11 can't work correctly with Unicode text

Performance tests

Performance tests for small String (length = 175), url in github (mode = Average Time, system = Linux, score 1,343 is the best):

              Benchmark                         Mode  Cnt   Score   Error  Units
 8. ByteArrayOutputStream and read (JDK)        avgt   10   1,343 ± 0,028  us/op
 6. InputStreamReader and StringBuilder (JDK)   avgt   10   6,980 ± 0,404  us/op
10. BufferedInputStream, ByteArrayOutputStream  avgt   10   7,437 ± 0,735  us/op
11. InputStream.read() and StringBuilder (JDK)  avgt   10   8,977 ± 0,328  us/op
 7. StringWriter and IOUtils.copy (Apache)      avgt   10  10,613 ± 0,599  us/op
 1. IOUtils.toString (Apache Utils)             avgt   10  10,605 ± 0,527  us/op
 3. Scanner (JDK)                               avgt   10  12,083 ± 0,293  us/op
 2. CharStreams (guava)                         avgt   10  12,999 ± 0,514  us/op
 4. Stream Api (Java 8)                         avgt   10  15,811 ± 0,605  us/op
 9. BufferedReader (JDK)                        avgt   10  16,038 ± 0,711  us/op
 5. parallel Stream Api (Java 8)                avgt   10  21,544 ± 0,583  us/op

Performance tests for big String (length = 50100), url in github (mode = Average Time, system = Linux, score 200,715 is the best):

               Benchmark                        Mode  Cnt   Score        Error  Units
 8. ByteArrayOutputStream and read (JDK)        avgt   10   200,715 ±   18,103  us/op
 1. IOUtils.toString (Apache Utils)             avgt   10   300,019 ±    8,751  us/op
 6. InputStreamReader and StringBuilder (JDK)   avgt   10   347,616 ±  130,348  us/op
 7. StringWriter and IOUtils.copy (Apache)      avgt   10   352,791 ±  105,337  us/op
 2. CharStreams (guava)                         avgt   10   420,137 ±   59,877  us/op
 9. BufferedReader (JDK)                        avgt   10   632,028 ±   17,002  us/op
 5. parallel Stream Api (Java 8)                avgt   10   662,999 ±   46,199  us/op
 4. Stream Api (Java 8)                         avgt   10   701,269 ±   82,296  us/op
10. BufferedInputStream, ByteArrayOutputStream  avgt   10   740,837 ±    5,613  us/op
 3. Scanner (JDK)                               avgt   10   751,417 ±   62,026  us/op
11. InputStream.read() and StringBuilder (JDK)  avgt   10  2919,350 ± 1101,942  us/op

Graphs (performance tests depending on Input Stream length in Windows 7 system)

Performance test (Average Time) depending on Input Stream length in Windows 7 system:

 length  182    546     1092    3276    9828    29484   58968

 test8  0.38    0.938   1.868   4.448   13.412  36.459  72.708
 test4  2.362   3.609   5.573   12.769  40.74   81.415  159.864
 test5  3.881   5.075   6.904   14.123  50.258  129.937 166.162
 test9  2.237   3.493   5.422   11.977  45.98   89.336  177.39
 test6  1.261   2.12    4.38    10.698  31.821  86.106  186.636
 test7  1.601   2.391   3.646   8.367   38.196  110.221 211.016
 test1  1.529   2.381   3.527   8.411   40.551  105.16  212.573
 test3  3.035   3.934   8.606   20.858  61.571  118.744 235.428
 test2  3.136   6.238   10.508  33.48   43.532  118.044 239.481
 test10 1.593   4.736   7.527   20.557  59.856  162.907 323.147
 test11 3.913   11.506  23.26   68.644  207.591 600.444 1211.545

JavaScript String – How to Replace All Occurrences of a String

As of August 2020: Modern browsers have support for the String.replaceAll() method defined by the ECMAScript 2021 language specification.

For older/legacy browsers:

function escapeRegExp(string) {
  return string.replace(/[.*+?^${}()|[\]\\]/g, '\\$&'); // $& means the whole matched string
}

function replaceAll(str, find, replace) {
  return str.replace(new RegExp(escapeRegExp(find), 'g'), replace);
}

Here is how this answer evolved:

str = str.replace(/abc/g, '');

In response to comment "what's if 'abc' is passed as a variable?":

var find = 'abc';
var re = new RegExp(find, 'g');

str = str.replace(re, '');

In response to Click Upvote's comment, you could simplify it even more:

function replaceAll(str, find, replace) {
  return str.replace(new RegExp(find, 'g'), replace);
}

Note: Regular expressions contain special (meta) characters, and as such it is dangerous to blindly pass an argument in the find function above without pre-processing it to escape those characters. This is covered in the Mozilla Developer Network's JavaScript Guide on Regular Expressions, where they present the following utility function (which has changed at least twice since this answer was originally written, so make sure to check the MDN site for potential updates):

function escapeRegExp(string) {
  return string.replace(/[.*+?^${}()|[\]\\]/g, '\\$&'); // $& means the whole matched string
}

So in order to make the replaceAll() function above safer, it could be modified to the following if you also include escapeRegExp:

function replaceAll(str, find, replace) {
  return str.replace(new RegExp(escapeRegExp(find), 'g'), replace);
}

Best Answer

Related Solutions

Java – How to Read and Convert an InputStream into a String

JavaScript String – How to Replace All Occurrences of a String

Related Question