文章自動生成標籤的演算法分析與實現

01-25

唯有回望，才能發現，我們究竟已經走出多遠。

唯有前瞻，才能相信，我們沿著這條航線，一定能抵達夢想的彼岸。

標籤匹配演算法分析

假設有一篇文章，標題和內容如下：

標題：Spring Boot 容器選擇 Undertow 而不是 Tomcat
內容：Spring Boot內嵌容器支持Tomcat、Jetty、Undertow。為什麼選擇Undertow？這裡有一篇文章，時間 2017年1月26日發布的：
Tomcat vs. Jetty vs. Undertow: Comparison of Spring Boot Embedded Servlet Containers
這篇文章詳細測試了Spring Boot應用在三種容器下的性能和內存使用，內含完整的測試代碼和測試流程。證明了Undertow在性能和內存使用上是最好的。

如果要為此文章自動生成標籤，該如何做呢？

1、創建一個帶指針的字元串對象

2、生成標籤字典

此處需要一個標籤庫，可以利用爬蟲技術從相關資源網站爬取

2.1 定義標籤節點 TagNode

headTwoCharMix 的計算規則：- char 16bit- int 32bit將第一個字元左移16位，然後加上第二個字元的值，即為結果

2.2 生成字典 TagNode[]

① 初始化標籤節點數組，數組大小(size)最好與標籤庫的數量相同，因為數組是順序存儲的，通過下標查找，速度非常快；
② 計算標籤頭2個字元的Hash值(hash)，計算標籤應該存到數組的位置(hash & (size - 1))；
③ 如果數組該位置為空，為此標籤生成節點，添加此節點到該位置；
④ 如果數組該位置不為空，判斷標籤和此位置的節點的headTwoCharMix是否相等，若相等，則將標籤添加到 TreeSet 中，若不相等，則生成新的節點，並用指針關聯；【拉鏈法解決Hash衝突】

2.3 在文本中匹配標籤

指針從文本的開頭，向後遍歷，計算當前的位置的headTwoCharMix，即此處的 「Bo」 2個字元，然後計算Hash值定位到字典的位置，字典的位置只會出現如下兩種情況：

無節點：指針向後移動，繼續匹配；
有節點：計算 headTwoCharMix ，若 headTwoCharMix 相等，然後根據 TreeSet 中的標籤，進行最長匹配；若 headTwoCharMix 不相等，則用後繼節點來匹配，直到後繼節點為空位置。中途匹配到標籤，則指針直接向後移動（標籤的長度）位。

標籤匹配在實際應用中的問題

1、權重問題

標題和內容的權重應該是不同的，所以在匹配出標籤的時候，需要給匹配到的標籤添加分數，依據得分高低對匹配標籤排序

2、英文字元大小寫的問題

例如：標籤庫中有一個標籤「Docker」，結果文中出現的是「docker」，這兩個字元串是不相等的，從邏輯上來講，標籤是匹配到的，所以要調整演算法，將大寫字母全部轉換為小寫字母來匹配

標籤匹配核心演算法

帶指針的字元串 StringPointer.java

/** * 帶指針的字元串 */public class StringPointer implements CharSequence, Comparable<StringPointer> { private final char[] value; private final int offset; public final int length; public StringPointer(String str) { value = str.toCharArray(); offset = 0; length = value.length; } private StringPointer(char[] value, int offset, int length) { this.value = value; this.offset = offset; this.length = length; } /** * 計算從該位置起2個字元的hash值 * * @param i 從 0 到 length - 2 * @return hash值 */ public int nextTwoCharHash(int i) { return 31 * lowerChar(value[offset + i]) + lowerChar(value[offset + i + 1]); } /** * 計算從該位置起2個字元的和 <br/> * 如果和相同，即2個字元相同 * * @param i 從 0 到 length - 2 * @return int值 */ public int nextTwoCharMix(int i) { return (lowerChar(value[offset + i]) << 16) | lowerChar(value[offset + i + 1]); } /** * 判斷該位置後的字元串，是否以某個詞開頭 * * @param i 從 0 到 length - 2 * @param word 詞 * @return 是否？ */ public boolean nextStartsWith(int i, StringPointer word) { // 是否長度超出 if (word.length > length - i) { return false; } // 從尾開始判斷 for (int c = word.length - 1; c >= 0; c--) { if (lowerChar(value[offset + i + c]) != lowerChar(word.value[word.offset + c])) { return false; } } return true; } private char lowerChar(char a){ if (Character.isUpperCase(a)){ return Character.toLowerCase(a); } return a; } public int length() { return length; } public char charAt(int i) { return value[offset + i]; } public StringPointer substring(int begin) { return new StringPointer(value, offset + begin, length - begin); } private StringPointer substring(int begin, int end) { return new StringPointer(value, offset + begin, end - begin); } public CharSequence subSequence(int start, int end) { return substring(start, end); } public String toString() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < length; i++) { sb.append(value[i]); } return sb.toString(); } public int compareTo(StringPointer that) { int length = this.length; int thatLength = that.length; int lim = Math.min(length, thatLength); int k = 0; while (k < lim) { char c1 = this.value[this.offset + k]; char c2 = that.value[that.offset + k]; if (c1 != c2) { return c1 - c2; } k++; } return length - thatLength; }}

標籤節點 TagNode.java

import java.util.TreeSet;/** * 標籤節點 */public class TagNode { /** * 頭兩個字元的混合值，值相同，兩個字元相同 */ public final int headTwoCharMix; /** * 所有以這兩個字元開頭的詞表 */ public final TreeSet<StringPointer> words = new TreeSet<>(); /** * 下一個節點 */ public TagNode next; public TagNode(int headTwoCharMix){ this.headTwoCharMix = headTwoCharMix; } public TagNode(int headTwoCharMix, TagNode parent){ this.headTwoCharMix = headTwoCharMix; parent.next = this; }}

標籤分數統計類 TagBean.java

import lombok.AllArgsConstructor;import lombok.Data;import lombok.NoArgsConstructor;@Data@NoArgsConstructor@AllArgsConstructorpublic class TagBean implements Comparable<TagBean> { // 標籤名 private String name; // 分數 private Integer score; // 增加分數 public void addScore(Integer num){ this.score = this.score + num; } @Override public int compareTo(TagBean o) { return o.getScore().compareTo(this.score); }}

標籤匹配工具類 TagTools.java

@Component@Log4j2@AllArgsConstructorpublic class TagTools implements InitializingBean { // 數組大小 private static final int DEFAULT_SIZE = 1024; // 內容分數 private static final int CONTENT_SCORE = 1; // 標題分數 private static final int TITLE_SCORE = 5; // 標籤數量 private static final int TAG_SIZE = 5; // 最低分數 private static final int MIN_SCORE = 2; // 標籤數組 private final TagNode[] nodes = new TagNode[DEFAULT_SIZE]; private final TagMapper tagMapper; @Override public void afterPropertiesSet() throws Exception { // 初始化標籤庫 List<String> tags = tagMapper.selectAll(); for (String tag : tags) { put(tag); } } /** * 自動生成標籤 */ public void generateTags(String title, String content) { Map<String, TagBean> tagMap = new HashMap<>(); matchTags(title, TagTools.TITLE_SCORE, tagMap); matchTags(content, TagTools.CONTENT_SCORE, tagMap); // 獲取所有匹配到的標籤名及分數 Collection<TagBean> tagBeans = tagMap.values(); // TODO 相關業務邏輯 } /** * 匹配標籤 */ private void matchTags(String content, Integer score, Map<String, TagBean> tagMap) { content = preHandle(content); StringPointer sp = new StringPointer(content); int i = 0; while (i < sp.length - 1) { int step = 1; int hash = sp.nextTwoCharHash(i); TagNode node = nodes[hash & (nodes.length - 1)]; if (node != null) { int mix = sp.nextTwoCharMix(i); outer: for (; node != null; node = node.next) { if (node.headTwoCharMix == mix) { NavigableSet<StringPointer> desSet = node.words.headSet(sp.substring(i), true); for (StringPointer word : desSet.descendingSet()) { if (sp.nextStartsWith(i, word)) { String tagWord = word.toString(); TagBean tag = tagMap.get(tagWord); if (tag == null) { tagMap.put(tagWord, new TagBean(tagWord, score)); } else { tag.addScore(score); } step = word.length; break outer; } } } } } i += step; } } /** * 文本預處理 * "-"轉空格 -> 移除Html標籤 */ private String preHandle(String content) { return content.replaceAll("-", " ").replaceAll("<.*?>", ""); } /** * 新增標籤節點 */ private void put(String word) { if (word == null || word.trim().length() < 2) { return; } StringPointer sp = new StringPointer(word.trim()); int hash = sp.nextTwoCharHash(0); int mix = sp.nextTwoCharMix(0); int index = hash & (nodes.length - 1); TagNode node = nodes[index]; if (node == null) { node = new TagNode(mix); node.words.add(sp); nodes[index] = node; } else { while (node != null) { if (node.headTwoCharMix == mix) { node.words.add(sp); return; } if (node.next == null) { new TagNode(mix, node).words.add(sp); return; } node = node.next; } } }}

----------------------

作者：Anoy

鏈接：文章自動生成標籤的演算法分析與實現 | Spring For All

聲明：本文來源於Spring For All，版權歸作者所有，有什麼問題，請聯繫我們，謝謝！