优化算法来比较两个URL的模板

编辑，请再读一遍，因为我添加了一些我的工作

我的任务是比较两个URL的模板。 我准备好了我的算法。 但是需要花费太多时间才能给出最终答案。

我使用Jsoup和Selenium在Java中编写了我的代码

这里， 模板表示任何页面呈现其内容的方式。

例：-

任何购物网站都有任何鞋子的页面，包含，

Images in the left. Price and Size in the right. Reviews in the bottom. 

如果两个URL是任何特定产品，则返回“两者都来自相同模板”。 例如， 此链接和此链接具有相同的模板。

如果一个URL显示任何产品而另一个URL显示任何类别，则显示“不匹配”。 例如， 此链接和此链接来自不同的模板。

我认为这个算法需要一些优化，这就是我在这个论坛中发布这个问题的原因。

我的算法

1. 获取，解析两个输入URL并制作他们的DOM树 。
2. 然后，如果任何页面包含UL和TABLE，则删除该标记。 我这样做是因为，可能是两个页面包含不同数量的项目。
3. 然后，我计算两个URL中的标签数量。 比如，initial_tag1，initial_tag2。
4. 然后，我开始删除在相应页面上具有相同位置的标签以及相同的Id及其下面的子树，如果该树的节点数小于10。
5. 然后，我开始删除在相应页面上具有相同位置的标记以及相同的类名称及其下面的子树，如果该树的节点数小于10。
6. 然后，如果该树的节点数小于10，我开始删除没有Id，No Class名称及其下面子树的标签。
7. 步骤4,5,6具有（N * N）复杂度。 这里，N是标签的数量。 [这样，在每一步DOM树都会收缩]
8. 当它从这个递归出来时，我检查final_tag1和final_tag2。
9. 如果final_tag1和final_tag2小于initial_tag1 *（0.2）和initial_tag2 *（0.2）那么我可以说Two URL matched ，否则not Two URL matched 。

我想了很多关于这个算法，我发现从DOM树中删除节点是一个非常缓慢的过程。 这可能是减慢此算法的罪魁祸首。

我从一些极客那里讨论过，并且

他们说使用每个标签的分数而不是删除它们，并添加它们，并在最后返回（得分）/（累积积分）或类似的东西，并在此基础上你决定两个URL是相似的或不。

但我不明白这一点。 所以你能解释一下这个极客的说法吗，或者你能否给出任何其他优化的算法来有效地解决这个问题。

提前致谢。 寻找你的回应。

Answer 1

为了提高算法的复杂性，假设您使用的是Jsoup，则必须使数据结构适应您的算法。

4）标签的位置是什么意思？ 标签的Xpath？ 如果是，则为每个标记O（n）预先计算一次该值，并将该值存储在每个节点中。 如果需要，您还可以将其存储在HashMap中以在O（1）中检索。

5）使用MultiMap按类名索引标记。 你将节省大量的计算

6）索引类没有Id，没有类名

所有这些预计算都可以在树的一次遍历中执行，因此O（n）。

通常，如果要减少计算，则必须在内存中存储更多数据。 由于DOM页面是非常小的数据，因此在您的情况下这没有问题。

Answer 2

为了比较网页，基本上有两种方式，快速和慢速：

1. 比较URLS：快
2. 比较DOM：慢（和复杂）

在您的情况下，前两个项似乎匹配类似的正则表达式，并且类别与另一个正则表达式匹配。

这是一个简短的JAVA解决方案

 import java.util.regex.Matcher; import java.util.regex.Pattern; public class TestRegexp { public static void main(String[] args) { String URL_ITEM_1 = "http://www.jabong.com/Puma-Flash-Ind-Black-Running-Shoes-187831.html"; String URL_ITEM_2 = "http://www.jabong.com/Lara-Karen-Full-Sleeve-Black-Polyester-Top-With-Cotton-Lace-196636.html"; String URL_CATEGORY_1 = "http://www.jabong.com/kids/shoes/floaters/"; String URL_CATEGORY_2 = "http://www.jabong.com/women/clothing/womens-tops/"; Pattern itemPattern = Pattern.compile("http://www\\.jabong.com/([\\w\\p{Punct}\\d]+)\\.html"); Pattern categoryPattern = Pattern.compile("http://www\\.jabong.com/([\\w\\p{Punct}]+/)+"); System.out.println("Matching items"); Matcher matcher = itemPattern.matcher(URL_ITEM_1); System.out.println(matcher.matches()); matcher = itemPattern.matcher(URL_ITEM_2); System.out.println(matcher.matches()); matcher = itemPattern.matcher(URL_CATEGORY_1); System.out.println(matcher.matches()); matcher = itemPattern.matcher(URL_CATEGORY_2); System.out.println(matcher.matches()); System.out.println("Matching categories"); Matcher category = categoryPattern.matcher(URL_ITEM_1); System.out.println(category.matches()); category = categoryPattern.matcher(URL_ITEM_2); System.out.println(category.matches()); category = categoryPattern.matcher(URL_CATEGORY_1); System.out.println(category.matches()); category = categoryPattern.matcher(URL_CATEGORY_2); System.out.println(category.matches()); } } 

并输出：

 Matching items true true false false Matching categories false false true true 

它将前两个第一个URLSvalidation为项目，最后两个作为类别。

我希望它符合您的要求。 随意适应JS。