一个可能有用的场景是REST Web服务.假设我已经提出了REST Web服务的公共接口的一些URL模式：
> / user / with-id / {userId}
> / user / with-id / {userId} / profile
> / user / with-id / {userId} /首选项
> / users
> / users / who-sign-up / on / {date}
/ / users / who-sign-up-between / {fromDate} /和/ {toDate}
> …
其中{…}被命名为占位符(如正则表达式捕获组).
Note: This question is not about whether the above REST interface is well-designed or not. (It probably isn’t,but that shouldn’t matter in the context of this question.)
可以假设占位符通常不会出现在模式的开头(但可以).还可以安全地假设任何字符串不可能匹配多个模式.
现在Web服务接收请求.当然,可以顺序匹配所请求的URI与一个URL模式,然后对下一个,依此类推;但是对于大量必须检查的模式,这可能不会很好地扩展.
有没有任何有效的算法呢？
输入：
>输入字符串
>一组“互斥”正则表达式(即没有输入字符串可能匹配多个表达式)
输出：
>输入字符串匹配的正则表达式(如果有).
支持正则表达式(即http://code.google.com/p/esmre/只是一个)的算法有不同之处,值得一看.
或者,您可以将块分割成块,将其组织在一棵树中,然后拆分网址以匹配一次一棵树. {userId}可以被认为是一个通配符,或者匹配一些特定格式(即为一个int).
当你到达一个叶子,你知道你匹配哪个url
