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

问一个算法题目,如何求字符串集合中全部公共字串的情况

  •  
  •   iblislsy · 2018-11-27 19:31:36 +08:00 · 2051 次点击
    这是一个创建于 1948 天前的主题,其中的信息可能已经有所发展或是发生改变。

    场景:

    先把实际情况说一下,数据量在 9000w 行,每行都是“一个字符串+一个种类”,字符串长度平均在 1000 位左右

    1.字符串类似'abcdefg','aabbcc','aabcc',没有实际英语含义。

    2.每个字符串都有一个种类, 'dog','cat,'car', 一共 10 种种类。

    3.显然数据集的大小是 9000w 行 × 2 列 的 dataframe

    目标:

    1.想观察出同一个种类的字符串有没有共性,由于字符串没有实际的英语含义,所以我的初步想法是通过最长字串的匹配情况来计算相似度,总结出每个种类下字符串的规则。当新的字符串出现时,我能够通过之前的规则来分类。

    期望:

    1.不管是算法层面的,机器学习,深度学习,还是 es 这样引擎方面的,希望能和大家讨论讨论可行的方案

    2.子串的复杂度有点高...还没有好的思路,想了很久,自闭了。

    3.如果我没有表述清楚问题,请指出

    15 条回复    2018-11-28 12:11:13 +08:00
    akira
        1
    akira  
       2018-11-27 19:41:39 +08:00
    如果字符串是摘要算法产生的,那就有难度了....
    shylockhg
        2
    shylockhg  
       2018-11-27 20:54:40 +08:00
    字符串 hash 画分布图
    shylockhg
        3
    shylockhg  
       2018-11-27 21:06:08 +08:00
    映射到向量空间算距离
    pwrliang
        4
    pwrliang  
       2018-11-27 21:32:05 +08:00
    AC 自动机不就是解决多个串找字串的吗
    111qqz
        5
    111qqz  
       2018-11-27 21:34:22 +08:00
    目标部分没有看懂,按照题目来说,我理解的是,有一个字符串集合 S,然后求 S 中所有字符串的(最长)公共子串?
    iblislsy
        6
    iblislsy  
    OP
       2018-11-27 22:13:54 +08:00
    @111qqz 不是“最长”子串,是“全部”子串的情况,来总结特征
    leriou
        7
    leriou  
       2018-11-27 22:15:56 +08:00
    还是用空间向量计算相似度吧
    ytterbium
        8
    ytterbium  
       2018-11-27 22:15:58 +08:00 via Android
    先用最裸的 lstm 做下分类,要是分类正确率还是随机水平那就说明类别与字串无关
    iblislsy
        9
    iblislsy  
    OP
       2018-11-27 22:16:17 +08:00
    @111qqz 最长的子串是其中一种特征,我希望能找到更多的特征
    iblislsy
        10
    iblislsy  
    OP
       2018-11-27 22:17:23 +08:00
    @leriou 相似度能体现在 abcdefg 的这种字符串顺序上吗,我也不清楚
    leriou
        11
    leriou  
       2018-11-27 22:33:58 +08:00
    @iblislsy 跟顺序没关系, 空间向量是用文本在多个词维度上的夹角计算的, es 也是用这个来计算文档相似度的
    xiyiailoli
        12
    xiyiailoli  
       2018-11-27 22:47:46 +08:00 via Android
    kmp ?
    ccpp132
        13
    ccpp132  
       2018-11-28 05:59:16 +08:00 via Android
    先找一个较短的字符串,把它所有子串弄出来。然后拿这些串对剩下的字符串做多模匹配,统计每个子串出现的次数看是否等于总字符串数目
    iblislsy
        14
    iblislsy  
    OP
       2018-11-28 08:53:41 +08:00
    @leriou 我以前试过余弦距离去计算相似度,效果不好
    lihanfeifan
        15
    lihanfeifan  
       2018-11-28 12:11:13 +08:00
    有没有试过前缀树?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1538 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 17:03 · PVG 01:03 · LAX 10:03 · JFK 13:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.