Java 判断一个字符串中是否含有多个字符串效率最高的算法？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1706 天前的主题，其中的信息可能已经有所发展或是发生改变。

因为牵扯到海量数据，所以对效率还是比较敏感的。用 JAVA 自带的 Contains 嵌套感觉效率应该不太行吧，有没有大佬推荐下，最好有现成的轮子。

字符

Java

效率

contains

9 条回复 • 2020-03-23 20:06:44 +08:00

woodensail

2020-03-23 19:45:26 +08:00

你的需求是，搜索引擎？

NeinChn

2020-03-23 19:47:50 +08:00

不知道场景，不过大概也就那么几种解决方案，比如 Trie 之类的，模式匹配之类的。

ebony0319

2020-03-23 19:48:23 +08:00

不知道 Guava 集合类型-Multiset 不知道能不能满足你的要求

ysn2233

2020-03-23 19:52:21 +08:00

@woodensail 用 Spark/Flink 跑 TB 级的历史 RAW 数据，类似 grep 的操作找关键词

ysn2233

2020-03-23 20:00:00 +08:00

看到了 ahocorasick 算法这个不知道合不合适

watera

2020-03-23 20:00:02 +08:00 via Android

不是 AC 自动机吗

NeinChn

2020-03-23 20:03:06 +08:00

如果你是存在上亿输入，每一次一行一行在几十 /几百万候选集中进行匹配
那你就用 Trie/AC 自动机做
如果你就是一行一行找几个关键词，随便做，效率差不了多少。

ipwx

2020-03-23 20:04:57 +08:00

场景描述再清晰一点。。。
- - - -

比如你是不是要从一整个数据库一堆较长的字符串里面，找少数一些不怎么长的字符串是否出现？如是的话，这个场景的基本思路是预先对你数据库里面的字符串进行切片索引，然后你的查询字符串也切片，根据切片结果可以缩小查询范围。类似于全文检索，不过去掉了一些比如停用词或者分词之类的操作。

ipwx

2020-03-23 20:06:44 +08:00

好吧楼主是一个字符串里面找其他字符串。。。那我觉得其实也可以用上面这个思路改编，你把原始的字符串切段，然后用更小的切片（比如长度为 3 、为 5 ）进行索引。把查询字符串也切片，根据索引能缩小查询范围，大大加快查找速度