29 10月 2013

[交融] 進位的字串

一直想不起來在哪一本書裡面讀到一句話 (只記得作者是個歐洲人),大意是說:「學問鑽研到某個程度以後,會發現不管什麼學科,最後都是數學和語言」。我想這裡的意思不是指「學習語言」,而是指像「語言規則」這種語言學家感興趣的東西。如此一來,我們就能把「語言」當作是一串符號,而數字則是這串符號背後的演繹規則了。

我正寫著最後的幾個收尾小程式,做「匯出數據」的功能。匯出 .csv 格式,小意思。十分鐘就寫好了;匯出成 .xls 格式,不算太難,配合 xlwt 也只花了三十分鐘,頂多只在上限的直行數量 (256 行) 上做些限制就行了。接著做到第三個,匯出 .ods 的格式,我用了 openodspy 這套工具來寫…乖乖隆滴東…

事情是這樣的,OpenOffice.org/LibreOffice 及任何開放文件格式能支援的 .ods 格式都支援 1024 行 (直行) 的格式。但經過測試後, simpleodspy 在處理直行時,只支援到 702 行 (直行)。

>>> from simpleodspy.sodsspreadsheet import SodsSpreadSheet
>>> sheet = SodsSpreadSheet()
>>> sheet.encodeColName(702)
'ZZ'
>>> sheet.encodeColName(703)
'[A'
>>>

為什麼會只支援到 702 行呢?把它的原始碼挖出來,長這個樣子… (開放原始碼的好處,就是大家都能看到底層,也能提出修改的建議,甚至直接動手修改):

def encodeColName(self, n):
    ''' encode a col number 1.. to a name "A" or "BC" '''
       
    n1 = (n - 1) % 26
    n2 = int((n - 1) / 26)
       
    if n2 == 0:
        return chr(ord('A') + n1)
       
    return chr(ord('A') + n2 - 1) + chr(ord('A') + n1)

深究其原因,是因為它用了 chr() 和 ord() 來組合從第 1 行到第 702 行順序的各種組合。不過這麼一來也限制了它最多只能處理到 "ZZ" 這種兩個字元的行數而已。

所以,如果我想知道第 702 行的位置的話,就呼叫 encodeColName(702),就能得到 "ZZ" 這個正確答案。可惜的是,如果再多一行,因為它的正確行號應該是 "AAA",超過 "ZZ" 的兩個字元,所以到 703 行的話,就出錯了,因此得到了 "[A" 這種奇怪的行號。

於是我停下手指,從頭開始檢視為什麼 xlwt 可以輕易地編出「超過 excel 支援」的行號,而 simpleodspy 卻無法編出「明明 OOo 有支援的行號」。

和 xlwt 不同的是,xlwt 利用 (x, y) 座標來標明 (橫列, 直行),且 x, y 為兩個數字。但 simpleodspy 卻是用了比較好讀,卻比較難處理的 ("A1") 這樣的座標系統來表示 "第 A 行第 1 列"的座標。

那就表示,我如果要寫入一筆有 27 行 (直行) 的數據,那我的座標就要從 A1, B1, C1..  一路標到 AA1 囉。

乍看之下好像沒什麼問題,但如果我的數據有 302 行 (直行) 呢?我又沒有雨人的腦袋可以一下子告訴你第 302 行的座標是 "KP"。那怎麼辦?

在計算紙上寫下 1, 2, 3, 4...直到 26,然後再標上 A, B, C, D... 直到 Z,我突然發現,這可以當做是一個構詞學的問題來看待。

假設今天有某種語言,它構成一個字的方式是先寫下字根

"ABCDEFGHIJKLMNOPQRSTUVWXYZ" ,然後再加上後綴。而後綴的決定方式,則是先數它是屬於第幾層加接,在第 1 層到第 26 層內,它的規則就是先重覆一次字根的第一個字元,然後再依序加上字根的每一個字元,所以就會形成如下的樣式…

"AA AB AC AD AE AF AG AH AI AJ AK AL AM AN AO AP AQ AR AS AT AU AV AW AX AY AZ"
如果一直加下去,最後兩個字元的 ZZ 也用完的時候,接著就是 AAA,AAB…這樣繼續下去了。

以語言學的方法來說,語料的分佈描述完了,接下來就是試圖用最少的規則加以歸納,並且假設以這個語言為母語的使用者腦袋裡是備具了這些規則的。那麼…究竟這個規則會寫成什麼樣子呢…

我在剛才的紙上隨手寫下 27 ,然後標上 AA…咦?等等,我突然發現這不只是一個字串問題,這其實也可以當成是一個數學上的進位系統問題。

簡單地說,這個語言的構詞系統是以字根配合 26 進位系統來運作的。

也就是說,就像 10 進位的系統是從 0 數到 9,然後下一個就要進位,先記著進位過一次的 1 ,然後跟從頭開始數的 0 就成了 "10"。

這個 26 進位的系統是從 A 數到 Z,然後就先記著一個進位過一次的 A,然後跟著從頭數的 A,形成了 "AA"。

嘿,還真的是「每個學科最後只剩下數學和語言」吶!

我還記得以前在外面繳錢學 JAVA 的課堂上,講師提過用短除法求餘數,就能做 2 進位的轉換 (真糟,花了一大筆錢去學的,結果現在也只剩下這個還記得了),那麼是不是也能做 26 進位的轉換呢?

我用手推算了一下,第 280 個詞綴應該是 "JT",那麼就用短除法來算算看吧…

那麼… "A~Z" 的第 10 個是… "J",而第 20 個則是 "T",合起來剛好是所求的 "JT"!

如果考慮到這裡為止的話,一個 10 進位的數字 (e.g., 280) 要轉成 26 進位制的數字,這仍然只是數學問題。但我的目標除了數學以外,還有字串的比對。而被我編上序號的字串是從 1 到 26 的 A 到 Z 這些字元。所以我還要額外注意整除的問題.

因為既然我要取的是餘數,那麼整除的那個數字當然就是「沒有餘數」的。也就是說…
因此,遇到剛好可以被整除的數字時,我要把 0 這個位置的字元往後跳到 Z,而且把下一階的餘數減 1。最後,再把手邊的短除法的式子改成以下的 Python 程式碼…

def myEncodeColName(n):
    import string
    colNameRef = string.uppercase
    #這裡利用 string 模組產生 "A...Z" 的 26 個字元。
    base = len(colNameRef)
    #如果只計 A...Z 之間的話,沒有進位,就直接回傳答案。
    name = ""
    if n <= base:
        name = colNameRef[n-1]
    else: #如果超過 A...Z 的字串,涉及進位,則做以下的計算。
        remLIST = [n%base]
        quotient = n/base
        while quotient > 0:
            remLIST.append(quotient%base)
            quotient = quotient/base
        #因為每次加入餘數時是往 remLIST 的後面塞進去的,
        #這麼一來,行號字串的第一個字,會在最後一個才算到。
        #因此,這裡用上 reverse() 把整個順序倒過來。      
        remLIST.reverse()
        #這裡做一下餘數為 0 時的檢查和處理。
        for i in range(0, len(remLIST)):
            if remLIST[i] == 0:
                remLIST[i-1] = remLIST[i-1]-1
        #最後把每個取得的餘數依序從一開始的 "A...Z" 的字根裡取出並串接。
        for i in remLIST:
            name = name+colNameRef[i-1]
    return name

這麼一來,別說是 702 的限制或是 1024 的上限了,理論上,只要電腦硬體受得了,作業系統受得了,不管是多大的數字應該都算得出來了呢。

數學和語言,也許真的在某個抽象的層次裡是可以彼此交流的吧。

[註] myEncodeColName() 於 2013.10.31 修為第二版.