第二章所介紹的壓縮技巧的確大幅度地節省了硬碟空間，但是還是無法解決如何有效率地對資訊做搜索的這個問題。本章就是要透過 index 來解決這個問題。本章將介紹各種索引方法以及索引壓縮 (index compression)。

比較：從一本書的index來查詢某個字出現的地方 v.s. 一頁一頁地找出某個詞 (page-by-page search)

詞彙定義

• 文檔 (document)
• 文檔集合 (document collection)
• 詞條 (term)

設計師必須考慮：

1. 多大的單位算作一個文檔?

一句話？一個段落？一篇文章？數篇文章？

A document will thus be the unit of text that is returned in response to queries. (p. 104, par. 2)

2. 索引的粒度 (The granularity of index, p. 105)

對於一個詞出現在每個文檔中的位置資訊，我們要記錄的多細？有時候我們只需要知道包含「漢堡」的文檔有哪些就好，所以這時候我們只需紀錄：

漢堡：文檔1、文檔3、…

但如果我們想查詢同時出現「漢堡」和「薯條」的句子，那麼我們還必須更詳細地記錄這些詞出現的位置：

漢堡: (文檔1, 句子3), (文檔2, 句子5), …
薯條: (文檔1, 句子5), (文檔2, 句子5), …

如此我們才能比對抽取出哪些句子同時出現漢堡跟薯條。

3. 什麼算作一個詞條?

is跟was算作兩個不同的詞條嗎？

相關議題：transformation (p. 105-6 & Ch. 3.7)

• case folding
• stemming
• stop words
• thesaural substitution (同義詞需不需要合併成一個term? 本章不討論)

Ch. 3.1: 文檔集合之樣本 (Sample document collections)

這一節以四個文章集合當作實驗對象，並分別列出一些統計數據：

*索引指標 (Index pointer) 所有 (文檔, 詞條) 組的數量，也就是索引的總大小。

Ch. 3.2: 索引方法一: Inverted file indexing

An index is a mechanism for locating a given term in a text.

適合作為索引的資料結構：

• inverted file (又稱 postings file, 或者 concordance) (本節; 是最合適的)
• signature files (Ch. 3.5) (使用時機有限)
• bitmaps (Ch. 3.5) (使用時機有限)

在大多數的應用中，比起 signature files 和 bitmaps，inverted files 在索引大小和處理搜索的速度都有較好的表現。(p. 111)

一個 inverted file 包含了 lexicon 當中每一個 term 的 inverted list (又稱為 postings list)，每個 inverted list 都儲存了指向該 term 所出現位置的 list of pointers，每個 pointer (又稱為 postings) 其實指向該詞出現的某篇文檔。

一本書後面的 Index 其實就是一個 inverted file的格式。

每個 inverted file index都需要 lexicon，lexicon就是 a list of all terms that appear in the database。

接著討論又回到了索引的粒度。紀錄的位置資訊越詳細，索引的大小當然就越大。

最後討論了未經壓縮的inverted files的尺寸大小，常常會佔原始文檔集合的 50 ~ 100%。

Ch. 3.3: Inverted file compression

最簡單的方法：d-gaps (p. 114-5)

各種方法分類：（這部分未讀）

• Global methods
• Local methods

Ch. 3.4: 比較各種索引壓縮方法的表現

未讀。

Ch. 3.5: 其他兩個索引方法

Signature files

Bitmaps

Ch. 3.6: 比較三種索引方法

本節結論（也就是最後一句話）：經過壓縮的inverted files無疑是最好的方法，最適用於巨大的文檔集合。

Ch. 3.7: What should be indexed?

本節處理在 p.106 已帶出的一些議題，到底在一個 inverted file 當中，如何定義一個詞條是什麼？需要全部轉換成大寫嗎？要以詞根形式作為詞條嗎？是否要去除停用詞？

• Case folding
• Stemming
• Effect on index size
• Stop words

留言與分享

目錄

Disk structure

##

Disk structure

• 每次對硬碟做讀寫時，總是以Block作為讀寫單位，每個Block的大小通常是512bytes。一個Block的地址可以由(Sector no., Track no.)來表達。
• 一個block上的每個byte也有自己的位置，稱為offset，從0到511。
• 所以要存取硬碟上某一個block的某一個byte，我們需要知道以下三個資訊：第幾個Track、第幾個Sector、第幾個offset。

參考資料:

• How is data stored and retrieved inside a disk in a computer?

留言與分享

學習資源

• Architecture of SQLite(官網)
• Let’s Build a Simple Database: Writing a sqlite clone from scratch in C
• Sibsankar Haldar 的書
  • Inside SQLite
    • yangmingzi /
      how-to-implement-a-DB-like-sqlite
  • SQLite Database System: Design and Implementation

留言與分享

1
2
3
4
5
6
7
8
9
10
11

# 先下載台北黑體字型
!wget -O taipei_sans_tc_beta.ttf https://drive.google.com/uc?id=1eGAsTN1HBpJAkeVM57_C7ccp7hbgSz3_&export=download

import matplotlib

# 新增字體
matplotlib.font_manager.fontManager.addfont('taipei_sans_tc_beta.ttf')

# 將 font-family 設為 Taipei Sans TC Beta
# 設定完後，之後的圖表都可以顯示中文了
matplotlib.rc('font', family='Taipei Sans TC Beta')

留言與分享

function 是傳值的 (pass by value)

所以如果要改動某一個記憶體中的位置的話，一定要傳某變數的地址給函數，而函數的形式參數也要指定為指標類型的才行。

const 作為函數的形式參數

1

void a_function (const char *) {...}

這麼做只是為了要保護傳進來的字串(字元指標)不能被修改而已。

Generally, if you pass the value of a variable into a function (with no &), you can be assured that the function can’t modify your original variable. When you pass a pointer, you should assume that the function can and will change the variable’s value. If you want to write a function that takes a pointer argument but promises not to modify the target of the pointer, use const, like this:

1
2
3
4
5

void
printPointerTarget(const int *p)
{
    printf("%d\n", *p);
}

(see link)

為什麼要傳 pointer 作為函數的參數?

Passing const pointers is mostly used when passing large structures to functions, where copying a 32-bit pointer is cheaper than copying the thing it points to. (see link)

Debugging tools

• gdb (在OSX上是 lldb)

• 參考資料

  • link

Automatic variable ( = local variable)

Each local variable in a function comes into existence only when the function is called, and disappears when the function is exited. This is why such variables are usually known as automatic variables, following terminology in other languages. (see K&R 2nd. 1.10)

只存活於某個函式執行時，執行完畢後，這些automatic variable就會消失。相對於此就有持存在函數之外的變數。

• 相對的概念:
  • 在函式當中的標有 static 的 local variable，他們在多次函數的調用時保持值不變 (see K&R ch4)
  • 宣告在所有函數外部的變量，並且只能定義一次 (see External variable)
  • 關鍵字: storage class

External variable

As an alternative to automatic variables, it is possible to define variables that are external to all functions, that is, variables that can be accessed by name by any function. (This mechanism is rather like Fortran COMMON or Pascal variables declared in the outermost block.) Because external variables are globally accessible, they can be used instead of argument lists to communicate data between functions. Furthermore, because external variables remain in existence permanently, rather than appearing and disappearing as functions are called and exited, they retain their values even after the functions that set them have returned.

An external variable must be defined, exactly once, outside of any function; this sets aside storage for it. The variable must also be declared in each function that wants to access it; this states the type of the variable. The declaration may be an explicit extern statement or may be implicit from context (see K&R 2nd. 1.10)

Definition vs. Declaration

Definition'' refers to the place where the variable is created or assigned storage;declaration’’ refers to places where the nature of the variable is stated but no storage is allocated. (see K&R 2nd. 1.10)

• see Declare vs Define in C and C++

Constant expression 常量表達式

A constant expression is an expression that involves only constants. Such expressions may be evaluated at during compilation rather than run-time. (see K&R 2nd. 2.3)

學習資源

• Notes on Data Structures and Programming Techniques (CPSC 223, Spring 2018)

留言與分享

• RcppCWB: 綁定CWB後端的R套件
• cwbtools: 與上面套件是來自同一個作者

以下參考連結皆來自 CWB官網的References段落

• Inside the IMS Corpus Workbench

  • Requires special database engine for text corpora
    • effcient indexing of large text corpora with linguistic annotation
    • allow non-technical users to write complex search patterns

• [Witten et al. 1999 (2nd)] Managing gigabytes

  • CWB作者自己說CWB的設計大體來自於本書

• [Christ 1994] Corpus Aministrator’s Manual

留言與分享

• Vyatkina & Johnson. (2007). Teaching German Modal Particles: A Corpus-based Approach.
  • 此網站有提供Handout的下載連結，很實用的練習
• Bross, Fabian. (2012). German modal particles and the common ground

留言與分享