V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
? MySQL 5.5 Community Server
? MySQL 5.6 Community Server
? Percona Configuration Wizard
? XtraBackup 搭建主从复制
Great Sites on MySQL
? Percona
? MySQL Performance Blog
? Severalnines
推荐管理工具
? Sequel Pro
? phpMyAdmin
推荐书目
? MySQL Cookbook
MySQL 相关项目
? MariaDB
? Drizzle
参考文档
? http://mysql-python.sourceforge.net/MySQLdb.html
kisshere
V2EX  ?  MySQL

MySQL 存储了 100 万个词组,给出一字符串,怎样最快找出 100 万个词组中存在的词组?

  •  
  •   kisshere · 2020-08-06 11:10:04 +08:00 · 4850 次点击
    这是一个创建于 1330 天前的主题,其中的信息可能已经有所发展或是发生改变。

    腾讯云最新优惠活动来了:云产品限时1折,云服务器低至88元/年 ,点击这里立即抢购:9i0i.cn/qcloud,更有2860元代金券免费领取,付款直接抵现金用,点击这里立即领取:9i0i.cn/qcloudquan

    (福利推荐:你还在原价购买阿里云服务器?现在阿里云0.8折限时抢购活动来啦!4核8G企业云服务器仅2998元/3年,立即抢购>>>:9i0i.cn/aliyun

    MySQL 中存储的词组,比如:yellow wall,little cat,brown cat 、yellow dog 、coffee cup 之类的完全不同的词组总共 100W 行,现在给出一个句子,比如:“a little cat is sleeping behind a yellow wall with a yellow dog”,怎样以最快速度提取出这个 100W 词组中存在的词组:yellow wall,little cat 、yellow dog

    32 条回复  ?  2020-08-11 14:35:08 +08:00
    wangkun025
        1
    wangkun025  
       2020-08-06 11:11:34 +08:00
    预处理好。
    yrj
        2
    yrj  
       2020-08-06 11:18:10 +08:00 via iPad
    全文检索?
    bestsanmao
        3
    bestsanmao  
       2020-08-06 11:20:47 +08:00
    select 字段名 from 表名 where instr('你的句子', 字段名)<>0
    err1y
        4
    err1y  
       2020-08-06 11:24:44 +08:00 via iPhone
    jieba 分词
    PhilC
        5
    PhilC  
       2020-08-06 11:29:23 +08:00
    先分词呗
    hbolive
        6
    hbolive  
       2020-08-06 11:35:56 +08:00
    上分词系统比较好,这么直接 mysql 查没搞过。。
    iblislsy
        7
    iblislsy  
       2020-08-06 11:40:20 +08:00
    把 100w 个词组添加到 jieba 的分词 dict,python 分词完直接用 counter 统计。
    lithbitren
        8
    lithbitren  
       2020-08-06 11:51:52 +08:00
    分词哈希,前缀树都可以,100W 个词读进内存也没多少,成熟的轮子也时一沓一沓的
    qiayue
        9
    qiayue  
       2020-08-06 11:52:47 +08:00   ?? 2
    经典的倒排索引使用场景
    sadfQED2
        10
    sadfQED2  
       2020-08-06 12:15:51 +08:00 via Android
    分词,上 es,mysql 或许不行吧? mysql 能改分词器吗
    zxcvsh
        11
    zxcvsh  
       2020-08-06 12:49:48 +08:00 via iPhone
    试试 ES 吧,如果场景合适的话
    rockyou12
        12
    rockyou12  
       2020-08-06 12:56:19 +08:00
    mysql 原生做不到
    ic2y
        13
    ic2y  
       2020-08-06 13:22:06 +08:00
    100 万条词组,首先向量化,例如 yellow wall,可以标记为 [1,2] 1 表示 yellow,2 表示 wall

    以此类推,little cat,可以标记为 [1, 3] 3 表示 cat 。

    100 万条 向量化的词组,就是 100 万条 整形数组的序列,把这个序列变成 一个字典前缀树。

    Node{
    int value;
    Map<Interget,Node> childs;
    }

    这棵树,在 100 万的量级,应该不大。都是整形的。保存在内存中。

    遇到 a little cat is sleeping behind 就向量化,变成 23 45 18 1 4 之类的数字,

    从 23 开始,依次从字典前缀树的 root,开始匹配,是否能匹配到叶子节点。如果匹配到,就输出。

    否则,继续匹配 45 、18 等。
    leapV3
        14
    leapV3  
       2020-08-06 15:23:44 +08:00
    先分词 再查询
    TimePPT
        15
    TimePPT  
       2020-08-06 15:31:24 +08:00
    请求量大上 ES
    请求量不大,可以看看这个?
    《 FlashText:语料库数据快速清理利器》
    https://www.jiqizhixin.com/articles/2017-11-10-4
    wjhjd163
        16
    wjhjd163  
       2020-08-06 15:34:45 +08:00 via Android
    同上,倒排索引
    直接查询还想要高速是肯定不可能的,这个结构还需要变化才行
    如果数据少那直接分词后搜索即可
    freelancher
        17
    freelancher  
       2020-08-06 15:39:07 +08:00
    我的原始思路是先分词。然后第一个词,一个个字母去对。

    O 了。这个是算法题吧。应该有解的。
    oscer
        18
    oscer  
       2020-08-06 15:41:56 +08:00
    ES
    lau52y
        19
    lau52y  
       2020-08-06 16:52:45 +08:00 via iPhone
    es 最合适了吧
    RJH
        20
    RJH  
       2020-08-06 17:39:37 +08:00
    何苦这样迫害 mysql 呢,人家原生就不是用来搞全文检索的,有 ES 不香吗?
    areless
        21
    areless  
       2020-08-06 17:54:28 +08:00 via Android
    MySQL 估计做不到。。。在内存里搞一棵庞大的 trie 树,跟 ES 速度就差不多了。就是有点废内存~
    xcstream
        22
    xcstream  
       2020-08-06 18:01:32 +08:00
    做一个键值对的表
    key | value
    yellow | yellow wall, yellow xxx,yellow xxxxxx

    然后分成一个一个单词 看到 yellow 就去找这个表

    方法就是怎么样
    用什么数据库还是内存 都可以
    gleport
        23
    gleport  
       2020-08-06 18:19:25 +08:00
    适合用字典树来实现。把这 100 万个词组从 MySQL 读出存进一棵字典树里,不会消耗多大内存。

    一百多行左右的核心代码就可以完成了:

    ```go
    package main

    import (
    "fmt"

    "github.com/hmgle/trie-x/go/trie"
    )

    func main() {
    t := trie.New()
    t.Insert("yellow wall", 1)
    t.Insert("little cat", 1)
    t.Insert("brown cat", 1)
    t.Insert("yellow dog", 1)
    t.Insert("coffee cup", 1)

    content := "a little cat is sleeping behind a yellow wall with a yellow dog"
    hits := t.ScanContent(content)
    for _, hit := range hits {
    fmt.Printf("word: %s, offset: %d\n", hit.Word, hit.Offset)
    }
    }
    ```

    输出:

    ```
    word: little cat, offset: 2
    word: yellow wall, offset: 34
    word: yellow dog, offset: 53
    ```
    rocky55
        24
    rocky55  
       2020-08-06 18:41:39 +08:00   ?? 2
    100 w 好像不多直接放内存,AC 自动机,速度应该不会慢
    rocky55
        25
    rocky55  
       2020-08-06 18:43:41 +08:00
    100 w 前缀树的方式存储应该也不会太占内存,如果词不是很长,如果是英文应该就更省了
    iyangyuan
        26
    iyangyuan  
       2020-08-06 18:48:48 +08:00 via iPhone
    分词,倒排
    xupefei
        27
    xupefei  
       2020-08-06 19:22:58 +08:00 via iPhone
    Boyer-Moore algorithm
    xupefei
        28
    xupefei  
       2020-08-06 19:25:02 +08:00 via iPhone
    @xupefei 多个关键字的话就用 Aho-Corasick algorithm
    chihiro2014
        29
    chihiro2014  
       2020-08-06 22:11:22 +08:00
    倒排索引,Radix 之类的
    gladuo
        30
    gladuo  
       2020-08-06 22:20:04 +08:00
    100w AC 自动机还可以,100-200M 空间
    wangyzj
        31
    wangyzj  
       2020-08-07 13:24:05 +08:00
    mysql 全文检索不咋好使
    上 es 把
    ifsclimbing
        32
    ifsclimbing  
       2020-08-11 14:35:08 +08:00
    e s
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   995 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 19:52 · PVG 03:52 · LAX 12:52 · JFK 15:52
    Developed with CodeLauncher
    ? Do have faith in what you're doing.


    http://www.vxiaotou.com