作者：京东零售 周德东

一、背景

需求非常简单，给定一组关键词，需要将商品名称中出现过的关键字替换掉；

如：skuName="HUAWEI Pura 70 Pro 国家补贴500元 羽砂黑 12GB+512GB 超高速风驰闪拍 华为鸿蒙智能手机" 需要替换成

skuName="HUAWEI Pura 70 Pro 羽砂黑 12GB+512GB 超高速风驰闪拍 华为鸿蒙智能手机" 这里的关键字"国家补贴500元";

直接skuName.replace("国家补贴500元", "")，不就可以了吗？如果是一组，那就循环替换就完了嘛，再考虑到关键字前缀问题，对这一组关键词，按字符长度进行排序，先替换长的关键词，再替换短的就ok了；

如果这一组关键词非常多，上千个怎么办？真实场景也是这样的，一般需要替换的关键词都是比较多，并且使用String.replace上线后，直接CPU打满，基本不可用；

这个字段替换本质上与敏感词过滤是一样的原理，针对敏感词的深入研究，出现了 Aho-Corasick（AC自动机） 算法；

Aho-Corasick（AC自动机）是一种多模式字符串匹配算法，结合了Trie树的前缀匹配能力和KMP算法的失败跳转思想，能够在单次文本扫描中高效匹配多个模式串。其核心优势在于时间复杂度为O(n + m + z)（n为文本长度，m为模式串总长度，z为匹配次数），适用于敏感词过滤、基因序列分析等场景。



二、方案

针对这几种算法进行对比；

字符串替换，定义一个接口，通过4个不同的方案实现，进行性能对比

1public interface Replacer {
2    String replaceKeywords(String text);
3}

2.1 String.replace 方案

这种方案最简单，也是关键词少的时候，最有效，最好用的;

1public class StrReplacer implements Replacer {
2    private final List<String> keyWordList;
3    public StrReplacer(String keyWords) {
4        this.keyWordList = Lists.newArrayList(keyWords.split(";"));
5        // 按关键字长度降序排序，确保长关键字优先匹配
6        keyWordList.sort((a, b) -> Integer.compare(b.length(), a.length()));
7    }
8    /**
9    * 替换文本中所有匹配的关键字为空字符串
10    */
11    @Override
12    public String replaceKeywords(String text) {
13        String newTxt = text;
14        for (String s : keyWordList) {
15            newTxt = newTxt.replace(s, "");
16        }
17        return newTxt;
18    }
19}

2.2 使用正则替换

String.replace本质，还是使用正则进行替换的，通过代码实现使用编译好的正则进行替换性能会好于直接使用replace；

String.replace的实现

1public String replace(CharSequence target, CharSequence replacement) {
2    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
3            this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
4}

使用正则替换的实现

1public class PatternReplacer implements Replacer {
2    // 预编译正则表达式模式
3    private final Pattern pattern;
4    public PatternReplacer(String keyWords) {
5        List<String> keywords = Lists.newArrayList(keyWords.split(";"));
6        // 按关键字长度降序排序，确保长关键字优先匹配
7        keywords.sort((a, b) -> Integer.compare(b.length(), a.length()));
8        // 转义每个关键字并用|连接
9        String regex = keywords.stream()
10                .map(Pattern::quote)
11                .collect(Collectors.joining("|"));
12
13        this.pattern = Pattern.compile(regex);
14    }
15
16    // 替换方法
17    @Override
18    public String replaceKeywords(String skuName) {
19        return pattern.matcher(skuName).replaceAll("");
20    }
21}

2.3 使用Aho-Corasick（AC自动机） 算法实现

在java中已有现成的算法实现，源代码github-robert-bor/aho-corasick，

引入jar包

1<dependency>
2    <groupId>org.ahocorasick</groupId>
3    <artifactId>ahocorasick</artifactId>
4    <version>0.6.3</version>
5</dependency>

基于 Aho-Corasick 算法的字符串替换实现

1public class AhoCorasickReplacer implements Replacer {
2    private final Trie trie;
3    public AhoCorasickReplacer(String keyWords) {
4        // 构建Aho-Corasick自动机
5        Trie.TrieBuilder builder = Trie.builder().ignoreOverlaps().onlyWholeWords();
6        //trie.caseInsensitive();
7        //trie.onlyWholeWords();
8        for (String s : keyWords.split(";")) {
9            builder.addKeyword(s);
10        }
11        this.trie = builder.build();
12    }
13    /**
14     * 替换文本中所有匹配的关键字为空字符串
15     */
16    @Override
17    public String replaceKeywords(String text) {
18        if (text == null || text.isEmpty()) {
19            return text;
20        }
21        StringBuilder result = new StringBuilder();
22        Collection<Emit> emits = trie.parseText(text); // 获取所有匹配结果
23        int lastEnd = 0;
24        for (Emit emit : emits) {
25            int start = emit.getStart();
26            int end = emit.getEnd();
27
28            // 添加未匹配的前缀部分
29            if (start > lastEnd) {
30                result.append(text, lastEnd, start);
31            }
32            // 跳过匹配的关键字（即替换为空）
33            lastEnd = end + 1; // 注意：end是闭区间，需+1移动到下一个字符
34        }
35        // 添加剩余未匹配的后缀部分
36        if (lastEnd <= text.length() - 1) {
37            result.append(text.substring(lastEnd));
38        }
39        return result.toString();
40    }
41}

2.4 自己实现Trie树算法实现

通过deepseek等人工智能，是非常容易自己实现一个Trie树，我们就只实现字符串替换的功能，其他的就不使用了；

Trie树，又叫字典树，前缀树(Prefix Tree)，单词查找树，是一种多叉树的结构.



结构说明： 表示根节点（空节点）

每个节点表示一个字符

粉色节点表示单词结束标记（使用 CSS class 实现）

路径示例：

root → c → a → t 组成 "cat"

root → c → a → r 组成 "car"

root → d → o → g 组成 "dog"

1public class TrieKeywordReplacer implements Replacer {
2
3    private final Trie trie;
4
5    @Override
6    public String replaceKeywords(String text) {
7        return trie.replaceKeywords(text, "");
8    }
9
10    public TrieKeywordReplacer(String keyWords) {
11        Trie trie = new Trie();
12        for (String s : keyWords.split(";")) {
13            trie.insert(s);
14        }
15        this.trie = trie;
16    }
17
18    static class TrieNode {
19        Map<Character,TrieNode> children;
20        boolean isEndOfWord;
21
22        public TrieNode() {
23            children = new HashMap<>();
24            isEndOfWord = false;
25        }
26    }
27
28    static class Trie {
29        private TrieNode root;
30
31        public Trie() {
32            root = new TrieNode();
33        }
34
35        private synchronized void insert(String word) {
36            TrieNode node = root;
37            for (char c : word.toCharArray()) {
38                if (node.children.get(c) == null) {
39                    node.children.put(c, new TrieNode());
40                }
41                node = node.children.get(c);
42            }
43            node.isEndOfWord = true;
44        }
45
46        public String replaceKeywords(String text, String replacement) {
47            StringBuilder result = new StringBuilder();
48            int i = 0;
49            while (i < text.length()) {
50                TrieNode node = root;
51                int j = i;
52                TrieNode endNode = null;
53                int endIndex = -1;
54                while (j < text.length() && node.children.get(text.charAt(j)) != null) {
55                    node = node.children.get(text.charAt(j));
56                    if (node.isEndOfWord) {
57                        endNode = node;
58                        endIndex = j;
59                    }
60                    j++;
61                }
62                if (endNode != null) {
63                    result.append(replacement);
64                    i = endIndex + 1;
65                } else {
66                    result.append(text.charAt(i));
67                    i++;
68                }
69            }
70            return result.toString();
71        }
72    }
73}

4个实现类对象的大小对比

性能对比

说明：待替换一组关键词共 400个；JDK1.8



通过性能对比，自己实现的Trie树的性能是最好的，因为只做了替换的逻辑，没有实现其他功能，其次是使用AhoCorasick算法，因为使用 AhoCorasick算法，实现字符串替换是最基本的功能，AhoCorasick算法，还能精准的匹配到在什么地方，出现过多少次等信息，功能非常强大；

通过对比编译好的正则性能确实是比使用原生String.replace;

1public class ReplacerTest {
2
3    @Test
4    public void testTrieKeywordReplacer(){
5        //String name = skuName;
6        //String expected = v2;
7        //String name = "三星Samsung Galaxy S25+ 超拟人AI助理 骁龙8至尊版 AI拍照 翻译手机 游戏手机 12GB+256GB 冷川蓝";
8        //String expected = name;
9
10        String name = keyWords;
11        String expected = v1;
12        int cnt = 2;
13        Replacer replacer = new TrieKeywordReplacer(keyWords);
14        check(replacer, name, expected);
15        for (int i = 0; i < cnt; i++) {
16            checkExec(replacer, name);
17        }
18    }
19
20    @Test
21    public void 替换所有关键字() throws InterruptedException {
22        //String name = skuName;
23        //String expected = v2;
24        //String name = "三星Samsung Galaxy S25+ 超拟人AI助理 骁龙8至尊版 AI拍照 翻译手机 游戏手机 12GB+256GB 冷川蓝";
25        //String expected = name;
26
27        String name = keyWords;
28        String expected = v1;
29
30        int cnt = 2;
31        System.out.println("替换：" + name);
32        Replacer replacer = new StrReplacer(keyWords);
33        check(replacer, name, expected);
34        for (int i = 0; i < cnt; i++) {
35            checkExec(replacer, name);
36        }
37
38
39        replacer = new PatternReplacer(keyWords);
40        check(replacer, name, expected);
41        for (int i = 0; i < cnt; i++) {
42            checkExec(replacer, name);
43        }
44
45        replacer = new TrieKeywordReplacer(keyWords);
46        check(replacer, name, expected);
47        for (int i = 0; i < cnt; i++) {
48            checkExec(replacer, name);
49        }
50
51        replacer = new AhoCorasickReplacer(keyWords);
52        check(replacer, name, expected);
53        for (int i = 0; i < cnt; i++) {
54            checkExec(replacer, name);
55        }
56
57
58
59    }
60
61
62    @Test
63    public void 无关键字替换() throws InterruptedException {
64        //String name = skuName;
65        //String expected = v2;
66        String name = "三星Samsung Galaxy S25+ 超拟人AI助理 骁龙8至尊版 AI拍照 翻译手机 游戏手机 12GB+256GB 冷川蓝";
67        String expected = name;
68
69        //String name = keyWords;
70        //String expected = v1;
71
72        int cnt = 1;
73        System.out.println("替换：" + name);
74        Replacer replacer = new StrReplacer(keyWords);
75        check(replacer, name, expected);
76        for (int i = 0; i < cnt; i++) {
77            checkExec(replacer, name);
78        }
79
80
81        replacer = new PatternReplacer(keyWords);
82        check(replacer, name, expected);
83        for (int i = 0; i < cnt; i++) {
84            checkExec(replacer, name);
85        }
86
87        replacer = new TrieKeywordReplacer(keyWords);
88        check(replacer, name, expected);
89        for (int i = 0; i < cnt; i++) {
90            checkExec(replacer, name);
91        }
92
93        replacer = new AhoCorasickReplacer(keyWords);
94        check(replacer, name, expected);
95        for (int i = 0; i < cnt; i++) {
96            checkExec(replacer, name);
97        }
98
99
100
101    }
102
103    @Test
104    public void 有1个关键字替换() throws InterruptedException {
105        //String name = skuName;
106        //String expected = v2;
107        //String name = "三星Samsung Galaxy S25+ 超拟人AI助理 骁龙8至尊版 AI拍照 翻译手机 游戏手机 12GB+256GB 冷川蓝";
108        //String expected = name;
109
110        //String name = keyWords;
111        //String expected = v1;
112
113        String name = "HUAWEI Pura 70 Pro 国家补贴500元 羽砂黑 12GB+512GB 超高速风驰闪拍 华为鸿蒙智能手机";
114        String expected = "HUAWEI Pura 70 Pro 500元 羽砂黑 12GB+512GB 超高速风驰闪拍 华为鸿蒙智能手机";
115
116        int cnt = 1;
117        System.out.println("替换：" + name);
118        Replacer replacer = new StrReplacer(keyWords);
119        check(replacer, name, expected);
120        for (int i = 0; i < cnt; i++) {
121            checkExec(replacer, name);
122        }
123
124
125        replacer = new PatternReplacer(keyWords);
126        check(replacer, name, expected);
127        for (int i = 0; i < cnt; i++) {
128            checkExec(replacer, name);
129        }
130
131        replacer = new TrieKeywordReplacer(keyWords);
132        check(replacer, name, expected);
133        for (int i = 0; i < cnt; i++) {
134            checkExec(replacer, name);
135        }
136
137        replacer = new AhoCorasickReplacer(keyWords);
138        check(replacer, name, expected);
139        for (int i = 0; i < cnt; i++) {
140            checkExec(replacer, name);
141        }
142
143
144
145    }
146
147
148    static void check(Replacer replacer, String name, String expected) {
149        System.out.println(replacer.getClass().getName()+"，对象大小："+ObjectSizeCalculator.getObjectSize(replacer));
150        String newTxt = replacer.replaceKeywords(name);
151        //System.out.println(newTxt);
152        Assert.assertEquals(replacer.getClass().getName() + ",对比不一致!", expected, newTxt);
153    }
154
155
156    void checkExec(Replacer replacer, String name) {
157        String newTxt = replacer.replaceKeywords(name);
158        int nThreads  = 2;
159        ExecutorService executorService = Executors.newFixedThreadPool(nThreads);
160        CountDownLatch downLatch = new CountDownLatch(nThreads);
161        int i = 0;
162        while (i++ < nThreads) {
163            executorService.submit(new Runnable() {
164                @Override
165                public void run() {
166                    int i = 0;
167                    long ns = System.nanoTime();
168                    while (i++ < 100000) {
169                        replacer.replaceKeywords(name);
170                    }
171                    String name = replacer.getClass().getName();
172                    downLatch.countDown();
173                    System.out.println(StringUtils.substring(name, name.length() - 50, name.length()) + "\ti=" + i + ", \t耗时：" + (System.nanoTime() - ns) / i + "ns");
174                }
175            });
176        }
177        executorService.shutdown();
178        try {
179            downLatch.await();
180        } catch (InterruptedException e) {
181            e.printStackTrace();
182        }
183    }

最后

1、使用现成的AhoCorasick算法进行实现，是性能与稳定性最优的选择，非常强调性能，还是可以自己实现Trie树来实现；

2、在真实的使用过程中，因为大部分的商品名称最多出现几个关键词，并且待替换的关键词往往都是比较多的，可以将这么关键词找出找出几个有代表性能的词，做前置判断，商品名称中是否存在；再进行全量替换；

如待替换的关键词有：政府补贴、国补、支持国补； 那么我们并不是直接就循环这个待替换的关键词组，而是找出这么关键词中都有的关键字”补”先判断商品名称中是否存在“补”字后，再做处理; 这里的前置判断，还可以使用布隆过滤器实现；

1
2public String replaceKeywords (String skuName){
3    Replacer replacer = new AhoCorasickReplacer(keyWords);
4    if(skuName.contains("补")){
5        return  replacer.replaceKeywords(skuName);
6    } else {
7        return skuName;
8    }
9}

参考

• [1] Aho-Corasick 算法 AC自动机实现

• [2] Trie字典树