Spring 2015 Natural Language Processing Lab.
Week 7. Linggle and MapReduce
Instructor: Jason S. Chang




這是一個實作簡易版 Linggle 的概念。

Introduction

先想像一下這個網路世界是由一堆的 URLs 和網頁所組成的 (Interlinking web pages with keywords)。而搜尋引擎的功能，就是當你輸入一個（或是一組）關鍵字之後，給你一堆的 URLs 以及網頁（或是這組關鍵字的交集），這就是 Inverted list。

然而，使用者不可能只搜尋一個或是一組關鍵字，使用者下的 query 有可能是 phrase, phrase with wildcard 或甚至是含有詞性的 phrase with wildcard，這些 query 又該怎麼處理呢？這次實作最基本的概念，就是利用這個 Inverted list 來找出所有可能的 query 相對應的 ngrams。

Linggle.com 是清大自然語言處理實驗室開發的一個語言搜尋引擎(Linguistic Google)，背後是 $10^{12}$ 的巨量資料。

這是 Linggle 的 command 語法。這次實作要處理的，是最簡單的 part of speech 以及底線的部分。舉個例子吧，假設使用者輸入這個 query：

adj. beach

這個 query 就是在問哪些形容詞可以來形容 beach 呢？
能得到以下以出現頻率高至低來排列的結果：

超神奇的啦。還記得當年在趕 NTCIR 論文的時候，一直很苦惱什麼字該搭配什麼動詞或是形容詞，然後學長聽到我的哀嚎就介紹了這個網站給我，當時真的覺得得到了救贖XDD

Implementation

由於時間上的限制，我們只需要處理簡單的 query：僅包含關鍵字、詞性以及 wildcard。以下是範例：

pleasantly surprised prep. her
adv. surprised
_ surprised _ her

而原始資料是已經斷好詞並標好詞性的 1-5gram，例如：

pleasantly|adv surprised|v by|prep her|pron  50

實作流程如下：

  1. Mapper
    (1) 讀入所有ngram
    (2) 產生的pairs，如下圖：

    先將所有 n-gram 讀入，然後做一些處理，去頭去尾啊，split() 之類的。為求統一，所有的 ne. 一律都被取代成 n.，這樣比較好處理。接著使用 product 來做「組合」，注意要把 product 結果中的 (‘_‘, ‘_‘, ‘_‘, ‘_‘) 給 pop() 出來，不然會產生很多無用的 n-gram。而且誰這麼無聊下這種 query 啦！XD

    這部份程式碼如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def mapper(files):
        for line in fileinput.input(files):
            allcand = []
            ngram, value = line.strip().split('\t')
            for w in ngram.strip().split(' '):
                w += '.|_'
                w = re.sub("ne.", "n.", w)
                allcand.append(tuple(w.split('|')))
            prod = list(product(*allcand))
            prod.pop() # pop ('_', '_', '_', '_')
            for element in prod:
                print '{}\t\t{}'.format(str(element), str(line)),

    mapper產生的結果節錄：

    (query)  ngram  freq.
('After', 'a', 'n') After|prep a|det moment|n   56
('After', 'a', '_') After|prep a|det moment|n   56
('After', 'det', 'moment')  After|prep a|det moment|n   56
('After', 'det', 'n')   After|prep a|det moment|n   56
('After', 'det', '_')   After|prep a|det moment|n   56
('After', '_', 'moment')    After|prep a|det moment|n   56
('After', '_', 'n') After|prep a|det moment|n   56
('After', '_', '_') After|prep a|det moment|n   56
('prep', 'a', 'moment') After|prep a|det moment|n   56
('prep', 'a', 'n')  After|prep a|det moment|n   56
('prep', 'a', '_')  After|prep a|det moment|n   56

  2. Reducer
    (1) 將mapper產生的pairs讀入
    (2) 產生一個query對上多個ngram的pairs，如下圖：

    步驟(1) 完成之後，又再次使用了 groupby，把所有相同 query 可以查到的 n-gram 都集合起來，並且依照出去頻率將他們排列，頻率排在該 query 前 10 的 n-gram 才會被輸出。程式碼如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    for key, group in groupby(allGrams, key = lambda x: x[0]):
        fileout.write('\n{}#'.format(key))
        withScores = []
        for g in group:
            ngram, value = g[1].strip().split('\t')
            ngram = re.sub('[a-z]* ', '', ngram)
            ngram = re.sub('[a-z]*$', '', ngram)
            try:
                withScores.append((ngram, int(value)))
            except:
                pass
        result = sorted(withScores, key = lambda x: x[1], reverse = True)
        if len(result) >= 10:
            for i in range(10):
                fileout.write('{}\t'.format(str(result[i])))
        else:
            for r in result:
                fileout.write('{}\t'.format(r))

    會產生一個長很醜的結果：

    (query)#(ngrams)
('After', 'a', 'n.')#('After a while', 105) ('After a moment', 56)  
('After a couple', 41) ('After a year', 34) ('After a period', 31)
('After a week', 27) ('After a time', 23)

    然後要讓使用者輸入query並即時取得result，所以必須再寫一隻query的程式才能完工。由於真的不知道怎麼處理這份結果，只好又將它建成字典，key是輸入的query，value則是ngrams：

    1
    2
    3
    4
    def buildDict():
        for line in fileinput.input('result_new.txt'):
            key, res = line.strip().split('#')
            dicAll[key.strip()] = res

  3. 再來是讓使用者輸入query來查詢的部分。
    這邊是先用 raw_input 取得使用者的輸入，然後去字典裡找，找到的就吐回 n-gram 給使用者，沒找到就印 “no matching result”。停止條件則是手動輸入 exit()。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def search():
        print "enter 'exit()' to quit."
        while True:
            query = str(tuple(raw_input('> query: ').split(' ')))
            if query == "('exit()',)":
                break
            if query in dicAll.keys():
                result = dicAll[query.strip()].split('\t')
                for r in result:
                    print r
            else: print "no matching result

以上，又完成一次壯烈的Lab了…