如何從句子中的單字搜尋詞典中符合的詞彙？ / How to search for the matching terms in the dictionary from a word in the sentence?
如果我想要以一個字搜尋字典裡面有的詞彙，而這個詞彙又需要符合該字在句子構成的詞彙時，要怎麼做呢？舉例來說，我想在「清晨時去游泳池」這個句子裡，用「泳」來找出「游泳池」、「泳池」、「游泳」，但要排除掉「晨泳」、「泳褲」等詞彙。我整理了一套搜尋演算法來實作這個目標，這套搜尋演算法包括了過濾出現字、過濾相連順序、過濾相符詞彙、排序詞彙長度、排序錨點字位置這五個步驟。以下我將以JavaScript程式碼來講解各步驟的做法，最後附上JavaScript跟PHP兩種版本的實作程式碼。
問題陳述 / Problem
輸入 / Input
現在我們有一個從句子的其中一個字來搜尋詞典的需求。在這個例子中輸入的參數有三個：
- 句子 (sentence)：「清晨很想去游一下，到了游泳池，才發現沒帶泳褲。」資料類型為字串
- 句子中欲搜尋的一個字的位置(在這裡稱為錨點字之位置) (anchorPosition)：「12」 (該位置對應的字是「泳」)，資料類型為整數
- 詞典中符合該字的詞彙列表 (dictTerms)：目前已經從資料庫中找出對應了「泳」的詞彙，資料類型為陣列，詞彙如下：
| 編號 | 詞彙 |
| 0 | 晨泳 |
| 1 | 游泳 |
| 2 | 游泳池 |
| 3 | 泳池游 |
| 4 | 泳池 |
| 5 | 泳褲 |
| 6 | 泳客 |
預期輸出 / Output
我們希望透過以上三個輸入參數，找出最符合句子中出現的詞彙，並依照詞彙長度遞減、錨點字位置遞增的順序排序，最後結果應該如下：
| 編號 | 詞彙 |
| 0 | 游泳池 |
| 1 |
泳池 |
| 2 | 游泳 |
實作程式碼 / Codes
這要怎麼做呢？
我將這套搜尋演算法寫成JavaScript與PHP兩種版本，都放在GitHub上可供參考：
- JavaScript版本：你可以直接用瀏覽器開啟來測試
- PHP版本：你可以在PHP Sandbox測試
以下我們就用JavaScript版本來看看整個演算法要怎麼運作吧。
演算法流程 / Algorithm
演算法的大致上順序如下：
- searchDictionaryByWordInSentence(sentence, anchorPosition, dictTerms)：進行以句子中的單字搜尋字典詞彙
- filterByOccurs 詞彙的每個字都得要出現在句子中
- filterBySequence 詞彙每個字在句子中的位置，必須是連續出現
- filterTermSequence 詞彙每個字在句子中的連續位置所組成的字，必須和詞彙相同
- sortTerms 詞彙排序
- 如果詞彙長度不同，較長的詞彙排序較前
- 如果詞彙長度相同，錨點字位置在詞彙中出現的位置較前者，排序較前
以下我不講解每個函式內部的運作細節，主要是展現資料在每個階段的變化，讓大家瞭解一下整個演算法是怎麽實際運作的吧。
主要流程 / Main
撇除前面的函式宣告之外，下面是主要執行的流程：
// 輸入句子
let sentence = "清晨很想去游一下，到了游泳池，才發現沒帶泳褲。"
// 輸入錨點字的位置
let anchorPosition = 12 // 泳
// 輸入詞彙
let dictTerms = [
"晨泳",
"游泳",
"游泳池",
"泳池游",
"泳池",
"泳褲",
"泳客"
]
// 開始執行
let sortedFilterTerms = searchDictionaryByWordInSentence(sentence, anchorPosition, dictTerms)
最後得到的sortedFilterTerms就是我們要的結果。
接下來讓我們來看看searchDictionaryByWordInSentence()這隻程式在做什麼吧。
以句子中的單字搜尋字典詞彙 searchDictionaryByWordInSentence() / Search for the matching terms in the dictionary from a word in the sentence
該程式做的事情大多都會對應到之前宣告的函式，讓我們一個一個來看看。
將句子轉換成反向索引典 buildInvertedIndex() / Convert sentence into inverted index
let sentenceIndex = buildInvertedIndex(sentence) // 將句子轉換成反向索引典在這一步中，會將輸入句子「清晨很想去游一下，到了游泳池，才發現沒帶泳褲。」轉換成反向索引典，這是一個JSON關聯陣列，結果如下：
{
。: [22],
一: [6],
下: [7],
了: [10],
到: [9],
去: [4],
帶: [19],
很: [2],
想: [3],
才: [15],
晨: [1],
池: [13],
沒: [18],
泳: [12, 20],
清: [0],
游: [5, 11],
現: [17],
發: [16],
褲: [21]
}反向索引典將根據字來記錄字在句子中出現的位置。例如「清」是句子中的第一個字，編號是0。「泳」則在句子中出現了兩次，各別是在「12」跟「20」這兩個位置。
將詞彙轉換成二維詞彙表格 buildTermsTable() / Convert terms into table
let termsTable = buildTermsTable(dictTerms) // 將詞彙轉換成二維詞彙表格原本輸入的詞彙列表如下，資料格式為陣列：
| 晨泳 |
| 游泳 |
| 游泳池 |
| 泳池游 |
| 泳池 |
| 泳褲 |
| 泳客 |
轉換過程會加上位置欄位(positions)，建立一個二維陣列的表格termsTable：
| 編號 | term | positions |
| 0 | 晨泳 | [] |
| 1 | 游泳 | [] |
| 2 | 游泳池 | [] |
| 3 | 泳池游 | [] |
| 4 | 泳池 | [] |
| 5 | 泳褲 | [] |
| 6 | 泳客 | [] |
詞彙的每個字都得要出現在句子中 filterByOccurs() / Does every words in term occurred in sentence
termsTable = termsTable.filter(item => {
let positions = filterByOccurs(sentenceIndex, anchorPosition, item.term)
if (positions === false) {
return false
}
item.positions = positions
return true
})在處理後，原本7個詞彙的termsTable只剩下6個，內容如下：
| 編號 | term | positions |
| 0 | 晨泳 | [1, 12, 20] |
| 1 | 游泳 | [5, 11, 12, 20] |
| 2 | 游泳池 | [5, 11, 12, 13, 20] |
| 3 | 泳池游 | [5, 11, 12, 13, 20] |
| 4 | 泳池 | [12, 13, 20] |
| 5 | 泳褲 | [12, 20, 21] |
| 6 | 泳客 | [12, 20, -1] |
「泳客」這個詞彙會在此階段中被刪除，因為「客」並不存在句子中。其他詞彙中每個字在句子中的位置則記錄在positions裡。例如「晨泳」的positions為[1, 12, 20]，這是由「晨」在句子中的位置 [1] 跟「泳」在句子中的位置[12, 20]所組成。
詞彙每個字在句子中的位置，必須是連續出現 filterBySequence() / Does the positions of term keep it continuous
termsTable = termsTable.filter(item => {
let termlegnth = item.term.length
let positionSequence = filterBySequence(anchorPosition, termlegnth, item.positions)
if (positionSequence === false) {
return false
}
item.positions = positionSequence
return true
})在處理後，原本6個詞彙的termsTable只剩下4個，內容如下：
| 編號 | term | positions |
| 0 | 晨泳 | [1, 12, 20] |
| 1 | 游泳 | [5, 11, 12, 20] |
| 2 | 游泳池 | [5, 11, 12, 13, 20] |
| 3 | 泳池游 | [5, 11, 12, 13, 20] |
| 4 | 泳池 | [12, 13, 20] |
| 5 | 泳褲 | [12, 20, 21] |
「晨泳」跟「泳褲」都在這個階段中被刪除。「晨泳」在句子中的位置並沒有連續，所以被移除。另一方面，「泳褲」的位置雖然有連續，而且連續的長度達到該詞彙的長度2，但是因為不包含錨點字的位置而被移除。
其他保留的四個詞彙，他們的positions欄位只留下有連續的位置，其餘位置資料移除。
詞彙每個字在句子中的連續位置所組成的字，必須和詞彙相同 filterTermSequence() / Is the positions of term in sentence match the term
termsTable = termsTable.filter(item => {
if (filterTermSequence(sentence, item.positions, item.term) === false) {
return false
}
return true
})在處理後，原本4個詞彙的termsTable只剩下3個，內容如下：
| 編號 | term | positions |
| 0 | 游泳 | [11, 12] |
| 1 | 游泳池 | [11, 12, 13] |
| 2 | 泳池游 | [11, 12, 13] |
| 3 | 泳池 | [12, 13] |
「泳池游」在這個階段中被刪除。在這個階段中，我們根據「泳池游」在句子中的位置取出對應的文字，並組成文字「游泳池」，結果發現這個字並不符合詞彙「泳池游」，所以被移除。
詞彙排序 sortTerms() / Sort terms by length and anchor position
let sortedFilterTerms = sortTerms(termsTable, anchorPosition)排序之後，sortedFilterTerms的內容如下：
| 編號 | term | positions |
| 0 | 游泳池 |
[11, 12, 13] |
| 1 | 泳池 | [12, 13] |
| 2 | 游泳 | [11, 12] |
排序有兩種權重，當前者相同時，再來考慮後者：
- 詞彙長度較長者，排序優先。因此「游泳池」比「泳池」還要前面。
- 錨點字位置較前者，排序優先。錨點字位置「12」在「泳池」的positions中的位置是0，在「游泳」的positions中的位置是1，因此「泳池」比「游泳」還要前面。
最後再重新建構一個只有term構成的陣列，就完成我們整個搜尋演算法囉。
想要自己試試看的話，請從以下連結找到演算法原始碼喔。
結語 / In closing
這個演算法為了講解方便，我做了很多拆分。運作效率可能還有提升的空間。
為什麼會想要整理這個演算法呢？以前在面對這個問題時，很多人都會先將句子進行「斷詞處理」，然後再用斷詞結果來查詢詞典。舉例來說，句子是「清晨時去游泳池」，斷詞結果會取出「清晨」、「時」、「去」、「游泳池」這四個字，而搜尋時會以「游泳池」這個詞彙來搜尋。
這個方法有很多缺點：
- 加入斷詞器會大幅度增加程式的複雜性。你必須先確保整個系統能夠運作斷詞器。
- 斷詞結果可能會與詞典中的詞彙不符合。
- 只能保存單一斷詞結果。
2跟3這個兩個缺點在實務運作上影響甚鉅。當我們用斷詞結果「游泳池」來搜尋詞典時，就找不出「游泳」和「泳池」這兩個字。
最近又有人遇到類似的問題，我才把這個問題的解法整理一下，寫成JavaScript跟PHP兩種版本。希望大家未來想要根據句子中的單字來搜尋詞典時，不要再用複雜的斷詞器了，用這個簡單的演算法就可以了。
那麼這次從句子中的單字搜尋詞典的教學就到這裡了。寫到最後，我想問你在面對這個問題時，你會怎麽做呢？
- A. 試試看這個演算法好了
- B. 看不太懂，我還是比較信賴斷詞器的結果
- C. 我從來沒遇到這樣的問題
- D. 其他
歡迎在下面的留言處跟我們分享你的想法。大家的意見是我繼續分享的動力喔！如果你覺得我這篇實用的話，請幫我在AddThis分享工具按讚、將這篇分享到Facebook等社群媒體吧！
感謝你的耐心閱讀，我是布丁，讓我們下一篇見。
