程序員：枯燥的表單數據也可以變得有趣

還有什么能比處理表格中的信用卡數據更枯燥的呢？恩，如果你打算對卡號進行加密就不會那么枯燥了，當然這需要應對一些挑戰。然而，它不過只是一個數字文本框，數據會存儲在一個數據庫里——沒什么特別，也用不到什么高深的技術。我有一些待處理數據，需要從中找到 ABN——一種沒有什么意思的數據。澳大利亞人肯定都知道 ABN，對其他人而言，它代表的是政府為每個公司分配的 11 位澳大利亞商業編號（Australian Business Number ）。這不是什么秘密（你可以在網上找到），所以你甚至不必為其加密，因為沒有人會因此感到興奮。當然，如果事情僅僅如此，那就不值得寫一篇博客了。對了，正如你想象的那樣，事情并不像它們看上去那么平淡無奇。

關于信用卡號一些有意思的事情

在 CrowdHired，我們并沒有和信用卡打過很多交道，但 ABN 完全是另外一回事，因為企業客戶是我們系統的用戶（順便說一下，正如你猜測的，過去幾個月里我為一家創業公司工作。我真的應該談一談如何創業，那肯定會是一個有意思的故事）。對于任何數據，你都希望盡可能對用戶輸入進行驗證。當我打算對 ABN 進行驗證時，我發現了一些有意思的特性，信用卡號也具有同樣的特性。正如你知道的那樣，信用卡和 ABN 號碼都是可自我驗證的數據。

時至今日，我已經做 web 開發很多年了，但對于處理這些數據沒有任何經驗。所以自然地，作為一名好奇的開發者，我做了一些深入的調查。結果是，這種能夠自我驗證的數據非常普遍，其他一些廣為人知的例子有 ISBN、UPC 和 VIN。其中大多數都是用了基于校驗數據位算法的一個變種進行驗證和生成。可能這些算法中最有名的就是信用卡采用的 Luhn算法。所以我們用信用卡作為示例。

驗證和生成信用卡號碼（及其他基于校驗數據位的數字）

例如我們有下面信用卡號碼：

4870696871788604

它有 16 個數字（維薩和萬事達卡通常是 16 位，Amex 是 15 位）。信用卡號可以分成下列部分：

發行編號     賬號   校驗數據

487069     687178860    4

你可以找到很多關于信用卡號的結構分析，但我們想要做的是應用 Luhn 算法來檢驗信用卡號是否有效。接下來要這么處理：

1. 從后往前，每隔一個數字對數據加倍

4 8 7 0 6 9 6 8 7 1 7 8 8 6 0 4

8 8 14 0 12 9 12 8 14 1 14 8 16 6 00 4

2. 如果需要加倍的數字有兩位，將這兩個數字相加

4 8 7 0 6 9 6 8 7 1 7 8 8 6 0 4

8 8 14 0 12 9 12 8 14 1 14 8 16 6 00 4

8 8 5 0 3 9 3 8 5 1 5 8 7 6 0 4

3. 將所有的數字相加得到結果

8+8+5+0+3+9+3+8+5+1+5+8+7+6+0+4 = 80

4. 如果相加之和和可以被 10 整除，那么就是一個有效的信用卡號碼。舉例的信用卡號就是有效的。

下面你可以看到我們是如何使用同樣的算法來生成一個有效的信用卡號。我們所要做的就是把校驗位值設置成X并且執行所有相似的步驟。在最后一步，我們只要將我們的校驗位置為可以將所有數字之和可以被 10 整除。讓我們在之前的信用卡號上稍微做一點修改（我們只要將校驗位置為1，這樣得到的就是一個無效的信用卡號）。

4 8 7 0 6 9 6 8 7 1 7 8 8 6 1 X

8 8 14 0 12 9 12 8 14 1 14 8 16 6 2 X

8 8 5 0 3 9 3 8 5 1 5 8 7 6 2 X

8+8+5+0+3+9+3+8+5+1+5+8+7+6+2+X = 78+X

X = (78%10 == 0) ? 0 : 10 - 78%10

X=2

正如你看到的，無論其他 15 個數字是什么，我們總能夠在 0 到 9 之前找到生成有效信用卡號碼的校驗數字。

當然，并不是每個子驗證數字都是采用 Luhn 算法。大多數不采用對 10 取余數生成校驗位，像 IBAN 一類的數據，校驗位實際上由兩個數字組成。并且，大多數奇怪的自我驗證數據都和我第一次知道的 ABN 一樣。因為，以我的經歷而言，我不能指出 ABN 的校驗位應該是什么。

ABN 的奇怪之處

澳大利亞肯定不愿意使用基于校驗位的算法。澳大利亞稅收文件數據 TFN（Tax File Number）和澳大利亞公司數據 ACN（Australian Company Number）就是兩個例子，但是 ABN 似乎與之不同。乍看上去，ABN驗證算法似乎與之類似，只是在最后使用了一個更大的數字進行取模操作（對 89取余數，mod (89)）

· 從（左邊）第一個數字開始逐個減一，得到一個新的 11 位數

· 對生成的新數據的每個數字乘以它的權重因子

· 將 11 個乘積加在一起

· 對乘積綜合除以 89，取余數

· 如果余數為0，那么該 ABN 有效

事實上，這里有一些用來驗證 ABN 的 ruby 代碼，這是我從 Ruby ABN gem 中抽取出來的（并且很好地結合進了 Rails3 ActiveRecord 驗證子，這樣我們可以任意地調用 validates_abn_format_of ）

　　def is_integer?(number)

　　  Integer (number)

　　  true 　　rescue

　　  false 　　end

　　def abn_valid?(number)

　　  raw_number = number

　　  number = number.to_s.tr ' ',''

　　  return false unless is_integer?(number) && number.length == 11

　　  weights = [10, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

　　  sum = 0

　　  (0..10) .each do i

　　    c = number[i,1]

　　    digit = c.to_i - (i.zero? ? 1 : 0)

　　    sum += weights[i] * digit

　　  end

　　  sum % 89 == 0 ? true : false 　　end

但是，盡管驗證 ABN 數據很容易，但是生成卻又是另外一回事了。正如我們看到的，基于校驗位的算法，生成和驗證數據的過程是一樣的，只有在取模步驟中我們需要選擇不同的數字來驗證余數是否為0。但是，像 ABN 這樣的數據，沒有明顯的校驗位（也許我可能比較愚笨，所以如果你發現有明顯的 ABN 校驗位請不吝賜教），如果有效地生成一個有效的數據呢？事實上，為什么想要生成這些數據呢，僅僅驗證數據的有效性還不夠用嗎？

恩，以 CrowdHired 為例，我們試圖生成一個很深的對象樹，所以我們構建了一段維護基礎架構的代碼來允許我們創建偽數據來供開發使用（我們會在晚些時候討論另一個有意思的事情）。在我們開始利用 ABN 數據的自我驗證特性之前我們僅僅生成了任意的 11 為數字組成的數值作為偽 ABN 數據，但是一旦驗證開始，我們就發現不能再這么干了。作為高效的開發者，我們（盡管我們這么稱呼自己）使用一些真正的 ABN（用我們掌握的那些），將他們放到一列數組中，然后隨機地從中選取。但這種方式冒犯了開發者心中的上帝（換句話說觸犯了我們的自尊——所以無論如何，我決定在周六花上幾個小時來編寫程序生成一些真正隨機且有效的 ABN 數據）。下面是我的代碼（現在這段代碼成為偽數據生成腳本的核心部分）：

　　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 do weight, index

　　    products << weight * initial_numbers[index]

　　  end

　　  product_sum = products.inject (0){sum, value sum + value}

　　  remainder = product_sum % 89

　　  if remainder == 0

　　    final_numbers = initial_numbers

　　  else 　　    current_remainder = remainder

　　    reversed_numbers = initial_numbers.reverse

　　    reversed_weights.each_with_index do weight, index

　　      next if weight > current_remainder

　　      if reversed_numbers[index] > 0

　　        reversed_numbers[index] -= 1

　　        current_remainder -= weight

　　        if current_remainder < reversed_weights[index+1]

　　          redo

　　        end

　　      end

　　    end

　　    final_numbers = reversed_numbers.reverse

　　  end

　　  final_numbers[0] += 1

　　  final_numbers.join

　　end

這個想法非常簡單。讓我們通過一個例子來講解一下：

 1.首先，我們隨機成成 11 個 0 到 9 之間的數據，來組成我們未來的 ABN（他們實際上并非都在 0 到 9 之間，后面很快會對此進行說明）

7 5 8 9 8 7 3 4 1 5 3

 2.然后，我們對該數據執行驗證步驟

對這些數據乘以他們的權重得到帶權重的乘積

7x10=70 5x1=5 8x3=24 9x5=45 8x7=56 7x9=63 3x11=33 4x13=52 1x15=15 5x17=85 3x19=57

將所有的乘積相加

70+5+24+45+56+63+33+52+15+85+57 = 505

對 89 取模得到余數

505 mod 89 = 60

3. 因為我們對 89 取模，所以最壞的情況得到的余數是 88（盡管加入我們幸運地得到余數是 0 也就是直接得到了一個有效的 ABN），我們現在可以使用帶有權重的數字乘積來“進行變換”，與余數相減直到我們得到的結果是0。

我們從最后一位數字開始（權重是 19），我們對這個數字減1，這就意味著我們從余數中減去了 19。依次對下一個數字進行同樣的操作，知道余數的變成0。

初始值改變后的數值余數

-------------------------------

  7x10=70 7x10=70 0

  5x1=5   5x1=5   0

  8x3=24  8x3=24  0

  9x5=45  9x5=45  0

  8x7=56  8x7=56  0

  7x9=63  6x9=63  0

  3x11=33 3x11=33 9

  4x13=52 4x13=52 9

  1x15=15 0x15=0  9

  5x17=85 4x17=68 24

  3x19=57 2x19=38 41

 4.結果產生了我們的新數值

7 5 8 9 8 6 3 4 0 4 2

5. 現在我們只要對每個數據的第一個數字加1（根據 ABN 的驗證步驟）這樣我們就得到了有效的 ABN 數據

85898634042

這些步驟之間有一些細微的差別。

我們生成的初始數據里沒有0。因為我們“進行變化”的時候是通過對每個數字減一，那么就必須確保我們能夠對他們減1（否則事情會變得更加復雜）。所以我們確保數據可以隨機的在 1 和 9 之間選擇，而不是 0 到9。

即使我們所有的初始數據都保證至少為1，我們任然可能會對一些余數“進行變化”時失敗，最簡單的例子就是當我們的余數是 2 時。唯一可以使用進行變化的數字權重為1（例如，ABN 的第二個數字）。如果這個數字初始生成為1，我們只能進行一次變換并且得到的余數為1，這樣我們就不能再進行任何的處理了。事實上，確切的場景還有余數為 86, 77, 66, 53, 38, 21。客服這個問題最簡單的辦法就是保證生成的數值至少為2.這樣我們至少可以進行兩次變化，這樣我們的問題余數都會被覆蓋到。

最后，盡管我們在最后一步對每個數據的第一位加1，我們需要確保這個數據不能為9，所以我們需要確保生成的數字在 1 到 8 之間。

即使注意到了所有這些區別，這個算法還是不能夠生成所有可能的 ABN，但是對應我們的需求已經可以提供盡可能多的有效 ABN。這個算法花費了我們 1 個小時（我們沒有提到我忘記于是不能為 0 這個小 bug，這個問題給我們的隨機數據生成器帶來了很大的悲劇:)）但是這確實是一個有意思的小練習——就我而言在這個上面花費的時間為有所值。要知道，所有的這些關于子驗證數據的學習以及算法編程的樂趣都是由表格里一段最常見的數據引起的。這也就說明了，無論你在哪里在做什么都可以學習和成長，你需要做的只是能夠發現這些機會而已。

原文：Alan Skorkin 編譯：伯樂在線 – 唐尤華