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

    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   121 天前
    预处理好。
    yrj
        2
    yrj   121 天前 via iPad
    全文检索?
    bestsanmao
        3
    bestsanmao   121 天前
    select 字段名 from 表名 where instr('你的句子', 字段名)<>0
    err1y
        4
    err1y   121 天前 via iPhone
    jieba 分词
    PhilC
        5
    PhilC   121 天前
    先分词呗
    hbolive
        6
    hbolive   121 天前
    上分词系统比较好,这么直接 mysql 查没搞过。。
    iblislsy
        7
    iblislsy   121 天前
    把 100w 个词组添加到 jieba 的分词 dict,python 分词完直接用 counter 统计。
    lithbitren
        8
    lithbitren   121 天前
    分词哈希,前缀树都可以,100W 个词读进内存也没多少,成熟的轮子也时一沓一沓的
    qiayue
        9
    qiayue   121 天前   ❤️ 2
    经典的倒排索引使用场景
    sadfQED2
        10
    sadfQED2   121 天前 via Android
    分词,上 es,mysql 或许不行吧? mysql 能改分词器吗
    zxcvsh
        11
    zxcvsh   121 天前 via iPhone
    试试 ES 吧,如果场景合适的话
    rockyou12
        12
    rockyou12   121 天前
    mysql 原生做不到
    ic2y
        13
    ic2y   121 天前
    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   120 天前
    先分词 再查询
    TimePPT
        15
    TimePPT   120 天前
    请求量大上 ES
    请求量不大,可以看看这个?
    《 FlashText:语料库数据快速清理利器》
    https://www.jiqizhixin.com/articles/2017-11-10-4
    wjhjd163
        16
    wjhjd163   120 天前 via Android
    同上,倒排索引
    直接查询还想要高速是肯定不可能的,这个结构还需要变化才行
    如果数据少那直接分词后搜索即可
    freelancher
        17
    freelancher   120 天前
    我的原始思路是先分词。然后第一个词,一个个字母去对。

    O 了。这个是算法题吧。应该有解的。
    oscer
        18
    oscer   120 天前
    ES
    lau52y
        19
    lau52y   120 天前 via iPhone
    es 最合适了吧
    RJH
        20
    RJH   120 天前
    何苦这样迫害 mysql 呢,人家原生就不是用来搞全文检索的,有 ES 不香吗?
    areless
        21
    areless   120 天前 via Android
    MySQL 估计做不到。。。在内存里搞一棵庞大的 trie 树,跟 ES 速度就差不多了。就是有点废内存~
    xcstream
        22
    xcstream   120 天前
    做一个键值对的表
    key | value
    yellow | yellow wall, yellow xxx,yellow xxxxxx

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

    方法就是怎么样
    用什么数据库还是内存 都可以
    gleport
        23
    gleport   120 天前
    适合用字典树来实现。把这 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   120 天前   ❤️ 2
    100 w 好像不多直接放内存,AC 自动机,速度应该不会慢
    rocky55
        25
    rocky55   120 天前
    100 w 前缀树的方式存储应该也不会太占内存,如果词不是很长,如果是英文应该就更省了
    iyangyuan
        26
    iyangyuan   120 天前 via iPhone
    分词,倒排
    xupefei
        27
    xupefei   120 天前 via iPhone
    Boyer-Moore algorithm
    xupefei
        28
    xupefei   120 天前 via iPhone
    @xupefei 多个关键字的话就用 Aho-Corasick algorithm
    chihiro2014
        29
    chihiro2014   120 天前
    倒排索引,Radix 之类的
    gladuo
        30
    gladuo   120 天前
    100w AC 自动机还可以,100-200M 空间
    wangyzj
        31
    wangyzj   120 天前
    mysql 全文检索不咋好使
    上 es 把
    ifsclimbing
        32
    ifsclimbing   115 天前
    e s
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2857 人在线   最高记录 5298   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 05:39 · PVG 13:39 · LAX 21:39 · JFK 00:39
    ♥ Do have faith in what you're doing.