有人能解释一下这个进制转换代码吗？

Question

有人能解释一下这个进制转换代码吗？

3

var ShortURL = new function() {

    var _alphabet = '23456789bcdfghjkmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ-_',
        _base = _alphabet.length;
    this.encode = function(num) {
        var str = '';
        while (num > 0) {
            str = _alphabet.charAt(num % _base) + str;
            num = Math.floor(num / _base);
        }
        return str;
    };

    this.decode = function(str) {
        var num = 0;
        for (var i = 0; i < str.length; i++) {
            num = num * _base + _alphabet.indexOf(str.charAt(i));
        }
        return num;
    };

};

我知道编码的原理是将十进制数转换为自定义进制（在这种情况下是自定义字母表/数字）

我不太确定解码的工作原理。为什么我们要将基数乘以当前数字，然后加上字母表的位置号码？我知道将二进制数010转换为十进制数时，我们会这样做

(2 * 0^2) + (2 * 1^1) + (2 * 0 ^ 0) = 2

不确定它在解码算法中是如何表示的。

编辑：我的解码版本

this.decode2 = function (str) {
    var result = 0;
    var position = str.length - 1;
    var value;
    for (var i = 0; i < str.length; i++) {
      value = _alphabet.indexOf(str[i]);
      result += value * Math.pow(_base, position--);
    }
    return result;
  }

这是我编写的自己的解码版本（就像我想在纸上转换一样）。我希望有人能更详细地解释第一个解码版本的工作原理。仍然不明白为什么要将 num * base 相乘并以 0 开头。

- CodeCrack

4

我不明白的是为什么字母表中不包括 0 或 1。 - Pointy

1

@Point，或者aeiouAEIOU - Mulan

如果它是为了人类可读性，那么很可能是为了避免与 o 和 l 混淆。你还会注意到 i 或 I 不在其中。我不确定为什么 a 和 A 也不在其中。或者任何元音，但这可能是为了防止意外拼写单词。 - Nathan K

不确定短网址是否意味着要记住它。 - Ryan

1

@codecrack，你对进制转换熟悉吗？这只是使用自定义字母表将其转换为基数-_alphabet.length。 - Mulan

显示剩余5条评论

3个回答

1

你问：

我想从逻辑角度理解decode函数的工作原理。为什么我们要使用num * base并以num = 0开始。

请翻译成：

我不太确定decode函数是如何工作的。为什么我们要用当前数字乘以基数，然后加上字母表的位置数字？我知道将二进制数010转换为十进制数的方法是：

(2 * 0^2) + (2 * 1^1) + (2 * 0 ^ 0) = 2

decode函数使用Horner's规则进行基数转换，因为它在计算上非常高效：

将变量设置为0，num = 0
将变量num乘以基数
将最高位（最左边的位）的值加到num中，
重复步骤2和3，直到没有要转换的数字为止，
变量num现在包含转换后的值（以10为基数）

使用十六进制数的例子 A5D：

将变量设置为0，num = 0
乘以基数（16），num现在仍然是0
取最高位数字的值（A的数字值为10）并加到num中，num现在为10
重复步骤2，将变量num乘以基数（16），num现在为160
重复步骤3，将十六进制数字5加到num中，num现在为165
重复步骤2，将变量num乘以基数（16），num现在为2640
重复步骤3，将十六进制数字D加到num中（加13）
没有要转换的数字了，变量num现在包含转换后的值（以10进制表示），即2653

将标准方法的表达式：

(10 × 16²) + (5 × 16¹) + (13 × 16⁰) = 2653

与使用Horner规则的方法进行比较：

(((10 × 16) + 5) × 16) + 13 = 2653

这是完全相同的计算，但重新排列成更容易计算的形式。这就是decode函数的工作原理。

为什么我们要使用num * base，并从num = 0开始。

转换算法需要一个起始值，因此将num设置为0。对于每次重复（每次循环迭代），num乘以base。这只对第二次迭代有任何影响，但是写成这样使得将转换编写为for循环更容易。

- Tomas Langkaas

谢谢提到霍纳规则。那正是我想要理解的内容。我想知道这个算法来自哪里。 - CodeCrack

1

原版和你自己的decode函数都能实现同样的功能，但原版更加高效。

在下面的赋值语句中：

num = num * _base + _alphabet.indexOf(str.charAt(i));

这里有两个部分：

_alphabet.indexOf(str.charAt(i))

indexOf 返回基于 _base 的数字值。您的算法中已经包含了此部分，因此应该很清楚。
num * _base

这将累积结果乘以当前基数。我的答案余下部分是关于这一部分的：

在第一次迭代中，这没有影响，因为此时 num 仍为0。但是在第一次迭代结束时，num 包含的值就好像 str 只有最左边的字符一样。它是最左边数字的基数-51的数字值。

从下一次迭代开始，结果将乘以基数，这会为下一个值腾出空间并添加到其中。它的功能类似于数字移位。

以 decode 的此示例输入为例：

bd35

这些单个字符代表的值为8、10、1和3。由于英文字母表中有51个字符，我们处于51进制。所以bd35代表的值为：

8*51³ + 10*51² +  1*51  +  3

这里是一个表格，显示了每次迭代后num的值：

                           8
                  8*51  + 10
         8*51² + 10*51  +  1
8*51³ + 10*51² +  1*51  +  3

为了使可视化更加清晰，让我们把51的幂放在列标题中，并从行中删除它：

3        2        1        0
----------------------------
                           8
                  8       10
         8       10        1
8       10        1        3

注意每次迭代中数字8向左移动并与基数（51）相乘。当数字10从右侧“移入”时，也会发生同样的情况。数字1和3也是如此，虽然它们是最后两个数字，不再移位。

因此，乘法num * _base表示将基数数字向左移位，为从右侧移入新数字（通过简单加法）腾出空间。

在最后一次迭代中，所有数字都已移入其正确的位置，即它们已被基数乘以足够的次数。

将您自己的算法放入相同的方案中，您将得到以下表格：

    3        2        1        0
    ----------------------------
    8
    8       10 
    8       10        1
    8       10        1        3

这里没有移位：数字立即放置在正确的位置，即它们立即乘以正确的51的幂。

- trincot

非常好的可视化答案。向左移动给解决方案带来了有趣的视角。 - CodeCrack

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pointy · Accepted Answer

好的，那么您的encode()函数输出的十进制376是什么意思呢？它表示：

1 * 100 +
5 * 10 +
4 * 1

为什么呢？因为在encode()函数中，每次迭代时都会通过基数进行除法。这意味着，在较早的迭代中推入字符串的字符隐含地每次通过循环增加一倍。

因此，decode()函数每次看到一个新字符时，都会乘以基数。这样，第一个数字就被乘以基数，以表示其过去的每个数字位置，并且对于其他数字也是如此。

请注意，在上面的解释中，1、5和4来自于字符3、7和6在“字母表”列表中的位置。这就是您的编码/解码机制的工作原理。如果您向decode()函数提供由某些尝试生成普通十进制数的东西编码的数字字符串，那么您肯定会得到奇怪的结果；这可能是显而易见的。

编辑为了进一步阐述decode()函数：暂时忘记特殊基数和编码字母表。无论涉及何种基数，该过程基本相同。因此，让我们看一个将十进制数的数字字符串解释为数字的函数：

function decode10(str) {
  var num = 0, zero = '0'.charCodeAt(0);
  for (var i = 0; i < str.length; ++i) {
    num = (num * 10) + (str[i] - zero);
  }
  return num;
}

累加变量num首先被初始化为0，因为在检查输入数字字符串的任何字符之前，唯一有意义的起始值是0。

然后函数从左到右迭代遍历输入字符串的每个字符。在每次迭代中，累加器乘以基数，并添加当前字符串位置处的数字值。

如果输入字符串是"214"，那么迭代过程如下:

num被设置为0
第一次迭代：str[i]是2，所以(num * 10) + 2是2
第二次迭代：str[i]是1，所以(num * 10) + 1是21
第三次迭代：str[i]是4，所以(num * 10) + 4是214

连续乘以10实现了代码中对Math.pow()的调用。请注意，数字2被乘以10 两次，这有效地将其乘以100。

你原来的代码中的decode()例程也是这样做的，只不过它不是通过简单地计算字符代码来获取数字的值，而是在字母表中执行查找。