程序员：枯燥的表单数据也可以变得有趣
openkk 13年前
<p> 还有什么能比处理表格中的信用卡数据更枯燥的呢？恩，如果你打算对卡号进行加密就不会那么枯燥了，当然这需要应对一些挑战。然而，它不过只是一个数字文本框，数据会存储在一个数据库里——没什么特别，也用不到什么高深的技术。我有一些待处理数据，需要从中找到 <a href="http://help.abr.gov.au/content.asp?sid=42&doc=/content/16974.htm&usertype=BC" rel="nofollow" target="_blank">ABN</a>——一种没有什么意思的数据。澳大利亚人肯定都知道 ABN，对其他人而言，它代表的是政府为每个公司分配的 11 位澳大利亚商业编号（Australian Business Number ）。这不是什么秘密（你可以<a href="/misc/goto?guid=4958329132823776014" rel="nofollow" target="_blank">在网上找到</a>），所以你甚至不必为其加密，因为没有人会因此感到兴奋。当然，如果事情仅仅如此，那就不值得写一篇博客了。对了，正如你想象的那样，事情并不像它们看上去那么平淡无奇。</p> <p> <strong>关于信用卡号一些有意思的事情</strong></p> <p lang="zh-CN"> 在 <a href="/misc/goto?guid=4958329133605088085" rel="nofollow" target="_blank">CrowdHired</a>，我们并没有和信用卡打过很多交道，但 ABN 完全是另外一回事，因为企业客户是我们系统的用户（顺便说一下，正如你猜测的，过去几个月里我为一家创业公司工作。我真的应该谈一谈<a href="/misc/goto?guid=4958329134385589455" rel="nofollow" target="_blank">如何创业</a>，那肯定会是一个有意思的故事）。对于任何数据，你都希望尽可能对用户输入进行验证。当我打算对 ABN 进行验证时，我发现了一些有意思的特性，信用卡号也具有同样的特性。正如你知道的那样，信用卡和 ABN 号码都是可自我验证的数据。</p> <p lang="zh-CN"> 时至今日，我已经做 web 开发很多年了，但对于处理这些数据没有任何经验。所以自然地，作为一名好奇的开发者，我做了一些深入的调查。结果是，这种能够自我验证的数据非常普遍，其他一些广为人知的例子有 <a href="/misc/goto?guid=4958329135190284761" rel="nofollow" target="_blank">ISBN</a>、<a href="/misc/goto?guid=4958329135985500647" rel="nofollow" target="_blank">UPC</a> 和 <a href="/misc/goto?guid=4958329136783451011" rel="nofollow" target="_blank">VIN</a>。其中大多数都是用了基于<a href="/misc/goto?guid=4958329137574219059" rel="nofollow" target="_blank">校验数据位</a>算法的一个变种进行验证和生成。可能这些算法中最有名的就是信用卡采用的 <a href="/misc/goto?guid=4958329138365044712" rel="nofollow" target="_blank">Luhn</a><a href="/misc/goto?guid=4958329138365044712" rel="nofollow" target="_blank">算法</a>。所以我们用信用卡作为示例。</p> <p lang="zh-CN"><strong> 验证和生成信用卡号码（及其他基于校验数据位的数字）</strong></p> <p> 例如我们有下面信用卡号码：</p> <blockquote> <p><code>4870696871788604</code></p> </blockquote> <p> 它有 16 个数字（维萨和万事达卡通常是 16 位，Amex 是 15 位）。信用卡号可以分成下列部分：</p> <blockquote> <p><code>发行编号 账号 校验数据</code></p> <p><code>487069 687178860 4</code></p> </blockquote> <p lang="zh-CN"> 你可以找到<a href="/misc/goto?guid=4958329139895287967" rel="nofollow" target="_blank">很多关于信用卡号的结构分析</a>，但我们想要做的是应用 Luhn 算法来检验信用卡号是否有效。接下来要这么处理：</p> <p lang="zh-CN"><strong> 1. 从后往前，每隔一个数字对数据加倍</strong></p> <blockquote> <p><code>4 8 7 0 6 9 6 8 7 1 7 8 8 6 0 4</code></p> <p><code>8 8 14 0 12 9 12 8 14 1 14 8 16 6 00 4</code></p> </blockquote> <p> <strong>2. 如果需要加倍的数字有两位，将这两个数字相加</strong></p> <blockquote> <p><code>4 8 7 0 6 9 6 8 7 1 7 8 8 6 0 4</code></p> <p><code>8 8 14 0 12 9 12 8 14 1 14 8 16 6 00 4</code></p> <p><code>8 8 5 0 3 9 3 8 5 1 5 8 7 6 0 4</code></p> </blockquote> <p> <strong>3. 将所有的数字相加得到结果</strong></p> <blockquote> <p><code>8+8+5+0+3+9+3+8+5+1+5+8+7+6+0+4 = 80</code></p> </blockquote> <p> <strong>4. 如果相加之和和可以被 10 整除，那么就是一个有效的信用卡号码。举例的信用卡号就是有效的。</strong></p> <p lang="zh-CN"> 下面你可以看到我们是如何使用同样的算法来生成一个有效的信用卡号。我们所要做的就是把校验位值设置成X并且执行所有相似的步骤。在最后一步，我们只要将我们的校验位置为可以将所有数字之和可以被 10 整除。让我们在之前的信用卡号上稍微做一点修改<em>（我们只要将校验位置为1，这样得到的就是一个无效的信用卡号）。</em></p> <blockquote> <p><code>4 8 7 0 6 9 6 8 7 1 7 8 8 6 1 X</code></p> <p><code>8 8 14 0 12 9 12 8 14 1 14 8 16 6 2 X</code></p> <p><code>8 8 5 0 3 9 3 8 5 1 5 8 7 6 2 X</code></p> <p><code>8+8+5+0+3+9+3+8+5+1+5+8+7+6+2+X = 78+X</code></p> <p><code>X = (78%10 == 0) ? 0 : 10 - 78%10</code></p> <p><code>X=2</code></p> </blockquote> <p> 正如你看到的，<strong>无论其他 15 个数字是什么，我们总能够在 0 到 9 之前找到生成有效信用卡号码的校验数字</strong>。</p> <p lang="zh-CN"> 当然，并不是每个子验证数字都是采用 Luhn 算法。大多数不采用对 10 取余数生成校验位，像 <a href="/misc/goto?guid=4958329140685232482" rel="nofollow" target="_blank">IBAN</a> 一类的数据，校验位实际上由两个数字组成。并且，大多数奇怪的自我验证数据都和我第一次知道的 ABN 一样。因为，以我的经历而言，<strong>我不能指出 ABN 的校验位应该是什么</strong>。</p> <p lang="zh-CN"><strong> ABN 的奇怪之处</strong></p> <p> 澳大利亚肯定不愿意使用基于校验位的算法。澳大利亚税收文件数据 TFN（<strong>T</strong>ax <strong>F</strong>ile <strong>N</strong>umber）和澳大利亚公司数据 ACN（<strong>A</strong>ustralian <strong>C</strong>ompany <strong>N</strong>umber）就是两个例子，但是 ABN 似乎与之不同。乍看上去，<a href="http://www.ato.gov.au/businesses/content.aspx?doc=/content/13187.htm&pc=001/003/021/002/001&mnu=610&mfp=001/003&st=&cy=1" rel="nofollow" target="_blank">ABN</a><a href="http://www.ato.gov.au/businesses/content.aspx?doc=/content/13187.htm&pc=001/003/021/002/001&mnu=610&mfp=001/003&st=&cy=1" rel="nofollow" target="_blank">验证算法</a>似乎与之类似，只是在最后使用了一个更大的数字进行取模操作（对 89<em>取余数</em>，<code>mod (89)</code>）</p> <blockquote> <p>· 从（左边）第一个数字开始逐个减一，得到一个新的 11 位数</p> <p>· 对生成的新数据的每个数字乘以它的权重因子</p> <p>· 将 11 个乘积加在一起</p> <p>· 对乘积综合除以 89，取余数</p> <p>· 如果余数为0，那么该 ABN 有效</p> </blockquote> <p> 事实上，这里有一些用来验证 ABN 的 ruby 代码，这是我从 <a href="/misc/goto?guid=4958329143023388596" rel="nofollow" target="_blank">Ruby ABN </a><a href="/misc/goto?guid=4958329143023388596" rel="nofollow" target="_blank">gem</a> 中抽取出来的<em>（并且很好地结合进了 Rails3 ActiveRecord 验证子，这样我们可以任意地调用 </em><code>validates_abn_format_of</code><em><em> </em><code></code><code>）</code></em></p> <div class="cnblogs_code"> <pre> def is_integer?(number) Integer (number) <span style="color:#0000ff;">true</span> rescue <span style="color:#0000ff;">false</span> end def abn_valid?(number) raw_number = number number = number.to_s.tr ' ','' <span style="color:#0000ff;">return</span> <span style="color:#0000ff;">false</span> unless is_integer?(number) && number.length == 11 weights = [10, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] sum = 0 (0..10) .each <span style="color:#0000ff;">do</span> i c = number[i,1] digit = c.to_i - (i.zero? ? 1 : 0) sum += weights[i] * digit end sum % 89 == 0 ? <span style="color:#0000ff;">true</span> : <span style="color:#0000ff;">false</span> end</pre> </div> <p lang="zh-CN"><br /> 但是，<strong>尽管验证 ABN 数据很容易，但是生成却又是另外一回事了</strong>。正如我们看到的，基于校验位的算法，生成和验证数据的过程是一样的，只有在取模步骤中我们需要选择不同的数字来验证余数是否为0。但是，像 ABN 这样的数据，没有明显的校验位<em>（也许我可能比较愚笨，所以如果你发现有明显的 ABN 校验位请不吝赐教）</em>，如果有效地生成一个有效的数据呢？事实上，<strong><em>为什么想要生成这些数据呢，仅仅验证数据的有效性还不够用吗？</em></strong></p> <p lang="zh-CN"> 恩，以 <a href="/misc/goto?guid=4958329133605088085" rel="nofollow" target="_blank">CrowdHired</a> 为例，我们试图生成一个很深的对象树，所以我们构建了一段维护基础架构的代码来允许我们创建伪数据来供开发使用<em>（我们会在晚些时候讨论另一个有意思的事情）</em>。在我们开始利用 ABN 数据的自我验证特性之前我们仅仅生成了任意的 11 为数字组成的数值作为伪 ABN 数据，但是一旦验证开始，我们就发现不能再这么干了。作为高效的开发者，我们<em>（尽管我们这么称呼自己）</em>使用一些真正的 ABN<em>（用我们掌握的那些）</em>，将他们放到一列数组中，然后随机地从中选取。但这种方式冒犯了开发者心中的上帝（换句话说触犯了我们的自尊——所以无论如何，我决定在周六花上几个小时来编写程序生成一些真正随机且有效的 ABN 数据）。下面是我的代码<em>（现在这段代码成为伪数据生成脚本的核心部分）</em>：</p> <div class="cnblogs_code"> <pre> def random_abn weights = [10,1,3,5,7,9,11,13,15,17,19] reversed_weights = weights.reverse initial_numbers = [] final_numbers = [] 9.times {initial_numbers << rand (9) +1} initial_numbers = [rand (8) +1, rand (7) +2] + initial_numbers products = [] weights.each_with_index <span style="color:#0000ff;">do</span> weight, index products << weight * initial_numbers[index] end product_sum = products.inject (0){sum, value sum + value} remainder = product_sum % 89 <span style="color:#0000ff;">if</span> remainder == 0 final_numbers = initial_numbers <span style="color:#0000ff;">else</span> current_remainder = remainder reversed_numbers = initial_numbers.reverse reversed_weights.each_with_index <span style="color:#0000ff;">do</span> weight, index next <span style="color:#0000ff;">if</span> weight > current_remainder <span style="color:#0000ff;">if</span> reversed_numbers[index] > 0 reversed_numbers[index] -= 1 current_remainder -= weight <span style="color:#0000ff;">if</span> current_remainder < reversed_weights[index+1] redo end end end final_numbers = reversed_numbers.reverse end final_numbers[0] += 1 final_numbers.join end</pre> </div> <p><br /> 这个想法非常简单。让我们通过一个例子来讲解一下：</p> <p> <strong> 1.首先，我们随机成成 11 个 0 到 9 之间的数据，来组成我们未来的 ABN<em>（他们实际上并非都在 0 到 9 之间，后面很快会对此进行说明）</em></strong></p> <blockquote> <p><code>7 5 8 9 8 7 3 4 1 5 3</code></p> </blockquote> <p> <strong> 2.然后，我们对该数据执行验证步骤</strong></p> <blockquote> <p>对这些数据乘以他们的权重得到带权重的乘积</p> <p><code>7x10=70 5x1=5 8x3=24 9x5=45 8x7=56 7x9=63 3x11=33 4x13=52 1x15=15 5x17=85 3x19=57</code></p> <p>将所有的乘积相加</p> <p><code>70+5+24+45+56+63+33+52+15+85+57 = 505</code></p> <p>对 89 取模得到余数</p> <p><code>505 mod 89 = 60</code></p> </blockquote> <p lang="zh-CN"><strong> 3. 因为我们对 89 取模，所以最坏的情况得到的余数是 88（尽管加入我们幸运地得到余数是 0 也就是直接得到了一个有效的 ABN），我们现在可以使用带有权重的数字乘积来“进行变换”，与余数相减直到我们得到的结果是0。</strong></p> <p> 我们从最后一位数字开始（权重是 19），我们对这个数字减1，这就意味着我们从余数中减去了 19。依次对下一个数字进行同样的操作，知道余数的变成0。</p> <blockquote> <p><code></code><code>初始值改变后的数值余数</code></p> <p><code>-------------------------------</code></p> <p> <code> </code><code>7x10=70 7x10=70 0</code></p> <p> <code> </code><code>5x1=5 5x1=5 0</code></p> <p> <code> </code><code>8x3=24 8x3=24 0</code></p> <p> <code> </code><code>9x5=45 9x5=45 0</code></p> <p> <code> </code><code>8x7=56 8x7=56 0</code></p> <p> <code> </code><code>7x9=63 6x9=63 0</code></p> <p> <code> </code><code>3x11=33 3x11=33 9</code></p> <p> <code> </code><code>4x13=52 4x13=52 9</code></p> <p> <code> </code><code>1x15=15 0x15=0 9</code></p> <p> <code> </code><code>5x17=85 4x17=68 24</code></p> <p> <code> </code><code>3x19=57 2x19=38 41</code></p> </blockquote> <p> <strong> 4.结果产生了我们的新数值</strong></p> <blockquote> <p><code>7 5 8 9 8 6 3 4 0 4 2</code></p> </blockquote> <p> <strong>5. 现在我们只要对每个数据的第一个数字加1（根据 ABN 的验证步骤）这样我们就得到了有效的 ABN 数据</strong></p> <blockquote> <p><code>85898634042</code></p> </blockquote> <p> 这些步骤之间有一些细微的差别。</p> <blockquote> <p lang="zh-CN"><strong>我们生成的初始数据里没有0</strong>。因为我们<em>“进行变化”</em>的时候是通过对每个数字减一，那么就必须确保我们能够对他们减1（否则事情会变得更加复杂）。所以我们确保数据可以随机的在 1 和 9 之间选择，而不是 0 到9。</p> <p><strong>即使我们所有的初始数据都保证至少为1，我们任然可能会对一些余数<em>“进行变化”</em>时失败</strong>，最简单的例子就是当我们的余数是 2 时。唯一可以使用进行变化的数字权重为1<em>（例如，ABN 的第二个数字）</em>。如果这个数字初始生成为1，我们只能进行一次变换并且得到的余数为1，这样我们就不能再进行任何的处理了。事实上，确切的场景还有余数为 86, 77, 66, 53, 38, 21。客服这个问题最简单的办法就是保证生成的数值至少为2.这样我们至少可以进行两次变化，这样我们的问题余数都会被覆盖到。</p> <p lang="zh-CN">最后，<strong>尽管我们在最后一步对每个数据的第一位加1，我们需要确保这个数据不能为9，</strong>所以我们需要确保生成的数字在 1 到 8 之间。</p> </blockquote> <p lang="zh-CN"> 即使注意到了所有这些区别，这个算法还是不能够生成所有可能的 ABN，但是对应我们的需求已经可以提供尽可能多的有效 ABN。这个算法花费了我们 1 个小时<em>（我们没有提到我忘记于是不能为 0 这个小 bug，这个问题给我们的随机数据生成器带来了很大的悲剧:)）</em>但是这确实是一个有意思的小练习——就我而言在这个上面花费的时间为有所值。要知道，所有的这些关于子验证数据的学习以及算法编程的乐趣都是由表格里一段最常见的数据引起的。这也就说明了，<strong>无论你在哪里在做什么都可以学习和成长，你需要做的只是能够发现这些机会而已</strong>。</p> <p> 原文：<a href="/misc/goto?guid=4958329145285144517" rel="nofollow" target="_blank">Alan Skorkin</a> 编译：<a href="/misc/goto?guid=4958185140659301754" target="_blank">伯乐在线</a> – <strong><a href="/misc/goto?guid=4958327305355149094">唐尤华</a></strong></p>