轉(zhuǎn)TextRank算法提取關(guān)鍵詞的Java實(shí)現(xiàn)
談起自動(dòng)摘要算法，常見的并且最易實(shí)現(xiàn)的當(dāng)屬TF-IDF，但是感覺TF-IDF效果一般，不如TextRank好。
TextRank是在Google的PageRank算法啟發(fā)下熟呛，針對(duì)文本里的句子設(shè)計(jì)的權(quán)重算法，目標(biāo)是自動(dòng)摘要尉姨。它利用投票的原理庵朝，讓每一個(gè)單詞給它的鄰居（術(shù)語稱窗口）投贊成票，票的權(quán)重取決于自己的票數(shù)又厉。這是一個(gè)“先有雞還是先有蛋”的悖論九府，PageRank采用矩陣迭代收斂的方式解決了這個(gè)悖論。TextRank也不例外:
PageRank的計(jì)算公式
TextRank公式
正規(guī)的TextRank公式在PageRank的公式的基礎(chǔ)上覆致，引入了邊的權(quán)值的概念侄旬，代表兩個(gè)句子的相似度。
如果把一個(gè)單詞視為一個(gè)句子的話煌妈，那么所有句子（單詞）構(gòu)成的邊的權(quán)重都是0（沒有交集儡羔，沒有相似性），所以分子分母的權(quán)值w約掉了璧诵，算法退化為PageRank汰蜘。
TextRank的Java實(shí)現(xiàn)
測(cè)試數(shù)據(jù)：
程序員(英文Programmer)是從事程序開發(fā)、維護(hù)的專業(yè)人員之宿。一般將程序員分為程序設(shè)計(jì)人員和程序編碼人員族操，但兩者的界限并不非常清楚，特別是在中國(guó)澈缺。軟件從業(yè)人員分為初級(jí)程序員坪创、高級(jí)程序員、系統(tǒng)分析員和項(xiàng)目經(jīng)理四大類姐赡。
我取出了百度百科關(guān)于“程序員”的定義作為測(cè)試用例，很明顯柠掂，這段定義的關(guān)鍵字應(yīng)當(dāng)是“程序員”并且“程序員”的得分應(yīng)當(dāng)最高项滑。
首先對(duì)這句話分詞，這里可以借助各種分詞項(xiàng)目涯贞，比如HanLP分詞枪狂，得出分詞結(jié)果：
程序員/n, (英文/nz, programmer/en, ), 是/v, 從事/v, 程序/n, 開發(fā)/v, 危喉、/w, 維護(hù)/v, 的/uj, 專業(yè)/n, 人員/n, 。/w, 一般/a, 將/d, 程序員/n, 分為/v, 程序/n, 設(shè)計(jì)/vn, 人員/n, 和/c, 程序/n, 編碼/n, 人員/n, 州疾，/w, 但/c, 兩者/r, 的/uj, 界限/n, 并/c, 不/d, 非常/d, 清楚/a, 辜限，/w, 特別/d, 是/v, 在/p, 中國(guó)/ns, 。/w, 軟件/n, 從業(yè)/b, 人員/n, 分為/v, 初級(jí)/b, 程序員/n, 严蓖、/w, 高級(jí)/a, 程序員/n, 薄嫡、/w, 系統(tǒng)/n, 分析員/n, 和/c, 項(xiàng)目/n, 經(jīng)理/n, 四/m, 大/a, 類/q, 。/w
然后去掉里面的停用詞颗胡，這里我去掉了標(biāo)點(diǎn)符號(hào)毫深、常用詞、以及“名詞毒姨、動(dòng)詞哑蔫、形容詞、副詞之外的詞”弧呐。得出實(shí)際有用的詞語：
程序員, 英文, 程序, 開發(fā), 維護(hù), 專業(yè), 人員, 程序員, 分為, 程序, 設(shè)計(jì), 人員, 程序, 編碼, 人員, 界限, 特別, 中國(guó), 軟件, 人員, 分為, 程序員, 高級(jí), 程序員, 系統(tǒng), 分析員, 項(xiàng)目, 經(jīng)理
之后建立兩個(gè)大小為5的窗口闸迷，每個(gè)單詞將票投給它身前身后距離5以內(nèi)的單詞：
開發(fā)=[專業(yè), 程序員, 維護(hù), 英文, 程序, 人員],
軟件=[程序員, 分為, 界限, 高級(jí), 中國(guó), 特別, 人員],
程序員=[開發(fā), 軟件, 分析員, 維護(hù), 系統(tǒng), 項(xiàng)目, 經(jīng)理, 分為, 英文, 程序, 專業(yè), 設(shè)計(jì), 高級(jí), 人員, 中國(guó)],
分析員=[程序員, 系統(tǒng), 項(xiàng)目, 經(jīng)理, 高級(jí)],
維護(hù)=[專業(yè), 開發(fā), 程序員, 分為, 英文, 程序, 人員],
系統(tǒng)=[程序員, 分析員, 項(xiàng)目, 經(jīng)理, 分為, 高級(jí)],
項(xiàng)目=[程序員, 分析員, 系統(tǒng), 經(jīng)理, 高級(jí)],
經(jīng)理=[程序員, 分析員, 系統(tǒng), 項(xiàng)目],
分為=[專業(yè), 軟件, 設(shè)計(jì), 程序員, 維護(hù), 系統(tǒng), 高級(jí), 程序, 中國(guó), 特別, 人員],
英文=[專業(yè), 開發(fā), 程序員, 維護(hù), 程序],
程序=[專業(yè), 開發(fā), 設(shè)計(jì), 程序員, 編碼, 維護(hù), 界限, 分為, 英文, 特別, 人員],
特別=[軟件, 編碼, 分為, 界限, 程序, 中國(guó), 人員],
專業(yè)=[開發(fā), 程序員, 維護(hù), 分為, 英文, 程序, 人員],
設(shè)計(jì)=[程序員, 編碼, 分為, 程序, 人員],
編碼=[設(shè)計(jì), 界限, 程序, 中國(guó), 特別, 人員],
界限=[軟件, 編碼, 程序, 中國(guó), 特別, 人員],
高級(jí)=[程序員, 軟件, 分析員, 系統(tǒng), 項(xiàng)目, 分為, 人員],
中國(guó)=[程序員, 軟件, 編碼, 分為, 界限, 特別, 人員],
人員=[開發(fā), 程序員, 軟件, 維護(hù), 分為, 程序, 特別, 專業(yè), 設(shè)計(jì), 編碼, 界限, 高級(jí), 中國(guó)]
然后開始迭代投票：
for (int i = 0; i < max_iter; ++i)
{
Map<String, Float> m = new HashMap<String, Float>();
float max_diff = 0;
for (Map.Entry<String, Set<String>> entry : words.entrySet())
{
String key = entry.getKey();
Set<String> value = entry.getValue();
m.put(key, 1 - d);
for (String other : value)
{
int size = words.get(other).size();
if (key.equals(other) || size == 0) continue;
m.put(key, m.get(key) + d / size * (score.get(other) == null ? 0 : score.get(other)));
}
max_diff = Math.max(max_diff, Math.abs(m.get(key) - (score.get(key) == null ? 0 :score.get(key))));
} score = m;
if (max_diff <= min_diff) break;
}
排序后的投票結(jié)果：
程序員=1.9249977,
人員=1.6290349,
分為=1.4027836,
程序=1.4025855,
高級(jí)=0.9747374,
軟件=0.93525416,
中國(guó)=0.93414587,
特別=0.93352026,
維護(hù)=0.9321688,
專業(yè)=0.9321688,
系統(tǒng)=0.885048,
編碼=0.82671607,
界限=0.82206935,
開發(fā)=0.82074183,
分析員=0.77101076,
項(xiàng)目=0.77101076,
英文=0.7098714,
設(shè)計(jì)=0.6992446,
經(jīng)理=0.64640945
