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 · 5173 次点击
    这是一个创建于 1569 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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   ·   实用小工具   ·   933 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 20:55 · PVG 04:55 · LAX 12:55 · JFK 15:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.