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

请教大神, 字符串搜索算法这种情况下怎么办

  •  
  •   Kaakira ·
    kaakira · 2020-02-18 00:05:39 +08:00 · 2423 次点击
    这是一个创建于 1739 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用的 Boyre-Moore 算法

    现在遇到了一个问题

    后台数据返回的文本字符串会包含高亮关键字,这个关键字是数据自带的,非搜索关键字

    例如:

    界面显示是这样的: "你好世界"

    原数据是这样: "你好<em>世界</em>"

    在搜索关键词为"好世界"时, 因为 em 标签(高亮)的缘故, 导致无法正确匹配

    请问怎样修改算法, 能达到:

    输入"好世界"

    可以匹配到例如以下情况: 好<em>世界</em> 、好</em>世界 、 好世</em>界

    16 条回复    2020-02-19 16:16:34 +08:00
    Kaakira
        1
    Kaakira  
    OP
       2020-02-18 00:12:47 +08:00
    求助...
    Tomotoes
        2
    Tomotoes  
       2020-02-18 00:22:39 +08:00 via Android
    正则表达式啊。。
    AmosAlbert
        3
    AmosAlbert  
       2020-02-18 00:37:11 +08:00
    正则表达式
    felix021
        4
    felix021  
       2020-02-18 00:45:30 +08:00
    All problems in computer science can be solved by another level of indirection

    比如:match(filter_tags(input_string), pattern)
    Kaakira
        5
    Kaakira  
    OP
       2020-02-18 00:46:47 +08:00
    @felix021 还是比较看重性能的场景, 替换字符串,正则表达式都不太适用(之前就是正则表达式)
    Kaakira
        6
    Kaakira  
    OP
       2020-02-18 00:57:07 +08:00
    我想过把搜索关键词所有的可能性组合遍历 -> 算法搜索 -> 命中就结束。
    搜索 好世界 未命中 ↓

    搜索 好<em>世界 未命中 ↓

    搜索 好<em 世</em>界 命中了 √

    不过还是挺笨的
    gaobing
        7
    gaobing  
       2020-02-18 01:04:18 +08:00 via Android
    为文本生成去除标签的副本,对副本进行查找,就是比较浪费空间。
    enlight
        8
    enlight  
       2020-02-18 01:30:25 +08:00
    Kaakira
        9
    Kaakira  
    OP
       2020-02-18 02:23:37 +08:00
    @enlight 哎挺麻烦的,我们已经是用 elasticsearch 从大量数据里筛选出来的, 然后高亮了, 我要对这些筛选出来的数据 在进行搜索, 算了, 返回上一个版本(正则表达式)...
    laminux29
        10
    laminux29  
       2020-02-18 03:11:04 +08:00
    ......

    上面都答错了。

    你这哪里是什么搜索问题,而是一个简单的网页制作的问题(前端问题)。

    1.<em>是 html 的标签,当它出现在网页源代码里,它的功能是强调标签内的文字。

    2.你的搜索结果字符串里,包含了 html 标签,如果你把这个字符串,没做任何处理,直接放在前端网页里显示,搜索结果字符串里的<em>标签,就成了 html 网页源代码里的一部分,也就变成了强调功能,并且最终在显示出来的网页上面,也没有<em>这个子串。

    2.你现在要做的是,把搜索结果,先进行 html 转义。转义后,再放在前端网页上显示,它就不会成为 html 功能的一部分,而会成为前端网页上的一个完整的字符串。
    Kaakira
        11
    Kaakira  
    OP
       2020-02-18 09:17:46 +08:00
    @laminux29 我就是要子界面高亮显示 em, 不需要转义
    Kaakira
        12
    Kaakira  
    OP
       2020-02-18 09:18:17 +08:00
    @Kaakira
    @laminux29 我就是要在界面高亮显示 em, 不需要转义
    jmc891205
        13
    jmc891205  
       2020-02-18 13:02:16 +08:00
    只需要考虑<em>标签吗?还是所有 html 标签甚至非 html 标签的其他字符串都需要考虑?
    Kaakira
        14
    Kaakira  
    OP
       2020-02-18 14:21:05 +08:00
    @jmc891205 只考虑<em></em>标签
    jmc891205
        15
    jmc891205  
       2020-02-18 15:15:16 +08:00   ❤️ 1
    @Kaakira 那我想你在实现 BM 算法比较 pattern 和当前 string window 发现 mismatch 的时候,看一下当前字符是不是'>',如果是的话再去检查前面是不是<em>或</em>,如果是这两个标签就跳过去检查这两个标签前面的字符是不是 mismatch。另外还要再额外维护一个跳转表,因为现在有忽略的字符,pattern 和 string 的 index 不是通过简单自增可以一一对应的了。
    coderEOS
        16
    coderEOS  
       2020-02-19 16:16:34 +08:00
    1.去格式 2.正则 3.FlashText
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4802 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 09:44 · PVG 17:44 · LAX 01:44 · JFK 04:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.