如何在大量文本中高效的匹配出字符串？

V2EX = way to explore

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

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

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

我不是专业做技术的，因此会有很多技术盲区，碰到棘手问题也不知如何自行寻找解决方案，因此提问，感谢诸位。

需求背景是这样的：

在数百万的网页 html 源代码里面，寻找出包含某个特定字符串（或匹配某条正则）的网页，输出其 URL 信息。

由于是数据分析用途，需要很频繁的为了突发的需求而多次运行。

目前的解决方案是这样的：

数据存在 MongoDB 里面（ zstd 压缩），匹配的时候使用 Python 直接遍历出所有网页，再通过 Python 内置的方法（ in 条件或者 re ）来进行判断。

如果仅使用 in 条件，目前每秒平均能匹配 4000 多个网页，百万的网页全部运行一次需要十多分钟，比较费力。此外，已经配置了阿里云 ECS 的对应容量下可选的最高速度的 SSD 。

尝试过的其它方案有：

使用 ElasticSearch 来建立全文索引。但发现在占用了大量额外硬盘空间的代价下，需要全量导出匹配结果时候的效率仍然很低下，或许是 ES 仅在匹配 top n 结果的时候才是高效的？又或只是我哪里没做对？

也尝试过 MongoDB 取消压缩，发现速度变更慢了，或许瓶颈是在硬盘 IO 不是在 CPU 上面？

匹配

网页

Python

MongoDB

25 条回复 • 2021-07-16 17:50:03 +08:00

TimePPT

2021-07-15 17:08:17 +08:00

试试 flashtext ?
https://github.com/vi3k6i5/flashtext

Rush9999

2021-07-15 17:13:03 +08:00

es 全量导出用 scroll-api
https://www.elastic.co/guide/en/elasticsearch/reference/7.13/scroll-api.html

est

2021-07-15 17:13:31 +08:00

> 或许瓶颈是在硬盘 IO 不是在 CPU 上面？

也有可能在网络传输上。你还是把百万网页都做成一个大 txt 然后 grep 算了。

guyueyiren

2021-07-15 17:34:55 +08:00

放到 linux 下用 grep 去正则匹配？

wzq001

2021-07-15 17:35:18 +08:00

1 、将每个 HTML 格式压缩为一行，每行标记 html 路径 >> 到 big.txt
2 、

wzq001

2021-07-15 17:36:06 +08:00

1 、将每个 HTML 格式压缩为一行，每行标记 html 路径 >> 到 big.txt
2 、grep 搞定

赞同#3 观点

GrayXu

2021-07-15 17:57:13 +08:00

in 的速度不快吧。。可以用 grep 试试

这个场景…mapreduce 启动！

CSM

2021-07-15 18:31:20 +08:00 via Android

用 ripgrep

ClericPy

2021-07-15 18:39:08 +08:00

本来以为在说 AC 自动机处理敏感词什么的, 点进来感觉又有点不一样...

如果是冷数据, S3 + Hadoop 能搞不

v2zero

2021-07-15 18:43:37 +08:00

@est 尝试了，10 万条数据匹配字符串用时 25 秒，每秒 4000 个，和原先几乎一样。

MrGoooo

2021-07-15 19:07:29 +08:00

数据分组,多线程,甚至多主机(mapreduce)

liuhan907

2021-07-15 20:53:02 +08:00 via Android

查询是在线的，那数据源更新的频繁程度如何呢？

est

2021-07-15 22:28:01 +08:00

@v2zero LC_ALL=C grep XXX 1.txt 试试。

est

2021-07-15 22:30:03 +08:00

如果上面的 grep 也很慢，先用 xz 把 1.txt 用最大压缩比压缩了。然后 xzgrep

akira

2021-07-15 23:16:45 +08:00

不需要芒果也不需要 ES，直接拆分成多个文本保存。然后你机器是几个核的，就开几个 PY 进程去跑，分别输出就可以了

假设平均一个页面的大小是 100kb，一百万个页面总字符数量大约是 1 亿个, 100MB 左右吧
1 亿个字符做子字符串查询的话，理论上应该能在 1s 内完成

xy90321

2021-07-16 01:33:53 +08:00 via iPhone

除非你每个网页里面每个词都独一无二，否则自然语言的话应该是拆词，然后根据词来作为索引储存 URL 。

当然如果不是自然语言，或者不是单词查询的话，就得重新考虑策略了。

xiadong1994

2021-07-16 01:40:04 +08:00 via iPhone

@akira 每个页面 100KB，1M 个文件，总共有 100GB……

xiadong1994

2021-07-16 01:40:47 +08:00 via iPhone

mapreduce 好像就是干这种事情的

wangxn

2021-07-16 08:56:58 +08:00

+1 。存成一个大文件然后直接 rigrep
rigrep 匹配的速度基本就是 IO 的速度，没有别的更快的方法了
假如需要多次查询，为什么不把结果保存下来？

wangxn

2021-07-16 08:59:41 +08:00

更正：rigrep -> ripgrep

nicolaz

2021-07-16 09:34:22 +08:00

AC 自动机应该可以吧
好处是如果你有 N 个关键词需要匹配的话,
一次循环就能全部匹配出来
而不需要每个词都跑一遍

wangxn

2021-07-16 09:34:48 +08:00 via Android

认真想想，我上面的说法还是太 naive，肯定有高效的方法。不了解

mainjzb

2021-07-16 10:37:09 +08:00

为什么大多数的 C++ 的开源库都喜欢自己实现 string ？ - 韦易笑的回答 - 知乎
https://www.zhihu.com/question/54664311/answer/140494146

love2020

2021-07-16 13:48:44 +08:00

前缀树，一楼的 flashtext 。或者 AC 自动机。

corningsun

2021-07-16 17:50:03 +08:00

@xy90321
同意，先对文档做分词，应该是有上限的。
ES 的倒排序索引很适合这个场景，分词方法需要根据你们需求定制。