gpt4 book ai didi

string - 由单词和分隔符组成的分层字符串的近似字符串匹配

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:19:48 24 4
gpt4 key购买 nike

我正在寻找一种支持将字符串与一组模式匹配的数据结构,其中字符串表示 mqtt topics .字符串被定义为由由斜线字符分隔的单词(“主题级别”)组成。字符串的示例是“topic1/topic2”或“//topic1/topic2”,其中包含一个空主题级别。字符集为 UTF-8,不包括 '#' 和 '+'。

模式是主题字符串,但可以包含两个通配符。第一个通配符“#”只能用在模式的末尾并匹配任意数量的后续主题,即“a/#”匹配任何以“a/”为前缀的字符串。第二个模式“+”匹配一个任意主题。例如,“sport/tennis/+”匹配“sport/tennis/player1”和“sport/tennis/player2”,但不匹配“sport/tennis/player1/ranking”。另外,由于单级通配符只匹配一个级别,“sport/+”不匹配“sport”,但匹配“sport/”。

用例是客户端注册提供模式的有趣主题。发送消息时,它会与主题字符串一起发布。该字符串必须与已注册的订阅者相匹配,因此我正在寻找一种数据结构,该数据结构可以有效地(在空间和时间方面)选择其注册模式与已发布主题相匹配的订阅者。

我正在考虑使用后缀树或 trie,因为这将允许在使用“#”时进行快速前缀匹配。 trie 中的节点将包含此字符串的订阅者,以及一组子字符串的所有订阅者。这应该允许快速查找精确查询和前缀查询,但我不知道这是否支持“+”通配符。

我正在考虑的另一种方法是创建一个有向图,其中每个节点包含一个主题和一条边 topic1 -> topic2 如果模式中有子字符串“topic1/topic2” .使用此图,我可以按主题遍历节点主题。 “+”通配符只意味着遍历所有 child 。

一个明显的替代方案是正则表达式,它会产生一个可能类似于图形方法的有限状态机。但是,我希望能更快地找到一些东西。

该算法应在 mqtt 代理中使用,订阅者可以随时注册和注销主题,因此它还必须支持通过添加或删除模式来更新搜索数据结构。

最佳答案

Aho-corasick 有限状态机支持通配符。您还可以反转 trie 并搜索通配符:http://phpir.com/tries-and-wildcards/

关于string - 由单词和分隔符组成的分层字符串的近似字符串匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35334271/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com