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
v2zero
V2EX  ›  Python

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

  •  
  •   v2zero · 2021-07-15 17:01:16 +08:00 · 3595 次点击
    这是一个创建于 1225 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    需求背景是这样的:

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

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

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

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

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

    尝试过的其它方案有:

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

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

    25 条回复    2021-07-16 17:50:03 +08:00
    TimePPT
        1
    TimePPT  
       2021-07-15 17:08:17 +08:00
    Rush9999
        2
    Rush9999  
       2021-07-15 17:13:03 +08:00
    est
        3
    est  
       2021-07-15 17:13:31 +08:00
    > 或许瓶颈是在硬盘 IO 不是在 CPU 上面?

    也有可能在网络传输上。你还是把百万网页都做成一个大 txt 然后 grep 算了。
    guyueyiren
        4
    guyueyiren  
       2021-07-15 17:34:55 +08:00
    放到 linux 下用 grep 去正则匹配?
    wzq001
        5
    wzq001  
       2021-07-15 17:35:18 +08:00
    1 、将每个 HTML 格式压缩为一行,每行标记 html 路径 >> 到 big.txt
    2 、
    wzq001
        6
    wzq001  
       2021-07-15 17:36:06 +08:00
    1 、将每个 HTML 格式压缩为一行,每行标记 html 路径 >> 到 big.txt
    2 、grep 搞定

    赞同#3 观点
    GrayXu
        7
    GrayXu  
       2021-07-15 17:57:13 +08:00
    in 的速度不快吧。。可以用 grep 试试

    这个场景…mapreduce 启动!
    CSM
        8
    CSM  
       2021-07-15 18:31:20 +08:00 via Android   ❤️ 1
    用 ripgrep
    ClericPy
        9
    ClericPy  
       2021-07-15 18:39:08 +08:00
    本来以为在说 AC 自动机处理敏感词什么的, 点进来感觉又有点不一样...

    如果是冷数据, S3 + Hadoop 能搞不
    v2zero
        10
    v2zero  
    OP
       2021-07-15 18:43:37 +08:00
    @est 尝试了,10 万条数据匹配字符串用时 25 秒,每秒 4000 个,和原先几乎一样。
    MrGoooo
        11
    MrGoooo  
       2021-07-15 19:07:29 +08:00
    数据分组,多线程,甚至多主机(mapreduce)
    liuhan907
        12
    liuhan907  
       2021-07-15 20:53:02 +08:00 via Android
    查询是在线的,那数据源更新的频繁程度如何呢?
    est
        13
    est  
       2021-07-15 22:28:01 +08:00
    @v2zero LC_ALL=C grep XXX 1.txt 试试。
    est
        14
    est  
       2021-07-15 22:30:03 +08:00
    如果上面的 grep 也很慢,先用 xz 把 1.txt 用最大压缩比压缩了。然后 xzgrep
    akira
        15
    akira  
       2021-07-15 23:16:45 +08:00
    不需要芒果也不需要 ES,直接拆分成多个文本保存。然后你机器是几个核的,就开几个 PY 进程去跑, 分别输出就可以了

    假设平均一个页面的大小是 100kb,一百万个页面 总字符数量大约是 1 亿个, 100MB 左右吧
    1 亿个字符做 子字符串查询 的话,理论上 应该能在 1s 内完成
    xy90321
        16
    xy90321  
       2021-07-16 01:33:53 +08:00 via iPhone
    除非你每个网页里面每个词都独一无二,否则自然语言的话应该是拆词,然后根据词来作为索引储存 URL 。

    当然如果不是自然语言,或者不是单词查询的话,就得重新考虑策略了。
    xiadong1994
        17
    xiadong1994  
       2021-07-16 01:40:04 +08:00 via iPhone
    @akira 每个页面 100KB,1M 个文件,总共有 100GB……
    xiadong1994
        18
    xiadong1994  
       2021-07-16 01:40:47 +08:00 via iPhone
    mapreduce 好像就是干这种事情的
    wangxn
        19
    wangxn  
       2021-07-16 08:56:58 +08:00
    +1 。存成一个大文件然后直接 rigrep
    rigrep 匹配的速度基本就是 IO 的速度,没有别的更快的方法了
    假如需要多次查询,为什么不把结果保存下来?
    wangxn
        20
    wangxn  
       2021-07-16 08:59:41 +08:00
    更正:rigrep -> ripgrep
    nicolaz
        21
    nicolaz  
       2021-07-16 09:34:22 +08:00
    AC 自动机应该可以吧
    好处是如果你有 N 个关键词需要匹配的话,
    一次循环就能全部匹配出来
    而不需要每个词都跑一遍
    wangxn
        22
    wangxn  
       2021-07-16 09:34:48 +08:00 via Android
    认真想想,我上面的说法还是太 naive,肯定有高效的方法。不了解
    mainjzb
        23
    mainjzb  
       2021-07-16 10:37:09 +08:00
    为什么大多数的 C++ 的开源库都喜欢自己实现 string ? - 韦易笑的回答 - 知乎
    https://www.zhihu.com/question/54664311/answer/140494146
    love2020
        24
    love2020  
       2021-07-16 13:48:44 +08:00
    前缀树,一楼的 flashtext 。或者 AC 自动机。
    corningsun
        25
    corningsun  
       2021-07-16 17:50:03 +08:00
    @xy90321
    同意,先对文档做分词,应该是有上限的。
    ES 的倒排序索引很适合这个场景,分词方法需要根据你们需求定制。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5760 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 06:23 · PVG 14:23 · LAX 22:23 · JFK 01:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.