My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer. Here, "template" means the way any page presents its contents.
Any shopping website have page of any Shoes, that contains,
Images in the left. Price and Size in the right. Reviews in the bottom.
I think that this algorithm requires some optimization, that's why I am posting this question in this forum.
- Fetch, parse two input URLS and make their DOM trees.
- Then if any page contains , UL and TABLE , then remove that tag. I done this because, may be two pages contains different number of items.
- Then, I count number of tags in both URLS. say, initial_tag1, initial_tag2.
- Then, I start removing tags that have same position on corresponding pages and same Id and their below subtree, if that tree has number of nodes less than 10.
- Then, I start removing tags that have same position on coresponding pages and same Class name and their below subtree, if that tree has number of nodes less than 10..
- Then, I start removing tags that have no Id ,and No Class name and their below subtree, if that tree has number of nodes less than 10.
- Steps 4, 5, 6 have (N*N) complexity. Here, N, is number of tags. [In this way, in every step DOM tree going to shrink]
- When it comes out from this recursion, then I check final_tag1 and final_tag2.
- If final_tag1 and final_tag2 is less than initial_tag1*(0.2) and initial_tag2*(0.2) then I can say that
Two URL matched, otherwise
I wrote my code in Java using Jsoup and Selenium. I asked before on Stack Overflow, but the answers did not help me.
I think a lot about this algorithm, and I found that removing node from DOM tree is pretty slow process. This may be the culprit for slowing this algorithm.
I discussed with some geeks, and
they said that use a score for every tag instead of removing them, and add them , and at the end return (score I Got)/(accumulatedPoints) or something similar, and on the basis of that you decide two websites are either similar or not.
But I didn't understand this. So can you explain this statement, or can you give any other algorithm that solves this problem efficiently?