潘怡++謝珍++劉志龍

摘 要：大學(xué)生作為網(wǎng)絡(luò)媒體的主要參與者，在網(wǎng)絡(luò)輿情的產(chǎn)生中扮演著重要的角色，為了能及時(shí)掌握學(xué)生的思想動(dòng)態(tài)，積極引導(dǎo)校園輿情，打造和諧健康的校園網(wǎng)絡(luò)社區(qū)輿情環(huán)境，創(chuàng)建文明校園，高校建立完善的輿情監(jiān)控系統(tǒng)是十分必要的。本文基于QS單模式匹配算法和SunWu算法，運(yùn)用關(guān)鍵字匹配技術(shù)，通過(guò)對(duì)校內(nèi)各門戶網(wǎng)站內(nèi)容的檢測(cè)實(shí)驗(yàn)，我們能夠發(fā)現(xiàn)輿情敏感詞并進(jìn)行預(yù)警，從而實(shí)現(xiàn)對(duì)各門戶網(wǎng)站的實(shí)時(shí)監(jiān)控，為校園網(wǎng)絡(luò)輿情監(jiān)控系統(tǒng)的開(kāi)發(fā)提供了合理依據(jù)。

關(guān)鍵詞：網(wǎng)絡(luò)輿情；QS單模式匹配算法；SunWu算法；敏感詞

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1002-7661（2015）06-003-01

一、引言

隨著互聯(lián)網(wǎng)的興起，信息的迅速傳播，人們的生活方式、人際交往以及思維方式也隨之改變。在高校，校園網(wǎng)絡(luò)作為學(xué)生日常學(xué)習(xí)生活的重要平臺(tái)，重要性毋庸置疑。學(xué)校主頁(yè)、校內(nèi)各學(xué)院、各部門主頁(yè)，學(xué)校BBS，甚至各個(gè)學(xué)院BBS，班級(jí)網(wǎng)站都是高校學(xué)生經(jīng)常訪問(wèn)的平臺(tái)。類似于這種公共廣場(chǎng)，是大學(xué)生自由發(fā)表評(píng)論、表達(dá)意見(jiàn)的網(wǎng)絡(luò)空間，校園內(nèi)外的一些重大事件和突發(fā)事件通常會(huì)以最新最快的速度在這種媒介場(chǎng)所內(nèi)出現(xiàn)，引發(fā)大學(xué)生的廣泛關(guān)注，形成大量的討論。隨著意見(jiàn)的擴(kuò)散和討論的深入，討論的主題往往會(huì)逐漸趨向特定的焦點(diǎn)，形成具有一定規(guī)模的較為明確的網(wǎng)絡(luò)輿情。而出于學(xué)生思想的積極引導(dǎo)以及校園安全工作的管理，對(duì)校園輿情進(jìn)行有效的監(jiān)控，是各高校所能采取的合適手段之關(guān)鍵。

關(guān)鍵字匹配算法主要是串匹配。串匹配是利用一個(gè)符號(hào)序列查找出一個(gè)或多個(gè)特定符號(hào)序列的過(guò)程。利用串匹配能在正文文本中尋找所有關(guān)鍵字集合中的關(guān)鍵字，并報(bào)告關(guān)鍵字出現(xiàn)的位置。依據(jù)在匹配過(guò)程中所要匹配的模式串個(gè)數(shù)，串匹配算法可分為單模式串和多模式串。串匹配技術(shù)的發(fā)展是與其應(yīng)用密切相關(guān)的。隨著計(jì)算機(jī)信息技術(shù)的發(fā)展，其應(yīng)用領(lǐng)域除了早期的文本編輯、全文檢索系統(tǒng)、查詢系統(tǒng)等，現(xiàn)今已廣泛應(yīng)用到了網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)（NetworkIntrusion Detection System）、內(nèi)容過(guò)濾、生物科學(xué)計(jì)算以及新聞主題提取等。利用串匹配技術(shù)，我和團(tuán)隊(duì)自主開(kāi)發(fā)了校園網(wǎng)絡(luò)輿情監(jiān)控系統(tǒng)，并通過(guò)模擬數(shù)據(jù)，驗(yàn)證了串匹配技術(shù)在輿情監(jiān)控系統(tǒng)中應(yīng)用的正確性。

二、算法介紹

QS（Quick Search）算法是利用不良字符跳轉(zhuǎn)表和文本串中未出現(xiàn)在模式串里的字符來(lái)匹配緊鄰當(dāng)前匹配窗口的下一個(gè)字符，能有效的加快匹配速度。在實(shí)際應(yīng)用中，QS適用于大字符集、模式串較短時(shí)的情況。QS算法的空間復(fù)雜度為O（σ），其預(yù)處理階段的時(shí)間復(fù)雜度為O（m+σ），最好情況下QS算法的時(shí)間復(fù)雜度可以達(dá)到O（n/（m+1））。

SunWu算法是基于單模式的BM算法設(shè)計(jì)出的一種多模式匹配算法。與其它算法不同，SunWu算法使用“塊字符”（Block Character）作為基本單位，將其作為進(jìn)一步匹配的入口和進(jìn)行跳轉(zhuǎn)的依據(jù)。SunWu算法使用長(zhǎng)度為B的字符串代替壞字符串，進(jìn)行最大限度的跳躍，并且使用散列技術(shù)和前綴表來(lái)減少需要進(jìn)行實(shí)際匹配的次數(shù)。此外，SunWu算法不受大小字符集環(huán)境的影響，在中文情況下能夠表現(xiàn)出比較好的性能，符合中文字

三、結(jié)果分析與展示

QS算法和SunWu算法是典型的關(guān)鍵字匹配技術(shù)的算法，二者有各自的優(yōu)點(diǎn)，但也存在著明顯的不足。因此，在自主開(kāi)發(fā)的輿情監(jiān)控系統(tǒng)中，我們將二者相結(jié)合運(yùn)用，通過(guò)測(cè)試數(shù)據(jù)分析可知，QS算法和SunWu算法結(jié)合使用能大大提高系統(tǒng)的性能和效率。如圖3.1所示，在其他條件相同的情況下，模式串的最小長(zhǎng)度m=2，模式串?dāng)?shù)量由500增加到5000時(shí)，各算法掃描時(shí)間的變化。從表中可以看出，隨著模式串?dāng)?shù)量的增加，各算法的運(yùn)行時(shí)間都有相應(yīng)增大，QS的運(yùn)行時(shí)間一直低于SunWu算法。當(dāng)模式串?dāng)?shù)量小于3000時(shí)，QS的運(yùn)行時(shí)間少于SunWu的運(yùn)行時(shí)間。當(dāng)模式串?dāng)?shù)量大于3000時(shí)，QS的運(yùn)行時(shí)間多于SunWu的運(yùn)行時(shí)間。而二者的結(jié)合使用所需的運(yùn)行時(shí)間則處于中間水平。加之，表3.2所示，模式串?dāng)?shù)量為100，模式串最短長(zhǎng)度從2到8時(shí)，各種算法在reuters21578語(yǔ)料上消耗的時(shí)間。由表可看出，二者結(jié)合使用所花的掃描時(shí)間始終明顯低于其它兩種算法。當(dāng)m=2時(shí)，二者結(jié)合使用所花的掃描時(shí)間低于SunWu算法的1/6，m=8時(shí)，二者結(jié)合使用所花的掃描時(shí)間低于SunWu算法的1/2。隨著m的增大，二者結(jié)合使用的算法所花的掃描時(shí)間呈減少趨勢(shì)，且差距亦呈減少趨勢(shì)。

四、總結(jié)

本文將單模式串匹配的QS算法和SunWu算法結(jié)合使用，取長(zhǎng)補(bǔ)短，并將其運(yùn)用到自主開(kāi)發(fā)的校園網(wǎng)絡(luò)輿情監(jiān)控系統(tǒng)中，通過(guò)對(duì)模擬數(shù)據(jù)的分析，也驗(yàn)證了QS算法和SunWu算法結(jié)合能極大的提高系統(tǒng)性能。這為校園輿情監(jiān)控系統(tǒng)提供了技術(shù)支持，也為校園安全工作管理奠定了基礎(chǔ)。