關(guān)鍵詞：推薦系統(tǒng);內(nèi)容相似性;過濾冗余信息;LZ77算法;哈夫曼編碼

中圖分類號(hào)：TP391.4 文獻(xiàn)標(biāo)志碼：A

0 引言（Introduction）

在基于內(nèi)容相似性的方法中，文本相似性具有重要意義[1]。文本相似性是指兩個(gè)文本之間的語義相似程度，它是自然語言處理領(lǐng)域中的一個(gè)基本問題，其研究領(lǐng)域廣泛，涵蓋多個(gè)方面，主要包括基于詞袋模型的算法[2]、基于詞匯的算法[3]及基于深度學(xué)習(xí)的算法[4]等。

然而，現(xiàn)有的文本相似性算法也存在一些不足?；谠~袋模型的算法在處理文本信息時(shí)，忽略了文本中的詞序和上下文信息，導(dǎo)致無法準(zhǔn)確評(píng)估文本之間的相似性[5]?；谠~匯的算法雖然考慮了詞序和上下文信息，但在處理大規(guī)模數(shù)據(jù)集時(shí)的計(jì)算復(fù)雜度較高，效率低[6]?；谏疃葘W(xué)習(xí)的算法在處理文本時(shí)，缺乏對(duì)文本語義的深入理解，容易受到局部信息的干擾[7]。

針對(duì)上述文本相似性算法出現(xiàn)的問題，本文提出了一種基于過濾冗余信息相似性的內(nèi)容推薦算法，旨在改進(jìn)現(xiàn)有文本相似性算法的不足。

1 相關(guān)工作（Related work）

本文首先分析了兩種信息優(yōu)化算法，即LZ77算法和哈夫曼編碼。這兩種算法都是優(yōu)化信息領(lǐng)域的經(jīng)典算法，它們分別通過利用數(shù)據(jù)的重復(fù)結(jié)構(gòu)信息和字符出現(xiàn)頻率信息，實(shí)現(xiàn)了有效的冗余信息處理。在此基礎(chǔ)上，本文利用這兩種方法研究如何計(jì)算文本內(nèi)容的相似性，以期提升文本相似性評(píng)估的準(zhǔn)確性。

LZ77算法以獨(dú)特的方式識(shí)別并過濾冗余信息，使數(shù)據(jù)變得更加緊湊，同時(shí)保留了原始信息的完整性。LZ77算法是由以色列工程師雅各布·齊夫和阿布拉罕·萊姆佩爾提出的。

該算法使用了一個(gè)滑動(dòng)窗口字典存儲(chǔ)歷史數(shù)據(jù)，并在其中查找與當(dāng)前數(shù)據(jù)最長(zhǎng)的匹配串，然后用一個(gè)三元組（偏移量，長(zhǎng)度，下一個(gè)字符）表示匹配結(jié)果。

近年來，LZ77算法的研究主要集中在提高信息優(yōu)化效率和速度、適應(yīng)不同類型的數(shù)據(jù)、結(jié)合其他信息優(yōu)化技術(shù)等方面。

SUN等[8]提出了LZ77改進(jìn)算法，結(jié)合靜態(tài)共享字典和自適應(yīng)動(dòng)態(tài)字典等方法，獲得了更好的數(shù)據(jù)優(yōu)化程度，可以顯著提高正則表達(dá)式的預(yù)處理及匹配性能，但是可能會(huì)導(dǎo)致在處理大規(guī)模數(shù)據(jù)時(shí)出現(xiàn)內(nèi)存溢出的問題，并且處理具有高度復(fù)雜性和隨機(jī)性的數(shù)據(jù)時(shí)的算法效率不高。

OSWALD等[9]提出了一種結(jié)合LZ77的混合算法，該算法可以處理跨域的語料庫(kù)，有效識(shí)別出哪些跨域的數(shù)據(jù)是冗余的，并采用了更高效的數(shù)據(jù)表示方式。這種優(yōu)化方式使得跨域數(shù)據(jù)之間的相關(guān)性得到了顯著提高，從而提高了數(shù)據(jù)處理和分析的效率。但是，該算法在識(shí)別冗余跨域數(shù)據(jù)并使用更高效的數(shù)據(jù)表示方式時(shí)，可能會(huì)忽視不同跨域數(shù)據(jù)的一些重要特性，從而影響跨域數(shù)據(jù)的完整性和準(zhǔn)確性。

哈夫曼編碼由美國(guó)計(jì)算機(jī)科學(xué)家大衛(wèi)·哈夫曼提出，旨在最小化平均編碼的長(zhǎng)度，并且具有唯一可譯性。該編碼技術(shù)在不損失原始信息的前提下，能夠盡可能地減少數(shù)據(jù)的大小;其核心在于采用了一種基于貪心策略的自下向上方法，通過構(gòu)造一棵最優(yōu)二叉樹，并為每個(gè)字符分配一個(gè)前綴不重復(fù)的二進(jìn)制編碼，從而實(shí)現(xiàn)高效的數(shù)據(jù)壓縮。

近年來，哈夫曼編碼的研究主要集中在幾個(gè)方面：一是改進(jìn)哈夫曼編碼的構(gòu)造方法和編碼方式;二是探索將哈夫曼編碼應(yīng)用于不同領(lǐng)域和場(chǎng)景;三是研究如何將哈夫曼編碼與其他信息優(yōu)化技術(shù)相結(jié)合。

RAHMAN等[10]提出了一種使用Burrows-Wheeler變換和哈夫曼編碼的文本信息處理技術(shù)，該技術(shù)在很大程度上縮短了原始文本文件的長(zhǎng)度，在保留原始文本內(nèi)容的前提下，節(jié)省了存儲(chǔ)空間并提高了文本的傳輸速度。但是，該技術(shù)也存在一些局限性。第一，這種方法在處理復(fù)雜結(jié)構(gòu)和大量獨(dú)特字符的文本時(shí)效果有限。第二，該技術(shù)需要預(yù)先計(jì)算輸入數(shù)據(jù)的概率分布，在處理動(dòng)態(tài)變化的數(shù)據(jù)時(shí)會(huì)產(chǎn)生一些問題。

QIAN等[11]提出一種基于增量哈夫曼樹合并的在線詞向量模型生成方法。該方法能夠?qū)崿F(xiàn)基于增量學(xué)習(xí)的在線詞向量模型生成，其顯著的特點(diǎn)是處理速度更快、性能更優(yōu)，能滿足對(duì)大量在線文本數(shù)據(jù)的高實(shí)時(shí)性處理要求。這種方法的原理是將新出現(xiàn)的詞或者詞頻發(fā)生變化的詞插入已有的哈夫曼樹中，從而避免了重新構(gòu)建整個(gè)哈夫曼樹的開銷。然而，這種技術(shù)也會(huì)導(dǎo)致哈夫曼樹的結(jié)構(gòu)發(fā)生變化，從而影響詞向量的編碼和解碼。如果哈夫曼樹的結(jié)構(gòu)變化過于頻繁，那么詞向量的穩(wěn)定性和一致性就會(huì)受到一定程度的影響。

通過前述分析可以看出，LZ77算法和哈夫曼編碼在信息優(yōu)化領(lǐng)域展現(xiàn)出了強(qiáng)大的能力，它們可以有效地識(shí)別出冗余的信息，從而實(shí)現(xiàn)信息的精簡(jiǎn)和壓縮。這兩種算法各自擁有豐富的理論與實(shí)踐研究基礎(chǔ)，為信息壓縮領(lǐng)域的發(fā)展做出了重要貢獻(xiàn)。在信息壓縮領(lǐng)域，它們可以結(jié)合使用，形成更高效的方案，例如LZH、ZIP、PNG等。因此，本文致力于探究將這兩種算法相結(jié)合的方法，并研究對(duì)應(yīng)的內(nèi)容相似性度量方法，以及其在推薦系統(tǒng)中的應(yīng)用。

2 方法（Method）

2.1 方法概述

本文提出的RIFS （Redundant Information Filtering Similaritybased Movie" Recommendation Algorithm ）是一種基于過濾冗余信息相似性的電影推薦算法，它融合了LZ77算法和哈夫曼編碼在信息優(yōu)化方面的優(yōu)勢(shì)。首先，該算法利用LZ77算法分別對(duì)每部電影信息及該部電影信息加上用戶輸入內(nèi)容的冗余信息進(jìn)行過濾，過濾冗余信息后分別將其以三元組序列的方式作為輸出;其次，構(gòu)建哈夫曼樹，進(jìn)行哈夫曼編碼后，分別計(jì)算經(jīng)過哈夫曼編碼輸出的總位數(shù)的長(zhǎng)度;再次，建立用戶輸入內(nèi)容與電影信息的相似性公式;最后，根據(jù)相似性降序得出預(yù)測(cè)電影，生成預(yù)測(cè)電影的電影推薦列表后推薦給用戶。算法結(jié)構(gòu)圖如圖1所示。

為了實(shí)現(xiàn)一個(gè)基于文本內(nèi)容相似性的電影推薦系統(tǒng)，本文使用了RIFS算法對(duì)電影數(shù)據(jù)集進(jìn)行冗余信息處理。RIFS算法結(jié)合了LZ77算法和哈夫曼編碼在信息優(yōu)化方面的優(yōu)勢(shì)，既能保證數(shù)據(jù)的完整性，又能保證達(dá)到較好的推薦效果。綜上所述，本文提出的算法的具體過程如下所示。

算法1 基于過濾冗余信息相似性的電影推薦算法

輸入：用戶輸入文本內(nèi)容信息U，電影內(nèi)容信息C_i

輸出：經(jīng)過基于過濾冗余信息相似性算法預(yù)測(cè)的電影M

1： 初始化查找緩沖區(qū)和輸入緩沖區(qū)

2： 將Ci 的前n 個(gè)字符放入輸入緩沖區(qū)

3： 將Ci 的剩余字符放入待處理隊(duì)列

4： FOR 每個(gè)字符 DO

5： 根據(jù)公式（1），公式（2），尋找最長(zhǎng)匹配子串

6： IF 找到匹配子串 THEN

7： 根據(jù)公式（3），輸出三元組

8： ELSE

9： 輸出三元組（0，0，當(dāng)前字符）

10： END IF

11： 添加三元組到序列L

12： 移出處理過的字符，補(bǔ)充待處理隊(duì)列的字符到輸入緩沖區(qū)

13： 將移出的字符添加到查找緩沖區(qū)

14： IF 查找緩沖區(qū)超過m 個(gè)字符 THEN

15： 刪除最左邊的字符

16： END IF

17： END FOR

18： 統(tǒng)計(jì)L 中元素，構(gòu)建哈夫曼樹

19： 得到字符集合C={c₁，c₂，…，c_n}及對(duì)應(yīng)的頻率集合W ={w₁，w₂，…，w_n}

20： 根據(jù)公式（4），計(jì)算哈夫曼編碼輸出的總位數(shù)B₁

21： 將C_i+U 重復(fù)以上步驟計(jì)算哈夫曼編碼輸出的總位數(shù)B₂

22： 根據(jù)公式（5），公式（6），計(jì)算U 與C_i 的相似性

23： 將相似性降序排序，得出最相似的電影M

24： RETURN 基于過濾冗余信息相似性算法預(yù)測(cè)的電影M

3實(shí)驗(yàn)（Experiment）

3.1 數(shù)據(jù)集選取

經(jīng)過調(diào)研，當(dāng)前主流的公開數(shù)據(jù)集都難以滿足本文的算法需求。本文所提算法建立在對(duì)電影文本內(nèi)容的深入分析之上，然而一些流行的電影數(shù)據(jù)集包含了大量用戶對(duì)電影的評(píng)分信息，但是缺乏對(duì)電影的詳細(xì)描述和評(píng)論，如Movie Lens[12]、Netflix[13]及TMDB數(shù)據(jù)集等，因此這些數(shù)據(jù)集并不滿足本文算法的計(jì)算條件。為了滿足本文算法的計(jì)算條件，本文利用Python爬蟲技術(shù)對(duì)豆瓣電影Top250數(shù)據(jù)集[14]進(jìn)行爬取。

本文使用的豆瓣電影Top250數(shù)據(jù)集是一個(gè)包含豆瓣網(wǎng)站上評(píng)分最高的250部電影信息的數(shù)據(jù)集。這個(gè)數(shù)據(jù)集中的每一部電影都有一些關(guān)鍵的屬性，包括電影名稱、導(dǎo)演、主演、編劇、上映日期、地區(qū)、簡(jiǎn)介、類型、豆瓣評(píng)分、豆瓣用戶評(píng)價(jià)及評(píng)價(jià)人數(shù)。

3.2 實(shí)驗(yàn)方法及實(shí)驗(yàn)環(huán)境

豆瓣電影Top250數(shù)據(jù)集可以很好地應(yīng)用于基于過濾冗余信息相似性的電影內(nèi)容推薦算法，本文將每部電影的導(dǎo)演、主演、編劇、豆瓣用戶評(píng)價(jià)組合拆分成短句子作為用戶輸入內(nèi)容，分別與電影名對(duì)應(yīng)，構(gòu)建了用戶輸入內(nèi)容與電影名對(duì)應(yīng)的數(shù)據(jù)集。實(shí)驗(yàn)驗(yàn)證時(shí)，利用每部電影名對(duì)應(yīng)的電影簡(jiǎn)介信息以及該電影簡(jiǎn)介信息加上用戶輸入內(nèi)容計(jì)算相似性，以此預(yù)測(cè)電影名。實(shí)驗(yàn)采用十折驗(yàn)證的方式，將數(shù)據(jù)隨機(jī)分為10組，依次選取1組數(shù)據(jù)作為測(cè)試集，剩余9組數(shù)據(jù)作為訓(xùn)練集，每次選取完后，算法只用訓(xùn)練集數(shù)據(jù)訓(xùn)練，用測(cè)試集數(shù)據(jù)驗(yàn)證，用10次實(shí)驗(yàn)的平均值作為最終結(jié)果。

實(shí)驗(yàn)所用處理器為12th Gen Intel（R） Core（TM） i7-12700H2.30 GHz，所用的顯卡為NVIDIA GeForce RTX 3060 LaptopGPU，內(nèi)存容量為32 GB，操作系統(tǒng)為64位Windows 11，所有的實(shí)驗(yàn)都是在上述的實(shí)驗(yàn)環(huán)境中進(jìn)行的，使本文能夠在相同的條件下對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行公正的比較。

3.3 基準(zhǔn)對(duì)比算法

本文選取了3種流行的文本相似性算法作對(duì)比實(shí)驗(yàn)。

（1）基于字符頻率的推薦算法[15]（Character Frequency-Based Recommendation Algorithm，Character）：該算法是一種利用用戶輸入文本的字符頻率推薦相關(guān)內(nèi)容的方法。用戶可以輸入自己喜歡的電影類型、導(dǎo)演、演員、情節(jié)等關(guān)鍵詞，然后系統(tǒng)會(huì)根據(jù)這些文本信息計(jì)算與不同電影的相似性，從而推薦最符合用戶的電影。

（2）融合文本情感的推薦算法[16] （Sentiment-BasedRecommendation Algorithm，Sentiment）：該算法可以實(shí)現(xiàn)一種根據(jù)用戶輸入的文本推薦符合用戶情感需求的電影的功能。用戶可以輸入文本，然后系統(tǒng)會(huì)根據(jù)這些文本信息計(jì)算與不同電影的情感向量相似性，從而推薦最適合用戶的電影。

（3）Seq2seq編碼器解碼器模型[17]（Sequence-to-SequenceEncoder-Decoder Model，Seq2seq）：該算法利用神經(jīng)網(wǎng)絡(luò)技術(shù)分析文本內(nèi)容信息。用戶輸入文本之后，根據(jù)其與不同電影的相似性為用戶提供個(gè)性化的電影推薦。這種方法可以讓用戶發(fā)現(xiàn)自己喜歡的電影類型或風(fēng)格，也可以讓系統(tǒng)有效地利用電影的文本信息。

3.4 評(píng)價(jià)指標(biāo)

本文從推薦系統(tǒng)的整體效果、用戶滿意度、用戶需求覆蓋和兩者的平衡性4個(gè)指標(biāo)做度量，這些指標(biāo)是準(zhǔn)確率[18]（Accuracy）、精確率[19]（Precision）、召回率[20]（Recall）和F1值[21]（F1-score）。這些指標(biāo)的計(jì)算公式和含義如下：

準(zhǔn)確率（Accuracy）是指推薦系統(tǒng)正確推薦的電影數(shù)量占全部電影數(shù)量的比例，它反映了推薦系統(tǒng)的整體效果。準(zhǔn)確率的計(jì)算公式是

其中：TP（True Positive）表示用戶實(shí)際感興趣且被推薦的電影數(shù)量，TN（True Negative）表示用戶實(shí)際不感興趣且未被推薦的電影數(shù)量，F(xiàn)P（False Positive）表示用戶實(shí)際不感興趣但被推薦的電影數(shù)量，F(xiàn)N（False Negative）表示用戶實(shí)際感興趣但未被推薦的電影數(shù)量。

精確率（Precision）是指推薦系統(tǒng)推薦給用戶的電影中用戶實(shí)際感興趣的電影的比例，它反映了推薦系統(tǒng)的用戶滿意度。精確率的計(jì)算公式是

3.5 實(shí)驗(yàn)結(jié)果

從圖2可以看出，預(yù)測(cè)1部電影時(shí)RIFS比Sentiment提升了約0.24百分點(diǎn)，比Seq2seq提升了約0.23百分點(diǎn)，高于第二名Character約0.07 百分點(diǎn)。預(yù)測(cè)3 部電影時(shí)RIFS 比Sentiment提升了約0.30百分點(diǎn)，比Seq2seq提升了約0.29百分點(diǎn)，高于第二名Character約0.05百分點(diǎn)。

從圖3中可以看出，在將RIFS算法的精確率設(shè)定為基準(zhǔn)（100%）的情況下，預(yù)測(cè)1部電影時(shí)，Sentiment的精確率約是RIFS的2.38%，Seq2seq的精確率約是RIFS的9.23%，第二名Character的精確率約是RIFS的70.24%;預(yù)測(cè)3部電影時(shí)，Sentiment的精確率約是RIFS的3.78%，Seq2seq的精確率約是RIFS的9.46%，第二名Character的精確率約是RIFS的84.87%。

從圖4可以看出，在將RIFS算法的召回率設(shè)定為基準(zhǔn)（100%）的情況下，預(yù)測(cè)1部電影時(shí)，Sentiment的召回率約是RIFS的2.38%，Seq2seq的召回率約是RIFS的9.23%，第二名Character的召回率約是RIFS的70.24%;預(yù)測(cè)3部電影時(shí)，Sentiment的召回率約是RIFS的3.78%，Seq2seq的召回率約是RIFS的9.46%，第二名Character的召回率約是RIFS的84.87%。

從圖5可以看出，在將RIFS算法的F1值設(shè)定為基準(zhǔn)（100%）的情況下，預(yù)測(cè)1部電影時(shí)，Sentiment的F1值約是RIFS的2.38%，Seq2seq的F1值約是RIFS的9.23%，第二名Character的F1值約是RIFS的70.24%;預(yù)測(cè)3部電影時(shí)，Sentiment的F1值約是RIFS的3.78%，Seq2seq的F1值約是RIFS的9.46%，第二名Character的F1值約是RIFS的84.87%。

從圖6可以看出，RIFS算法的用時(shí)比Sentiment減少了約4.2 s，比Seq2seq減少了約1.62 s，多于Character約0.89 s。

本文設(shè)計(jì)的RIFS算法，通過有效過濾內(nèi)容的冗余信息，并進(jìn)一步比較文本之間的內(nèi)容相似性，使得對(duì)內(nèi)容相關(guān)程度的判斷更加準(zhǔn)確且嚴(yán)謹(jǐn)。在文本相似性類方法的性能方面，本文算法都顯著優(yōu)于其他幾種算法，同時(shí)在計(jì)算復(fù)雜度方面犧牲的時(shí)間不多。與之相比，Character算法可以評(píng)估字詞對(duì)內(nèi)容相似性的重要程度，但是未能考慮到文本內(nèi)容中的詞序及上下文信息。Sentiment算法只考慮了內(nèi)容之間的情感相似性，但是同樣的詞或短語在不同的上下文中可能具有完全不同的情感含義。Seq2seq算法可以學(xué)習(xí)文本內(nèi)容的高層特征，但是訓(xùn)練模型時(shí)通常需要大量的數(shù)據(jù)且計(jì)算復(fù)雜度較高。因此，本文提出的模型是有效的，并且具有時(shí)間復(fù)雜度低、可解釋性強(qiáng)的特點(diǎn)。

4 結(jié)論（Conclusion）

本文提出了一種基于過濾冗余信息相似性的啟發(fā)式方法，并將其應(yīng)用于電影內(nèi)容推薦領(lǐng)域，解決了文本內(nèi)容相似性算法難以充分覆蓋文本內(nèi)容信息的問題。本文使用LZ77算法過濾了文本內(nèi)容的冗余信息，并對(duì)過濾后的信息進(jìn)行哈夫曼編碼，利用電影信息經(jīng)過哈夫曼編碼輸出的總位數(shù)的長(zhǎng)度及電影信息加上用戶輸入文本經(jīng)過哈夫曼編碼輸出的總位數(shù)的長(zhǎng)度，構(gòu)建用戶輸入內(nèi)容與每部電影的相似性，實(shí)現(xiàn)了更準(zhǔn)確地推薦電影。通過實(shí)驗(yàn)驗(yàn)證，本文所提RIFS算法在各個(gè)指標(biāo)上的表現(xiàn)明顯優(yōu)于Sentiment、Seq2seq和Character，證明了其高準(zhǔn)確性和低計(jì)算復(fù)雜度的優(yōu)勢(shì)。

在未來的研究中，可以進(jìn)一步探索如何度量信息完全沒有冗余并對(duì)原始信息進(jìn)行加權(quán)，還可以和深度學(xué)習(xí)的方法結(jié)合，雖然可能會(huì)增加一定的計(jì)算時(shí)間，但是有望進(jìn)一步提升算法的整體性能。

作者簡(jiǎn)介：

艾均（1980-），男，博士，副教授。研究領(lǐng)域：通用人工智能，推薦系統(tǒng)，社交網(wǎng)絡(luò)計(jì)算。

孫陽（1999-），男，碩士生。研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，推薦系統(tǒng)。

蘇湛（1983-），女，博士，副教授。研究領(lǐng)域：通用人工智能，推薦系統(tǒng)，社交網(wǎng)絡(luò)計(jì)算。

方元江（1999-），男，本科生。研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，推薦系統(tǒng)。

謝正彬（1999-），男，本科生。研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，推薦系統(tǒng)。