V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
fardream
V2EX  ›  程序员

大量短字符串模糊匹配用什么方法比较合适啊?

  •  
  •   fardream · 61 天前 · 2111 次点击
    这是一个创建于 61 天前的主题,其中的信息可能已经有所发展或是发生改变。

    想写一个和 everything 差不多的东西,目前试了用 mysql ,插了 130 万个文件名进去,引擎用 MyISAM ,ngram 索引,最短长度设置为 2 ,然后匹配".py",大概 48W 个结果,执行时间长达 5 秒。 有没有什么更加适合干这事的数据库或者方法。elastic search 这种特别重量级的就不考虑了。

    19 条回复    2024-05-20 12:15:25 +08:00
    securityCoding
        1
    securityCoding  
       61 天前 via Android
    速刷一下 leetcode 字符串匹配。。。
    foolishcrab
        2
    foolishcrab  
       61 天前 via iPhone
    你需要的是一个全文搜索引擎
    大部分语言都有轻量级实现
    比如 java 有个 lucene
    fardream
        3
    fardream  
    OP
       61 天前
    @securityCoding 我想要的是基于索引的...
    haiku
        4
    haiku  
       61 天前
    ES 的 Go/Rust 轻量级替代品,Meilisearch ZincSearch
    xupefei
        5
    xupefei  
       61 天前 via iPhone
    手写 AC 自动机😂
    henix
        6
    henix  
       60 天前
    手写后缀树
    netnr
        7
    netnr  
       60 天前 via Android
    duckdb
    tyrantZhao
        8
    tyrantZhao  
       60 天前
    手写 kmp 。。。qaq
    netnr
        9
    netnr  
       60 天前
    写了个示例

    创建表 files(id,name)
    插入 200 万数据,耗时:00:00:04.1143475
    查找 .py 结尾的文件共 368640 条,耗时:00:00:00.9355087

    jorneyr
        10
    jorneyr  
       60 天前
    Redis 有全文索引
    fugu37
        11
    fugu37  
       60 天前
    性能慢的不正常,查询有问题,可能没有走索引
    fardream
        12
    fardream  
    OP
       60 天前
    @fugu37 不建全文索引都没法调用 match 啊..
    ```
    SELECT id
    FROM files
    WHERE MATCH(name) AGAINST('".py"' IN BOOLEAN MODE)
    ;
    ```
    搜索 bpy apy 只有几百条,都能在 1s 内完成,cpy ,.py 都是十几万条,就掉到 3S 以上了
    fardream
        13
    fardream  
    OP
       60 天前
    emmmmm 把 ngram 索引换成普通的索引,查询时间变成了 700ms,想不懂为什么..........
    fugu37
        14
    fugu37  
       60 天前
    @fardream #12

    ".py" 中的 "." 有问题

    Fulltext index match string with period (.) mysql

    https://stackoverflow.com/questions/43319480/fulltext-index-match-string-with-period-mysql
    fardream
        15
    fardream  
    OP
       60 天前
    @fugu37 emmm 我搜索"pyc" / "py"也是一样的慢,完全无法理解为什么。我全部 select 到内存里,golang 直接暴力搜也才花了 98ms.....
    Gitmeeri
        16
    Gitmeeri  
       60 天前
    19 亿数据在 35s 内完成查询
    coder001
        17
    coder001  
       59 天前
    才 130 万,就算每个条目 1KB 也才 1.3GB ,完全可以全部载入再用循环去筛选,按照当下的处理器速度应该不会太慢🐶
    netabare
        18
    netabare  
       58 天前
    我也想知道这东西该怎么设计,想给自己 blog 做一个。随便搜一下满屏幕的 ES 、Redis 和布隆真是让人绷不住。

    我自己一开始的想法是 edit distance ,但这个数据集太大的话效率感人。

    跟人讨论的结论似乎是先建索引,也有查到倒排索引之类的东西,对我的使用场景应该足够,但如果有上百万条数据的话我不好说。
    mmdsun
        19
    mmdsun  
       58 天前 via iPhone
    Java 用 lucene ,不想用 es 的话
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1062 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 22:31 · PVG 06:31 · LAX 15:31 · JFK 18:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.