动态

详情 返回 返回

你是否也在尋找二進制和字符串的高效轉換算法？ - 动态 详情

做底層框架或技術產品的研發同學在代碼調優過程中不可避免的會遇到序列化/反序列化的場景，除了面向前端的場景一般情況下我們會選取一些二進制序列化框架比如hessian2、Protocol Buffers、Thrift、Avro、Kryo等，它們體積更小、精度更高也更安全，但當需要存儲時需要將其轉為字符串，業界比較普遍使用的方案是Base64 https://en.wikipedia.org/wiki/Base64，它是一種早期且至今仍流行的編碼，於 1987 年 首次作為RFC) 989的一部分指定，對於Java程序員而言使用它非常的便捷，因為它已經被集成進入了jdk中。

import java.util.Base64;

public class Base64Example {

  public static void main(String[] args) {
      // 原始二進制數據
      String originalInput = "Hello, World!";
      
      // 編碼
      String encodedString = Base64.getEncoder().encodeToString(originalInput.getBytes());
      System.out.println("Encoded: " + encodedString);
      
      // 解碼
      byte[] decodedBytes = Base64.getDecoder().decode(encodedString);
      String decodedString = new String(decodedBytes);
      System.out.println("Decoded: " + decodedString);
  }
  
}

文本友好性、支持廣泛、無特殊字符、易於實現等等特點使其成為了二進制轉文本最流行的選擇，但它也有着致命的缺陷——相對於原始二進制數據的大小會產生 33–37% 的開銷（其中 33% 來自編碼本身；最多可增加 4% 來自插入的換行符）。

當數據量不多的時候這些開銷看起來還容易承受，但隨着數據量的不斷攀升找到其它更高效的算法就成為了一種必然的選擇，參考https://en.wikipedia.org/wiki/Binary-to-text_encoding

下表比較了最常用的二進制到文本編碼形式。列出的效率是輸入位數與編碼輸出位數之間的比率（如Base64每三個字節的數據被編碼成四個字符效率為3/4=75%）

編碼 數據類型 效率 備註
Ascii85 隨意的 80％ 這種編碼有幾種變體，Base85，btoa等。
Base32 隨意的 62.5％
Base36 整數 ~64％ 使用阿拉伯數字0–9 和拉丁字母A–Z（ISO 基本拉丁字母）。通常由TinyURL或 SnipURL/Snipr 等URL 重定向系統用作緊湊的字母數字標識符。
Base45 隨意的 約 67% (QR碼97% ) 在 IETF 規範 RFC 9285 中定義，用於在QR 碼中緊湊地包含二進制數據。
Base56 整數 — Base58 編碼的一種變體，進一步刪除了“1”和小寫的“o”字符，以最大程度地降低欺詐和人為錯誤的風險。
Base58 整數 ~73％ 與 Base64 類似，但經過修改，避免使用非字母數字字符（+ 和 /）以及打印時可能看起來模稜兩可的字母（0 – 零，I – 大寫 i，O – 大寫 o 和 l – 小寫 L）。Base58 用於表示比特幣地址。[需要引用]一些消息傳遞和社交媒體系統會在非字母數字字符串上換行。通過不使用URI 保留字符（例如 +）可以避免這種情況。對於SegWit，它已被 Bech32 取代，見下文。
Base62 隨意的 ~74％ 與 Base64 類似，但僅包含字母數字字符。
Base64 隨意的 75％ 一種早期且至今仍流行的編碼，於 1987 年 首次作為RFC 989的一部分指定
Base85 隨意的 80％ Ascii85的修訂版本。
Base91 隨意的 81％ 恆定寬度變體
basE91 隨意的 81％ 可變寬度版本
Base94 隨意的 82％
Base122 隨意的 87.5％
BaseXML 隨意的 83.5％
RFC 1751 (S/KEY) 隨意的 33% “人類可讀的128 位密鑰約定”。與十進制或其他二進制到文本的編碼系統相比，一系列小的英文單詞更易於人類閲讀、記憶和輸入。[ 12 ]每個 64 位數字都映射到六個短詞，每個短詞由 1 到 4 個字符組成，這些短詞來自公共的 2048 字詞典。
S-record (Motorola hex) 隨意的 49.6％ 通常用於編程EPROM、NOR 閃存芯片。49.6% 假設每個記錄有 255 個二進制字節。
Xxencoding 隨意的 ~75% (與 Uuencoding 類似) 建議（並偶爾使用）作為 Uuencoding 的替代品，以避免 ASCII 和 EBCDIC 系統之間的字符集轉換問題，這些問題可能會損壞 Uuencoded 數據
z85 (ZeroMQ spec:32/Z85) 二進制和 ASCII 80%（類似於 Ascii85/Base85） 指定類似於Ascii85的 ASCII 子集，省略一些可能導致程序錯誤的字符（` \ " ' _ , ;）。格式符合ZeroMQ spec:32/Z85。
BinHex 隨意的 75％ 經典版 MacOS
Hexadecimal (Base16) 隨意的 50％ 有大寫和小寫兩種形式
Decimal 整數 ~42％ 通常是人類輸入/輸出的默認表示。
TxMS 十六進制 ~32％ 用於使用UTF-16BE通過短信傳輸區塊鏈交易。
Quoted-printable 文本 ~33–100% [ d ] 保留換行符；在 76 個字符處剪斷行
MIME 隨意的 請參閲Quoted-printable和Base64 用於電子郵件格式的編碼容器
Tektronix hex 隨意的 通常用於編程EPROM、NOR閃存芯片。
Percent-encoding 文本 ( URI )，任意 ( RFC1738 ) 約 40% [ b ]（33–70% [ c ]）
Uuencoding 隨意的 ~60% (最高可達 70% ) 1980 年為Unix-to-Unix複製開發的早期編碼。大部分已被 MIME 和yEnc取代
Intel HEX 隨意的 ≲50% 通常用於編程EPROM、NOR 閃存芯片
Bech32 隨意的 62.5% + 至少 8 個字符（標籤、分隔符、6 個字符的ECC） 規範。用於比特幣和閃電網絡。數據部分採用類似 Base32 的編碼方式，可以使用末尾的 6 個字符BCH 代碼檢查和更正最多 6 個輸入錯誤的字符，這還可以檢查/更正人類可讀部分。Bech32m 變體有一個微妙的變化，使其更能適應長度的變化。

可以看出Base122 http://blog.kevinalbs.com/base122 是其中效率最高的一種算法，它誕生的目的是用在網頁上替換Base64，作者給出了JS的實現https://github.com/kevinAlbs/Base122 ，但不幸的是沒有人將其移植到Java中，因此Java的同學沒辦法直接使用此算法，同時很多跡象表明其與Base64相比穩定性差很多，所以如果想替換Base64同時又對穩定性有一定那麼我們推薦你使用Base85算法，這裏給出一版Java實現（僅供參考）

public class Base85 {

  private final static char[] ALPHA = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.-:+=^!/*?&<>()[]{}@%$#".toCharArray();

  private final static int[] DECODE_CHAR_MAP = {
      68, 0, 84, 83, 82, 72, 0, 75, 76, 70, 65, 0, 63, 62,
      69, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 64, 0, 73, 66, 74, 71,
      81, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
      48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
      77, 0, 78, 67, 0, 0, 10, 11, 12, 13, 14, 15, 16, 17, 18,
      19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
      33, 34, 35, 79, 0, 80};

  private final static int CHAR_INDEX_OFFSET = 33;

  /**
   * Encode the Byte array into Base85 format.
   *
   * @param input byte[] Array of byte to encode.
   * @return String The encoded String
   */
  public static String encode(byte[] input) throws RuntimeException {

    // check input len > 0 or null//
    if (input == null || input.length == 0) {
      throw new IllegalArgumentException("Input is wrong");
    }

    int length = input.length;
    int index = 0;
    byte[] buff = new byte[4];

    // Use mutable StringBuilder for fast string append //
    StringBuilder sb = new StringBuilder((input.length * 5 / 4) + 1);

    while (length >= 4) {

      // copy input to buff //
      buff[3] = input[index++];
      buff[2] = input[index++];
      buff[1] = input[index++];
      buff[0] = input[index++];

      // Append result string to StringBuilder
      sb.append(encodeQuarter(buff));

      length -= 4;
    }

    // Padding zone //
    if (length > 0) {

      buff = new byte[length];

      for (int i = length - 1; i >= 0; i--) {
        buff[i] = input[index++];
      }

      // Append result string to StringBuilder
      sb.append(encodePadding(buff));
    }

    // Return whole string //
    return sb.toString();
  }

  /**
   * Decodes a Base85 encoded string.
   *
   * @param input byte[] String The encoded Base85 String.
   * @return byte[] The decoded array of bytes.
   */
  public static byte[] decode(String input) throws RuntimeException {

    // check input len > 0 or null//
    if (input == null || input.isEmpty()) {
      throw new IllegalArgumentException("Input is wrong");
    }

    int length = input.length();
    int index = 0;

    char[] buff = new char[5];

    ByteBuffer byteBuffer = ByteBuffer.allocate((length * 4 / 5));

    while (length >= 5) {

      buff[0] = input.charAt(index++);
      buff[1] = input.charAt(index++);
      buff[2] = input.charAt(index++);
      buff[3] = input.charAt(index++);
      buff[4] = input.charAt(index++);

      byteBuffer.put(decodeQuarter(buff));

      length -= 5;
    }

    // If last length > 0 Then need padding //
    if (length > 0) {

      // create padding buffer //
      char[] padding = new char[length];

      // copy last input value to padding buffer //
      for (int i = 0; i < length; i++) {
        padding[i] = input.charAt(index++);
      }

      // decode padding //
      byteBuffer.put(decodePadding(padding));
    }

    byteBuffer.flip();

    if (byteBuffer.limit() == 0) {
      throw new RuntimeException("Output is empty!");
    }

    return Arrays.copyOf(byteBuffer.array(), byteBuffer.limit());
  }

  private static char[] encodeQuarter(byte[] data) {

    long value = (data[0] & 0x00000000000000FFL) |
        ((data[1] & 0x00000000000000FFL) << 8) |
        ((data[2] & 0x00000000000000FFL) << 16) |
        ((data[3] & 0x00000000000000FFL) << 24);

    char[] out = new char[5];

    out[0] = ALPHA[(int) ((value / 0x31C84B1L) % 85)];
    out[1] = ALPHA[(int) ((value / 0x95EEDL) % 85)];
    out[2] = ALPHA[(int) ((value / 0x1C39L) % 85)];
    out[3] = ALPHA[(int) ((value / 0x55L) % 85)];
    out[4] = ALPHA[(int) ((value) % 85)];

    return out;
  }

  /**
   * Encode padding scheme
   *
   * @param data byte[] Array of length = 4 of data
   * @return char[] Encoded padding
   */
  private static char[] encodePadding(byte[] data) {

    long value = 0;
    int length = (data.length * 5 / 4) + 1;
    char[] out = new char[length];

    switch (data.length) {
      case 3:
        value |= (data[2] & 0x00000000000000FFL) << 16;
      case 2:
        value |= (data[1] & 0x00000000000000FFL) << 8;
    }

    value |= (data[0] & 0x00000000000000FFL);

    switch (data.length) {
      case 3:
        out[3] = ALPHA[(int) ((value / 0x95EEDL) % 85)];
      case 2:
        out[2] = ALPHA[(int) ((value / 0x1C39L) % 85)];
    }

    out[1] = ALPHA[(int) ((value / 0x55L) % 85)];
    out[0] = ALPHA[(int) ((value) % 85)];

    return out;
  }

  private static byte[] decodeQuarter(char[] data) {

    long value = 0;

    value += DECODE_CHAR_MAP[data[0] - CHAR_INDEX_OFFSET] * 0x31C84B1L;
    value += DECODE_CHAR_MAP[data[1] - CHAR_INDEX_OFFSET] * 0x95EEDL;
    value += DECODE_CHAR_MAP[data[2] - CHAR_INDEX_OFFSET] * 0x1C39L;
    value += DECODE_CHAR_MAP[data[3] - CHAR_INDEX_OFFSET] * 0x55L;
    value += DECODE_CHAR_MAP[data[4] - CHAR_INDEX_OFFSET];

    return new byte[]{
        (byte) (value >>> 24),
        (byte) (value >>> 16),
        (byte) (value >>> 8),
        (byte) (value)
    };

  }

  private static byte[] decodePadding(char[] data) {

    long value = 0;
    int length = data.length * 4 / 5;

    switch (data.length) {
      case 4:
        value += DECODE_CHAR_MAP[data[3] - CHAR_INDEX_OFFSET] * 0x95EEDL;
      case 3:
        value += DECODE_CHAR_MAP[data[2] - CHAR_INDEX_OFFSET] * 0x1C39L;
      case 2:
        value += DECODE_CHAR_MAP[data[1] - CHAR_INDEX_OFFSET] * 0x55L;
    }

    value += DECODE_CHAR_MAP[data[0] - CHAR_INDEX_OFFSET];

    byte[] buff = new byte[length];

    for (int i = length - 1; i >= 0; i--) {
      buff[length - i - 1] = (byte) (value >>> 8 * i);
    }

    return buff;
  }

}

測試用例

public class Base85Test {

  @Test
  public void test() {
    for (int i = 0; i < 1000; i++) {
      byte[] rnd = seedRandomByte(i + 4);
      String encoded = Base85.encode(rnd);
      byte[] decoded = Base85.decode(encoded);
      ArrayAsserts.assertArrayEquals(rnd, decoded);
    }
  }

  @Test
  public void testEncode() {
    // Without padding, normal hello world :) //
    byte[] in_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B};
    Assert.assertEquals("HelloWorld", Base85.encode(in_test), "Assert first HelloWorld");

    // With 1-th padding //
    in_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B, (byte) 0xAF};
    Assert.assertEquals("HelloWorld52", Base85.encode(in_test), "With 1 byte padding");

    // With 2-th padding //
    in_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B, (byte) 0xAF, (byte) 0xBF};
    Assert.assertEquals("HelloWorldqj6", Base85.encode(in_test), "With 2 byte padding");

    // With 3-th padding //
    in_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B, (byte) 0xAF, (byte) 0xBF, (byte) 0xCF};
    Assert.assertEquals("HelloWorld-e:i", Base85.encode(in_test), "With 3 byte padding");

    // Test all byte variation //
    in_test = new byte[256];
    for (int i = 0; i < in_test.length; i++) {
      in_test[i] = (byte) i;
    }

    String testStr = "009c61o!#m2NH?C3>iWS5d]J*6CRx17-skh9337xar." +
        "{NbQB=+c[cR@eg&FcfFLssg=mfIi5%2YjuU>)kTv.7l" +
        "}6Nnnj=ADoIFnTp/ga?r8($2sxO*itWpVyu$0IOwmYv" +
        "=xLzi%y&a6dAb/]tBAI+JCZjQZE0{D[FpSr8GOteoH(" +
        "41EJe-<UKDCY&L:dM3N3<zjOsMmzPRn9PQ[%@^ShV!$" +
        "TGwUeU^7HuW6^uKXvGh.YUh4]Z})[9-kP:p:JqPF+*1" +
        "CV^9Zp<!yAd4/Xb0k*$*&A&nJXQ<MkK!>&}x#)cTlf[" +
        "Bu8v].4}L}1:^-@qDS{";
    Assert.assertEquals(testStr, Base85.encode(in_test), "Full byte field test");

    Base85.encode(null);
  }

  @Test
  public void testDecode() {
    // Without padding, normal hello world :) //
    byte[] out_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B};
    assertArrayEquals("Assert first HelloWorld", out_test, Base85.decode("HelloWorld"));

    // With 1-th padding //
    out_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B, (byte) 0xAF};
    assertArrayEquals("With 1 byte padding", out_test, Base85.decode("HelloWorld52"));

    // With 2-th padding //
    out_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B, (byte) 0xAF, (byte) 0xBF};
    assertArrayEquals("With 2 byte padding", out_test, Base85.decode("HelloWorldqj6"));

    // With 3-th padding //
    out_test = new byte[]{(byte) 0x86, (byte) 0x4F, (byte) 0xD2, (byte) 0x6F, (byte) 0xB5,
        (byte) 0x59, (byte) 0xF7, (byte) 0x5B, (byte) 0xAF, (byte) 0xBF, (byte) 0xCF};
    assertArrayEquals("With 3 byte padding", out_test, Base85.decode("HelloWorld-e:i"));
  }

  @Test
  public void testFullCycle() {
    int len = 1024;

    // Generate random data //
    byte[] seed_test = seedRandomByte(len);

    // Encode 1024 byte (no padding) //
    assertArrayEquals("Test 1024 random byte encode -> decode", seed_test,
        Base85.decode(Base85.encode(seed_test)));

    // Generate random data //
    seed_test = seedRandomByte(len + 1);

    // Encode 1025 byte (1 byte padding) //
    assertArrayEquals("Test 1025 (1 byte padding) random byte encode -> decode", seed_test,
        Base85.decode(Base85.encode(seed_test)));

    // Generate random data //
    seed_test = seedRandomByte(len + 2);

    // Encode 1026 byte (2 byte padding) //
    assertArrayEquals("Test 1026 (2 byte padding) random byte encode -> decode", seed_test,
        Base85.decode(Base85.encode(seed_test)));

    // Generate random data //
    seed_test = seedRandomByte(len + 3);

    // Encode 1027 byte (3 byte padding) //
    assertArrayEquals("Test 1027 (3 byte padding) random byte encode -> decode", seed_test,
        Base85.decode(Base85.encode(seed_test)));
  }

  private byte[] seedRandomByte(int length) {
    byte[] seeds = new byte[length];

    for (int i = 0; i < length; i++) {
      seeds[i] = (byte) (Math.random() * 0xFF);
    }

    return seeds;
  }
}

Base85看上去比Base64只提升了5%的效率但對於海量數據而言5%也是一份不小的收益，更別提因為體積縮小而帶來的帶寬收益，so，享受Base85吧。

base64 , JAVA
user avatar u_16502039 头像 u_11365552 头像 chaochenyinshi 头像 chengxy 头像 wxweven 头像 aishang 头像 enaium 头像 sheyingshichenjian 头像 cumeimaodeyingpan 头像 sulf 头像 uname67 头像 junction_640ae1a257911 头像
点赞 15 用户, 点赞了这篇动态!
点赞

Add a new 评论

Some HTML is okay.