面向網際網路的有意義串的提取方法及裝置的製作方法

2023-06-15 20:46:01

專利名稱：面向網際網路的有意義串的提取方法及裝置的製作方法
技術領域：
本發明涉及的是一種利用計算機技術輔助網絡信息智能分析或輿情管理的技術， 具體的講是從海量的網際網路網頁和論壇信息中快速準確高效的提取有意義串的方法和系 統。
背景技術：
文本表示是基於內容的文本處理的首要步驟。文本表示中的特徵項是影響文本分 類和聚類結果的重要因素。目前常用的文本特徵項主要有字，詞，短語，語義等。從理論上 講，語義概念(語義集)高於短語(句法集)，短語高於詞(詞語集)，詞高於字(字符集)。 通常語義概念可以藉助於語義詞典(同義詞，近義詞詞典等)或進行潛在語義索引獲取。然 而大規模、覆蓋面廣的語義資源較難獲取，潛在語義索引的算法複雜度很高，從而限制了語 義概念在文本表示中的使用。目前最常用的文本表示模型是向量空間模型，向量空間模型 以詞作為特徵。以詞作為特徵的缺點在於它只簡單地考慮一個詞是否在文檔中出現及其 出現頻度，把特徵看作是獨立存在的，而完全忽略了文本上下文間的語義關係，也沒有考慮 特徵之間的先後次序。有意義串是具有獨立語義，緊密耦合，具有廣泛流通性的完整的語言 單元。有意義串實際上就是以短語為特徵，以短語為特徵的文本表示優於以詞做特徵的文 本表示。目前對有意義串的分析的研究主要有兩大方向，串內分析和串外分析。串內分析 是通過分析本串的結構特徵以及組成方式，來判斷串是否滿足有意義串的要求。目前常用 的串內分析方法主要是通過簡單互信息，位置成詞概率，相鄰字對的耦合性來判斷。簡單互 信息[1]比較了一個模式串及其部分子串的頻度，它可以衡量模式串各部分之間的相關度。 當從該模式串所取的子串的長度過短時，由於統計較短子串的頻次沒有意義，此時簡單互 信息的作用也失效了。位置成詞概率[2]表示某個漢字在某個位置(詞首或詞尾)出現的 概率。由於漢字用法比較豐富以及不規則新詞的不斷出現，不能完全採用某個漢字的位置 乘此概率來篩選模式串。在切分好的訓練語料中掃描所有出現過的連續子對，統計出每組 字對出現的總次數以及該字對作為某個詞子串的總次數，後者與前者的比稱作相鄰字對的 耦合度[3]。如果耦合對比較大，表明該字對很可能出現在一個串中。當選取的詞對為偶然 組合的無意義詞對時，該字對作為某個詞子串的總次數出現次數會很少，計算耦合度會過 濾掉一些實義的串。串外分析是分析緊鄰串的上下文的信息，以判斷串的語義環境是否豐富。目前常 用的串外分析主要是通過鄰接類別，熵值，鄰接對熵概念來判斷。鄰接類別[4]是串上文和 下文中出現的不同字符數量的最大值。鄰接類別只考慮字符串左邊和右邊的不同字符的種 類數量，而沒有考慮每個種類的字符出現的頻次。熵值[1][2][3]可以反映出該串語用環境的 豐富程度，度量一個串的獨立性，但是當串出現的頻次整體都不多時效果不太明顯，而且熵 值計算沒有考慮上下文的組合關係。串的上文和下文的組合稱為鄰接對。鄰接對熵[3]是 對鄰接對求熵值。如果鄰接類別，熵值，鄰接對熵都比較大，則一個串很有可能成為一個有意乂串。概括而言，已有的有意義串提取算法存在以下缺點1)串內分析中採用互信息作 為特徵不能很好的篩選雙字串，對於雙字串來說，去掉首字和去尾字的串實際上是單字串， 計算單字出現的頻次沒有意義；2)串內分析和串外分析都沒有考慮串和串之間的差異性， 提取的有意義串中會有很多串表徵的內容相似，造成許多有意義串的語義相似和冗餘。與本發明相關的公開報導主要包括[1]胡吉祥.基於頻繁模式的消息文本聚類研究[D].中科院研究生院碩士學位論 文.2006.44-46 ；[2]賀敏.面向網際網路的中文有意義串挖掘[D].中國科學院計算技術研究所碩士 論文 2007 ；[3] 200710120755. 5，一種面向網際網路的有意義串的挖掘方法和系統；[4] haodi feng. Accessor Variety Criteria for Chinese Word Extraction[J]. Computational Linguistics,30(1)，2004。

發明內容
本發明的目的在於提供一種能夠有效的提取新聞網頁和論壇上的有意義串，並可 以應用於輿情監管系統中的面向網際網路的有意義串的提取方法。本發明的目的還在於提供 一種面向網際網路的有意義串的提取裝置。本發明的目的是這樣實現的本發明的面向網際網路的有意義串的提取方法包括下列步驟步驟1 提取重複字符串；步驟2 通過串內分析過濾所述字符串；步驟3 通過串外分析過濾所述字符串；步驟4 通過串間分析過濾所述字符串。本發明的面向網際網路的有意義串的提取方法還可以包括1、步驟1中所述提取重複字符串包括將網頁語料處理得到規則化的文本，記錄 文本中出現的重複串以及其出現的次數，過濾掉頻次低於閾值的重複串和串長低於閾值的 重複串；具體步驟為步驟1. 1去除網頁標籤，將網頁預處理得到規則化的文本格式，並把文本編碼格 式轉化成GB2312格式的編碼；步驟1. 2根據GB2312編碼格式，將漢字，英文，數字符號分別轉化成其ID表示，並 將其他符號用空格的ASCII碼代替；步驟1.3提取該文本的重複串，記錄文本中出現的重複串和重複串的次數，過濾 出現次數小於一定閾值的重複串；步驟1.4如果提取的重複串中有空格，則以空格為分隔符把重複串拆成子串。步驟二中所述對字符串進行串內分析包括如果該串不是雙字串，計算字符串的 互信息，判斷互信息是否達到設定的閾值，根據判斷結果過濾掉沒有達到閾值的文本串；如 果該串是雙字串，根據訓練得到的雙字串統計表和白名單以及雙字串分詞後的結果對雙字 串進行過濾；具體步驟為
步驟2. 1對訓練語料進行訓練，生成雙字串詞性統計表，雙字串白名單；步驟2. 2如果字符串的長度大於2，轉入步驟2. 3，否則轉入步驟2. 5 ；步驟2. 3計算每個重複串的互信息，如果互信息達到閾值，則轉入步驟3 ；步驟2. 4如果互信息沒有達到閾值，則將該串過濾掉；步驟2. 5如果該串在雙字串白名單裡，則轉入步驟3 ；步驟2. 6對該串用分詞程序進行分詞；步驟2. 7如果分詞後的詞性組合在雙字串詞性統計表裡，則轉入步驟3 ；步驟2. 8如果分詞後的詞性組合不在雙字串詞性統計表裡，則過濾此串。步驟3中所述對字符串進行串外分析包括計算字符串的熵值，判斷熵值是否達 到設定的閾值，根據判斷結果過濾掉沒有達到閾值的文本串；具體步驟為步驟3. 1計算字符串的熵值，判斷熵值是否達到設定的閾值；步驟3. 2如果達到閾值，轉入步驟4 ；步驟3. 3如果熵值未達到閾值，則將其過濾掉。步驟4中所述對字符串進行串間分析包括對所有字符串進行排序，計算排序後 的相鄰兩串之間的重合率，並根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃 分成若干種類型，並分別對每種類型進行分析，並過濾掉不符合要求的字符串，進而得到有 意義串；具體步驟為步驟4. 1對所有字符串進行排序，計算排序後每一對相鄰串的重合率；步驟4. 2如果重合率大於閾值，根據相鄰兩串之間的組合關係，將每一對相鄰串 劃分到其所屬的類型；如果重合率小於閾值，則不統計該相鄰串的類型；步驟4. 3如果該相鄰串屬於A-AB型數據，計算A串和AB串的頻率比值；根據頻率 比值的大小來確定如何對A串，AB串處理； 步驟4. 4如果連續兩個相鄰串屬於A-AB-ABC型數據，根據A串，AB串，ABC串的頻 次的組合關係來確定如何對A串，AB串，ABC串進行處理；步驟4. 5如果連續兩個相鄰串屬於A-AB-AC型數據，根據A串，AB串，AC串的頻次 的組合關係來確定如何對A串，AB串，AC串進行處理；步驟4. 6如果該相鄰串屬於最長公共子串僅為1的類型，則過濾掉相鄰串中長度 較小的字符串，保留長度較長的字符串。本發明的面向網際網路的有意義串的提取裝置包括依次串接的重複串發現模塊、串 內分析模塊、串外分析模塊和串間分析模塊；重複串發現模塊，用於將網頁語料預處理得到規則化的文本，記錄文本中出現的 重複串以及其出現的次數，過濾掉頻次低於閾值的重複串和長度低於閾值的重複串；串內分析模塊，用於對字符串進行串內分析，判斷串的長度，如果該串的長度大於 2，計算字符串的互信息，判斷互信息是否達到設定的閾值，根據判斷結果過濾掉沒有達到 閾值的文本串；如果該串是雙字串，利用訓練得到的雙字串統計表和白名單，根據雙字串分 詞後的結果對雙字串進行過濾；串外分析模塊，用於對字符串進行串外分析，計算字符串的熵值，判斷熵值是否達 到設定的閾值，根據判斷結果過濾掉沒有達到閾值的字符串。串間分析模塊，用於對字符串進行串間分析，對所有字符串進行排序，計算排序後的相鄰兩串之間的重合率，並根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃 分為若干種類型，並分別對每種類型進行分析，過濾掉不滿足要求的字符串，進而得到有意義串。所述重合率，是根據兩串的最長公共子串和最長公共子序列計算得到，反映兩個 串之間重合程度大小的一個特徵量。所述重複串發現算法可以使用N元遞增分步算法，以及後綴索引算法(包括後綴 樹算法，後綴數組算法)等。本系統採用後綴數組算法。本發明的有益效果是本發明的面向網際網路的有意義串的提取方法和系統，從互 聯網中下載網頁數據，然後經過重複串發現，串內分析，串外分析和串間分析等四個階段達 到提取出網際網路的有意義串的目的。本發明在重複串發現階段採用將標點符號和特殊符號 換成分隔符號(空格)，能夠很好的限制串的範圍，使有意義串不跨標點，句子，段落，提高 了重複串的準確性。串內分析可以使串內部更加穩固和完整，互信息處理雙字串時需要計 算單字出現頻率，單個漢字的出現頻率很隨機並且單字不能完整的概括出雙字串的語義， 而利用對雙字串訓練後的雙字串詞性統計表和白名單處理雙字串有很好的效果。串外分析 是為了使串能用於比較豐富的語用環境，更具用獨立性。串間分析通過對串和串之間差異 性比較，使串具有更好的語義獨立性，減少串之間的相似程度，並能夠減少特徵串的數量。 本發明可廣泛應用於網絡輿情管理、網際網路智能信息處理等應用領域。


圖1是本發明的面向網際網路的有意義串的提取方法過程示意圖；圖2是本發明的面向網際網路的的串內分析過程流程圖；圖3是本發明的面向網際網路的的串間分析過程流程圖；圖4是本發明表面向網際網路的有意義串的提取裝置示意圖。
具體實施例方式為了使本發明的目的，技術方案及優點更加清楚明白，以下結合附圖及實施例，對 本發明的一種面向網際網路的有意義串的提取方法和系統進行進一步詳細說明。本發明將在網際網路存在的海量網頁中提取出有意義串。有意義串是具有獨立語 義，緊密耦合，具有廣泛流通性的完整的語言單元。本發明提取的有意義串可以作為文本表 示模型的特徵表示，應用於網際網路海量數據的聚類和分類中。本發明將有意義串挖掘方法過程分為重複串發現，串內分析，串外分析，串間分析 等四個階段，整個過程如圖1所示，包括以下步驟步驟S1，在重複串發現階段，將網頁語料預處理得到規則化的文本，記錄文本中出 現的重複串以及其出現的次數，過濾掉頻次低於閾值的重複串和串長低於閾值的重複串。步驟S2，在串內分析階段，判斷串的長度，如果該串的長度大於2，計算字符串的 互信息，判斷互信息是否達到設定的閾值，根據判斷結果過濾掉沒有達到閾值的字符串。如 果該串是雙字串，利用訓練得到的雙字串詞性統計表和白名單，根據雙字串分詞後的結果 對雙字串進行過濾。步驟S3，在串外分析階段，計算字符串的熵值，判斷熵值是否達到設定的閾值，根據判斷結果過濾掉沒有達到閾值的文本串。步驟S4，在串間分析階段，對所有字符串進行排序，計算排序後的相鄰兩串之間的 重合率，並根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃分為若干種類型，並 分別對每種類型進行分析，過濾掉不滿足要求的字符串，進而得到有意義串。本發明主要使用了兩個標準來衡量。首先，本發明在串內分析中，對長度大於2的 串計算互信息，如果互信息值小於閾值，則刪除該串。對於雙字串，首先判斷該串是否在雙 字串白名單裡，如果在的話直接對該串進行串外分析。如果雙字串不出現在白名單裡，判斷 雙字串分詞後的詞性組合是否在雙字串詞性統計表中，如果不在的話過濾該串，否則對該 串進行串外分析。其次，本發明引入了串間分析，以減少串之間的相異程度。計算排序後的相鄰兩 串之間的重合率，根據串和串之間的組成關係把重合率大於閾值的鄰串對劃分成若干種類 型，並分別對每種類型進行分析，過濾掉不滿足要求的字符串。下面詳細說明步驟S1中，將網頁語料處理得到規則化的文本，記錄文本中出現的 重複串以及其出現的次數，過濾掉頻次低於閾值的重複串和串長低於閾值的重複串的過程。本發明利用網絡爬蟲以增量方式採集網際網路上的數據，並將下載到的網頁抽取正 文並格式化成純文本文件。然後將文本轉化成GB2312編碼，根據GB2312編碼規則將文本 中的漢字，數字，英文轉化成其對應的ASCII碼值，將其他符號轉化成空格的ASCII碼，空格 主要起到了分隔符的作用。採用ASCII碼代替字符編碼可以有效的避免所提取的串中含有 半個漢字的問題，並能有效縮短提取重複串的時間。目前比較成熟的提取重複串的方法有基於產生式文法的Sequitur算法，N元遞 增分步算法，以及後綴索引算法(包括後綴樹和後綴數組)等等。後綴數組是一種全文索 引結構，利用後綴數組計算語料中所有子串的集合頻度和文檔頻度的算法的時間複雜度為 O(NlogN)，空間複雜度為0(N)，N為文本的長度。本發明實例採用的後綴數組算法。後綴數 組能在0(n)時間內建立。在提取完重複串之後，要將重複串中的空格去掉，以空格為分隔符號將重複串拆 成兩個子重複串，直至所有重複串都不含有空格為止。去掉重複串中的空格的作用是保證 提取的重複串不會跨標點、句子、段落，提高了重複串的語義完整性。互信息是衡量重複串內部各組成部分之間的相關度。如果互信息比較高，則重複 串與其單獨左右部分子串相比更可能成為有意義串，否則刪除該串。互信息是通過計算而 得到。計算互信息的公式如下給定字符串S = cic2. . . cn，其中Ci(l≤i≤n)為漢字、 英文或數字，MI (S)為S串的互信息。MI(S)={f(s)}/[f(sl) + f(sr)-f(s)}其中f(sl)為去掉首字的S串的頻次，f(sr)為去掉尾字的S串的頻次，f(s)為S 串的頻次。如圖2所示，雙字串詞性統計表和雙字串白名單是通過訓練語料訓練得到的，訓 練過程需要在人工的幫助下來訓練數據。雙字串進行分詞的結果只有兩種情況。第一種情況是對該雙字串用分詞程序只分出一個詞性出來，即該串為一個雙字詞。觀察滿足這種詞 性的所有雙字串是否有實際的語義，如果實義串的數目與滿足該類所有串的數目的比值超 過閾值的話，則將這種詞性加入到雙字串詞性統計表中。第二種情況是該雙字串用分詞程 序分成兩個詞性，即兩個單字詞，觀察滿足這種詞性的所有雙字串是否有實際的語義，如果 實義串的數目與滿足該類所有串的數目的比值超過閾值的話，則將其詞性加入到雙字串詞 性統計表中。 對於第二種情況，如果實義串的數目與該種詞性組合的串的總數目的比值沒有超 過閾值的話，我們不將該類詞性組合加入到雙字串詞性統計表中。不過滿足這類詞性組合 的雙字串中也會有部分串具有實際語義，為了避免去掉這些實義雙字串造成的有意義串特 徵提取不完全，所以可以把這些實義雙字串加入到雙字串白名單裡。雙字串白名單可以事 先過濾那些有實在意義但其分詞後的詞性組合卻不滿足雙字串詞性分析表的雙字串。對雙 字串進行串內分析時候首先要用雙字串白名單過濾雙字串，如果雙字串在白名單中，則直 接對該串進行串外分析。如果不在白名單中，再對其進行串內分析步驟中後續的分析。表1給出了雙字串詞性統計表的部分內容及其注釋
雙字串詞 注釋
性統計表分詞結果第一個詞性第二個詞性雙字串舉例
內容
ng1個詞性ng (名語素)無韃虜
nr1個詞性nr (人名)無布希
ns1個詞性ns (地名)無中國
V1個詞性v (動詞)無監督
vn1個詞性vn (名動詞)無管理
mng2個詞性m (數詞)ng(名語素)二舅
ngng2個詞性ng(名語素)ng(名語素)木骨(地名)
nrnr2個詞性nr (人名)nr (人名)湯唯
vn2個詞性v (動詞)n (名詞)借錢
無論用分詞程序將雙字串分成一個詞性還是兩個詞性，只要訓練I
者詞性組合中大部分是完整的實義串，則將該詞性或者詞性組合加入到雙字串詞性統計表 中。對雙字串進行的串內分析可以摒棄很多無意義的特徵，提高特徵的準確率。而且 還能極大地減少特徵數目。通過實驗驗證，加入雙字串串內分析可以使有意義串的特徵減 少了 89. 1%。下面詳細描述步驟S3中，計算字符串的熵值，判斷熵值是否達到設定的閾值，根 據判斷結果過濾掉沒有達到閾值的文本串的過程。熵值主要是反映字符串的獨立性，熵值越大說明該串越能夠在多種語言環境中使 用。串外分析利用熵值來判別是否對字符串進行篩選。計算熵值的公式為EL代表串的熵值。令文本T的子串R共出現F次，其左鄰接 集合L = IA，C2……CJ，C,出現頻次為fi(l彡i彡n)，貝丨J R的左鄰接熵如以下公式計算。
10 同理可計算右鄰接熵，左鄰接熵和右鄰接熵的算術平均值為串的熵值。由於當串處在句子首部時，上文為空，無法計算左鄰接熵，此&為該串處在句首的 次數。同理當串處在句子尾部時，下文為空，無法計算右鄰接熵，此時此時fi為該串處在句 尾的次數。下面詳細描述步驟S4中，對所有字符串進行排序，計算排序後的相鄰兩串之間的 重合率，並根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃分成若干種類型，並 分別對每種類型進行分析，過濾掉不滿足要求的字符串，進而得到有意義串的過程。為了判斷兩個串的相似程度，本發明定義了重合率的概念。重合率能夠度量兩個 串的重合程度的大小。當重合率大於閾值時，則兩串相似。該閾值取值要大於0.5。重合率 的計算公式如下設字符串a，字符串b的長度分別為lengthl，length2。兩串的最長公共子序列的 長度為si，兩串的最長重複子串的長度為s2，設兩串的重合率記為C (a, b)，則重合率公式
如下

圖3所示，將所有字符串排序，計算排序後兩兩相鄰串的重合率。根據相鄰串的 組合形式，只將那些重合率大於閾值的兩兩相鄰串歸入到以下5種類型中，A-AB型相鄰串， A-AB-AC型相鄰串，A-AB-ABC型相鄰串，最長公共子串為1的相鄰串及其他類型。如果相鄰 串的重合率大於閾值，則說明相鄰的兩串之間相似程度比較大。下面分別對各種類型的數 據進行分析來篩選修剪字符串，以減少字符串的語義冗餘和字符串的相似程度。對於A-AB型數據，本發明引入頻率比值來反映兩個串語用環境豐富程度上的差 異程度。我們利用頻率比值來對A-AB型數據進行篩選和修剪。設A串的頻次為f(A)，AB 串的頻次為f (AB)，則頻率比值的公式如下
A-ab型有意義_雜值
串的頻次f(AB)計算A-AB型相鄰串的頻率比值，然後判斷頻率滿足以下哪種情況。S11)如果該頻率比值大於大閾值，則說明A串出現的頻次遠遠高於AB串出現的頻 次，AB串為小概率出現的串。一般來說，小概率出現的串在全文中的作用不太突出，內容可 以忽略，而且A串在語義上能對AB串語義的丟失有一定的彌補，因此這種情況可以把AB串 過濾掉。S12)如果該頻率比值小於小閾值，則說明A串後面緊接著B串的頻次的概率遠遠 大於A串後面不緊接著B串的概率，也就是說AB串有很大的概率作為一個整體出現，因此 這種情況把A串過濾掉。S13)如果該頻率比值介於小閾值和大閾值之間，則說明A串後面接B串以及A串 後面不接B串的概率差不多，A串和AB串都具有比較完整的語義，因此這種情況兩串都保甶。對於A-AB-AC型數據，本發明通過A串，AB串，AC串的頻次來對字符串進行篩選和 修剪。設A串的頻次為f(A)，AB串的頻次為f(AB)，AC串的頻次為f(AC)。對該類型數據 的處理一共有以下四種情況。
f(AB) + f(AC)S21)如果~^的值大於重合閾值，說明AB串加上AC串出現的總次數
和A串出現的總次數差不多，這時用AB串和AC串在語義上可以很好的代替A串。因此這 種情況下我們將A串過濾掉。S22)如果^^^^的值小於重合閾值，並且AB串(或AC串)的頻次小於
最小閾值，即AB串(或AC串)出現的次數比較少。出現次數少的串大都是臨時組合，AB串 (或AC串)通常並不作為一個整體出現。因此這種情況下把AB或AC修剪成B或C。S23)如果的值小於重合閾值，並且AB和AC的頻次小於最小閾值，
這種情況下則把AB和AC修剪成B和C。 f(AB) + /(AC)S24)如果^勺值小於重合閾值，並且的頻次都大於最小閾
值，即AB串和AC串都頻繁出現，兩串有很大的概率作為一個整體存在，這種情況下不修剪 AB串和AC串。對A-AB-AC型數據進行串間分析，既能夠減少特徵的數目又可以修剪部分冗餘串 成為語義更加完整的有意義串。將AB串修剪成B串，也就是說刪除有意義串集合中的AB 串，並在有意義串集合中增加B串。當然如果B串事先已經出現在有意義串集合中，此時就 不用增加B串；否則向有意義串集合中添加B串，並將AB串的頻次作為B串的頻次。對於A-AB-ABC型數據，設A串的頻次為f (A)，AB串的頻次為f (AB)，ABC串的頻次
為f(ABC)。本來發明通過主要根據^^，二、'f(AB)和f(ABC)四個參數來對該類
所有字符串進行篩選和修剪。對於該類數據，根據以下規則處理A串和AB串，再根據相同 規則處理AB串和ABC串，將兩種處理結果結合起來就可得到對A-AB-ABC型數據的處理結^ o對於A-AB-ABC型數據中的A串和AB型的處理規則如下1)如果f(A)遠遠高於f(AB)串，這種情況將AB串過濾掉。2)如果f (A)接近f (AB)，這種情況將A串過濾掉。3)如果f (AB)小於最小閾值，這種情況把AB串修剪成B串。4)如果f(AB)大於最小閾值，這種情況A串和AB串都保留。對A-AB-ABC型數據處理的最終規則如下，規則的優先級順序是從上到下，如果滿 足任一規則後則可退出，即該對相鄰串處理完畢。「最終保留的串」是經過對A串，AB串， ABC串的修剪和篩選後最後形成的串。S30) f (AB)遠遠大於f (A)，最終保留的串為A串。 S31) f (AB)接近f(A), f (ABC)小於f (AB)，最終保留的串為ABC串。
S32) f (AB)接近f (A)，f (ABC)接近f (AB)，最終保留的串為AB串。S33)f(AB)接近f(A)，f(ABC)小於最小閾值，最終保留的串為AB串和C串。S34)f(AB)接近f(A)，f(ABC)大於最小閾值，最終保留的串為AB串。S35)f(AB)小於最小閾值，最終保留的串為A串，B串和C串。S36)f(AB)大於最小閾值，f(ABC)小於f (AB)，最終保留的串為A串和ABC串。S37)f(AB)大於最小閾值，f(ABC)接近f(AB)，最終保留的串為A串和AB串。S38)f(AB)大於最小閾值，f(ABC)小於最小閾值，最終保留的串為A，AB和C串。S39)f(AB)大於最小閾值，f (ABC)大於最小閾值，最終保留的串為A，AB和ABC串。對A-AB-ABC類型的數據進行串間分析，可以極大的減少特徵串的數目，並且使特 徵串和特徵串之間的相似程度有所減小，而保留的特徵串在語義上完全可以概括原有的特 徵串。對於相鄰串的最長公共子串為1類型的數據來說，只有相鄰串的重合率大於閾值 才有可能將相鄰串劃分到該類。既然相鄰串的重合率大於閾值，則兩串的最長公共子序列 必定大於2。通過實驗數據觀察，兩串的語義上比較相似，如下表所示。對於這種類型的數 據，可將兩串合併成1個串，只保留長度較長的串，而刪除掉長度較短的串。最後將兩串頻 次的總和作為該長度較長的串的頻次。表2給出了最長公共子串為1的相鄰串類型部分數據的處理結果 通過實驗驗證，滿足該類型的數據通常情況下一個特徵串是另一個特徵串的縮寫 形式，兩者在語義上比較相似。對該類型數據進行串間分析，可以增加特徵的強度，減少語 義漂移，使特徵具有更好的代表性；而且也能夠減少特徵的數目，起到降維的作用。以上過程提到的閾值都是經過不斷調整閾值並觀察實驗效果訓練得到。經過這一系列步驟，還沒有被過濾掉的特徵串確定為有意義串。將這些有意義串 和有意義串的頻次輸出，過程結束。為了驗證本發明的有效性，我們搭建了典型應用環境。實驗採用AMD 0PTER0N 2G 的曙光伺服器，作業系統為2. 6. 16. 19內核的Linux企業版。利用輿情系統收集到的來自新浪，中華網，網易，騰訊等六大論壇和各個新聞網頁收集到的1萬多網頁，作為測試數據 的原始網頁的一部分。經過格式化文本最終的大小為12. 3MB。本發明的有意義串的挖掘方 法在這些新聞網頁上提取有意義串的正確率可以達到85.3%。與所屬面向網際網路的有意義串的提取方法相對應，本發明還提供了一種面向互聯 網的有意義串的提取系統，如圖4所示，其包括重複串發現模塊，用於將網頁語料預處理得到規則化的文本，記錄文本中出現的 重複串以及其出現的次數，過濾掉頻次低於閾值的重複串和串長低於閾值的重複串。串內分析模塊，用於對字符串進行串內分析，判斷字符串的長度，如果該串不是雙 字串，則計算字符串的互信息，判斷互信息是否達到設定的閾值，根據判斷結果過濾掉沒有 達到閾值的文本串；如果該串是雙字串，利用訓練得到的雙字串詞性統計表和白名單，根據 雙字串分詞後的結果對雙字串進行過濾。串外分析模塊，用於對字符串進行串外分析，計算字符串的熵值，判斷熵值是否達 到設定的閾值，根據判斷結果過濾掉沒有達到閾值的字符串。串間分析模塊，用於對字符串進行串間分析，對所有字符串進行排序，計算排序後 的相鄰兩串之間的重合率，並根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃 分為若干類型，並分別對每種類型進行分析，過濾掉不滿足要求的字符串，進而得到有意義
串o本發明的面向網際網路的有意義串的提取系統，採用與面向網際網路的有意義串的提 取方法相同的過程工作，因此，在本發明實施例中，不再對該系統進行重複描述。
1權利要求
一種面向網際網路的有意義串的提取方法，其特徵是包括下列步驟步驟1提取重複字符串；步驟2通過串內分析過濾所述字符串；步驟3通過串外分析過濾所述字符串；步驟4通過串間分析過濾所述字符串。
2.根據權利要求1所述的面向網際網路的有意義串的提取方法，其特徵是所述提取重複 字符串包括將網頁語料處理得到規則化的文本，記錄文本中出現的重複串以及其出現的 次數，過濾掉頻次低於閾值的重複串和串長低於閾值的重複串；具體步驟為步驟1. 1去除網頁標籤，將網頁預處理得到規則化的文本格式，並把文本編碼格式轉 化成GB2312格式的編碼；步驟1. 2根據GB2312編碼格式，將漢字，英文，數字符號分別轉化成其ID表示，並將其 他符號用空格的ASCII碼代替；步驟1.3提取該文本的重複串，記錄文本中出現的重複串和重複串的次數，過濾出現 次數小於一定閾值的重複串；步驟1.4如果提取的重複串中有空格，則以空格為分隔符把重複串拆成子串。
3.根據權利要求1或2所述的面向網際網路的有意義串的提取方法，其特徵是所述對字 符串進行串內分析包括如果該串不是雙字串，計算字符串的互信息，判斷互信息是否達到 設定的閾值，根據判斷結果過濾掉沒有達到閾值的文本串；如果該串是雙字串，根據訓練得 到的雙字串統計表和白名單以及雙字串分詞後的結果對雙字串進行過濾；具體步驟為步驟2. 1對訓練語料進行訓練，生成雙字串詞性統計表，雙字串白名單； 步驟2. 2如果字符串的長度大於2，轉入步驟2. 3，否則轉入步驟2. 5 ； 步驟2. 3計算每個重複串的互信息，如果互信息達到閾值，則轉入步驟3 ； 步驟2. 4如果互信息沒有達到閾值，則將該串過濾掉； 步驟2. 5如果該串在雙字串白名單裡，則轉入步驟3 ； 步驟2. 6對該串用分詞程序進行分詞；步驟2. 7如果分詞後的詞性組合在雙字串詞性統計表裡，則轉入步驟3 ； 步驟2. 8如果分詞後的詞性組合不在雙字串詞性統計表裡，則過濾此串。
4.根據權利要求1或2所述的面向網際網路的有意義串的提取方法，其特徵是所述對字 符串進行串外分析包括計算字符串的熵值，判斷熵值是否達到設定的閾值，根據判斷結果 過濾掉沒有達到閾值的文本串；具體步驟為步驟3. 1計算字符串的熵值，判斷熵值是否達到設定的閾值；步驟3. 2如果達到閾值，轉入步驟4 ；步驟3. 3如果熵值未達到閾值，則將其過濾掉。
5.根據權利要求6所述的面向網際網路的有意義串的提取方法，其特徵是所述對字符串 進行串外分析包括計算字符串的熵值，判斷熵值是否達到設定的閾值，根據判斷結果過濾 掉沒有達到閾值的文本串；具體步驟為步驟3. 1計算字符串的熵值，判斷熵值是否達到設定的閾值；步驟3. 2如果達到閾值，轉入步驟4 ；步驟3. 3如果熵值未達到閾值，則將其過濾掉。
6.根據權利要求1或2所述的面向網際網路的有意義串的提取方法，其特徵是所述對字 符串進行串間分析包括對所有字符串進行排序，計算排序後的相鄰兩串之間的重合率，並 根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃分成若干種類型，並分別對每 種類型進行分析，並過濾掉不符合要求的字符串，進而得到有意義串；具體步驟為步驟4. 1對所有字符串進行排序，計算排序後每一對相鄰串的重合率； 步驟4. 2如果重合率大於閾值，根據相鄰兩串之間的組合關係，將每一對相鄰串劃分 到其所屬的類型；如果重合率小於閾值，則不統計該相鄰串的類型；步驟4. 3如果該相鄰串屬於A-AB型數據，計算A串和AB串的頻率比值；根據頻率比值 的大小來確定如何對A串，AB串處理；步驟4. 4如果連續兩個相鄰串屬於A-AB-ABC型數據，根據A串，AB串，ABC串的頻次的 組合關係來確定如何對A串，AB串，ABC串進行處理；步驟4. 5如果連續兩個相鄰串屬於A-AB-AC型數據，根據A串，AB串，AC串的頻次的組 合關係來確定如何對A串，AB串，AC串進行處理；步驟4. 6如果該相鄰串屬於最長公共子串僅為1的類型，則過濾掉相鄰串中長度較小 的字符串，保留長度較長的字符串。
7.根據權利要求3所述的面向網際網路的有意義串的提取方法，其特徵是所述對字符串 進行串間分析包括對所有字符串進行排序，計算排序後的相鄰兩串之間的重合率，並根據 串和串之間的組成關係，把重合率大於閾值的鄰串對劃分成若干種類型，並分別對每種類 型進行分析，並過濾掉不符合要求的字符串，進而得到有意義串；具體步驟為步驟4. 1對所有字符串進行排序，計算排序後每一對相鄰串的重合率； 步驟4. 2如果重合率大於閾值，根據相鄰兩串之間的組合關係，將每一對相鄰串劃分 到其所屬的類型；如果重合率小於閾值，則不統計該相鄰串的類型；步驟4. 3如果該相鄰串屬於A-AB型數據，計算A串和AB串的頻率比值；根據頻率比值 的大小來確定如何對A串，AB串處理；步驟4. 4如果連續兩個相鄰串屬於A-AB-ABC型數據，根據A串，AB串，ABC串的頻次的 組合關係來確定如何對A串，AB串，ABC串進行處理；步驟4. 5如果連續兩個相鄰串屬於A-AB-AC型數據，根據A串，AB串，AC串的頻次的組 合關係來確定如何對A串，AB串，AC串進行處理；步驟4. 6如果該相鄰串屬於最長公共子串僅為1的類型，則過濾掉相鄰串中長度較小 的字符串，保留長度較長的字符串。
8.根據權利要求4所述的面向網際網路的有意義串的提取方法，其特徵是所述對字符串 進行串間分析包括對所有字符串進行排序，計算排序後的相鄰兩串之間的重合率，並根據 串和串之間的組成關係，把重合率大於閾值的鄰串對劃分成若干種類型，並分別對每種類 型進行分析，並過濾掉不符合要求的字符串，進而得到有意義串；具體步驟為步驟4. 1對所有字符串進行排序，計算排序後每一對相鄰串的重合率； 步驟4. 2如果重合率大於閾值，根據相鄰兩串之間的組合關係，將每一對相鄰串劃分 到其所屬的類型；如果重合率小於閾值，則不統計該相鄰串的類型；步驟4. 3如果該相鄰串屬於A-AB型數據，計算A串和AB串的頻率比值；根據頻率比值 的大小來確定如何對A串，AB串處理；步驟4. 4如果連續兩個相鄰串屬於A-AB-ABC型數據，根據A串，AB串，ABC串的頻次的 組合關係來確定如何對A串，AB串，ABC串進行處理；步驟4. 5如果連續兩個相鄰串屬於A-AB-AC型數據，根據A串，AB串，AC串的頻次的組 合關係來確定如何對A串，AB串，AC串進行處理；步驟4. 6如果該相鄰串屬於最長公共子串僅為1的類型，則過濾掉相鄰串中長度較小 的字符串，保留長度較長的字符串。
9.根據權利要求5所述的面向網際網路的有意義串的提取方法，其特徵是所述對字符串 進行串間分析包括對所有字符串進行排序，計算排序後的相鄰兩串之間的重合率，並根據 串和串之間的組成關係，把重合率大於閾值的鄰串對劃分成若干種類型，並分別對每種類 型進行分析，並過濾掉不符合要求的字符串，進而得到有意義串；具體步驟為步驟4. 1對所有字符串進行排序，計算排序後每一對相鄰串的重合率； 步驟4. 2如果重合率大於閾值，根據相鄰兩串之間的組合關係，將每一對相鄰串劃分 到其所屬的類型；如果重合率小於閾值，則不統計該相鄰串的類型；步驟4. 3如果該相鄰串屬於A-AB型數據，計算A串和AB串的頻率比值；根據頻率比值 的大小來確定如何對A串，AB串處理；步驟4. 4如果連續兩個相鄰串屬於A-AB-ABC型數據，根據A串，AB串，ABC串的頻次的 組合關係來確定如何對A串，AB串，ABC串進行處理；步驟4. 5如果連續兩個相鄰串屬於A-AB-AC型數據，根據A串，AB串，AC串的頻次的組 合關係來確定如何對A串，AB串，AC串進行處理；步驟4. 6如果該相鄰串屬於最長公共子串僅為1的類型，則過濾掉相鄰串中長度較小 的字符串，保留長度較長的字符串。
10.一種面向網際網路的有意義串的提取裝置，其特徵是包括依次串接的重複串發現模 塊、串內分析模塊、串外分析模塊和串間分析模塊；重複串發現模塊，用於將網頁語料預處理得到規則化的文本，記錄文本中出現的重複 串以及其出現的次數，過濾掉頻次低於閾值的重複串和長度低於閾值的重複串；串內分析模塊，用於對字符串進行串內分析，判斷串的長度，如果該串的長度大於2，計 算字符串的互信息，判斷互信息是否達到設定的閾值，根據判斷結果過濾掉沒有達到閾值 的文本串；如果該串是雙字串，利用訓練得到的雙字串統計表和白名單，根據雙字串分詞後 的結果對雙字串進行過濾；串外分析模塊，用於對字符串進行串外分析，計算字符串的熵值，判斷熵值是否達到設 定的閾值，根據判斷結果過濾掉沒有達到閾值的字符串。串間分析模塊，用於對字符串進行串間分析，對所有字符串進行排序，計算排序後的 相鄰兩串之間的重合率，並根據串和串之間的組成關係，把重合率大於閾值的鄰串對劃分 為若干種類型，並分別對每種類型進行分析，過濾掉不滿足要求的字符串，進而得到有意義 串o
全文摘要
本發明提供的是一種面向網際網路的有意義串的提取方法及裝置。提取方法包括提取重複字符串，通過串內分析過濾所述字符串，通過串外分析過濾所述字符串，通過串間分析過濾所述字符串步驟；提取裝置包括依次串接的重複串發現模塊、串內分析模塊、串外分析模塊和串間分析模塊。本發明能夠有效的提取新聞網頁和論壇上的有意義串。本發明可廣泛應用於網絡輿情管理、網際網路智能信息處理等應用領域。
文檔編號G06F17/30GK101853284SQ20101017968
公開日2010年10月6日 申請日期2010年5月24日 優先權日2010年5月24日
發明者楊武, 王巍, 苘大鵬, 董紅臣 申請人:哈爾濱工程大學