我正在寻找一种支持将字符串与一组模式匹配的数据结构，其中字符串表示 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/