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

算法:如何从一个大字符串中搜索一个子串,可以有一定的模糊度。

  •  
  •   James369 · 204 天前 · 2373 次点击
    这是一个创建于 204 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给定:
    一个大字符串(不超过 100 万个字符)和一个查询子串(不超过 20 个字符)。
    现在需要在这个大串中找到这些个子串,但可以设定匹配的模糊度:
    比如:
    当设定精确度为 100%时,则精确匹配这个子串。
    当设定精确度为 80%时,可以只匹配子串的 80%内容。

    好不好做?
    第 1 条附言  ·  204 天前
    其实本意是想找到一些相关联的子串,比如要找“路边有一条狗”,
    包括这些也能找到:“路边有一只狗”、“路边有一只小狗”、“路边有一只小花狗”、“路边蹲着一条狗”、“道路旁边有一只小狗”等等。

    但我不知道怎么处理这个,可能想想能不能用 正则表达式匹配,或者用一些同义词去识别,总之没有思路。
    djyde
        1
    djyde   204 天前
    还有一个前提条件需要确认:80%是指连续的 80%吗
    imn1
        2
    imn1   204 天前
    排列还是组合?就是有没有顺序要求?
    例如给出 abcde——
    1. bacde 算 100%还是 80%?
    2. eacdx 满足 80%么
    3. aacde 呢?就是出现的次数只算一次匹配还是多次匹配?
    ……

    你这个精确度的定义不同,影响很大
    算法楼下继续,非我所长,轮子我只会用,不会造,🐶
    ipwx
        3
    ipwx   204 天前
    如果只是针对一个查询串:带边界条件的 edit-distance 算法?复杂度大概是 O(MN) 感觉。。。( M=100 万,N=20 )

    如果针对很多很多查询串:把大字符串预先拆成重叠的 k-字符(比如 3 ),然后针对这些 k-字符建立倒排索引。然后用查询串的 k-字符去取出相关的索引,根据索引的先后位置和匹配次数你可以快速筛选出可能匹配的位置。最后针对这些位置做一次 edit-distance 最终确认。
    ipwx
        4
    ipwx   204 天前
    筛选这一步太麻烦了,楼下贤者可以补充。
    ipwx
        5
    ipwx   204 天前
    最后补充一句:因为倒排索引是根据位置排序的,多个倒排索引 + 不能超过 20 个字符误差范围这个条件能快速进行多路倒排索引的合并。合并过程可以用二分。。。总之是挺复杂的一个程序,但可以很快。
    ipwx
        6
    ipwx   204 天前
    …… 合并的过程不仅要用二分,可能还要用优先队列。优先队列是为了 O(1) 确定哪个倒排索引的下一个元素是最前面的,二分是为了跳过某个倒排索引因为太靠前了和别的倒排索引根本不可能相交的位置。
    James369
        7
    James369   204 天前
    @djyde 非连续,这种模糊确切说是一种意义上的相近。
    TimePPT
        8
    TimePPT   204 天前
    你这模糊程度定义完全不科学。
    「一定意义上的相近」如果是指语义相似度,就跟子串长度和字符没啥关系了。
    ericgui
        9
    ericgui   204 天前
    你这属于自然语言处理了,NLP is hard
    James369
        10
    James369   204 天前
    @ericgui 能不能用“正则表达式”来实现类似的效果呢,加上一些概率论的知识,分词,然后用同义词判断?
    LeeReamond
        11
    LeeReamond   204 天前   ❤️ 1
    感觉跟搜索引擎算法比较类似了,毕竟搜索引擎也可以抽象成标题是连续储存的字符串,通过搜索进行模糊定位,的一种业务。只不过当然现代搜索引擎处理的内容远比百万更长罢了。一个简单的 nlp 实现思路是,首先你需要对自己的字集进行 w2v,过程中可以有若干优化省略不表,在向量化以后每个向量就代表一个自然含义,且如果你的训练集合适,那么其自然含义有群聚性,比如 LZ 主题中的狗,小狗,小花狗,一条狗等等这些词会具有相近的向量位置。那么自然而然地近似一句话(可以解释为多个词向量的和),如果其自然语义接近,向量和落点肯定也是近似的,而后再进行准确+高效的位匹配就是储存层方面的工作。

    只是简述一下思路,当然这只是理想情况下,你实际做过就知道难度。
    dbsquirrel
        12
    dbsquirrel   204 天前 via iPhone
    jieba?
    4kingRAS
        13
    4kingRAS   204 天前
    这不就是搜索引擎吗,你用百度也没打正则表达式吧。不过我觉得倒也用不到 nlp,同 3 楼,编辑距离问题,https://zhuanlan.zhihu.com/p/80682302 总之就是得到一个相似性得分,按得分排序。
    7075
        14
    7075   204 天前
    用词向量试试
    ipwx
        15
    ipwx   204 天前
    那你的需求就是搜索引擎。。。直接找经典的信息检索教材就行。
    yolee599
        16
    yolee599   204 天前
    讲道理能做出来这个算法可以开公司卖算法了吧
    rrfeng
        17
    rrfeng   204 天前
    一般都是分词索引,分词查询的。
    longkas239
        18
    longkas239   204 天前
    现有工具的话,今天刚了解到 Elasticsearch 。设定同义词:一条狗=一只狗。 检索的时候用 match_phase 类型, 通过 slop 参数控制模糊程度。 可以试一下
    James369
        19
    James369   204 天前
    @yolee599 #16 确切说也不能算是算法,我觉得应该有现成的轮子解决这个问题。 毕竟这是个比较普遍的需求。LS 有几位 V 友给了些思路,我觉得可以进一步研究看看。
    hzder
        20
    hzder   204 天前
    ES
    zviacx
        21
    zviacx   204 天前
    在生物信息学中这个问题叫全局比对:给定短的基因链,在基因组上做有模糊的查找。

    这个挺多算法的,可以看看适不适合这个输入。
    sailgu
        22
    sailgu   204 天前
    @zviacx blast 就是干这个的了😂,毕业后搞了 2 年生物信息,果断跳坑。
    igoist
        23
    igoist   204 天前
    我抛砖引玉下吧,有兴趣的可以自己加参数去做精度的设置、优化:

    (() => {
    const fuzzyMatches = (fuzzy, text) => {
    fuzzy = fuzzy.toLowerCase();
    text = text.toLowerCase();

    let tp = 0; // text position / pointer
    let matches = [];

    // 这边随你去优化
    for (let i = 0; i < fuzzy.length; i++) {
    const f = fuzzy[i];

    for (; tp < text.length; tp++) {
    const t = text[tp];
    if (f === t) {
    matches.push(tp);
    tp++;
    break;
    }
    }
    }

    return matches;
    };

    // let r = fuzzyMatches('路边有一条狗', '路边有一只狗'); // r = [ 0, 1, 2, 3 ]
    // let r = fuzzyMatches('路边有一条狗', '路边有一只小狗'); // r = [ 0, 1, 2, 3 ]
    // let r = fuzzyMatches('路边有一条狗', '路边有一只小花狗'); // r = [ 0, 1, 2, 3 ]
    let r = fuzzyMatches('路边有一条狗', '道路旁边有一只小狗'); // r = [ 1, 3, 4, 5 ]

    console.log(r);
    })();
    iFlicker
        24
    iFlicker   204 天前
    楼上说的对 这属于 NLP 范畴了
    leven87
        25
    leven87   204 天前
    楼上说了很多,我来说下吧,这个不属于子字符串了。就是一个 NLP 的范畴,包括关键字提取,如你这个就是提取"路","旁边",“狗”。 或者句子主干提取吧,“路边有狗“。 然后你那个要查找的文章就是语料,也可以提取关键字或者句子主干吧。 然后两者做一个这样的查找,匹配,距离计算(各种框架算法)。看能不能匹配上?
    leven87
        26
    leven87   204 天前
    等待 NLP 高手解答,不过应该人家也没时间逛论坛。
    learningman
        27
    learningman   204 天前
    我帮你叫了个搞 NLP 的,不知道他来不来
    minilyn
        28
    minilyn   204 天前
    看楼主的本意如果是「想找到一些相关联的子串」,更像是需要做一个搜索引擎的基础功能。
    简化的描述一下业界常用的方案就是基于 ES,将候选集做实体识别 /打标签 /分词等,放入倒排索引中,然后将 input 字符串做同样的处理,然后就可以用 实体 /分词 /标签等信息去做 match 了,模糊度相关性等要求 可以在打分公式和过滤条件限制。 单纯的子字符串匹配是没办法很好的满足相关联的条件的,比如「路边有一条狗」和「有一个狗在路边」这种 pair 对
    rus4db
        29
    rus4db   204 天前
    提供一个参考概念:布隆过滤器( Bloom Filter )
    Arthur2e5
        30
    Arthur2e5   204 天前
    不走 NLP 处理的话就是字符串近似匹配。有几个不同版本的 agrep 都可以拿来看看,直接用的话推荐试试 TRE agrep 。
    kylejustknows
        31
    kylejustknows   203 天前
    1, 字符串扩大: 比如说你要 80% 准确率, 那么你搜索 8 个字的时候, 定义对比原文字符长度为 10 个.
    2, 快速过滤: 大段文字 10 个字一组, 如果这 10 个字里一个搜索字都没有或者只有一两个(小于一半), 迅速跳过.
    3, 精选结果. 当遇到一组(10 个)文字中有 4 个或更多字匹配, 则这一组 和其前后两组, 从第一个匹配字开始, 尝试更细致的分组. 最坏情况是分成了 10+10+10 组长度为 10 的文字, 这 30 串文字中, 任何一组匹配了超过 8*80%= 大概 6 个搜索字, 那么这一组这 10 个字, 从第一个匹配字到最后一个匹配字之间的那段话, 就是你想要的结果.
    Xs0ul
        32
    Xs0ul   203 天前
    在不用 NLP 的情况下,如果要搜“路边有一只狗”,那“路边有一条狗”和“路边有一只猫”与它的相似程度是一样的(按 edit-distance ), 因为都只差一个字。

    但是单单 NLP 并不能自动解决复杂度的问题。Embedding 只能提供更好的相似度估计,比如“只”和“条”相似度可能是 0.9,但“狗”和“猫”是 0.6,还是需要搜索引擎领域的知识。
    James369
        33
    James369   203 天前
    @igoist #23 你的这个 fuzzyMatches 操作不错,很好用。但我想问一下,能否返回匹配串在原始大串中的具体位置呢?
    igoist
        34
    igoist   203 天前
    @James369

    昨天其实没仔细审题,NPL 我也没研究过,大意了,好想撤回消息啊😂

    以查询短字串、匹配单个为例,前面的 fuzzyMatches 稍微改一下,调整下测试用例,可以有下面这样的结果:

    [ 15, 16, 17, 18 ] 路边有一

    [ 18, 19, 20 ] 边有一


    按照你的需求,还得判断结果区间能否接受,之后要确定具体位置,就是楼上说的,还需要有个 fNPL 去分别处理区间左右两侧内容,这是左侧:

    fNPL(index = 15, distance = n, originalText, dictionaryForLeft)

    fNPL(index = 18, distance = n + 1, originalText, dictionaryForLeft)

    右侧同理,你加油!/逃
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1770 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 87ms · UTC 16:44 · PVG 00:44 · LAX 08:44 · JFK 11:44
    ♥ Do have faith in what you're doing.