URL路径相似性/字符串相似性算法

Question

我的问题是需要比较URL路径并判断它们是否相似。下面提供了要处理的示例数据：

# GROUP 1
/robots.txt

# GROUP 2
/bot.html

# GROUP 3
/phpMyAdmin-2.5.6-rc1/scripts/setup.php
/phpMyAdmin-2.5.6-rc2/scripts/setup.php
/phpMyAdmin-2.5.6/scripts/setup.php
/phpMyAdmin-2.5.7-pl1/scripts/setup.php
/phpMyAdmin-2.5.7/scripts/setup.php
/phpMyAdmin-2.6.0-alpha/scripts/setup.php
/phpMyAdmin-2.6.0-alpha2/scripts/setup.php

# GROUP 4
//phpMyAdmin/

我尝试使用Levenshtein距离进行比较，但对我来说不够准确。我不需要100%准确的算法，但我认为必须达到90%及以上。

我认为我需要某种分类器，但问题是每个新数据部分都可能包含应该归类到新未知类别的路径。

请问您可以指引我正确的方向吗？

谢谢。

- lbednaszynski

---

所以，基本上，您有一组URL，并且想将其分成不相交的集合（进行聚类），或者更准确地说，您的任务是什么？我猜测，类的数量也不是预先知道的，对吧？ - jakub.g

离散的 -> 不相交 - jakub.g

是的，你说得对，我的任务有点像聚类。问题在于数据一直在不断地到来，所以算法应该适应新数据——类别数量可能会增加。这个任务是预处理数据，以便在下一步中使用它们。我想要实现的是获取被请求的应用程序/脚本的知识，对我来说，无论是phpMyAdmin版本2.5.6还是2.6.0都没有区别——我需要知道请求了phpMyAdmin setup.php脚本。我希望这可以帮助你理解我的问题。 - lbednaszynski

Answer 1

Levenshtein距离是最好的选择，但需要调整距离。您必须使用加权编辑距离，并可能在标记（单词和数字）上拆分路径。因此，例如版本号“2.5.6-rc2和2.5.6”可以视为0权重差异，但像phpMyAdmin和javaMyAdmin这样的名称标记则会产生1个权重差异。

- yura

Answer 2

在检查@jakub.gieryluk的建议时，我意外地找到了一个能够满足我的解决方案 - “Hobohm聚类算法，最初设计用于减少生物序列数据集的冗余。”

Bruno Vecchi实施的PERL库测试给了我真正好的结果。唯一的问题是我需要Python的实现，但我相信我可以在互联网上找到或重新实现代码。

下一件事是我还没有检查这个算法的主动学习能力；)

- lbednaszynski

---

这正是我正在寻找的东西。你在这方面有进展吗？ - Unitech

也许这个可以帮到你 --> https://dev59.com/zFgQ5IYBdhLWcg3wym-n#67293055 （nodejs） - Wahsei

Answer 3

我知道这不是你问题的确切答案，但你是否熟悉k-means算法？

我想即使Levenshtein在这里也可以工作，但困难在于如何使用该方法计算质心。

也许您可以将输入集分成不相交的子集，然后对每个子集中的每个URL计算与同一子集中所有其他URL的距离，具有最低距离总和的URL应该是质心（当然，这取决于输入集的大小；对于巨大的集合来说，这可能不是一个好主意）。

k-means的好处是您可以从绝对随机的分割开始，然后逐步改进。

k-means的坏处是您必须在开始之前确定k。但是，在运行过程中（也许是在第一次迭代后情况稳定下来时），您可以测量每个集合的内部相似性，如果它很低，您可以将集合分成两个子集并继续使用相同的算法。

- jakub.g