1

編集済み、もう一度お読みください。私の作品をいくつか追加しました

私の仕事は、2 つの URL のテンプレートを比較することです。アルゴリズムの準備が整いました。しかし、最終的な答えを出すには時間がかかりすぎます。

JsoupとSeleniumを使用してJavaでコードを作成しました

ここで、テンプレートとは、ページがコンテンツを表示する方法を意味します。

例：-

どのショッピングサイトにも、靴のページがあり、

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

2 つの URL が特定の製品のものである場合、「両方とも同じテンプレートからのものです」が返されます。例 、このリンクとこのリンクは同じテンプレートを持っています。

ある URL が製品を示し、別の URL がカテゴリを示している場合、「一致なし」と表示されます。例、このリンクとこのリンクは別のテンプレートからのものです。

このアルゴリズムには最適化が必要だと思うので、この質問をこのフォーラムに投稿しています。

私のアルゴリズム

  1. 2 つの入力 URL を取得して解析し、それらのDOM ツリーを作成します。
  2. 次に、ページに 、 UL 、および TABLE が含まれている場合は、そのタグを削除します。2つのページに異なる数のアイテムが含まれている可能性があるため、これを行いました。
  3. 次に、両方の URL のタグの数をカウントします。たとえば、initial_tag1、initial_tag2 とします。
  4. 次に、ツリーのノード数が 10 未満の場合、対応するページで同じ位置にあり、同じ ID とその下のサブツリーを持つタグの削除を開始します。
  5. 次に、ツリーのノード数が 10 未満の場合、対応するページで同じ位置にあり、同じクラス名とそのサブツリーの下にあるタグの削除を開始します。
  6. 次に、ツリーのノード数が 10 未満の場合、ID がなく、クラス名がなく、サブツリーの下にあるタグの削除を開始します。
  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 matchednot

このアルゴリズムについてよく考えてみたところ、DOM ツリーからノードを削除するプロセスはかなり遅いことがわかりました。これが、このアルゴリズムを遅くする原因になっている可能性があります。

私は何人かのオタクから議論しました、そして

彼らは、タグを削除する代わりにすべてのタグにスコアを使用し、それらを追加し、> 最後に (score I Got)/(accumulatedPoints) または同様のものを返すと述べ、それに基づいて、2 つの URL が類似していると判断します。か否か。

しかし、私はこれを理解していませんでした。では、この問題を効率的に解決する、オタクのこのことわざを説明できますか、または他の最適化されたアルゴリズムを教えてください。

前もって感謝します。あなたの親切な対応を求めています。

4

2 に答える 2

2

Web ページを比較するには、基本的に高速と低速の 2 つの方法があります。

  1. URL の比較: 高速
  2. DOM の比較: 遅い (そして複雑)

あなたの場合、最初の 2 つの項目は同様の正規表現に一致し、カテゴリは別の正規表現に一致するようです。

ここに短い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

最初の 2 つの URL がアイテムとして検証され、最後の 2 つの URL がカテゴリとして検証されます。

それがあなたの要件に合っていることを願っています。自由にJSに適応させてください。

于 2013-03-31T09:09:55.900 に答える
1

アルゴリズムの複雑さを改善するには、Jsoup を使用していると仮定して、データ構造をアルゴリズムに適合させる必要があります。

4) タグの位置とはどういう意味ですか? タグの Xpath ? はいの場合、タグ O(n) ごとにこの値を 1 回事前計算し、この値を各ノードに格納します。必要に応じて、HashMap に格納して O(1) で取得することもできます。

5) MultiMap を使用して、クラス名でタグ付けしたインデックスを作成します。多くの計算を節約できます

6) Id もクラス名もないインデックス クラス

これらすべての事前計算は、ツリーの 1 回の走査で実行できるため、O(n) になります。

一般に、計算を減らしたい場合は、より多くのデータをメモリに格納する必要があります。DOM ページは非常に小さなデータなので、これは問題ありません。

于 2013-03-31T13:09:59.903 に答える