警告: 找到缺漏結束短代碼的起始短代碼。
如果確定這是誤判警告，請前往 [一般設定]→[註腳內容起始及結束短代碼]→[檢查註腳短代碼是否完整] 停用語法驗證功能。
缺漏結束短代碼的起始短代碼位於以下文字前方:
“n/2)!) , 這個數字相當可怕, 一般文章平均一句話大概都有個十到十五字, 這樣下去index 中的entry 過多, db檔也膨脹的極大,針對index 檔搜尋已經等同直接搜尋目標檔了, 喪失2-levels的IO優勢. 這一點必須改良, 在跟同事討論的結果, 同…”
這是整理以前寫過的MLGS介紹跟緣起的文章, 原發表在自己的bbs站上, 如今事過境遷我想也無所謂機密與否的問題, 趁著整理資料時貼出來.
[MLGS] 緣起/需求/理論
MLGS(Multi Language/Multi Levels Global Search)的誕生算是巧合, 其實說穿了什麼都是巧合啦!
正好某個我們公司服務的網站需要一個Search Engine, 他們不是要一個向外面 PortalSite 用的一些WebSearch,
而是一個需要搜尋網站內部的Search Engine, 所以我就被assign去作這個工作了. 這聽起來感覺是個簡單任務,
只要grep一下Apache 中的DocumentRoot就可以了啊! 一碰下去才知道不是這麼一回事.
首先, 該網站的頁面量相當龐大, 大概目前應該有上五萬個頁面!而且因為是新聞性網站, 平均每小時都會增加約30的頁面左右, 也就是一天有大約有個500左右的新增量.
這麼大的數量讓我有點望之卻步, 畢竟第一次面對這麼龐大的資料量,以往沒什麼專注在演算法的我, 這回碰到要逼自己從零開始的東西了.此時上司給我一點方向跟情報: 首先是GAIS的作法.
GAIS的主要發展者吳昇老師並沒有放出原始碼, 所以也無從得知到底GAIS 怎麼作, 但是在一位曾經跟過吳昇老師的碩士那兒, 得到一點資訊, GAIS 的前身是Glimpse這個英文的全文檢索, 於是第一步就是, 先去研讀一下文件跟網路上的資料.
Glimpse用的是2-levels的搜尋方式, 這種搜尋方式是利用英文的語言特色而作, 首先先對所有的目標文件做一次index,
使用空白或跳位字元去分割文章,抽取出文章中的所有字彙, 然後建立一個index檔和db檔, index
檔放某個字彙在db檔中的位置(pointer), 最後取pointer 後到db檔中直接讀出該檔的位置,就可以減少整個grep一次的IO量.
這種搜尋index後再去根據pointer 取資料的方式, 就是2-levels的技巧.
[MLGS] 困境/改良/挫敗
當模仿Glimpse 實作時, 第一個困境出現了, 那就是中文的字彙分隔, 在英文的狀況下, 可以很單純用空白或是tab 字元分隔出每個字,
但是中文不可能, 於是開始時, 只能用最笨的方法, 碰到中文字就從單字取, 雙字取, 三字取, 取到一個極限值,
我期初的設定值是取到五個中文字為止.
暫時先用perl寫最簡單的字串處理, 試試看這樣效果如何. 第一次測試相當慘,
因為一篇文章, 如果有一句話總字串長度為n , 那個就要在(n/2) 取字, 取的量會是 sigma[k=2;k=n/2]((n/2)!) ,
這個數字相當可怕, 一般文章平均一句話大概都有個十到十五字, 這樣下去index 中的entry 過多, db檔也膨脹的極大,針對index
檔搜尋已經等同直接搜尋目標檔了, 喪失2-levels的IO優勢.
這一點必須改良, 在跟同事討論的結果,
同事認為應該用詞庫檔去作index ,畢竟前述方法中大多數的index entry 都是無意義的, 例如”李登輝總統”這個詞中,
取到”輝總”這個字就絕對無意義, 作了這個index 完全無用, 而且index 檔膨脹後, 多了這些無用的index entry
會造成IO速度低落跟seek time 拉長的缺陷, 所以第一步改良, 就是分散index 檔, 使用檔名當key ,
這樣可以直接開到需要的檔案, 不會被累贅的index entry 拖累.
於是就採用目錄式的方式放index ,
每個index 檔就只放一個keyword , 其中的內容用binary直接放一個flow number , 這個序號就是在另外一個table
中的資料序號. 這樣可以把重複出現在各個index entry 中的資料縮小到一個int ,而採用4 bytes 的資料長度, 存放int
已經足夠儲存到256^4 了, 也不需要多一個byte放置長度, 直接4 bytes seek, 速度是最快的.
這樣的放置方式可以在搜尋速度上得到最佳化, 而每次只要append新的進去就完成更新, 每小時約30篇的文章利用crontab 來作,
相當輕鬆. 一邊對現有的一萬多篇跑著index , 一邊就用php4開始寫web interface 了, 寫出來後的速度跟準確度,
都讓我及上司相當滿意, 但是惡夢馬上就會出現了….
我在作index 的過程中,
有把目前的進度跟一些資料dump到console 上, 隔天到公司時, 發現console 暴走了, 挖拉挖拉的一堆disk full
的訊息, 不對, 不可能, 我明明mount 了一顆9G的硬碟上去了, 絕對不可能不夠的啊! 連ctrl-c都沒用了,
只好remote進去kill掉, df一下才發現, 原來inode 用完了, 因為把每個index entry 都作成檔案, 所以檔案數暴漲,
inode 一下就吃光光了, 這回可真的碰到了絕大的困境了.
[MLGS] 檢討/歸零/重生
把inode 吃光的下場讓我很難堪, 雖然上司沒有針對這個責備我, 上司說, 人家吳昇老師研究了多久作出來的東西, 要是讓你一個人短時間搞定, 那吳昇老師多沒面子.
於是全盤檢討, 從最基礎檢討起, 分析好各個問題點. 首先必須確立的, 是index 的使用有其必要性, 但是index 必須減低佔用的空間,
而分析過後, 在三個層面: 1.製作index 的速度, 2.index 佔用的空間,
3.作Search的時間.成本一定是要放在三者其中之一, 而我們的目的要做到快速, 所以一定不能放置在第三點,
而第一點必須要趕上網站成長的速度, 所以也不行; 而放置在空間上就如同前兩篇一樣的下場, 硬碟空間的需求量相當可怕,
根本已經到了不切實際的地步.
檢討之下全面錯誤的結果讓我很沮喪, 但是也告訴自己必須讓自己歸零重來. 重新畫系統圖跟flow chart, 重新reserach資料結構, 看一點壓縮跟編碼的RFC….
重複的思考跟失眠後, 我確定作index 的正確性, 將成本抽離使用者介面絕對正確, 所以必須檢討的是index 的儲存方式.
前面提過詞庫法, 只作有意義的詞庫index , 放棄無意義的index entry , 但是這樣會把成本放置在準確度與index
repair/update 上, 我認為不合適於超大系統上. 而採用資料壓縮的方式也行不通, 因為index 中的資料已經binary化,
幾乎可以說是最簡狀態,最多只能壓縮掉hex 中的高位null值, 對實際的空間節省沒有什麼大幫助.
這時候我想到同事說的有限理論, 於是改採平均的方式, 將index 做的長度降低到雙字, 如此一來在中文字的範疇中, 最多到21916^2 個index 檔, 省下了inode 跟硬碟空間, 但是一定會有個疑問是, 要如何比對超過兩個中文字的字串?
這就必須靠拆字, 假設一個詞有n 個中文字, 那麼可以用相接的兩個字作出n-1 個雙字對, 這些雙字對可以在index 中取得各自的entry
serial array,再利用這n-1 個array 的聯集, 就可以拿到”準搜尋結果”, 這些”準搜尋”的結果就可以拿來作實際的搜尋動作,
這樣一來把IO數降到合理的量, 也把index佔用的空間作最合理的分配.
於是, 我把這種以雙字組一層一層mask上去的方法, 稱為multi-levels, 又因為可以同時處理英文字與非英文字, 所以也稱multi-language, 這時候MLGS的大體就成形了.