基于前后端分離算法的ACM 智能管家系統

高云澤， 王莉莉， 董文睿， 馮紫君， 胡祖容， 趙中楠

（哈爾濱理工大學 計算機科學與技術學院， 哈爾濱 150080）

0 引 言

國際大學生程序設計競賽（ACM／ICPC）是由國際計算機協會（ACM）主辦的比賽，其宗旨是展示大學生的創新能力、團隊精神，以及在壓力環境下通過編寫程序進行分析和解決問題的能力。

目前，在國內ACM 賽事的訓練過程中發現一些急需解決的問題。 根據1995 ～2018 年中國大陸高校入圍ACM-ICPC 全球總決賽統計數據可知，大部分高素質人才集中在名校，入圍高校中只有5 所是非985／211。 其次，有些高校的投入力度不夠，很多學校ACM 活動僅由社團、協會或團委以課余活動的形式開展，在資金、師資、設備、場地等方面受到一定的限制，影響了發展規模。 還有一些學校起步比較晚，經驗不足，只能通過去友校參觀學習、摸著石頭過河等方法去積累經驗，需要很多拓荒者。 在此過程中，會遇到許多困難，比如訓練內容繁多復雜，短期內看不到成績、感覺不到自己的進步等等，慢慢會感到枯燥、迷茫，甚至放棄。 造成這些問題的另一個重要原因，是缺少一個好的學習輔助平臺，以及系統的學術交流平臺來提供指導和幫助。 對于參加ACM 競賽的學生來說，訓練過程中迫切地需要相應的科學指導；對于學校的ACM 組織來說，也需要一個高效的團隊管理系統。 因此，開發一個集能力分析、訓練指導、團隊管理和學術交流平臺于一體的智能管家系統尤為必要。

本文針對此問題研發了ACM 智能管家系統，該系統通過爬蟲技術獲取題目信息，通過機器學習中的分詞技術，歸納出題目的標簽，建立智慧題庫，讓用戶更方便地選擇適合自己能力的題目；通過爬蟲技術抓取用戶歷史刷題記錄，并將可視化展示給用戶，讓用戶更好地在系統中感受到自己的成長。 該系統還具有好友通信、復盤總結等功能來輔助用戶更好地提升ACM 競賽能力。

1 系統分析

1.1 需求分析

系統用戶共有兩類，分別為普通用戶和管理員用戶。 管理員爬取國內外OJ 系統的題目信息，再通過關鍵詞搜索，結合分詞技術補全題目相應的算法標簽，從而構建一個大而全的智慧題庫，使用戶可以更好地篩選題目進行專項練習；同時通過用戶綁定的信息，可以獲取用戶在各大做題平臺上的做題記錄，然后再對所有做題記錄進行聚合分析，并最終整合為圖表展現給用戶，從而使用戶的成長記錄可視化。

用戶可發布團隊或者個人定時訓練賽，訓練賽題目可由用戶選擇，或者規定范圍由系統進行推送。 在用戶訓練過程中，系統會記錄用戶提交的記錄以及瀏覽記錄，并將這些信息轉化為圖表展現給用戶，方便用戶進行復盤總結。

日志主要用于滿足用戶即想即記的需求，并且采用多級分類結構，可以讓日志的管理更為便捷。在通信方面，通過WebSocket 建立長連接，滿足用戶間實時通信的需要。

系統用例如圖1 所示。

圖1 系統用例圖Fig. 1 Use case diagram of system

1.2 系統框架

該平臺基于B／S 的開發模式，利用前后端分離技術，實現系統的高內聚低耦合，減少后端服務器的并發／負載壓力。 前端使用Electron 和Vue 框架搭建，基于組件化思想來提高各個組件復用，降低耦合度。 后端使用Django 框架搭建，利用各種數據庫訪問插件，大大提高了數據庫訪問的效率。 用戶操作用戶界面向后端發送對應事件，后端收到事件，通過方法查詢對應數據并整理后送給前端，前端收到結果集后，將數據整理并渲染展示給用戶。 系統結構如圖2 所示。

圖2 系統結構圖Fig. 2 Structure of system

1.3 系統基本策略

該系統研究的主要問題如下：

（1）如何在抓取題解后使用合適的文本分詞來劃分題目標簽，并提高題目標簽的準確性；

（2）系統需要隨時執行抓取題目，獲取用戶做題信息，處理題目標簽等任務，系統如何在保證高效的情況下執行這一系列操作，無論是用戶信息或者題庫信息都會存在變動，系統如何實時并同步更新這些信息；

（3）如何保證用戶間實時通信和消息推送。

根據以上分析，本系統的基本策略如下：

（1）對目前的算法標簽種類進行整理，獲取一個全集計數表。 對于一份題解進行分詞處理后，提取所有題目標簽，在全集表中對相應的題目標簽進行計數。 在查詢獲取一定題目的標簽后，統計全集表中計數最大的題目標簽，并以此標簽作為該題目的標簽；

（2）利用Redis 作為消息隊列來處理耗時的異步操作。 主服務器向Redis 中的對應任務隊列分發任務；后臺服務器通過隊列的優先級別，由高到低不斷獲取隊列中的任務并在主服務器中運行。 同時主服務器可以向Redis 中下發定時任務，后臺服務器按照消息隊列的任務優先級來調度處理。 在處理完單個任務之后，按需將結果返回給主服務器。 任務處理機制如圖3 所示；

圖3 任務處理機制Fig. 3 Task processing mechanism diagram

（3） 對比常用實時通信方法， 本文選擇WebSocket 協議。 用戶成功登錄后，與后端服務器建立雙向通信通道。 當用戶間進行實時通信時（如聊天、發信息等），系統會將消息即時推送給同時在線的用戶，或者將消息緩存到數據庫中，直到對方下次登錄時再進行推送；此外服務器也可以在特定時機，主動將消息推送給用戶。

1.4 系統數據組成

本系統數據主要由3 個部分組成：

（1）用戶在系統內的行為數據。 其中包括用戶的基礎信息、團隊信息、訓練記錄以及相關日志信息；

（2）用戶在其他訓練平臺的歷史做題記錄，主要用于將用戶的成長過程進行可視化展現；

（3）系統題庫數據是系統的核心數據，這部分數據主要通過爬蟲的方式，去獲取主流做題訓練平臺的題庫信息，再通過關鍵詞搜索加分詞技術補全題目相應的算法標簽。

2 系統主要模塊設計

2.1 智慧題庫模塊

智慧題庫模塊由爬蟲獲取的信息實現，爬蟲能力占據該模塊的主體。 模塊中所需要爬取的信息可分為兩類：一類為題目信息，另一類為用戶做題記錄信息。 系統將這兩類信息的爬取任務交給后臺主線程執行，主線程將任務分發到不同的任務棧中，對任務棧初始化后，由子進程來執行任務棧中的任務。在子進程處理任務期間，若遇到異常則及時拋出，當所有任務棧中的任務執行完畢后，后臺主線程結束。爬蟲框架如圖4 所示。

圖4 爬蟲框架Fig. 4 Spider framework

2.1.1 系統題庫搭建

本系統主要獲取國內外最主要的三大實體OJ題庫信息，分別為CodeForces、HDU，以及POJ。 題庫中，除Codeforces 可以直接通過爬蟲抓取題目標簽以外，其余題庫題目均為從題目標簽層面來對題目進行劃分。 因此，系統題庫的實現首先必須滿足以下條件：

（1）獲取題庫原始數據；

（2）對于原始題庫中缺乏的數據進行補全。

為了搭建系統題庫，首先通過爬蟲來獲取各個題庫的題目信息，存入題庫后再由后臺分發對應的任務存入到Redis 服務器中。 當后臺服務器處理到任務時，通過爬蟲抓取對應題庫的題目信息。 對于已有標簽的題目則直接存入系統題庫，對于沒有標簽的題目再進行第二次爬蟲。 第二次爬蟲基于題目信息來爬取題目的題解，在html 頁面獲取題解內容后，通過文本分詞劃分高頻標簽，并進行計數統計，以計數最高的標簽作為該題目的標簽并存入題庫。 題目處理流程如圖5 所示。

圖5 題目處理流程Fig. 5 Flow chart of problem handling

2.1.2 用戶成長記錄模塊

支持用戶成長記錄模塊的數據，主要來自題庫內獲取到的用戶做題信息及題目信息。 當用戶使用該系統時，可以選擇希望綁定的OJ。 系統在綁定OJ后，會對該用戶的做題記錄進行爬取，將爬取的題目映射到系統題庫內的題目，并對這些題目進行時間、題庫以及題目標簽上的劃分，使用ECharts 來處理這些數據并整合為圖表展示給用戶，讓用戶對自己做題的數量、類型和周期有一個直觀的了解。

（1）用戶信息抓取：當用戶登錄管家系統后，系統會向用戶申請綁定OJ 賬號，當賬號綁定成功后，系統將利用爬蟲模擬用戶登錄并獲取用戶提交過的題目id。 這個過程具有一定的時間間隔，該任務會被放到定時任務中，在特定的時刻對任務進行爬取并執行。 在完成模擬登錄以及獲取題目id 后，系統將此部分的題目id 與系統題庫內的id 進行映射對比，獲取此部分的題目信息集合，將該部分內容的時間、題目來源和題目標簽等信息進行抽離，并形成圖表所必須的信息集合；

（2）用戶數據可視化：用戶可視化需要使用到用戶信息集合，將用戶信息集合按照做題時間、題目來源、題目標簽進行劃分后，在ECharts 的模型層，將對應的JSON 數據注入到對應的圖表信息中，并在視圖層對圖表樣式進行配置。 之后，在控制層對事件展示進行控制，最后將用戶的做題信息以圖表的形式展現給用戶。

2.1.3 用戶個性化題庫模塊

用戶個性化題庫模塊負責將后端采集到的題目信息展現給用戶。 其中包括用戶是否通過、題目名稱、算法標簽以及該題目的通過數，并提供篩選功能。 用戶可以通過輸入題目進行模糊匹配，選擇特定平臺的題庫或者根據特定的算法標簽進行篩選。

鑒于題庫中題量較大，且需要滿足用戶的精準查詢，系統將需精準搜索的平臺題庫和標簽做了一層緩存，將用戶每次的查詢都放入緩存里，從而提升用戶使用的流暢度。

2.2 訓練與復盤模塊

訓練賽模塊支持個人訓練以及團隊訓練，用戶可在本地完成代碼，通過管家系統的接口進行提交。通過訓練模塊中的任意題目，用戶均可打開提交界面，該界面會接受用戶傳輸的源代碼并將代碼打包發送到對應OJ 平臺進行提交。

用戶在選題時，可以手動輸入題庫平臺和題目ID 來添加題目，也可以選擇一些過濾條件，通過隨機方式自動添加一些所有參與者均沒有通過的題目。

用戶在結束訓練賽后，可以進入當前比賽的“復盤模塊”。 當用戶第一次進入這個模塊時，系統自動給用戶生成一個復盤文檔的模板，用戶可以回顧整個比賽的過程，并寫下自己的收獲。

2.3 日志模塊

在日志模塊中，用戶可創建多級日志用于賽后復盤總結，每頁日志最多可存儲2 Mb 的數據。 當用戶完成日志的構建后，后臺會校驗日志數據合格性，通過校驗后存入數據庫，同時將用戶日志的緩存更新，保持數據一致性。 日志編輯框支持markdown 語法，用戶可在日志中添加文字、圖片、鏈接等一系列內容來完成賽后總結或刷題記錄，并將日志以二進制文件的方式存入數據庫中。 在用戶進入系統時由子進程查詢日志目錄結構，并將這些內容放入緩存中。 當用戶點擊對應日志時，系統進行解析，交給前端渲染，同時在緩存中添加此內容。

（1）數據結構：日志模塊中創建多層級的日志，創建的日志目錄會直觀的展示給用戶，但是為了保持數據的穩定性以及查詢效率，整體目錄最多向下延伸3 個層級。 對于任意日志均存在兩種指針：一種指向其父節點，用于子日志后回溯父日志；另一種指向子日志，用于快速展示目錄。 用戶目錄會在第一次加載后進行緩存，之后用戶刷新界面都使用緩存中獲取的目錄，直到更新目錄后臺時再次獲取新的日志目錄，并更新用戶界面，同時將新的用戶目錄傳入緩存；

（2）日志內容：用戶可使用markdown 語法來完成日志的添加。 文字和鏈接將以html 文件的形式存入數據庫，圖片也保存至數據庫。 每次加載日志時，會從數據庫匯總獲取并解析，解析后的內容會存入緩存，下次進入頁面時不再重新加載和渲染。 當用戶修改日志內容后，系統直接將用戶修改后的html文件存入數據庫，同時將緩存中的內容同步修改。

2.4 通信模塊

當用戶進行通信時，系統會在用戶之間建立一個長鏈接，用來保證信息可以實時進行傳輸。 使用長鏈接還可以在每次傳輸中復用TCP 鏈接，節約了信息傳輸時間。

通信協議遵守三層數據的規范，保證整體協議的規范化。 第一層包含具體對象、具體場景編號以及第二層數據；第二層包含好友編號和第三層數據；第三層包含具體要傳輸的數據。

當用戶編輯完消息后點擊發送鍵，后臺會將用戶編輯的信息進行序列化，并通過長鏈接將序列化后的數據傳輸給對應的好友。 對于收到的好友消息，后臺將遵守三層數據規范對數據進行解析，前端將反序列化的數據展示給用戶，至此完成了用戶之間的數據傳輸。 由于保持著長鏈接的存在，用戶進行數據傳輸的過程中減少了鏈接的反復建立，可以很大程度上提高用戶間通信的實時性。

3 系統測試

3.1 用戶登錄主頁

用戶登錄后的個人頁面展示了用戶在各個OJ平臺中的做題信息，可以直觀的查看自己在特定時間內做題的數量、標簽分類以及平臺分布。 圖6 是用戶在2021 年10 月份的做題情況。

其中，雷達圖用來展示不同標簽的做題量；餅狀圖用來展示不同題庫的做題量；柱狀圖用來展示當月每日的做題量。

3.2 題庫運行情況

訓練賽定制頁面如圖7 所示。 用戶可選擇團隊或個人的訓練方式，并且可以添加訓練賽題目：

圖6 用戶界面Fig. 6 User interface

圖7 題庫運行圖Fig. 7 Question bank

3.3 訓練賽定制和賽后復盤

訓練賽定制頁面如圖8 所示。 用戶可選擇團隊或個人的訓練方式，并且可以添加訓練賽題目。 隨機生成題目的過程如下。

（1）當用戶點擊“隨機”的時候，會檢驗當前所有的比賽參與者，個人訓練為1 人，團隊訓練為3人，并向服務端傳遞所有的參與者信息；同時服務端會通過異步的方式，篩選出所有參與者未通過的題目集合寫入緩存中；

（2）當用戶對過濾條件進行選擇并點擊“確定”時，會向服務端傳遞過濾條件，服務端根據過濾條件分別從緩存中提取滿足條件的題目集合，將這些題目集合的交集返回給用戶。

圖8 創建訓練Fig. 8 Create training match

用戶可以自定義個人／團隊的訓練賽，訓練賽后可以復盤比賽。 復盤模塊的目的是，引導用戶逐步建立起及時復盤的習慣。 復盤頁面如圖9 所示。

圖9 復盤界面Fig. 9 Match reply

3.4 用戶日志頁面運行圖

用戶可主動創建以及打開并編輯日志，所有日志都保存在用戶本地磁盤中。 日志運行界面如圖10 所示。

圖10 日志頁面Fig. 10 Log page

4 結束語

本系統實現了題目分析、訓練賽添加、信息可視化展示、好友實時通信、日志添加等功能，為用戶提供了一個全渠道的ACM 技能提升系統，目的在于提升用戶ACM 競賽水平。 本文對其功能實現和相關技巧進行了詳細闡述。 系統功能多樣、實用，交互性強，經過各個模塊的測試，系統穩定性也符合預期，是一款符合用戶需求的軟件。