# Optimized algorithm to compare templates of two websites

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.

Example:

Any shopping website have page of any Shoes, that contains,

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


If two websites are of any specific product, then it returns "Both are from same templates". Example, this link and this link have the same template.

If one website shows any product and another website shows any category, then it shows "No match". Example, this link and this link are from different template.

I think that this algorithm requires some optimization, that's why I am posting this question in this forum.

My algorithm

1. Fetch, parse two input URLS and make their DOM trees.
2. 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.
3. Then, I count number of tags in both URLS. say, initial_tag1, initial_tag2.
4. 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.
5. 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..
6. 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.
7. 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]
8. When it comes out from this recursion, then I check final_tag1 and final_tag2.
9. 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 not.

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?

• I think SO is better for this question.
– avi
Apr 7 '13 at 10:32
• It is just that this isn't an algorithm question, but a request to write a (quite substantial) program. If you have a precise, specific problem that somebody might know how to solve simply there is a chance you'll get an answer. Nobody is going to sit down a day or so just to answer a question like yours. Apr 7 '13 at 11:48
• @vonbrand Ohk, Can you please this part 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. So that I can try to implement this. Apr 7 '13 at 12:11
• You have a big problem here: your algorithm seems to be very ad-hoc. Specify outside of any algorithm but as formally and precisely as possible what it means for two websites to be "similar". In essence, you are comparing strings, and there are many string metrics. On a pragmatic note, it may be useful for you to consider only tags up to a certain nesting depth.
– Raphael
Apr 7 '13 at 13:17

Reading between the lines, here is what I propose. I assume that you are interested in the structure of websites, so the first step is to expose this structure.

1. Throw away all non-structure tags as well as attributes (maybe keep class) and text. I imagine we would be left with <div>, <table>, <ul>/<ol>¹, HTML5 structure tags and little else, depending on coding style.
For the sake of efficiency, use a SAX-style parser for this step.
2. Create a tree of the remaining tags, either directly or in a second run. The structure of this tree should hold the information you want. You may want to cut everything that is nested deeper than some level; the overall structure of some website is likely to be clear from the first five to ten levels.
3. Compare the trees. What is useful here depends heavily on the kind of similarity you want and on the degree of sophistication the used websites display.

Equality of trees would be simplest measure but also coarse. There has been work on tree similarity measures, see e.g. here. Some research may unearth a measure that suits your purpose.

Finetuning the steps will require experiments and will most likely depend on the class of websites you compare.

1. You say you remove lists and tables because the may contain different numbers of elements. While that is true, the action is overcompensating since the occurrence of a list or table can be significant. Instead, remove all contained tags but keep the main ones. But then again, maybe the templates differ in the amount of columns in some table?
• Help me I have one doubt, If I remove position calculation part, and I say if two tags have same id and same class name, then both must be at same position in theri respective pages. Is it assumption is correct or not ? Apr 8 '13 at 11:03
• @devsda Since it is easy to write two chunks of HTML violating that property, no. In any case, such considerations are concerning the specifics of web programming, not the science part.
– Raphael
Apr 8 '13 at 14:36
• If I say, I have two pages of any product , let us suppose two books, from Amazon., then in this case my above said assumption will true or not ? Apr 8 '13 at 17:29
• I don't know, look at dumps of those sites. In terms of computer science, questions such as these are pointless: the answer completely depends on the application context.
– Raphael
Apr 8 '13 at 17:53
• Ohk, I am just expecting some mathematical proof from your side, that answers my question. Apr 8 '13 at 18:18