0

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

极乐小程序商店 2018年01月04日 发布于后端 zhuanlan.zhihu.com

标签匹配算法分析

假设有一篇文章,标题和内容如下:

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

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

2018年01月04日 发布,来源:zhuanlan.zhihu.com

唯有回望,才能发现,我们究竟已经走出多远。

唯有前瞻,才能相信,我们沿着这条航线,一定能抵达梦想的彼岸。

标签匹配算法分析

假设有一篇文章,标题和内容如下:

标题: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
@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;
            }
        }
    }

}

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

作者:Anoy

链接:文章自动生成标签的算法分析与实现 | Spring For All

声明:本文来源于Spring For All,版权归作者所有,有什么问题,请联系我们,谢谢!

1.2k 浏览 收藏 报告 阅读模式
载入中...