从示例列表生成简单的 URL 模式

Question

假设我有一个很大的 URL 列表，如下所示：

foo.com/abc/123
foo.com/abc/456
foo.com/abc/789
bar.com/11111/xyz
bar.com/22222/xyz
bar.com/33333/xyz
etc.

我想处理这个列表并生成非常简单的类似 glob 的模板 如果列表中存在 3 个或更多仅该路径段不同的 URL，则概括特定路径段。通用路径段被替换为通配符 (*)。

因此，对于上面的列表，我希望我的程序生成两个模板：

foo.com/abc/*
bar.com/*/xyz

请注意，通用路径段可以出现在 URL 中的任何位置。是否有一种有效的算法来生成此类模板？我不需要完整的正则表达式生成器。

Answer 1

这取决于您希望事情变得多么复杂。段替换非常简单。

让我们首先看看最简单的情况：常见前缀，如 foo.com 的示例。

让我稍微扩展一下你的例子：

foo.com/abc/123
foo.com/abc/456
foo.com/abc/789
foo.com/123/abc
foo.com/123/def
foo.com/123/ghi

我们要做的是构建一个层次结构（一棵树），其中 foo.com 位于顶部，还有两个子节点：abc 和 123。每个子节点都有三个子节点。所以你拥有的是：

foo.com
  abc
    123
    456
    789
  123
    abc
    def
    ghi
    

很容易编写一个递归程序，遍历这个结构来找到具有叶子节点的父节点，然后决定是否要制作模板。目前还不清楚你如何做出这个决定。也许你会说，如果一个节点有三个或更多子节点，你就为它创建一个模板。所以在这里你会有

foo.com/abc/*

和

foo.com/123/*

。

但你可能也有：

foo.com/abc/123/barby
foo.com/abc/123/fooby
foo.com/abc/123/foobidity

您可能需要额外的规则：

foo.com/abc/123/*

你可以很容易地根据公共子串找到这些公共序列。

您可以通过转换 URL 来扩展该方法。因此，以 bar.com 为例：

bar.com/11111/xyz
bar.com/22222/xyz
bar.com/33333/xyz

您将 URL 转换为：

bar.com/xyz/11111
bar.com/xyz/22222
bar.com/xyz/33333

然后再次经历层次结构构建过程。但在这里您要确保“xyz”的数量与第二段中的项目数量完全相同。例如，如果有第四个 URL

bar.com/4444/xyz

，您就不想生成模板

bar.com/*/xyz

。

如果您正在寻找基于段的替换模式，此技术很简单并且非常有效。如果每个 URL 的分段数量不是很大，则效率相当高。但是，如果您的网站具有超过六个层次结构级别，则可能会遇到其他问题。或不。这些站点通常已经具有可供您利用的整体结构。像 bigblogsite.com/user-name/section/year/month/day/title 这样的东西。

当您寻找两段替换时，尤其是当两个段不连续时，事情会变得更加困难。例如，试图找到

fooby.com/*/xyz/*/barby

。