algorithm - 与某种模式匹配的快速文件系统路径(但没有通配符)

Question

假设一组(Unix)路径，例如

/usr
/lib
/var/log
/home/myname/somedir
....

给定一个路径 /some/path，我想测试这个 /some/path 是否匹配上面设置的路径中的任何一个，并且通过“匹配"，我的意思是

1. /some/path 正好是上面的路径之一，或者
2. 它是上述路径之一的子路径。

我知道我可以通过 / 拆分路径并逐个进行字符串匹配，但我想非常快地执行此操作，可能通过使用一些哈希技术或类似的东西，以便我可以转换那些字符串匹配到一些整数匹配。

有什么算法吗？或者，是否有任何证据表明它没有？

Answer 1

哈希表方法

由于路径通常不是很深，您可能有能力存储所有可能的匹配子路径。

对于输入集中的每个路径，将其每个子路径添加到哈希表中。例如，这个集合:

/usr
/lib
/var/log
/home/myname/somedir

将生成此表:

hash0 -> /usr
hash1 -> /lib
hash2 -> /var
hash3 -> /var/log
hash4 -> /home
hash5 -> /home/myname
hash6 -> /home/myname/somedir

现在搜索查询归结为在此哈希表中查找完全匹配项。只有在哈希冲突的情况下才需要进行字符串比较。

此方法的一个主要缺点是，在一般情况下，它需要超线性内存量(相对于输入集的大小)。

考虑一个 600 个字符长的路径:

[400characterlongprefix]/a/a/a/...[100 times].../a/a/a/

以及对应的总共包含50500个字符的表格:

hash0   -> [400characterlongprefix]
hash1   -> [400characterlongprefix]/a
hash2   -> [400characterlongprefix]/a/a
...
hash100 -> [400characterlongprefix]/a/a/a/...[100 times].../a/a/a/

特里树方法

预计算步骤

1. 将集合中的每条路径拆分为其组件。
2. 为每个不同的组件分配一个索引，并将该对(组件、索引)添加到哈希表中。
3. 对于每条路径，将其组件索引的序列添加到 prefix tree 中.

示例

输入集:

/usr
/var/log
/home/log/usr

组件索引:

usr  -> 0
var  -> 1
log  -> 2
home -> 3

前缀树:

0            // usr
1 -> 2       // var, log
3 -> 2 -> 0  // home, log, usr

搜索查询

1. 拆分其组件的路径。
2. 对于每个组件，在哈希表中找到它的索引。
3. 如果其中一个组件没有相应的索引，则报告不匹配。
4. 在前缀树中搜索组件索引序列。