基于正向最大匹配算法的問答應用與圖譜構建

焦自程

（西藏大學 西藏 拉薩 850000）

0 引言

本文將問答功能視作系統的核心功能，以四大名著為數據基礎，并將數據以知識圖譜的形式展現出來，體現數據的可視化操作。該知識圖譜以四大名著中的人物為基礎，通過收集大量關于四大名著的人物數據，將各名著人物之間進行關聯，具體功能有：登錄注冊功能、查詢功能、問答功能、人物關系修改功能、前端知識圖譜展示功能、問答記錄功能。用戶初始需要進行登錄，這需要用戶輸入個人信息，當用戶注冊成功后，用戶輸入已注冊好的賬號密碼即可登錄成功。登錄成功后用戶可以直接看到該知識圖譜中含有的人物關系數量、實體數量、人物簡介數量，還展示了目前數據中四大名著各自的占比為多少。查詢功能為：用戶可以直接搜尋某個人物，系統會顯示該人物的簡介，以及與該人物有關的人物關系。問答功能為：用戶可直接查詢某些與四大名著有關的問題，如：“孫悟空和唐僧的關系是什么？”，系統會查找孫悟空與唐僧的數據，提取出關鍵詞“關系”，將數據中孫悟空與唐僧的關系輸出，即可得到自己的答案。問答記錄為：顯示用戶所查找的問題，避免用戶重復搜索一個問題。人物關系修改為：用戶可搜索兩個人物之間的關系，然后進行修改，最終數據以自己修改后的為準。其中問答功能為重中之重，以正向最大匹配算法為實現基礎，將用戶想要詢問的句子中的詞分割，之后將分割好的詞與用戶提前導入的詞庫組匹配，找到相應的詞匯即會輸出相對應的答案。該算法在原本基礎上添加同義詞，對于同義不同命的詞系統會看作同一個詞，減輕了系統需要添加的詞匯量，并提高了系統的成功率與可行性。

1 項目背景

知識圖譜最早是谷歌開始使用，隨后在教育、交通、醫療、金融等各個領域開始大規模應用，知識圖譜技術已經發展的較為成熟，應用于各種領域之中[1]。而如今科技飛速發展，有越來越多的人開始遺忘中國古代傳統文化，其中就包含四大名著。四大名著是中國傳統文化的重要組成部分，它包含了一些中國特別的元素，它也教導我們一些重要的道理，因此加強四大名著的學習就顯得格外重要。本項目以四大名著為數據基礎進行知識圖譜的構建，該項目有助于將我們的傳統文化，推廣到國外愛好中國文化的人之中，讓世界的人都認識到中國傳統文化的獨特以及中華文學的深厚。

2 項目展現

四大名著知識圖譜系統軟件總共有4 大子模塊，他們分別是：登錄注冊模塊、知識圖譜數據展示模塊、人物查詢模塊、問題回答與問題記錄模塊。登錄注冊模塊體現為：用戶初次登錄需進行注冊，輸入自己的個人信息，登錄時填寫好自己的賬號密碼登錄即可。四大名著知識圖譜系統軟件通過前端知識圖譜展示四大名著中人物，有各自數據占比、人物數據與人物關系數據[2]。人物查詢模塊為：用戶可以直接查詢自己想要了解的人物，進入人物查詢模塊即可直接輸入人物，之后系統會輸出關于該人物有關的數據。問答模塊主要為：對用戶提出的問題利用正向最大匹配算法進行分詞查詢，利用詞典里的數據進行逐步比較查詢，當輸入的語句中分離的詞語能在詞典中找到時，即可輸出答案[3]。而用戶利用問答記錄能顯示用戶查詢的所有問題，節省用戶時間。系統總的流程圖見圖1。

當系統程序初始化之后，系統根據用戶需求進入登錄界面，開始展現登錄頁面，用戶初次登錄需進行注冊，注冊需填寫自己的個人信息，待注冊好之后下次可直接登錄無需重新注冊。進入知識圖譜用戶可直接看到關于四大名著中人物數據，每個名著的人物占比、人物關系數據、人物簡介數據，知識圖譜可一目了然地顯示這些數據。之后用戶如果要查詢，又可分為查詢人物與問題兩模塊。當用戶想要查詢某個人物時，可直接在查詢人物里輸入自己想查找的人物，該人物的簡介和一些經典視頻就會出現；當用戶想查詢問題時，例如人物之間的關系，此時在查詢問題里即可顯示。用戶的問題都可在記錄里查找到，避免用戶重復查詢一個問題。用戶想要修改一些數據例如人物關系時，用戶可在修改里找到自己想要修改的關系，然后進行修改。

3 問題描述

當用戶對于四大名著中的人物有一些問題時，這時就需要系統具備問答功能以解決用戶簡單的問題。問答功能的實現必須依賴一定的算法，其中涉及處理句子的分詞等功能，最關鍵的是能通過對句子的操作來找到該句子在詞庫中最相似的問題與答案[4]。而當用戶想查詢的句子中涉及多個詞匯時就需要思考如何操作才能滿足多個詞匯均可適合的答案。在眾多算法中，正向最大匹配算法可以找到用戶想查詢的語句在詞庫中的詞匯[5]，隨后根據詞匯的詞性做出正確的選擇。

4 基于正向最大匹配算法的問答實現

正向最大匹配算法通過分詞，將一個完整的句子分為若干個單字詞，按照原語句的順序，從第一個字開始搜查是否在詞庫中，無論是否找到都需要繼續向右查詢，直到從句首查找到句尾，并記錄最后一次可以在詞庫中查詢的結果，視作該詞可以在詞庫中找到，若從句首開始查詢無法在句子中找到詞匯，則從下一個字開始查詢；當找到詞匯時，下次查詢詞時要去掉上次已經查詢過的詞[6]，隨后繼續從新句子的句首開始查詢，循環如此。最終可以找到一個句子中有幾個詞是可以被查詢到的，并根據詞匯占比將得到詞匯對應的句子輸出[7]。

表1 詞匯占比及其相關性

4.1 對句子進行分詞

一個完整的句子是由許許多多的詞組成，要進行算法的第1 步便是對句子進行拆分詞，將一個句子的所有字都拆分為單獨的詞[8]。這里以“計算機課程十分有趣”為例，對句子進行正向最大匹配算法，分詞后的結果為sentence1={“計”，“算”，“機”，“課”，“程”，“十”，“分”，“有”，“趣”}。

4.2 找到在詞典的對應詞

在詞典終提前導入以下對應的詞匯words={“計算”，“計算機”，“課程”，“有趣”}，隨后將sentence1={“計”，“算”，“機”，“課”，“程”，“十”，“分”，“有”，“趣”}中的詞按照在句子中的順序進行查找，從“計”詞開始，按照“計”→“計算”→“計算機”→“計算機課”→“計算機課程”的順序，而“計算機課程”為以“計”為句首找到的最長的詞，從“計算機課程十”到“計算機課程十分有趣”為過渡的詞均無法在詞庫words 中找到，最終可找到以“計”為句首的詞為“計算機課程”，將原句子中的“計算機課程”剔除之后的句子為“十分有趣”；隨后在詞典中查找以“十”為句首的詞，從“十”→“十分”→“十分有”→“十分有趣”在詞庫中均無法找到，因此，將“十”剔除；查找以“分”為句首的詞，從“分”→“分有”→“分有趣”中均無法找到以“分”為句首的詞，因此繼續將位置后移，將“分”在句子中剔除，保留句子為“有趣”；在詞典中查找以“有”為句首的詞，“有”→“有趣”，“有趣”可在詞庫中找到。通過以上步驟，最終得到詞匯“計算機課程”和“有趣”[9]。

4.3 輸出詞匯對應的語句

通過分詞和正向最大匹配算法，找到能在詞庫中對應句子的詞匯“計算機課程”和“有趣”，因為這里“計算機課程”與“有趣”在句子“計算機課程十分有趣”中的詞匯占比為0.78，這里系統會將最長詞匯“計算機課程”在詞庫中對應的語句輸出，實現初步問答的功能。

4.4 加入同義詞

當前已實現初步的問答功能，但僅僅只能實現單一詞匯的識別，對于同義不同名的詞將會識別為不同詞，為了提高系統的靈活性，該系統添加同義詞詞典，將不同名稱的詞但含義相同的詞識別為一類詞，例如“西紅柿”和“番茄”為同一種蔬菜，但只是不同的名稱而已[10-11]。

5 將正向最大匹配算法應用到問答系統

我們將該正向最大匹配算法應用到問答系統中，具體的思想為：提前在數據庫中導入需要的數據，然后將用戶輸入的問題進行正向最大匹配算法的處理，得到最終的詞匯，根據詞匯占比將詞匯對應的匹配語句進行輸出，實現問答功能[12]。

首先，該問答系統需要提前存儲相關的數據，這是保證問答功能實現的前提條件。然后將用戶想要詢問的問題輸入在搜索框里，隨后通過正向最大匹配算法對用戶輸入的問題進行處理，得到在系統中提前導入的詞匯，將系統中詞匯對應的語句進行輸出，實現問答功能[13]。最后要注意做好需要咨詢的數據不在數據庫里的準備。存儲數據的有限性使得我們不會總能夠查找到相關數據。當我們需要查找的數據的詞語占比低于0.4 時，這時需要查找該方面的數據將其導入，將數據再導入數據庫中進行完善。

總結流程：（1）將用戶輸入的問題進行正向最大匹配算法處理；（2）若最終得到的詞匯占比大于0.8，直接將詞匯對應的語句輸出；（3）若詞匯占比小于0.8 大于0.4，則將最長詞匯進行輸出；（4）若詞匯占比小于0.4，則查詢相關數據，將數據到的新數據導入數據庫，并將其輸出。

6 算法實驗

在該實驗中，以“我愛西紅柿與大米”為簡單例子進行實驗。如圖2 所示。

首先，在該算法里，list 代表原句，即用戶咨詢的語句；listcode 代表分詞后的詞組，dict 代表在詞典中可以查到的相對應的詞組，finallist 為通過正向最大匹配算法得到的詞組。Proportion of vocabulary1 與Proportion of vocabulary2 都是通過finallist/list 得到的結果[14-15]。

當不加入“番茄”為同義詞時，系統并不能對“西紅柿”進行識別，此時系統能查詢到的詞匯為“我”“愛”和“大米”，此時的詞匯占比為0.5，僅僅將“大米”對應的語句進行輸出。

在加入同義詞時，系統識別的詞匯為“我”“愛”“西紅柿”和“大米”，此時的詞匯占比為0.88，系統會將“我”“愛”“西紅柿”和“大米”對應的語句都進行輸出。

加入同義詞前與加入同義詞后進行對比，原句是“西紅柿與大米”，明顯“西紅柿”和“大米”的共同加入更符合問答。

7 結語

本文將名著傳統知識以圖譜的形式構建出來，可以清晰地看出各名著的所占比和相關人物數據，體現出數據的可視化，并在圖譜的大框架中加入問答系統，而正向最大匹配算法是問答系統成功實現的算法前提。正向最大匹配算法應用在問答系統中的案例并不多，在該問答系統中，主要依賴算法分詞后最終得到的詞組，根據詞組在原句中的詞匯占比來決定輸出哪一部分的詞匯語句，并在該基礎上添加同義詞來增強系統的準確度和可靠性。