[IR] Text Compression 概念與 Random Access


思考 Text Compression
Our focus are compression methods that
1. allow random access to text
2. do not require decoding the entire text

請問記憶體Random Access Memory (RAM) 為何要用random access機制?
依照index隨便跳到一個地方存取
不用從頭找到尾
隨時可以存取任何一個為這的資料
因為它
隨時存取任何一個位置的資料所花的時間是一樣的！！！！！

以演算法的觀點來分析 Random Access與Sequential Access
Sequential: O(n)
Random: O(1)
硬碟存取資料是接近 O(1)

留言

張貼留言

這個網誌中的熱門文章

[筆記] CRLF跟LF之區別 --- 隱形的 bug

圖片
最近在當助教時，偶然間遇到一個隱形的Bug 為什麼稱之為隱形呢？ 請見下面兩張圖 說明：answer.txt 與 answer_test.txt 這兩個檔案的內容用文字編輯器打開時，完全一模一樣，但是我在使用 diff 指令的時候居然出現判定為每一行都不一樣的情形 指令 diff answer.txt answer_test.txt 由最上面第一張圖中可以注意到，answer.txt 的檔案大小是 958 byte answer_test.txt 的檔案大小則為 924 byte 此時不禁讓我疑惑到，兩個檔案內容相同，空白數量也完全相同的情況下，造成檔案大小不同的原因是什麼呢？ 下圖說明了一切 原來在 answer.txt 檔案當中，他的換行是採用 CRLF 而 answer_test.txt 的換行則是一般UNIX的情形 LF # 以下感謝梁浩穎同學解釋 CRLF 就是 \r\n 是只有在 windows 系統在用的形式 所有的 UNIX 系統都是用 \n   (的確，上圖中的 answer.txt 是用windows 7系統的記事本所編輯的，answer_test.txt 則是用 mac 系統透過 sublime text 所編輯的) CR是carriage return的意思， 也就是\r  LF是line feed的意思，也就是\n 這就是為什麼有些檔案從unix系統拿去windows上面看 會變成全部都在同一行 因為只有LF 他不知道是換行 windows只吃CRLF 除了一些比較聰明的文字編輯器會 分的出來 不過其實，CRLF才是真正的打字機運作方式，你可以想像：打字機打到最右邊，要先return到最左邊之後，再往下一行， 所以是CRLF 如果想要清空 answer.txt 裡面所有的 \r 的話，可以使用以下指令 tr -d '\r’ answer.txt # 遇到這個隱形的bug真是難得的好玩經驗，分享給大家 :)
Read more »

[ML筆記] Batch Normalization

圖片
Batch Normalization 本篇為台大電機系李宏毅老師 Machine Learning and having it Deep and Structured (2017)  課程筆記 上課影片： https://www.youtube.com/watch?v=BZh1ltr5Rkg 先從 Feature scaling 或是稱作 Feature Normalization 說起 假設 x1 跟 x2 的數值差距很大 x1 值的範圍 1,2,3,4, ... x2 值的範圍 100, 200, 300, … x1 的 weight 是 w1，x2 的 weight 是 w2 w1 前面乘的值比較小，所以他對於結果的影響比較小 w2 前面乘的值比較大，所以他對於結果的影響比較大
Read more »

[筆記] 統計實習(1) SAS 基礎用法 (匯入資料並另存SAS新檔，SUBSTR，計算總和與平均，BMI)

圖片
使用版本 SAS 9.3 繁體中文 OS: windows xp 匯入資料並另存成SAS新檔 step 1: 匯入資料 step 2: 選擇匯入檔案類型 step 3: 去資料夾 Browse 找尋要匯入的資料檔案 (這裡我命名為Man) step 4: 選好檔案後按OK step 5: 然後按Next step 6: 成功匯入excel資料  (我命名為 Man)，欲找尋這個檔案在哪 -> 按左側的資料館 step 7: 再選Work資料夾 step 8: 就會看到剛剛被我命名的 Man 檔案資料 step 9: 做些簡單的資料分析，在Editor視窗中寫code             Data test;             set man;             run;             以上code做的事會把這個 man (大小寫沒差)資料表複製一份，另命名成 test 存起來 step 10: 要複製另存成SAS檔，使用libname語法 後面放 目錄名稱'檔案路徑'               這裡的目錄名稱為 J 路徑為 '   ' 之中。                      step 11: 如此的code寫完，按下小人圖示提交執行程式 step 12: 會發現資料館裡面，多了一個名稱為 J 的資料夾目錄 step 13: 在 J 資料夾目錄裡面會成功看到被複製出來的名稱為 test 的資料 step 14: 實際跑到剛剛在 '   ' 之中的路徑看，也會看到test資料 SAS SUBSTR的用法 substr (sub string)顧名思義就是將一串文字當中切割出來一條子字串 語法為 新Table欄位名稱 = SUBSTR( Table欄位名稱 , 起始bit位置 , 要往後多少位元 ) 常用於將日期年月日分別切割出來變成數字來運算 step 1: 在Editor當中輸入語法 以第一橫排 16/10/1986為例 要取得日期DAY要從time欄位的第1個bit開始往後切長度
Read more »

[ML筆記] Ensemble - Bagging, Boosting & Stacking

圖片
ML Lecture 27: Ensemble 本篇為台大電機系李宏毅老師 Machine Learning (2016) 課程筆記 上課影片： https://www.youtube.com/watch?v=tH9FH1DH5n0 課程網 (投影片出處)： http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML16.html Ensemble 方法其實就是 “團隊合作” 好幾個模型一起上的方法 假如我們手上有一堆 Classifier ，這些 Classifier 每個都有不同的屬性， 要把他們集合起來一起合作，集合再一起需要用比較好的方法 以下來介紹一些 Ensemble 的方法 Bagging
Read more »