文章自动生成标签的算法分析与实现

唯有回望，才能发现，我们究竟已经走出多远。
唯有前瞻，才能相信，我们沿着这条航线，一定能抵达梦想的彼岸。

标签匹配算法分析

假设有一篇文章，标题和内容如下：

标题：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、创建一个带指针的字符串对象

↓
S	p	r	i	n	g		B	o	o	t

2、生成标签字典

此处需要一个标签库，可以利用爬虫技术从相关资源网站爬取

2.1 定义标签节点 TagNode

属性	数据类型	描述
headTwoCharMix	int	标签头2个字符的int值
words	TreeSet	头2个字符相同的标签集合
next	TagNode	指向下一个标签节点的指针

headTwoCharMix 的计算规则：
- char 16bit
- int 32bit
将第一个字符左移16位，然后加上第二个字符的值，即为结果

2.2 生成字典 TagNode[]

① 初始化标签节点数组，数组大小(size)最好与标签库的数量相同，因为数组是顺序存储的，通过下标查找，速度非常快；
② 计算标签头2个字符的Hash值(hash)，计算标签应该存到数组的位置(hash & (size - 1))；
③ 如果数组该位置为空，为此标签生成节点，添加此节点到该位置；
④ 如果数组该位置不为空，判断标签和此位置的节点的headTwoCharMix是否相等，若相等，则将标签添加到 TreeSet 中，若不相等，则生成新的节点，并用指针关联；【拉链法解决Hash冲突】

2.3 在文本中匹配标签

							↓
S	p	r	i	n	g		B	o	o	t	容	器
选	择		U	n	d	e	r	t	o	w	而	不
是		T	o	m	c	a	t

指针从文本的开头，向后遍历，计算当前的位置的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
@AllArgsConstructor
public 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
@AllArgsConstructor
public 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;
            }
        }
    }

}