java使用ac算法实现高性能关键词高亮

标签：amp   pre   rdma   lda   位置   ext   pac   ast   util   

需求背景

标记出一句话中所有关键词
inpu:我想买苹果手机，请问哪里可以买苹果手机
keyword:"苹果", "苹果手机", "哪里"
result:我想买[[苹果手机]]，请问[[哪里]]可以买[[苹果手机]]
10w条耗时：41ms

难点：需要考虑单词重叠问题（overlap），例如“苹果手机”同时包含两个关键词，只标记一次。

思路

1. 通过ac自动机遍历得到所有关键词；
2. 新建一个byte[]，长度等于原句子，根据ac算法结果将关键字位置设为1；
3. 将原句子转为char[]，遍历char[]和byte[]，如果byte[]前后位置不一致，则插入替换符；
   3.1 如果前一个为1，后一个为0，则插入“]]”；
   3.2 如果前一个为0，后一个为1，则插入“[[”；
4. 判断末尾是否插入替换符；

代码

pom文件引入hanlp，使用其中ac算法

com.hankcs
    hanlp
    portable-1.7.8

package com.bincoder.StringUtils;

import com.hankcs.hanlp.collection.AhoCorasick.AhoCorasickDoubleArrayTrie;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

public class KeywordMatch {

    /**
     * 构建ac自动机
     */
    public static AhoCorasickDoubleArrayTrie buildAcdt(List keywords){
        AhoCorasickDoubleArrayTrie acdt = new AhoCorasickDoubleArrayTrie();
        TreeMap map = new TreeMap();
        for(String keyword : keywords){
            map.put(keyword, keyword);
        }
        acdt.build(map);
        return acdt;
    }

    public static String highLight(String originText, AhoCorasickDoubleArrayTrie acdt){
        List hitLocationList = new ArrayList();
        // ac算法匹配关键词
        acdt.parseText(originText, (begin, end, value)->{
           int[] indexPair = new int[2];
           indexPair[0] = begin;
           indexPair[1] = end-1;
           hitLocationList.add(indexPair);
        });
        // 构建bitmap
        byte[] posStatus = new byte[originText.length()];
        for(int[] item : hitLocationList){
            for(int i=item[0]; i keywords = Arrays.asList("苹果", "苹果手机", "哪里");

        AhoCorasickDoubleArrayTrie acdt = KeywordMatch.buildAcdt(keywords);
        String result = KeywordMatch.highLight(text, acdt);
        System.out.println("inpu:" + text);
        System.out.println("result:" + result);

        long start = System.currentTimeMillis();
        for(int i=0; i

java使用ac算法实现高性能关键词高亮

标签：amp   pre   rdma   lda   位置   ext   pac   ast   util   

原文地址：https://www.cnblogs.com/bincoding/p/13613492.html