基于前后端分離算法的ACM 智能管家系統(tǒng)

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

（哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 哈爾濱 150080）

0 引 言

國際大學(xué)生程序設(shè)計(jì)競賽（ACM／ICPC）是由國際計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的比賽，其宗旨是展示大學(xué)生的創(chuàng)新能力、團(tuán)隊(duì)精神，以及在壓力環(huán)境下通過編寫程序進(jìn)行分析和解決問題的能力。

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

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

1 系統(tǒng)分析

1.1 需求分析

系統(tǒng)用戶共有兩類，分別為普通用戶和管理員用戶。 管理員爬取國內(nèi)外OJ 系統(tǒng)的題目信息，再通過關(guān)鍵詞搜索，結(jié)合分詞技術(shù)補(bǔ)全題目相應(yīng)的算法標(biāo)簽，從而構(gòu)建一個(gè)大而全的智慧題庫，使用戶可以更好地篩選題目進(jìn)行專項(xiàng)練習(xí)；同時(shí)通過用戶綁定的信息，可以獲取用戶在各大做題平臺(tái)上的做題記錄，然后再對(duì)所有做題記錄進(jìn)行聚合分析，并最終整合為圖表展現(xiàn)給用戶，從而使用戶的成長記錄可視化。

用戶可發(fā)布團(tuán)隊(duì)或者個(gè)人定時(shí)訓(xùn)練賽，訓(xùn)練賽題目可由用戶選擇，或者規(guī)定范圍由系統(tǒng)進(jìn)行推送。 在用戶訓(xùn)練過程中，系統(tǒng)會(huì)記錄用戶提交的記錄以及瀏覽記錄，并將這些信息轉(zhuǎn)化為圖表展現(xiàn)給用戶，方便用戶進(jìn)行復(fù)盤總結(jié)。

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

系統(tǒng)用例如圖1 所示。

圖1 系統(tǒng)用例圖Fig. 1 Use case diagram of system

1.2 系統(tǒng)框架

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

圖2 系統(tǒng)結(jié)構(gòu)圖Fig. 2 Structure of system

1.3 系統(tǒng)基本策略

該系統(tǒng)研究的主要問題如下：

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

（2）系統(tǒng)需要隨時(shí)執(zhí)行抓取題目，獲取用戶做題信息，處理題目標(biāo)簽等任務(wù)，系統(tǒng)如何在保證高效的情況下執(zhí)行這一系列操作，無論是用戶信息或者題庫信息都會(huì)存在變動(dòng)，系統(tǒng)如何實(shí)時(shí)并同步更新這些信息；

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

根據(jù)以上分析，本系統(tǒng)的基本策略如下：

（1）對(duì)目前的算法標(biāo)簽種類進(jìn)行整理，獲取一個(gè)全集計(jì)數(shù)表。 對(duì)于一份題解進(jìn)行分詞處理后，提取所有題目標(biāo)簽，在全集表中對(duì)相應(yīng)的題目標(biāo)簽進(jìn)行計(jì)數(shù)。 在查詢獲取一定題目的標(biāo)簽后，統(tǒng)計(jì)全集表中計(jì)數(shù)最大的題目標(biāo)簽，并以此標(biāo)簽作為該題目的標(biāo)簽；

（2）利用Redis 作為消息隊(duì)列來處理耗時(shí)的異步操作。 主服務(wù)器向Redis 中的對(duì)應(yīng)任務(wù)隊(duì)列分發(fā)任務(wù)；后臺(tái)服務(wù)器通過隊(duì)列的優(yōu)先級(jí)別，由高到低不斷獲取隊(duì)列中的任務(wù)并在主服務(wù)器中運(yùn)行。 同時(shí)主服務(wù)器可以向Redis 中下發(fā)定時(shí)任務(wù)，后臺(tái)服務(wù)器按照消息隊(duì)列的任務(wù)優(yōu)先級(jí)來調(diào)度處理。 在處理完單個(gè)任務(wù)之后，按需將結(jié)果返回給主服務(wù)器。 任務(wù)處理機(jī)制如圖3 所示；

圖3 任務(wù)處理機(jī)制Fig. 3 Task processing mechanism diagram

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

1.4 系統(tǒng)數(shù)據(jù)組成

本系統(tǒng)數(shù)據(jù)主要由3 個(gè)部分組成：

（1）用戶在系統(tǒng)內(nèi)的行為數(shù)據(jù)。 其中包括用戶的基礎(chǔ)信息、團(tuán)隊(duì)信息、訓(xùn)練記錄以及相關(guān)日志信息；

（2）用戶在其他訓(xùn)練平臺(tái)的歷史做題記錄，主要用于將用戶的成長過程進(jìn)行可視化展現(xiàn)；

（3）系統(tǒng)題庫數(shù)據(jù)是系統(tǒng)的核心數(shù)據(jù)，這部分?jǐn)?shù)據(jù)主要通過爬蟲的方式，去獲取主流做題訓(xùn)練平臺(tái)的題庫信息，再通過關(guān)鍵詞搜索加分詞技術(shù)補(bǔ)全題目相應(yīng)的算法標(biāo)簽。

2 系統(tǒng)主要模塊設(shè)計(jì)

2.1 智慧題庫模塊

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

圖4 爬蟲框架Fig. 4 Spider framework

2.1.1 系統(tǒng)題庫搭建

本系統(tǒng)主要獲取國內(nèi)外最主要的三大實(shí)體OJ題庫信息，分別為CodeForces、HDU，以及POJ。 題庫中，除Codeforces 可以直接通過爬蟲抓取題目標(biāo)簽以外，其余題庫題目均為從題目標(biāo)簽層面來對(duì)題目進(jìn)行劃分。 因此，系統(tǒng)題庫的實(shí)現(xiàn)首先必須滿足以下條件：

（1）獲取題庫原始數(shù)據(jù)；

（2）對(duì)于原始題庫中缺乏的數(shù)據(jù)進(jìn)行補(bǔ)全。

為了搭建系統(tǒng)題庫，首先通過爬蟲來獲取各個(gè)題庫的題目信息，存入題庫后再由后臺(tái)分發(fā)對(duì)應(yīng)的任務(wù)存入到Redis 服務(wù)器中。 當(dāng)后臺(tái)服務(wù)器處理到任務(wù)時(shí)，通過爬蟲抓取對(duì)應(yīng)題庫的題目信息。 對(duì)于已有標(biāo)簽的題目則直接存入系統(tǒng)題庫，對(duì)于沒有標(biāo)簽的題目再進(jìn)行第二次爬蟲。 第二次爬蟲基于題目信息來爬取題目的題解，在html 頁面獲取題解內(nèi)容后，通過文本分詞劃分高頻標(biāo)簽，并進(jìn)行計(jì)數(shù)統(tǒng)計(jì)，以計(jì)數(shù)最高的標(biāo)簽作為該題目的標(biāo)簽并存入題庫。 題目處理流程如圖5 所示。

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

2.1.2 用戶成長記錄模塊

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

（1）用戶信息抓?。寒?dāng)用戶登錄管家系統(tǒng)后，系統(tǒng)會(huì)向用戶申請(qǐng)綁定OJ 賬號(hào)，當(dāng)賬號(hào)綁定成功后，系統(tǒng)將利用爬蟲模擬用戶登錄并獲取用戶提交過的題目id。 這個(gè)過程具有一定的時(shí)間間隔，該任務(wù)會(huì)被放到定時(shí)任務(wù)中，在特定的時(shí)刻對(duì)任務(wù)進(jìn)行爬取并執(zhí)行。 在完成模擬登錄以及獲取題目id 后，系統(tǒng)將此部分的題目id 與系統(tǒng)題庫內(nèi)的id 進(jìn)行映射對(duì)比，獲取此部分的題目信息集合，將該部分內(nèi)容的時(shí)間、題目來源和題目標(biāo)簽等信息進(jìn)行抽離，并形成圖表所必須的信息集合；

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

2.1.3 用戶個(gè)性化題庫模塊

用戶個(gè)性化題庫模塊負(fù)責(zé)將后端采集到的題目信息展現(xiàn)給用戶。 其中包括用戶是否通過、題目名稱、算法標(biāo)簽以及該題目的通過數(shù)，并提供篩選功能。 用戶可以通過輸入題目進(jìn)行模糊匹配，選擇特定平臺(tái)的題庫或者根據(jù)特定的算法標(biāo)簽進(jìn)行篩選。

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

2.2 訓(xùn)練與復(fù)盤模塊

訓(xùn)練賽模塊支持個(gè)人訓(xùn)練以及團(tuán)隊(duì)訓(xùn)練，用戶可在本地完成代碼，通過管家系統(tǒng)的接口進(jìn)行提交。通過訓(xùn)練模塊中的任意題目，用戶均可打開提交界面，該界面會(huì)接受用戶傳輸?shù)脑创a并將代碼打包發(fā)送到對(duì)應(yīng)OJ 平臺(tái)進(jìn)行提交。

用戶在選題時(shí)，可以手動(dòng)輸入題庫平臺(tái)和題目ID 來添加題目，也可以選擇一些過濾條件，通過隨機(jī)方式自動(dòng)添加一些所有參與者均沒有通過的題目。

用戶在結(jié)束訓(xùn)練賽后，可以進(jìn)入當(dāng)前比賽的“復(fù)盤模塊”。 當(dāng)用戶第一次進(jìn)入這個(gè)模塊時(shí)，系統(tǒng)自動(dòng)給用戶生成一個(gè)復(fù)盤文檔的模板，用戶可以回顧整個(gè)比賽的過程，并寫下自己的收獲。

2.3 日志模塊

在日志模塊中，用戶可創(chuàng)建多級(jí)日志用于賽后復(fù)盤總結(jié)，每頁日志最多可存儲(chǔ)2 Mb 的數(shù)據(jù)。 當(dāng)用戶完成日志的構(gòu)建后，后臺(tái)會(huì)校驗(yàn)日志數(shù)據(jù)合格性，通過校驗(yàn)后存入數(shù)據(jù)庫，同時(shí)將用戶日志的緩存更新，保持?jǐn)?shù)據(jù)一致性。 日志編輯框支持markdown 語法，用戶可在日志中添加文字、圖片、鏈接等一系列內(nèi)容來完成賽后總結(jié)或刷題記錄，并將日志以二進(jìn)制文件的方式存入數(shù)據(jù)庫中。 在用戶進(jìn)入系統(tǒng)時(shí)由子進(jìn)程查詢?nèi)罩灸夸浗Y(jié)構(gòu)，并將這些內(nèi)容放入緩存中。 當(dāng)用戶點(diǎn)擊對(duì)應(yīng)日志時(shí)，系統(tǒng)進(jìn)行解析，交給前端渲染，同時(shí)在緩存中添加此內(nèi)容。

（1）數(shù)據(jù)結(jié)構(gòu)：日志模塊中創(chuàng)建多層級(jí)的日志，創(chuàng)建的日志目錄會(huì)直觀的展示給用戶，但是為了保持?jǐn)?shù)據(jù)的穩(wěn)定性以及查詢效率，整體目錄最多向下延伸3 個(gè)層級(jí)。 對(duì)于任意日志均存在兩種指針：一種指向其父節(jié)點(diǎn)，用于子日志后回溯父日志；另一種指向子日志，用于快速展示目錄。 用戶目錄會(huì)在第一次加載后進(jìn)行緩存，之后用戶刷新界面都使用緩存中獲取的目錄，直到更新目錄后臺(tái)時(shí)再次獲取新的日志目錄，并更新用戶界面，同時(shí)將新的用戶目錄傳入緩存；

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

2.4 通信模塊

當(dāng)用戶進(jìn)行通信時(shí)，系統(tǒng)會(huì)在用戶之間建立一個(gè)長鏈接，用來保證信息可以實(shí)時(shí)進(jìn)行傳輸。 使用長鏈接還可以在每次傳輸中復(fù)用TCP 鏈接，節(jié)約了信息傳輸時(shí)間。

通信協(xié)議遵守三層數(shù)據(jù)的規(guī)范，保證整體協(xié)議的規(guī)范化。 第一層包含具體對(duì)象、具體場景編號(hào)以及第二層數(shù)據(jù)；第二層包含好友編號(hào)和第三層數(shù)據(jù)；第三層包含具體要傳輸?shù)臄?shù)據(jù)。

當(dāng)用戶編輯完消息后點(diǎn)擊發(fā)送鍵，后臺(tái)會(huì)將用戶編輯的信息進(jìn)行序列化，并通過長鏈接將序列化后的數(shù)據(jù)傳輸給對(duì)應(yīng)的好友。 對(duì)于收到的好友消息，后臺(tái)將遵守三層數(shù)據(jù)規(guī)范對(duì)數(shù)據(jù)進(jìn)行解析，前端將反序列化的數(shù)據(jù)展示給用戶，至此完成了用戶之間的數(shù)據(jù)傳輸。 由于保持著長鏈接的存在，用戶進(jìn)行數(shù)據(jù)傳輸?shù)倪^程中減少了鏈接的反復(fù)建立，可以很大程度上提高用戶間通信的實(shí)時(shí)性。

3 系統(tǒng)測試

3.1 用戶登錄主頁

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

其中，雷達(dá)圖用來展示不同標(biāo)簽的做題量；餅狀圖用來展示不同題庫的做題量；柱狀圖用來展示當(dāng)月每日的做題量。

3.2 題庫運(yùn)行情況

訓(xùn)練賽定制頁面如圖7 所示。 用戶可選擇團(tuán)隊(duì)或個(gè)人的訓(xùn)練方式，并且可以添加訓(xùn)練賽題目：

圖6 用戶界面Fig. 6 User interface

圖7 題庫運(yùn)行圖Fig. 7 Question bank

3.3 訓(xùn)練賽定制和賽后復(fù)盤

訓(xùn)練賽定制頁面如圖8 所示。 用戶可選擇團(tuán)隊(duì)或個(gè)人的訓(xùn)練方式，并且可以添加訓(xùn)練賽題目。 隨機(jī)生成題目的過程如下。

（1）當(dāng)用戶點(diǎn)擊“隨機(jī)”的時(shí)候，會(huì)檢驗(yàn)當(dāng)前所有的比賽參與者，個(gè)人訓(xùn)練為1 人，團(tuán)隊(duì)訓(xùn)練為3人，并向服務(wù)端傳遞所有的參與者信息；同時(shí)服務(wù)端會(huì)通過異步的方式，篩選出所有參與者未通過的題目集合寫入緩存中；

（2）當(dāng)用戶對(duì)過濾條件進(jìn)行選擇并點(diǎn)擊“確定”時(shí)，會(huì)向服務(wù)端傳遞過濾條件，服務(wù)端根據(jù)過濾條件分別從緩存中提取滿足條件的題目集合，將這些題目集合的交集返回給用戶。

圖8 創(chuàng)建訓(xùn)練Fig. 8 Create training match

用戶可以自定義個(gè)人／團(tuán)隊(duì)的訓(xùn)練賽，訓(xùn)練賽后可以復(fù)盤比賽。 復(fù)盤模塊的目的是，引導(dǎo)用戶逐步建立起及時(shí)復(fù)盤的習(xí)慣。 復(fù)盤頁面如圖9 所示。

圖9 復(fù)盤界面Fig. 9 Match reply

3.4 用戶日志頁面運(yùn)行圖

用戶可主動(dòng)創(chuàng)建以及打開并編輯日志，所有日志都保存在用戶本地磁盤中。 日志運(yùn)行界面如圖10 所示。

圖10 日志頁面Fig. 10 Log page

4 結(jié)束語

本系統(tǒng)實(shí)現(xiàn)了題目分析、訓(xùn)練賽添加、信息可視化展示、好友實(shí)時(shí)通信、日志添加等功能，為用戶提供了一個(gè)全渠道的ACM 技能提升系統(tǒng)，目的在于提升用戶ACM 競賽水平。 本文對(duì)其功能實(shí)現(xiàn)和相關(guān)技巧進(jìn)行了詳細(xì)闡述。 系統(tǒng)功能多樣、實(shí)用，交互性強(qiáng)，經(jīng)過各個(gè)模塊的測試，系統(tǒng)穩(wěn)定性也符合預(yù)期，是一款符合用戶需求的軟件。