将字节数组转换为任意基数

Question

我有一个字节数组（任意长度），我想使用我自己的基本编码器将此数组编码为字符串。在 .NET 中是标准的 Base64 编码器，但是如果我想用 Base62、Base53 或Base13？

是否有可能创建这样的通用基础编码器？

我知道我可以用简单的方法做到这一点，即为每个字节保留固定数量的字符（在Base62的情况下，这将是5个字符），并进行直接字节->字符编码，但我会浪费空间，因为 5 个 Base62 字符能够包含超过 1 个字节，但少于 2 个字节。

我应该如何编写这样的编码器？或者已经有一些课程可以做到这一点？
请注意，我还需要通用解码器，否则这对我来说毫无用处。

资源

由于该解决方案是已知的（使用 BigInteger），我只想在这里放置一些与 BigInteger 类相关的资源，因为它在 .NET 3.5 中不可用：

C# 中的大整数
http://intx.codeplex.com/
https:/ /svn.apache.org/repos/asf/incubator/heraldry/libraries/csharp/openid/trunk/Mono/Mono.Math/BigInteger.cs
http://www.codeproject.com/KB/cs/BigInteger_Library.aspx
http://www.codeproject.com/KB/cs/biginteger.aspx

Answer 1

有点晚了，但是......

因为您的规范要求任意数量的位，所以您必须有一个可以使用任意数量的位的整数类型。如果您不能以 .NET 4.0 为目标，您将不得不在某个地方乞求、借用或窃取 BigInteger 实现（也许是 .NET 4.0）。

public static class GenericBaseConverter
{
    public static string ConvertToString(byte[] valueAsArray, string digits, int pad)
    {
        if (digits == null)
            throw new ArgumentNullException("digits");
        if (digits.Length < 2)
            throw new ArgumentOutOfRangeException("digits", "Expected string with at least two digits");

        BigInteger value = new BigInteger(valueAsArray);
        bool isNeg = value < 0;
        value = isNeg ? -value : value;

        StringBuilder sb = new StringBuilder(pad + (isNeg ? 1 : 0));

        do
        {
            BigInteger rem;
            value = BigInteger.DivRem(value, digits.Length, out rem);
            sb.Append(digits[(int)rem]);
        } while (value > 0);

        // pad it
        if (sb.Length < pad)
            sb.Append(digits[0], pad - sb.Length);

        // if the number is negative, add the sign.
        if (isNeg)
            sb.Append('-');

        // reverse it
        for (int i = 0, j = sb.Length - 1; i < j; i++, j--)
        {
            char t = sb[i];
            sb[i] = sb[j];
            sb[j] = t;
        }

        return sb.ToString();

    }

    public static BigInteger ConvertFromString(string s, string digits)
    {
        BigInteger result;

        switch (Parse(s, digits, out result))
        {
            case ParseCode.FormatError:
                throw new FormatException("Input string was not in the correct format.");
            case ParseCode.NullString:
                throw new ArgumentNullException("s");
            case ParseCode.NullDigits:
                throw new ArgumentNullException("digits");
            case ParseCode.InsufficientDigits:
                throw new ArgumentOutOfRangeException("digits", "Expected string with at least two digits");
            case ParseCode.Overflow:
                throw new OverflowException();
        }

        return result;
    }

    public static bool TryConvertFromString(string s, string digits, out BigInteger result)
    {
        return Parse(s, digits, out result) == ParseCode.Success;
    }

    private enum ParseCode
    {
        Success,
        NullString,
        NullDigits,
        InsufficientDigits,
        Overflow,
        FormatError,
    }

    private static ParseCode Parse(string s, string digits, out BigInteger result)
    {
        result = 0;

        if (s == null)
            return ParseCode.NullString;
        if (digits == null)
            return ParseCode.NullDigits;
        if (digits.Length < 2)
            return ParseCode.InsufficientDigits;

        // skip leading white space
        int i = 0;
        while (i < s.Length && Char.IsWhiteSpace(s[i]))
            ++i;
        if (i >= s.Length)
            return ParseCode.FormatError;

        // get the sign if it's there.
        BigInteger sign = 1;
        if (s[i] == '+')
            ++i;
        else if (s[i] == '-')
        {
            ++i;
            sign = -1;
        }

        // Make sure there's at least one digit
        if (i >= s.Length)
            return ParseCode.FormatError;


        // Parse the digits.
        while (i < s.Length)
        {
            int n = digits.IndexOf(s[i]);
            if (n < 0)
                return ParseCode.FormatError;
            BigInteger oldResult = result;
            result = unchecked((result * digits.Length) + n);
            if (result < oldResult)
                return ParseCode.Overflow;

            ++i;
        }

        // skip trailing white space
        while (i < s.Length && Char.IsWhiteSpace(s[i]))
            ++i;

        // and make sure there's nothing else.
        if (i < s.Length)
            return ParseCode.FormatError;

        if (sign < 0)
            result = -result;

        return ParseCode.Success;
    }
}

Answer 2

如果性能不是问题，请使用 BigInteger类在后台。您有一个采用字节数组的 BigInteger 构造函数，然后您可以手动运行除法和模数循环来获取其他非标准基数的表示形式。

另请查看此。

Answer 3

这是我的 博客 的副本，我希望对您有所帮助（以及为什么）我转换为 Base62

我目前正在开发自己的 url 缩短器：konv.es。为了创建尽可能短的 url 字符哈希，我使用字符串的 GetHashCode() 方法，然后将结果数字转换为基数 62 ([0-9a-zA-Z])。迄今为止我发现的进行转换的最优雅的解决方案（这也是收益率回报的一个方便的花花公子的例子）是：

public static IEnumerable<char> ToBase62(int number)
    {
        do
        {
            yield return "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"[number % 62];
            number /= 62;

        } while (number > 0);
    }

额外的信用：重构作为扩展方法

Answer 4

BASE64 效果很好，因为 64 是 2 的幂 (2^6)，因此每个字符保存 6 位数据，3 个字节 (3 * 8 = 24 位) 可以编码为 4 个字符 (4 * 6 = 24)。编码&解码可以仅向下位移位。

对于不与 2 的幂对齐的基数（例如基数 62 或基数 53），则必须将尝试编码的消息视为一个长数，并对其执行除法和模运算。您可能最好使用 Base32 编码并浪费一些带宽。

Answer 5

您可以从 Base32 由 Michael Giagnocavo 实施。

Answer 6

受到 Steve Konves 的回答的启发

using System.Numerics;

const string base62Chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string base26Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

static void Main() {
    string id = "xAQ0f58JgG";

    BigInteger i = fromBaseX(id, base62Chars);
    Console.WriteLine(i);

    string c = ToBaseX(i, base62Chars);
    Console.WriteLine(c);

    string c2 = ToBaseX(i, base26Chars);
    Console.WriteLine(c2);

    BigInteger i2 = fromBaseX(c2, base26Chars);
    Console.WriteLine(i2);
}

public static string ToBaseX(BigInteger number, string baseX)
{
    int l = baseX.Length;
    string result = "";
    while (number > 0)
    {
        BigInteger remainder = number % l;
        int index = (int)remainder;
        if (index >= l)
        {
            throw new ArgumentException($"Cannot convert {number} ToBaseX {baseX}");
        }
        result += baseX[index];
        number /= l;
    }
    return result;
}

public static BigInteger fromBaseX(string input, string baseX)
{
    int l = baseX.Length;
    BigInteger result;
    int pow = 0;
    foreach (char c in input)
    {
        int index = baseX.IndexOf(c);
        if (index < 0)
        {
            throw new ArgumentException($"Cannot convert {input} fromBaseX {baseX}");
        }
        BigInteger additions = BigInteger.Pow(l, pow) * index;
        result += additions;
        pow++;
    }
    return result;
}

Answer 7

另一个值得关注的示例是 Ascii85，用于 Adob​​e PostScript 和 PDF 文档。在Ascii85中，5个字符用于编码4个字节。您可以算出此编码的效率为 (256^4)/(85^5) = 96.8%。这是实际使用的位组合的分数。

因此，无论您想要使用什么新基数来编码数据，如果您想最大限度地提高编码效率，您都需要寻找一种能够使其略高于 256 次方的幂。对于每个基地来说这可能并不容易。检查基数 53 表明，您可能得到的最好结果是使用 7 个字节来编码 5 个字节（效率为 93.6%），除非您想使用 88 个字节来编码 63 个字节。

Answer 8

我写了一篇文章< /a> 它描述了 Python 中的一个解决方案，可以完全解决您的问题。我没有使用 Python 的非常特殊的功能来获得可以轻松用其他语言实现的解决方案。您可能会看一下并确定它是否符合您的需求。

Answer 9

CodeReview 上的帖子提示我创建一个 RadixEncoding 类它能够处理字节数组与基数 N 字符串的编码/解码。

该类可以在此问答线程中找到，以及有关处理 BigInteger、字节序支持和类整体性能时的一些边缘情况（及其解决方案）的文档

Answer 10

以下是将字节数组转换为 Base64 的示例代码片段。关于此有一篇非常好的文章，我参考了 这个。

public class Test {

    private static final char[] toBase64URL = {
            'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
            'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
            'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-', '_'
    };

    public static void main(String[] args) {

        byte[] mess = "ABC123".getBytes();

        byte[] masks = { -128, 64, 32, 16, 8, 4, 2, 1 };
        StringBuilder builder = new StringBuilder();

        for(int i = 0; i < mess.length; i++) {
            for (byte m : masks) {
                if ((mess[i] & m) == m) {
                    builder.append('1');
                } else {
                    builder.append('0');
                }
            }
        }

        System.out.println(builder.toString());

        int i =0;
        StringBuilder output = new StringBuilder();
        while (i < builder.length()){
            String part = builder.substring(i, i+6);
            int index = Integer.parseInt(part, 2);
            output.append(toBase64URL[index]);
            i += 6;
        }

        System.out.println(output.toString());

    }
}