CN116484126A - List extraction and visualization in web pages - Google Patents

Abstract

The present disclosure provides methods, apparatus, and computer program products for list extraction and visualization in web pages. At least one anchor element group in the target webpage may be detected, the at least one anchor element group including the first anchor element group. Boundary detection may be performed on a plurality of anchor elements in the first anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to a first original list in the target webpage. Multiple sets of representative metadata corresponding to the multiple items respectively can be obtained from the target webpage by utilizing boundaries of the multiple items. The plurality of sets of representative metadata may be visualized as a structured list.

Description

List Extraction and Visualization in Web Pages

Background technique

There are a large number of web pages (web pages) in the network, and these web pages contain various information. In some scenarios, network users may need to find interesting webpages on the network in order to obtain desired information. Search engine providers can provide search services to assist users in finding web pages of interest. For example, in response to a search query from a user, the search service may return a search result page to the user, the search result page including information on web pages related to the search query, such as web page links, snippets, and the like.

Contents of the invention

This Summary is provided to introduce a set of concepts that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Embodiments of the present disclosure propose methods, apparatuses and computer program products for list extraction and visualization in web pages. At least one anchor element group in the target webpage may be detected, the at least one anchor element group including the first anchor element group. Boundary detection may be performed on multiple anchor elements in the first anchor element group to obtain boundaries of multiple items respectively associated with the multiple anchor elements, the multiple items corresponding to the first original list in the target web page. Multiple sets of representative metadata respectively corresponding to the multiple items may be obtained from the target webpage by using boundaries of the multiple items. The sets of representative metadata can be visualized as a structured list.

It should be noted that one or more of the above aspects include the features specified in the following detailed description as well as in the claims. Certain illustrative features of the one or more aspects are set forth in detail in the following description and accompanying drawings. These features are merely indicative of the various ways in which the principles of various aspects can be implemented and this disclosure is intended to include all such aspects and their equivalents.

Description of drawings

The disclosed aspects will be described below with reference to the accompanying drawings, which are provided to illustrate but not limit the disclosed aspects.

Figure 1 shows an exemplary listing web page.

Figure 2 shows an exemplary listing web page.

Fig. 3 shows an existing exemplary search result page.

Fig. 4 shows an exemplary process of list extraction and visualization in a web page according to an embodiment.

Fig. 5 shows an exemplary process of anchor point element group detection according to an embodiment.

Fig. 6 shows an exemplary set of anchor elements according to an embodiment.

Fig. 7 shows an exemplary process of boundary detection according to an embodiment.

8A-8F illustrate examples of iterative bounds extension according to an embodiment.

9A-9F illustrate examples of iterative bounds extension according to an embodiment.

Fig. 10 shows exemplary boundary detection results according to an embodiment.

FIG. 11 shows an exemplary process of master list determination according to an embodiment.

Fig. 12 shows an exemplary process of representative metadata acquisition according to an embodiment.

Figure 13 illustrates an exemplary search results page, according to an embodiment.

Fig. 14 shows a flow chart of an exemplary method for list extraction and visualization in a webpage, according to an embodiment.

Fig. 15 shows an exemplary apparatus for list extraction and visualization in a web page according to an embodiment.

Fig. 16 shows an exemplary apparatus for list extraction and visualization in a web page according to an embodiment.

Detailed ways

The present disclosure will now be discussed with reference to various exemplary embodiments. It should be understood that the discussion of these embodiments is only for enabling those skilled in the art to better understand and thus implement the embodiments of the present disclosure, rather than teaching any limitation to the scope of the present disclosure.

Existing search services usually extract specific text from the original web page to form a text summary, that is, a text summary, and display the text summary on the search result page, so that users can roughly understand the content involved in the original web page when seeing the text summary. There are a large number of list webpages on the Internet, wherein the list webpage may mean that the main content of the webpage is a list and the list includes multiple items (items). For such a list web page, existing search services still only extract specific text from the list web page to form a text summary, and the text in the text summary may only be extracted from a specific item in the list, for example, from the first item in the list. Therefore, when the user sees the text abstract in the search result page, he can only learn limited partial information about the listed webpage.

Embodiments of the present disclosure propose to perform list extraction and visualization in a web page, so as to extract list content from a target web page and organize the list content into a structured form. In this context, the landing page can be a listing page. Embodiments of the present disclosure may extract list content from the target webpage, and visualize at least a part of the extracted list content to form a summary in the form of a list, that is, a list summary. Compared with text summaries, list summaries can contain richer content about the original list in the target web page, so that users can learn more comprehensive information about the original list from the list summaries. Since the list summary itself is a structured list, the embodiments of the present disclosure can present information about the original list to the user in a more friendly and intuitive manner. Embodiments of the present disclosure can present key or representative information of items in the original list in the list summary, so that information that the user may expect can be comprehensively and concisely provided. When the list abstract is presented on the search result page, the user can conveniently and comprehensively learn the content of the corresponding target webpage without clicking on the webpage link.

The original lists in the target web page processed by the embodiments of the present disclosure are not limited to those lists with html list tags, but may cover any visually perceivable lists. The "original list" referred to in the embodiments of the present disclosure is a visually perceivable list. A visually perceptible list may mean, for example, that the list contains multiple items with a visually similar structure. Herein, an "item" may refer to a component constituting a list, which may also be called an object, an entity, a data record, or the like. A visually perceivable list may or may not have an html list tag, whereby a visually perceptible list may have any html tag without restriction. Embodiments of the present disclosure are proposed at least for target webpages including visually perceivable lists, and can process these target webpages at least from the perspective of visual perception, rather than simply using html list tags to process these target webpages. Accordingly, embodiments of the present disclosure can be applied to any target web page that includes a visual list.

In one aspect, the embodiments of the present disclosure can at least identify the original list that may be included in the target web page by detecting a group of anchor elements (anchorelelement) in the target web page. An anchor element in an anchor element group does not necessarily have an html list tag. Since anchor elements may have representative information of items in the original list, detection of groups of anchor elements will help to discover the original list in the target web page.

In one aspect, embodiments of the present disclosure may perform boundary detection on multiple anchor elements in an anchor element group to determine the boundaries of multiple items in the original list corresponding to the anchor element group in the target web page. In this context, determining the boundaries of a project may refer to determining which specific elements are included in the project, and accordingly these elements together form the project. Boundary detection may include iterative boundary extension. For each anchor element, elements that may be within the same item as the anchor element are found by iterative bounds expansion, so that the anchor element and the found elements define the bounds of the item. Boundary detection can also include similarity testing. A similarity check may be performed to determine whether items determined by extension from different anchor elements are indeed items in the same original list, eg whether the items do form an original list. At least through the boundary detection according to the embodiments of the present disclosure, the original list in the target web page and each item in the original list can be accurately identified.

In one aspect, if the target web page includes two or more original lists, embodiments of the present disclosure may determine the dominant list from these original lists. Herein, the main list may refer to, for example, a list occupying a main position in a web page, presenting main content, and the like. Preferably, by determining the master list and performing subsequent processing only on the master list, embodiments of the present disclosure can include only information about the master list in the finally generated structured list, thereby avoiding interference caused by information about lists that are not master lists.

In one aspect, embodiments of the present disclosure may obtain sets of representative metadata for different items in the original list from the target web page. For example, sets of representative metadata for items in the original list can be obtained from the target web page using at least the boundaries of the items. In some implementations, the plurality of sets of representative metadata may be important, representative metadata selected from initial metadata in the target webpage by sorting.

In one aspect, embodiments of the present disclosure can visualize the obtained sets of representative metadata to form a structured list. The structured list can serve as, for example, a list summary of the target web page.

Embodiments of the present disclosure may be applied in various application scenarios. For example, in a search service, embodiments of the present disclosure may generate a structured list for target web pages, for example, to create list summaries for the target web pages. Correspondingly, the search service may present the structured list generated according to the embodiments of the present disclosure as list summaries in the search result page. It should be understood that the embodiments of the present disclosure are not limited to be applied in the search service, but can also be applied in any application scenario where target web pages need to be extracted and visualized.

The target webpages processed by embodiments of the present disclosure may be various listing webpages from various websites, online services, and the like. Figure 1 shows an exemplary listing web page. Listing page 12 is an exemplary article on the web, which may be located, for example, on an academic website, an online question-and-answer community, and the like. This article introduces the top ten festivals in China, such as "Spring Festival", "Mid-Autumn Festival", "Dragon Boat Festival" and so on. The sections of the article dealing with the festivals presented form a visually perceptible list 122 . For example, the parts related to "Spring Festival", the parts related to "Mid-Autumn Festival", the parts related to "Dragon Boat Festival" and so on respectively form a plurality of items in the list 122 .

The list web page 14 is a web page from, for example, a book sales website, a reading exchange website, and the like. Assuming that multiple options have been selected in the "Options" column on the left side of the webpage 14, the introduction information of the four recommended books matching the selected options is presented on the right side of the webpage 14. Taking the first book as an example, the introduction information of the book may include, for example, a cover photo 144, a text introduction 146, and the like. The introduction information of the four books forms a visually perceptible list 142 . For example, the introductory information for each book forms an item in list 142 .

Listing web page 16 is a web page for the exemplary topic "Restaurant X" from a certain review forum, which includes discussion threads about "Restaurant X" by multiple users. For example, web page 16 includes multiple display areas for users Tom, David, Jane, etc., respectively. Taking the user Tom as an example, the display area for Tom includes, for example, Tom's avatar, Tom's name, release time of Tom's comment, specific content of Tom's comment, and the like. The display area for Tom, the display area for David, the display area for Jane, etc. form a visually perceptible list 162, and these display areas form a plurality of items in the list 162, respectively.

FIG. 2 shows an exemplary listing web page 20 . Web page 20 may be from, for example, an online shopping site or the like. Online shopping websites usually generate or provide a large number of webpages including lists, such as best-selling webpages, most popular product webpages, product category webpages, webpages containing products searched by users, and the like. Web page 20 may be a web page presenting, for example, cell phones that meet certain criteria. Assuming that multiple options have been selected in the "options" column on the left side of the web page 20, introduction information of multiple mobile phones matching the selected options is presented on the right side of the web page 20. For example, the introduction information of the mobile phone "M mobile phone A4" is presented in the area 22, including, for example, the picture 222 of the mobile phone, the introduction of the mobile phone "M mobile phone A4, 6.5 inches, 256G, black", the 5-star rating of the mobile phone, the number of comments about the mobile phone "25900 comments", the price of the mobile phone "5500RMB" and so on. Similarly, the introduction information of the mobile phone "M mobile phone A3" including at least the picture 242 of the mobile phone is presented in the area 24, the introduction information of the mobile phone "M mobile phone A2" at least including the picture 262 of the mobile phone is presented in the area 26, and so on. The introduction information of these mobile phones forms a visually perceivable list 202 , wherein the introduction information of each mobile phone forms an item in the list 202 . In addition, the webpage 20 also presents recommendations about related products in the area 28, for example, the introduction information of the first related product including at least the picture 282 of the product, the introduction information of the second related product including at least the picture 284 of the product, the introduction information of the third related product at least including the picture 286 of the product, etc. The introduction information of these related products forms a visually perceivable list 204 , wherein each introduction information of related products forms an item in the list 204 .

It should be understood that embodiments of the present disclosure are not limited to the exemplary listing pages shown in FIGS. 1 and 2 , but may encompass various other types of listing pages from various other websites, online services, etc., for example, listing pages from forum websites on topics in various fields, listing pages from product review websites, listing pages from news websites, listing pages from hotel or airline reservation websites, etc.

FIG. 3 shows an existing exemplary search results page 300 . The search result page 300 may be presented to the user in a search service provided by a general search engine provider. Assume that the user has entered the query "M mobile phone" in the search box 310 to indicate that he wants to obtain web search results about M mobile phones. Search results area 320 in search results page 300 includes a plurality of web search results. For example, search results for web page 20 in FIG. 2 are shown in area 330 . As shown in area 330 , the search results for the webpage 20 include the text abstract "M mobile phone A4, 6.5 inches, 256G, black, 5 stars, 25900 reviews, 5500RMB". The text abstract is only generated by using the introduction information about "M mobile phone A4" in the webpage 20. Based on the text abstract in the area 330, the user can only learn limited information about the webpage 20, for example, only can learn about the information about the mobile phone "M mobile phone A4", but cannot learn any information about other mobile phones in the list 202 in the webpage 20. Moreover, such text summarization also lacks intuition and legibility.

FIG. 4 shows an exemplary process 400 of list extraction and visualization in a web page, according to an embodiment. Process 400 may be performed to implement list extraction and visualization for raw listings in target web page 402 to generate structured listing 404 . The target web page 402 may be a list web page containing lists, and the list in the target web page 402 may be referred to herein as the original list. If target web page 402 includes two or more listings, process 400 may generate structured list 404 for the main list in target web page 402 .

At 410, at least one set of anchor elements in the target web page 404 can be detected. Each anchor element group may include one or more anchor elements, and each anchor element group may correspond to a possible origin list. For example, if the target web page 404 includes two or more original listings, then at 410 two or more groups of anchor elements corresponding respectively to the original listings may be detected. In an implementation manner, multiple anchor elements in the target webpage 404 may be identified first, and then the multiple anchor elements are clustered into at least one anchor element group.

At 420, for each anchor element group, boundary detection may be performed on multiple anchor elements in the anchor element group to obtain boundaries of multiple items respectively associated with the multiple anchor elements. These items may form the original list in the target web page 404 corresponding to the set of anchor elements. Boundary detection may include, for example, iterative boundary expansion, similarity checking, etc., to accurately identify at least one original list in the target web page 404 and individual items in each original list.

At 430, optionally, if it is determined through the previous steps that the target web page 404 includes two or more original lists, a master list may be determined from these original lists. In one implementation, at least visual features of these original lists can be utilized to determine the master list.

At 440, for the original list in the target webpage 404, multiple sets of representative metadata respectively corresponding to the multiple items may be obtained from the target webpage 404 by using at least boundaries of the multiple items in the original list. Optionally, the obtaining of representative metadata at 440 may be performed for the master list in the target web page 404 . Herein, representative metadata may refer to data contained in the original list and to be presented in the structured list 404, eg, images, text, and the like. In one implementation, for each item, a set of initial metadata may first be obtained from the target web page 404, and then a set of representative metadata corresponding to the item to be presented in the structured list 404 is selected from the initial set of metadata.

At 450 , the sets of representative metadata obtained at 440 can be visualized as structured list 404 . In one implementation manner, the structured list 404 may be formed using the plurality of sets of representative metadata according to a predetermined format or layout. The structured list 404 is a simplified version of the original list in the target web page 402, but it still contains enough information for the user to intuitively and comprehensively understand the main content of the original list. Structured list 404 may be, for example, a list summary of the original list.

It should be understood that all steps and their order in process 400 are exemplary, and embodiments of the present disclosure will also encompass modifications to process 400 in any manner. For example, although process 400 includes the step of master list determination at 430, this step may also be omitted where target web page 402 includes only one original list. For example, although step 430 is shown as being performed before step 440 in FIG. 4 , step 430 may also be performed after step 440 . In this case, multiple sets of representative metadata of each original list can be obtained first through step 440 , and then, after the main list is determined through step 430 , only multiple sets of representative metadata of the main list can be provided to step 450 .

FIG. 5 shows an exemplary process 500 of anchor element group detection according to an embodiment. Process 500 is an exemplary implementation of step 410 in FIG. 4 .

At 510 , a plurality of anchor elements can be identified from the target web page 502 . For example, these anchor elements can be identified from the html source file of the target web page 502 . Each item in the original list may include multiple html elements, and the anchor element may be the most representative html element among these html elements and the most helpful for identifying the entire item. The anchor element identified at 510 may also be referred to as an identified anchor element. In an implementation manner, anchor element constraints may be defined in advance, and multiple html elements in the target web page 502 that satisfy the anchor element constraints may be identified as multiple identified anchor elements. For example, the anchor element constraint may include at least one of: the html element has an image tag; the html element has a title tag; the html element represents a date; and so on. In one case, each item in the original list may have a corresponding image, therefore, html elements with image tags, such as <img> tags, etc., in the html source file can be used as anchor elements to help identify the corresponding item. In one case, each item in the original list may have a corresponding heading, so html elements with heading tags, such as <h1> tags, <h2> tags, etc., in the html source file can be used as anchor elements to help identify the corresponding item. In one case, each item in the original list may have a date, such as a post date, etc. Therefore, an html element in the html source file with a string representing a date can be used as an anchor element to help identify the corresponding item. In this case, various techniques such as regular matching can be used to identify the character string representing the date in the html source file. It should be understood that embodiments of the present disclosure are not limited to the above exemplary anchor element constraints, but may cover any other types of anchor element constraints.

At 520 , a set of properties for each of the plurality of identified anchor elements identified at 510 can be extracted from the target web page 502 . An attribute set identifying an anchor element may include one or more intrinsic attributes of the identifying anchor element, for example, the html tag attribute (tag attribute), Cascading Style Sheets (CSS: Cascading Style Sheets) category (class), XML path language (XPath) information, etc. of the identifying anchor element. The html tag attribute may indicate the type of html tag that identifies the anchor element. CSS classes may indicate which CSS classes the identifying anchor element has. The XPath information may indicate the location information and node information of the identified anchor element, which may be obtained, for example, from a Document Object Model (DOM: Document Object Model) tree corresponding to the html source file. It should be understood that the embodiments of the present disclosure are not limited to the above exemplary attributes for identifying anchor elements, but may cover any other types of attributes. Through step 520, multiple attribute sets respectively corresponding to multiple identification anchor elements can be obtained.

At 530, the plurality of identifying anchor elements can be clustered into at least one anchor element group 504 based on the plurality of attribute sets of the identifying anchor elements. Each recognition anchor element may be characterized by a corresponding attribute set, and multiple attribute sets of multiple recognition anchor elements may be provided as input to the pre-trained clustering model. The clustering model is trained to cluster the plurality of anchor elements into at least one group of anchor elements based on the set of attributes. For example, those identified anchor elements with similar attributes will be clustered into the same anchor element group. Each anchor element group includes a plurality of anchor elements with similar attributes, and may correspond to a possible original list, wherein the anchor elements may be respectively associated with different items in the possible original list.

It should be understood that all steps in process 500 are exemplary, and embodiments of the present disclosure will also encompass modifications to process 500 in any manner. For example, process 500 may employ any combination of various anchor element constraints, attribute sets containing any combination of various attributes, and the like.

Fig. 6 shows an exemplary set of anchor elements according to an embodiment. In FIG. 6 , it is assumed that a first set of anchor elements and a second set of anchor elements are detected for the web page 20 in FIG. 2 . The first anchor element group may include a plurality of anchor elements corresponding to the image 222, the image 242, and the image 262 in the original list 202 in FIG. The second anchor point element group may include a plurality of anchor point elements, and these anchor point elements correspond to image 282, image 284, image 286, etc. in the original list 204 in FIG.

It should be understood that although FIG. 6 shows anchor element groups detected according to the anchor element constraint of "html element has an image tag", embodiments of the present disclosure may also detect anchor element groups according to other types of anchor element constraints. For example, for the webpage 12 in FIG. 1 , the anchor element group formed by the title "Spring Festival", the title "Mid-Autumn Festival", the title "Dragon Boat Festival" and the like can be detected according to the anchor element constraint of "html element has a title tag". For example, for the webpage 16 in FIG. 1 , the anchor element group formed by the date "2021-10-05" in the display area of Tom, the date "2021-10-05" in the display area of David, the date "2021-10-06" in the display area of Jane, etc. can be detected according to the anchor element constraint of "the html element represents the date".

FIG. 7 shows an exemplary process 700 of boundary detection according to an embodiment. Process 700 is an exemplary implementation of step 420 in FIG. 4 . The process 700 may be used to perform boundary detection on the exemplary set of anchor elements 702, so as to obtain the boundaries of multiple items respectively associated with the multiple anchor elements in the set of anchor elements 702, thereby identifying the original list 704 corresponding to the set of anchor elements 702 in the target web page and each item in the original list 704. Process 700 may be performed based at least on a DOM tree corresponding to a target web page.

At 710, iterative bounds expansion can be performed on each anchor element in anchor element group 702 to find elements that are likely to be within the same item as the anchor element. In an implementation manner, based on the DOM tree corresponding to the target web page, the iterative boundary expansion may be performed synchronously with multiple anchor elements in the anchor element group 702 as starting points. Each anchor point element can be used as a starting point, and through iterative boundary expansion, it can be sequentially determined from the anchor point element in the DOM tree and extended to multiple other elements. The anchor element forms a tree together with other determined elements, and this tree represents an item, so it can also be called an item tree. A plurality of nodes in the item tree may respectively correspond to a plurality of elements, such as the anchor element and elements determined through iterative boundary expansion. The iteration of each step can be expanded to the next node, and that next node can be included into the project tree. Iteration of multiple steps forms a corresponding expansion path. Through the iterative boundary expansion at 710 , multiple item trees respectively originating from multiple anchor elements in the anchor element group 702 can be obtained. The multiple project trees respectively define boundaries of multiple projects.

Iterative boundary expansion may include various types of expansion, for example, sibling node expansion, parent node expansion, and the like. Sibling node expansion may be performed to expand from the current node to sibling nodes of the current node in the DOM tree corresponding to the target web page. In one case, if the current node has multiple sibling nodes belonging to the same parent node, the multiple sibling nodes may be extended from the current node from near to far. In one case, sibling node expansion may adopt a predetermined expansion direction, for example, expand to the right, expand to the left, expand to the right and left alternately, change to expand to the left after multiple times of right expansion or satisfy a predetermined condition, change to right after multiple times of left expansion or satisfy a predetermined condition, and so on. Parent node expansion may be performed to expand to a parent node of the current node and include the parent node into the item tree after all sibling nodes of the current node have been included in the same item tree. After expanding to the parent node, you can continue to perform sibling expansion on the parent node, for example, expand to sibling nodes of the parent node. By analogy, it can iteratively expand to the upper node. In addition, if a certain node is included in the project tree through iterative boundary expansion and the node has its own subordinate nodes, such as child nodes, grandchildren nodes, etc., all the subordinate nodes of the node can be further included in the project tree.

Iterative boundary expansion may be performed synchronously between different project trees corresponding to different anchor elements. For example, in each iteration of the step, a sibling expansion or parent expansion is performed synchronously in the item trees. In one case, for example, in the expansion of sibling nodes in a certain step, if a project tree S currently has no sibling nodes that can be expanded, but other project trees have sibling nodes that can be expanded, then the expansion of the project tree S can be suspended once at the current step while the sibling node expansion of the current step is performed on other project trees.

According to an embodiment of the present disclosure, the boundary of each item may be expanded as much as possible, for example, each item includes as many elements as possible by iterative boundary expansion. However, there should be no content overlap between different items, eg, the same element or content should not be included in different items. Furthermore, the structures of different items should be similar, eg, different items should have at least a predetermined proportion of similar elements or nodes, etc.

Content overlap between two projects may be caused by overlapping nodes of the two project trees corresponding to the two projects, for example, a certain node is shared by the two project trees. Therefore, content overlap between different items can be avoided by detecting node overlap during the iterative boundary expansion at 710 .

At 720, it can be determined whether the iteration of the current step in the iterative boundary expansion resulted in node overlap between at least two item trees. For example, whether iteration of the current step resulted in the inclusion of the same node or nodes into at least two project trees simultaneously. The node overlap determination at 720 may be performed synchronously with the iterative boundary extension at 710, eg, after each iteration of the step it is determined whether there is node overlap.

If it is determined at 720 that the iteration of the current step has not resulted in a node overlap, then process 700 may return to 710 and continue to perform iterative boundary expansion.

If it is determined at 720 that the iteration of the current step resulted in overlapping nodes, then at 730 execution of the iterative bounds extension is stopped and the nodes determined by the iteration of the current step are excluded from each item tree. For example, causing each project tree to roll back or reset to the state at the iteration of the previous step before the iteration of the current step.

By executing step 720 and step 730, the embodiment of the present disclosure can prevent multiple project trees obtained from overlapping nodes, thereby preventing different projects from having content overlapping.

To determine whether the structures of different projects are similar, process 700 may perform a similarity check on multiple project trees. In one instance, the similarity check may be performed in response to determining that the number of nodes in at least one of the plurality of item trees exceeds a node number threshold. In one aspect, for example, the at least one project tree may be a predetermined number or a predetermined proportion of project trees in the plurality of project trees, whereby the performance of the similarity check may require that the number of nodes in each project tree in the predetermined number or predetermined proportion of project trees in the plurality of project trees exceed a node number threshold. In another aspect, for example, performance of the similarity check may require that the iterative bounds expansion at 710 has been performed for a predetermined number of iterations of steps, i.e., each item has contained a predetermined number of elements or each item tree has contained a predetermined number of nodes. In one case, the similarity check may be performed synchronously with the iterative boundary extension at 710, eg, after each iteration of the step. In one case, the similarity check may be performed every time a predetermined number of iterations of steps are performed, for example, every time a predetermined number of new elements are added to each item or every time a predetermined number of new nodes are added to each item tree, the similarity check may be performed. Embodiments of the present disclosure are not limited to the above exemplary timings for performing the similarity check.

At 740, tree similarity between any two item trees of the plurality of item trees can be calculated. Embodiments of the present disclosure are not limited to any particular technique for computing tree similarity. Preferably, the embodiments of the present disclosure propose a tree similarity calculation method obtained by improving an existing simple tree matching algorithm, and the proposed tree similarity calculation method at least utilizes CSS similarity-based weights and/or minimum depth levels to calculate tree similarity.

In an implementation manner, the embodiments of the present disclosure may at least use matching weights calculated based on CSS similarity between root nodes of two item trees to calculate tree similarity. In a web page, the style presented by CSS is important information indicating the page layout. Therefore, by calculating the matching weight based on the CSS similarity between the root nodes of two item trees and using the matching weight to calculate the tree similarity between the two item trees, the accuracy of tree similarity calculation can be effectively improved. The matching weights may be calculated based on, for example, the respective CSS classes of the two root nodes.

In one implementation, the embodiments of the present disclosure may utilize nodes within the minimum depth level in two item trees to calculate tree similarity. Herein, the minimum depth level can be defined such that: the number of visible (visible) nodes within the minimum depth level of an item tree reaches a predetermined ratio, such as 80% or any other ratio, of the number of all visible nodes in the item tree. In another aspect, the minimum depth level can also be defined such that the number of visible nodes within a level of the item tree less than the minimum depth level does not reach a predetermined proportion of the number of all visible nodes in the item tree. In this paper, visible nodes may refer to visually visible nodes in web pages, such as nodes presenting images, nodes presenting text, etc. Therefore, compared with other nodes, visible nodes are more important for determining the structural similarity between item trees. An item tree may have multiple levels. For example, assuming that the root node of the item tree is located at a level with a depth of 0, the child nodes of the root node are located at a level with a depth of 1, and so on. The deeper the hierarchy, the smaller the contribution to judging the similarity of the structure between the two trees. Therefore, the embodiments of the present disclosure propose to use only part of the levels of the item tree instead of all the levels to calculate the tree similarity, so that the calculation efficiency can be effectively improved and the calculation resources can be saved. Tree similarity can be computed using the minimum depth level and those levels that are less than the minimum depth level. For example, assuming that the minimum depth level is 3, the tree similarity can be calculated using levels of depth 0, 1, 2 and 3. Since the minimum depth level is determined by at least considering the number of visible nodes, for example, the number of visible nodes within the minimum depth level should not be lower than a predetermined ratio of the number of all visible nodes in the project tree, therefore, properly setting the predetermined ratio will ensure that even if those levels greater than the minimum depth level are not considered in the calculation of tree similarity, accurate tree similarity can still be calculated. The predetermined ratio may have any value preset according to actual application requirements. It should be understood that although the above discusses using nodes within the minimum depth level in the two item trees to calculate the tree similarity, embodiments of the present disclosure are not limited thereto, but may instead use nodes in all levels of the two item trees to calculate the tree similarity.

Suppose T and T' are two item trees. Root(T) represents the root node of the tree T, and Root(T') represents the root node of the tree T'. It should be understood that if T and T' do not have actual root nodes, virtual root nodes may be set for T and T' respectively, and the two virtual root nodes may have the same attribute configuration. For each of T and T', L ₀ , L ₁ ,...,L _n denote the set of subtrees at hierarchical depth 0, 1,...,n, respectively. L _i1 , L _i2 ,...,L _ik respectively denote k subtrees in the hierarchical depth i, that is, the subtrees in the subtree set L _i .

Assume that css ₁ represents the set of CSS classes that Root(T) has, where Root(T) may have 0, 1 or any other number of CSS classes. Suppose css ₂ represents the set of CSS classes that Root(T') has, where Root(T') may have 0, 1 or any other number of CSS classes. In an implementation manner, the matching weight between T and T' can be calculated by using the Jaccard coefficient. For example, the matching weight between T and T' can be calculated as:

Among them, MatchWeight( ) is a function to calculate the matching weight, |css ₁ | indicates the number of CSS categories included in css ₁ , |css ₂ | indicates the number of CSS categories included in css ₂ , |css ₁ ∩css ₂ | indicates the number of CSS categories included in both css ₁ and css ₂ .

The tree similarity between T and T' can be calculated based on, for example, the procedure in Table 1 below.

Table 1

At step 1.1, a minimum depth level MinDepth may be determined. At step 1.2, a similarity check function SimilarityCheck(·) for calculating the similarity measure of T and T' at the current level layer is defined, and this function may include subsequent processing in steps 1.3 to 1.18. At step 1.3 and step 1.4, if it is determined that Root(T) and Root(T') have different html tags, the calculation result of SimilarityCheck(·) is 0. At step 1.5 and step 1.6, if it is determined that the current layer layer is greater than the minimum depth level MinDepth, then the calculation result of SimilarityCheck( ) is 0, so that tree similarity calculation can be avoided when the current level is greater than the minimum depth level. At step 1.8, use m to denote the subtrees in the subtree set L layer+1 in T corresponding to the depth layer ₊₁ . At step 1.9, use n to denote the subtrees in the subtree set L' layer+1 corresponding to the depth _layer+1 in T'. In the procedure of Table 1, a similarity function M[i,j] is defined, which represents the maximum similarity between the first i subtrees in T and the first j subtrees in T'. At step 1.10 and step 1.11, M[i,0] and M[0,j] are initialized to 0 respectively. At step 1.12, define the subtrees in the set m of subtrees of T that will be traversed. At step 1.13, define the subtrees in the set n of subtrees that will be traversed T'. At step 1.14 and step 1.15, the similarity can be calculated using the similarity function M[i,j]. For example, techniques such as dynamic programming may be employed to perform the calculations at steps 1.14 and 1.15. M[i,j] will get the best similarity from three candidates including M[i,j-1], M[i-1,j] and M[i-1,j-1]+W[i,j]. W[i,j] will recursively compute the similarity between the i-th subtree T _i in T and the _j -th subtree T' j in T' at the level of layer+1. Thus, the entire tree structure can be considered, not just the root node. At step 1.18, the calculation result of SimilarityCheck( ) may be returned, expressed as MatchWeight(Root(T), Root(T'))*(M[m,n]+1), where M[m,n] is the best similarity of the subtrees of T and T', and "1" represents the root node. It should be understood that the calculation result returned at step 1.18 may indicate, for example, the number of similar nodes. At step 1.19, all nodes whose depth is not greater than the minimum depth level can be further used to calculate the final tree similarity, where TreeSimilarity( ) is a tree similarity function, |T| is the number of nodes in T whose depth is not greater than the minimum depth level, and |T'| is the number of nodes in T' whose depth is not greater than the minimum depth level. It should be understood that all steps in Table 1 are exemplary, and embodiments of the present disclosure will also encompass modifications to these steps in any manner.

After calculating the tree similarity between any two item trees in the plurality of item trees through step 740 , the plurality of item trees may be divided into at least one tree set at 745 using at least a similarity threshold. Each tree set in the at least one tree set may include at least one item tree, and at least one item tree in the same tree set has a tree similarity between each other that is not lower than the similarity threshold. Through step 745, item trees with high similarity to each other can be divided into the same tree set. At 750, it may be determined whether the number of item trees in the set of trees of the at least one set of trees containing the greatest number of item trees is below a tree count threshold. The set of trees containing the largest number of item trees may be used as the target set of trees for determining whether execution of the iteration should stop. The tree quantity threshold may have a preset value, which may be used, for example, to ensure that most of the plurality of item trees are included in the target tree set. If it is determined at 750 that the number of item trees in the target tree set is not below the tree count threshold, then process 700 may return to 710 and continue to perform iterative bound expansion. If it is determined at 750 that the number of item trees in the target set of trees is below the tree number threshold, then performing the iterative bounds expansion may cease at 760 and nodes determined through iterations of a predetermined number of previous steps are respectively excluded from the plurality of item trees. In one implementation manner, the iterations of the predetermined number of previous steps may be determined in the following manner: by respectively excluding nodes determined through the iterations of the predetermined number of previous steps from the plurality of item trees, the number of item trees in the target tree set obtained for the updated plurality of item trees may not be lower than the tree number threshold, for example, through the processing of steps 740 and 745.

By executing step 740 , step 745 , step 750 and step 760 , the embodiment of the present disclosure can realize the similarity check on multiple project trees. Similarity checks help ensure that the resulting project trees are structurally similar. For example, in case a plurality of item trees in the target tree set are provided as the iterative expansion result, these item trees in the iterative expansion result will have high similarity to each other, thereby ensuring that different items have similar structures.

According to process 700, optionally further iterative bounds expansion can be performed at 770 in an attempt to find better item trees. In one implementation, after step 730 is performed, if it is determined that the iteration of the current step is sibling node expansion, further iteration boundary expansion may be performed on the plurality of item trees in a direction opposite to the iteration direction of the current step. For example, for each item tree, if the current step's iteration was expanding right to a sibling, it might try expanding left to a different sibling. In another implementation manner, after step 760 is performed, the plurality of project trees may first be reset to the state at the iteration of the predetermined previous step. The predetermined number of iterations of previous steps may be determined, for example, using the predetermined number of iterations of previous steps involved at 760 . For example, if the iteration of the predetermined number of previous steps is an iteration of the previous 2 steps, the iteration of the predetermined number of previous steps may be an iteration of the 3rd step preceding. Then, if it is determined that the iteration of the next step after the iteration of the predetermined previous step is sibling expansion, a further iteration boundary expansion of the plurality of item trees may be attempted in a direction opposite to that of the iteration of the next step. For example, for each item tree, if the item tree was reset to the state at the previous iteration of step 3, and the previous iteration of step 2 was right-extending to a sibling, then further left-extending to a different sibling could be attempted.

It should be appreciated that, although not shown, process 700 may also include performing steps 720-730 and/or steps 740-760 for further iterative boundary expansion at 770, so as to ensure that the obtained multiple project trees have no overlapping nodes and have similar structures, thereby ensuring that different projects have no overlapping content and similar structures.

Through the process 700, multiple item trees respectively originating from multiple anchor elements in the anchor element group 702 can be obtained, and these item trees respectively define boundaries of multiple corresponding items, so that the original list 704 formed by these items can be finally identified.

It should be understood that all steps in the process 700 are exemplary, and embodiments of the present disclosure will also cover modifications to the process 700 in any manner. For example, both the process of determining whether node overlap occurs and the process of performing a similarity check in process 700 are optional, and any one or both of these two processes may be included in process 700, or any one or both of these two processes may be omitted from process 700. In addition, for example, the process 700 may also only provide a plurality of item trees in the target tree set as the iterative expansion result, and use these item trees to form the original list 704 .

8A-8F illustrate examples of iterative bounds extension according to an embodiment. In FIGS. 8A-8F , an exemplary process of iterative boundary expansion is shown in an exemplary DOM tree corresponding to a target web page.

The DOM tree may include multiple nodes, such as node 801 to node 826 and other nodes not shown. Symbols such as "Div", "A", "Span", "P", "Img" and the like displayed in boxes representing nodes indicate html tags of corresponding nodes. In addition, the embodiments of the present disclosure propose to set a "Text (text)" tag for the text strings appearing in the html source file, although there is no such html tag, and these text strings can also be used as nodes in the DOM tree, such as node 819, node 820, etc. These text strings may be visible elements that can be rendered, so setting Text tags and corresponding nodes for these text strings will help to more accurately determine the item boundary. It should be understood that, for the purpose of explanation, only several exemplary node labels are shown in FIGS. 8A to 8F , any other types of node labels may exist in practical applications, and embodiments of the present disclosure are not limited by what specific labels the nodes in the DOM tree have. Furthermore, in FIGS. 8A to 8F , the nodes included into the item tree by iterative boundary expansion are highlighted with shading, and the expansion paths of iterative boundary expansion are indicated with arrows.

In FIG. 8A, assume that node 818, node 821, and node 824 have been identified as anchor elements with an Img (image) tag. An iterative boundary expansion can then be performed synchronously starting from each of these nodes in order to obtain a tree of items originating from each of these nodes. Hereinafter, the item tree originating from node 818 is referred to as a first item tree, the item tree originating from node 821 is referred to as a second item tree, and the item tree originating from node 824 is referred to as a third item tree.

Figure 8B shows an iteration of Step 1. Since node 818, node 821, and node 824 have no sibling nodes, parent node expansion will be performed in the iteration of step 1 . For example, in the first item tree, expand from node 818 to the parent node 806 of node 818; in the second item tree, expand from node 821 to the parent node 810 of node 821; in the third item tree, expand from node 824 to the parent node 814 of node 824.

Figure 8C shows the iteration of steps 2 to 4, where sibling expansion will be performed. Taking the first item tree as an example, the node 806 determined by the iteration of the first step is the current node, which has sibling nodes 807, 808 and 809. Therefore, the iterations of the second step to the fourth step will be extended to the right in turn to the node 807, node 808 and node 809 as shown by the arrows. Similarly, in the second project tree, the iterations from the 2nd step to the 4th step will be extended to node 811, node 812 and node 813 to the right as shown by the arrow; Furthermore, since node 808 has child node 819 and node 809 has child node 820, node 819 and node 820 may also be included in the first item tree. Similarly, child node 822 of node 812 and child node 823 of node 813 may be included into a second item tree, and child node 825 of node 816 and child node 826 of node 817 may be included into a third item tree.

Figure 8D shows an iteration of step 5, where parent node expansion will be performed. Taking the first item tree as an example, since all sibling nodes 807, 808 and 809 of the node 806 have been included in the first item tree through the iteration of the second step to the fourth step, the iteration of the fifth step will be extended to the parent node 803 of the node 806 to the node 809 as shown by the arrow. Similarly, in the second item tree, the iteration of step 5 will expand to node 804 as indicated by the arrow; in the third item tree, the iteration of step 5 will expand to node 805 as indicated by the arrow.

Figure 8E shows an iteration of step 6, where parent node expansion will be performed. Taking the first item tree as an example, the node 803 determined by the iteration of step 5 has no sibling nodes, so the iteration of step 6 will extend to the parent node 802 of node 803 as shown by the arrow. Similarly, in the second item tree, the iteration of step 6 will expand to node 802 as indicated by the arrow; in the third item tree, the iteration of step 6 will expand to node 802 as indicated by the arrow.

Through the iteration of the sixth step, the node 802 will be included in the first item tree, the second item tree and the third item tree at the same time, thus resulting in node overlap. Therefore, execution of the iterative boundary expansion will cease and the nodes 802 determined by the iteration of step 6 will be excluded from the first item tree, the second item tree and the third item tree respectively. In FIG. 8F , the finally obtained first item tree 830 , the finally obtained second item tree 840 , and the finally obtained third item tree 850 are shown by dotted line boxes. The first item tree 830, the second item tree 840, and the third item tree 850 respectively correspond to the first item, the second item, and the third item in the original list in the target web page. Thus, through the iterative boundary expansion in FIGS. 8A to 8F , the original list in the target web page and the items in the original list can be identified. It should be understood that the similarity check described above in connection with FIG. 7 may also be performed on the final item tree shown in FIG. 8F. In addition, it should be noted that, as shown in FIG. 8F , each item tree has its own root node. For example, the first item tree 830, the second item tree 840 and the third item tree 850 have their own root nodes 803, 804, and 805 respectively. Therefore, the boundary of each item tree can actually be indicated by the html tag of the root node. For example, the boundary of the first item tree can be indicated by the "Div" label of the root node 803.

9A-9F illustrate examples of iterative bounds extension according to an embodiment. FIGS. 9A to 9F illustrate examples of iterative boundary expansion in different ways in an exemplary DOM tree corresponding to a target web page. The DOM tree may include multiple nodes, such as node 901 to node 929 and other nodes not shown.

In FIG. 9A, assume that node 919, node 923, and node 927 have been identified as anchor elements with an Img (image) tag. An iterative boundary expansion can then be performed synchronously starting from each of these nodes in order to obtain a tree of items originating from each of these nodes. Hereinafter, the item tree originating from node 919 is referred to as a first item tree, the item tree originating from node 923 is referred to as a second item tree, and the item tree originating from node 927 is referred to as a third item tree.

Figure 9B shows an iteration of Step 1. Since node 919, node 923, and node 927 have no sibling nodes, parent node expansion will be performed in the iteration of step 1 . For example, in the first item tree, expand from node 919 to the parent node 904 of node 919; in the second item tree, expand from node 923 to the parent node 909 of node 923; in the third item tree, expand from node 927 to the parent node 914 of node 927.

FIG. 9C shows an item tree finally obtained by performing subsequent iterative boundary expansion in an extended manner on the basis of the iteration in the first step in FIG. 9B . As shown in FIG. 9C , the iterations from the second step to the fifth step will sequentially perform sibling node expansion to the left as indicated by the arrow. In the first project tree, the iteration of step 2 will expand leftwards to node 903 as indicated by the arrow, and since there are no other sibling nodes, the iteration of steps 3 to 5 will be suspended in the first project tree. In the second project tree, the iterations of steps 2 to 5 will be expanded to the left sequentially to node 908 , node 907 , node 906 and node 905 as indicated by the arrows. In the third item tree, the iterations of the 2nd step to the 5th step will be expanded to the left sequentially to node 913 , node 912 , node 911 and node 910 as indicated by the arrows. Since node 902 is the common parent node of the first item tree, the second item tree and the third item tree, in order to avoid node overlap, the finally obtained first item tree, second item tree and third item tree do not include node 902 . In FIG. 9C , the finally obtained first item tree 932 , the finally obtained second item tree 934 , and the finally obtained third item tree 936 are shown by dotted line boxes. It should be noted that node 915, node 916, node 917, node 928, and node 929 are not included in any project tree. In addition, it is assumed that the similarity test described above in conjunction with FIG. 7 is further performed on these finally obtained item trees, and it is found that although the second item tree 934 and the third item tree 936 have a high similarity, the tree similarities between the first item tree 932 and the second item tree 934 and the third item tree 936 are all lower than the similarity threshold. Therefore, the first item tree 932 can be considered as an unqualified item tree and thus discarded. Correspondingly, the expansion method in FIG. 9C actually outputs only two item trees 934 and 936 in the end.

FIG. 9D shows the item tree finally obtained by performing subsequent iterative boundary expansion in another expansion manner on the basis of the iteration in the first step in FIG. 9B . As shown in FIG. 9D , the iterations from step 2 to step 5 will perform sibling node expansion to the right in sequence as indicated by the arrow. In the first project tree, the iterations of steps 2 to 5 will be expanded to the right sequentially to node 905 , node 906 , node 907 and node 908 as indicated by the arrows. In the second project tree, the iterations from step 2 to step 5 will be expanded to the right sequentially to node 910 , node 911 , node 912 and node 913 as indicated by the arrows. In the third item tree, the iteration of step 2 to step 4 will be extended to the right in turn as indicated by the arrows to node 915, node 916, and node 917, and since there are no further sibling nodes, the iteration of step 5 will be suspended in the third item tree. In FIG. 9D , the finally obtained first item tree 942 , the finally obtained second item tree 944 , and the finally obtained third item tree 946 are shown by dashed boxes. It should be noted that node 903 and node 918 are not included into any project tree. In addition, it is assumed that the similarity test described above in conjunction with FIG. 7 is further performed on these finally obtained item trees, and it is found that the tree similarity between these item trees is not lower than the similarity threshold. Accordingly, the expansion of FIG. 9D actually ends up outputting all three item trees 942 , 944 and 946 .

According to an embodiment of the present disclosure, in order to find a better item tree, further iterative boundary expansion may be performed according to, for example, step 770 in FIG. 7 . Assume that the item tree shown in FIG. 9D is respectively reset to the state at the iteration of step 4, as shown in FIG. 9E. In FIG. 9E , the current expansion path of the first project tree includes node 919, node 904, node 905, node 906, and node 907 as shown by the arrows, the current expansion path of the second project tree includes node 923, node 909, node 910, node 911, and node 912 as shown by the arrow, and the current expansion path of the third item tree includes node 927, node 914, node 915, node 916, and node 917. Unlike the step 5 iteration in FIG. 9D , which was sibling expansion to the right, the step 5 iteration in FIG. 9F may attempt sibling expansion to the left, i.e., in the direction opposite to that of the iteration of step 5 in FIG. 9D . Correspondingly, in the iteration of the fifth step in FIG. 9F , the expansion path of the first item tree will further include node 903 as shown by the arrow, the expansion path of the second item tree will further include node 908 as shown by the arrow, and the expansion path of the third item tree will further include node 913 as shown by the arrow. In FIG. 9F , the finally obtained first item tree 952 , the finally obtained second item tree 954 , and the finally obtained third item tree 956 are shown by dashed boxes. In addition, it is assumed that the similarity test described above in conjunction with FIG. 7 is further performed on these finally obtained item trees, and it is found that the tree similarity between these item trees is not lower than the similarity threshold. Accordingly, the expansion of FIG. 9F actually ends up outputting all three item trees 952 , 954 and 956 .

In the embodiments of the present disclosure, the execution of the iterative boundary extension may follow a predetermined standard, for example, the more item trees obtained, the better, the more nodes in each item tree, the better, the higher the tree similarity between different item trees, the better, and so on. By comparing FIG. 9C, FIG. 9D and FIG. 9F, it can be seen that the expansion method of FIG. 9D and FIG. 9F is better than that of FIG. 9C, because the expansion method of FIG. 9D and FIG. 9F can output a larger number of item trees. In addition, the expansion mode of Fig. 9F will be better than the expansion mode of Fig. 9D, this is because: the expansion mode of Fig. 9F can include more nodes (for example, node 903 and node 918) in the item tree; tree similarity.

It should be understood that embodiments of the present disclosure may perform further iterative boundary expansion in various ways. For example, instead of respectively resetting the item tree shown in FIG. 9D to the state at the iteration of the 4th step as shown in FIG. 9E , the item tree shown in FIG. 9D may be respectively reset to the state at the iteration of any other predetermined previous step, for example, reset to the state at the iteration of the 3rd step. Expansion of the reset tree of items may then be performed in a direction opposite to that of the iteration of the next step following the iteration of the predetermined previous step. In addition, it should be understood that the embodiments of the present disclosure may also perform further iterative boundary expansion in a variety of different ways, and select the way that can obtain the best item tree among these different ways.

Fig. 10 shows exemplary boundary detection results according to an embodiment. Assume that boundary detection has been performed for the target web page 20 in FIG. 2 . As shown in FIG. 10 , the dotted line frame 1010 marks the item corresponding to "M mobile phone A4" identified through the boundary detection, the dotted line frame 1020 marks the item corresponding to "M mobile phone A3" recognized through the boundary detection, and the dotted line frame 1030 marks the item corresponding to "M mobile phone A2" recognized through the boundary detection. The items marked by dashed boxes 1010, 1020 and 1030 together form the original list 202 in the target web page 20 as shown in FIG. 2 .

FIG. 11 illustrates an exemplary process 1100 for master list determination, according to an embodiment. Process 1100 is an example implementation of step 430 in FIG. 4 . Assuming it has been determined that the target web page includes more than one original list, eg, first original list 1102, second original list 1104, etc., process 1100 can be performed to determine a master list from these original lists.

At 1110 , visual characteristics of the first raw list 1102 can be determined using at least boundaries of items in the first raw list 1102 . At 1120 , visual characteristics of the second original list 1104 can be determined using at least boundaries of items in the second original list 1104 .

In an embodiment of the present disclosure, the visual features of an original list may refer to various visual features that help determine whether the original list occupies a main position in the target webpage, whether it is used to present the main content of the target webpage, and the like. In one implementation, the visual features may include a minimum border distance between adjacent items within the original list, which may indicate the visual distance between the two items. For example, the borders of two adjacent items can be used to calculate the minimum border distance between these two items. In one implementation, the visual feature may include a listing position, which may indicate whether the original listing occupies a dominant position in the target web page and thus serves as a major content portion in the target web page. For example, the listing location may include the horizontal location of the original listing in the target web page. For example, the list position may include the vertical position of the original list in the target webpage, such as whether the list is located above-the-fold of the screen, and so on. In one implementation, the visual characteristics may include item content richness, which indicates the visual content richness of the items within the original list. For example, the item content richness of an item may include such items as the size of the item, the number of nodes contained in the item, etc. determined based on the boundary of the item.

At 1130 , a master list may be determined from the first original list 1102 and the second original list 1104 based on the visual characteristics of the first original list 1102 and the second original list 1104 . In one implementation, a number of heuristic rules defined for visual features can be utilized to determine the master list. For example, for the minimum border distance, a heuristic rule can be defined as to whether the visual distance between items in the list is small, based on the consideration that the distance between items in the main list is usually not very far. For example, for list position, you can define a heuristic as to whether the original list dominates the landing page, based on the consideration that the main list usually dominates the landing page. For example, regarding item content richness, a heuristic rule about whether the original list has high item content richness can be defined, which is based on the consideration that the main list usually has high item content richness. According to the above heuristic rules, an original list that can better satisfy these heuristic rules can be selected from the first original list 1102 and the second original list 1104 as the main list.

Taking the target webpage 20 in FIG. 2 as an example, by performing the process 1100 , the original list 202 can be identified as the main list among the original list 202 and the original list 204 .

It should be understood that all steps in the process 1100 are exemplary, and embodiments of the present disclosure will also cover modifications to the process 1100 in any manner. For example, when there are more than two original lists, in a manner similar to process 1100, at least the visual features of these original lists can be used to determine the main list. In addition, the various visual features and various heuristic rules given above are exemplary, and embodiments of the present disclosure may adopt any one or more of these visual features and heuristic rules, or any other type of visual features and heuristic rules.

FIG. 12 illustrates an exemplary process 1200 for representative metadata acquisition, according to an embodiment. Process 1200 is an example implementation of step 440 in FIG. 4 . Assume that process 1200 is performed to obtain a representative set of metadata for a particular item 1202 in an original list.

At 1210, a set of leaf nodes in the project tree identified by the boundaries of project 1202 can be identified. For example, a leaf node in the project tree corresponding to project 1202 can be identified.

At 1220, an initial set of metadata corresponding to the identified set of leaf nodes can be extracted. For example, the initial metadata of each leaf node can be extracted. Taking the item marked by the dotted line box 1010 in FIG. 10 as an example, the initial metadata may include, for example, the picture in the item, the character string "M mobile phone A4, 6.5 inches, 256G, black", the icon of 5 solid stars, the character string "25900 comments", the character string "5500RMB", etc.

At 1230, a set of tags corresponding to the extracted initial set of metadata can be determined. For example, a corresponding label is determined for each initial metadata to indicate the specific meaning of the initial metadata. The set of tags can be determined at 1230 in various ways.

In one implementation manner, the set of initial metadata may be used first to form a sequence of tokens. Each term in the sequence of terms corresponds to an initial metadata in the set of initial metadata. Then, a set of features for each term in the sequence of terms can be calculated. The set of features may include various features that are helpful for determining tags, for example, DOM tree features, XPath features, content features, language features, rendering features, and the like. DOM tree features may include, for example, the hierarchical depth of the node corresponding to the term, tags, category IDs, and the like. XPath features may include, for example, the name of the node corresponding to the term, a CSS class, and the like. Content features may include, for example, the text vector of the entry, whether the first letter is capitalized, and so on. The language feature may include, for example, the language used by the entry, the Word2vec semantic feature vector of the entry, and the like. The rendering features may include, for example, various features involved in rendering the node corresponding to the entry, such as position, length, width, and so on. It should be understood that the embodiments of the present disclosure are not limited to the exemplary features included in the set of features given above, but may cover any other features or any combination of these features. A tag for each entry may be generated based on multiple feature sets of multiple entries in the sequence of entries by using a pre-trained tagger model. Exemplarily, the marker model can be a combined model formed by a discriminative model and a generative model, wherein the discriminative model can be, for example, a binary or multi-class model, and the generative model can be, for example, a sequence-to-sequence (Seq2seq) model. It should be understood that the embodiments of the present disclosure are not limited to generating labels through the above-mentioned marker model, but may also generate labels in any other manner.

Still taking the project marked by the dotted frame 1010 in Figure 10 as an example, through step 1230, an "image" tag can be generated for the pictures in the project, a "title" tag can be generated for the string "M mobile phone A4, 6.5 inches, 256G, black", a "rating" tag can be generated for the icon of 5 solid stars, a "comment" tag can be generated for the string "25900 comments", and a "price" tag can be generated for the string "5500RMB".

At 1240, the set of initial metadata can be sorted using the generated set of tags. In an implementation manner, a keyword ranking model can be pre-trained, which can be used to rank a set of tags serving as keywords. For example, the keyword ranking model can be trained to rank multiple tags according to, for example, degree of importance, representativeness, and the like. As an example, for image tags, title tags, rating tags, review tags, price tags, etc., by sorting at 1240, these tags may be sorted from high to low, such as image tags, title tags, price tags, rating tags, review tags, etc. Correspondingly, the initial metadata corresponding to these tags are also sorted in the same order.

At 1250 , one or more of the highest ranked initial metadata can be selected as a representative set of metadata corresponding to item 1202 .

By performing the process 1200 for each item in the original list, multiple sets of representative metadata respectively corresponding to multiple items in the original list can be obtained. The sets of representative metadata may be subsequently used to generate a structured list.

It should be understood that all steps in process 1200 are exemplary, and embodiments of the present disclosure will also encompass modifications to process 1200 in any manner.

According to an embodiment of the present disclosure, after obtaining multiple sets of representative metadata respectively corresponding to multiple items in the original list, the multiple sets of representative metadata may be visualized as a structured list. Each set of representative metadata can form a new item in the structured list. It should be understood that embodiments of the present disclosure are not limited to any particular manner of visualizing sets of representative metadata as a structured list. In one implementation, the format or layout of the structured list may be pre-defined to specify, for example, the arrangement of multiple items in the structured list (for example, horizontal arrangement, vertical arrangement, etc.), the arrangement of multiple elements in each item, the size of the items and elements, and the like. In one implementation, the format or layout of the structured list may be similar to the structure and layout of the original list, except that the structured list may include fewer items or elements than the original list.

Figure 13 illustrates an exemplary search results page 1300, according to an embodiment. Assume that the user has entered the query "M mobile phone" in the search box 1310 to indicate that he wants to obtain web search results about M mobile phones. Search results area 1320 in search results page 1300 includes a plurality of web search results. Unlike the search results shown in area 330 of FIG. 3 for web page 20 in FIG. 2 , search results area 1320 in FIG. 13 includes an exemplary structured listing 1330 generated for web page 20 in FIG. 2 . The structured listing 1330 is a simplified version of the original listing 202 in the target web page 20 , which can serve as a listing summary of the original listing 202 . The structured list 1330 still contains enough information to enable the user to intuitively and comprehensively understand the main content of the original list 202 . For example, structured list 1330 includes item 1332, item 1334, and item 1336, which respectively correspond to item 1010, item 1020, and item 1030 in the original list in target web page 20 (as shown in FIG. 10 ) and include major representative content in the corresponding items in the original list. Taking item 1332 as an example, it includes the picture, introduction and price of the mobile phone "M mobile phone A4" presented in area 22 of FIG. 2 . Therefore, by viewing the structured list 1330 in the search result area 1320, the user can intuitively and conveniently understand the main content of the target webpage 20 without, for example, clicking a link to the target webpage 20 to understand the content of the webpage. It should be understood that the search result page 1300 and the structured list 1330 in FIG. 13 are only exemplary, and embodiments of the present disclosure are not limited by this example.

FIG. 14 shows a flowchart of an exemplary method 1400 for list extraction and visualization in web pages, according to an embodiment.

At 1410, at least one anchor element group in the target webpage may be detected, the at least one anchor element group including the first anchor element group.

At 1420, boundary detection may be performed on a plurality of anchor elements in the first anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to the first original list in the target webpage.

At 1430, multiple sets of representative metadata respectively corresponding to the multiple items may be obtained from the target webpage by using boundaries of the multiple items.

At 1440, the sets of representative metadata can be visualized as a structured list.

In an implementation manner, the detecting at least one anchor element group may include: identifying a plurality of html elements satisfying anchor element constraints in the target webpage as a plurality of identified anchor elements; extracting an attribute set of each identified anchor element in the plurality of identified anchor elements from the target web page; and clustering the plurality of identified anchor elements into the at least one anchor element group based on the plurality of attribute sets of the identified anchor elements.

The anchor element constraint may include at least one of: the html element has an image tag; the html element has a title tag; and the html element represents a date. Each attribute set identifying an anchor element may include at least one of the html tag attribute, CSS category, and XPath information identifying the anchor element.

In an implementation manner, the boundary detection may include: based on the DOM tree corresponding to the target web page, synchronously performing iterative boundary expansion starting from the multiple anchor elements respectively to obtain multiple item trees respectively originating from the multiple anchor elements, wherein each item tree represents an item and includes multiple nodes, and each node corresponds to an element determined through the iterative boundary expansion.

The iterative boundary extension may include: for each item tree, in each iteration of the step, expanding to a next node and including the next node into the item tree.

The iterative boundary expansion may include at least one of: performing sibling expansion to expand from the current node to sibling nodes of the current node; and performing parent node expansion to expand to the parent node of the current node after all sibling nodes of the current node have been included in the item tree.

The boundary detection may include: determining whether iteration of the current step results in node overlap between the item tree and at least one other item tree of the plurality of item trees; and in response to determining that the node overlap occurs, stopping execution of the iteration boundary expansion and excluding nodes determined by the iteration of the current step from the plurality of item trees, respectively.

The method may further comprise: if the iteration of the current step is a sibling node expansion, performing further iteration boundary expansion on the plurality of item trees in a direction opposite to that of the iteration of the current step.

In an implementation manner, the boundary detection may include: performing a similarity check on the multiple item trees.

The similarity check may be performed in response to determining that the number of nodes in at least one of the plurality of item trees exceeds a node number threshold.

The similarity checking may comprise: calculating tree similarity between any two item trees of the plurality of item trees; dividing the plurality of item trees into at least one set of trees using at least a similarity threshold, the item trees in each set of trees of the at least one set of trees having a tree similarity between each other not lower than the similarity threshold; determining whether the number of item trees in the set of trees of the at least one set of trees containing the greatest number of item trees is below a tree number threshold; and in response to determining that the number of item trees is below the number of tree threshold, stopping The iterative boundary expansion is performed, and nodes determined through iterations of a predetermined number of previous steps are respectively excluded from the plurality of item trees.

The calculating the tree similarity may include at least one of the following: at least calculating the tree similarity using the matching weight calculated based on the CSS similarity between the root nodes of the two item trees; and calculating the tree similarity using nodes within a minimum depth level in the two item trees, the minimum depth level being defined so that the number of visible nodes within the minimum depth level of an item tree reaches a predetermined ratio of the number of all visible nodes in the item tree.

The method may further include: resetting the plurality of item trees to a state at an iteration of a predetermined previous step; and if an iteration of a next step after the iteration of the predetermined previous step is sibling node expansion, performing a further iteration boundary expansion on the plurality of item trees in a direction opposite to that of the iteration of the next step.

In one implementation, the obtaining multiple sets of representative metadata may include, for each of the plurality of items: identifying a set of leaf nodes in the item tree identified by the boundary of the item; extracting a set of initial metadata corresponding to the set of leaf nodes; determining a set of labels corresponding to the set of initial metadata; sorting the set of initial metadata using the set of labels;

The determining a set of tags may include: using the set of initial metadata to form a sequence of entries, each entry in the sequence of entries corresponds to an initial metadata in the set of initial metadata; calculating a feature set of each entry in the sequence of entries; and generating a label for each entry based on a plurality of feature sets of multiple entries in the sequence of entries through a pre-trained tagger model.

In an implementation manner, the at least one anchor element group may include a second anchor element group. The method may further include: performing boundary detection on a plurality of anchor elements in the second anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to the second original list in the target web page. The method may further include, before said obtaining the plurality of sets of representative metadata, or before visualizing the plurality of sets of representative metadata into a structured list: using boundaries of items in the first original list and boundaries of items in the second original list, respectively determining visual features of the first original list and visual features of the second original list;

The visual features may include at least one of: minimum border distance between adjacent items; list position; and item content richness.

In one implementation, the structured list may be presented in a search results page provided by a search service.

It should be understood that the method 1400 may also include any steps/processes for list extraction and visualization in web pages according to the above-mentioned embodiments of the present disclosure.

Fig. 15 shows an exemplary apparatus 1500 for list extraction and visualization in web pages according to an embodiment.

The apparatus 1500 may include: an anchor element group detection module 1510, configured to detect at least one anchor element group in the target webpage, the at least one anchor element group comprising a first anchor element group; a boundary detection module 1520, configured to perform boundary detection on a plurality of anchor elements in the first anchor element group, to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to the first original list in the target webpage; a representative metadata obtaining module 1530, configured to use the boundaries of the plurality of items, from the Multiple sets of representative metadata respectively corresponding to the multiple items are obtained from the target webpage; and a representative metadata visualization module 1540, configured to visualize the multiple sets of representative metadata as a structured list.

In addition, the apparatus 1500 may also include any other modules configured to perform any operations of the method for extracting and visualizing a list in a web page according to the above-mentioned embodiments of the present disclosure.

Fig. 16 shows an exemplary apparatus 1600 for list extraction and visualization in web pages according to an embodiment.

Apparatus 1600 may include at least one processor 1610 . The apparatus 1600 may further include a memory 1620 connected to at least one processor 1610 . The memory 1620 may store computer-executable instructions. When the computer-executable instructions are executed, at least one processor 1610: detects at least one anchor element group in the target webpage, and the at least one anchor element group includes a first anchor element group; performs boundary detection on a plurality of anchor elements in the first anchor element group, so as to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, and the plurality of items correspond to the first original list in the target webpage; corresponding sets of representative metadata; and visualizing the sets of representative metadata as a structured list. In addition, at least one processor 1610 may also be configured to perform any other operations of the method for list extraction and visualization in a web page according to the above-mentioned embodiments of the present disclosure.

Embodiments of the present disclosure propose computer program products for list extraction and visualization in web pages. The computer program product includes a computer program, the computer program being run by at least one processor to: detect at least one anchor element group in a target web page, the at least one anchor element group including a first anchor element group; perform boundary detection on a plurality of anchor elements in the first anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to a first original list in the target web page; use the boundaries of the plurality of items to obtain from the target web page multiple sets of representative metadata corresponding to the plurality of items; Representative metadata is visualized as a structured list. In addition, the computer program may also be executed by the at least one processor to perform any other operations of the method for extracting and visualizing a list in a webpage according to the above-mentioned embodiments of the present disclosure.

Embodiments of the present disclosure can be embodied on a non-transitory computer readable medium. The non-transitory computer-readable medium may include instructions that, when executed, cause one or more processors to execute any steps/processes of the method for list extraction and visualization in webpages according to the above-mentioned embodiments of the present disclosure.

It should be understood that all operations in the methods described above are exemplary only, and the present disclosure is not limited to any operations in the methods or the order of these operations, but should cover all other equivalent transformations under the same or similar concept.

In addition, the articles "a" and "an" as used in this specification and the appended claims should generally be construed to mean "one" or "one or more" unless otherwise specified or clear from the context to refer to a singular form.

It should also be understood that all modules in the apparatus described above may be implemented in various ways. These modules may be implemented as hardware, software, or a combination thereof. Furthermore, any of these modules may be functionally further divided into sub-modules or grouped together.

Processors have been described in connection with various apparatus and methods. These processors may be implemented using electronic hardware, computer software, or any combination thereof. Whether such processors are implemented as hardware or software will depend upon the particular application and overall design constraints imposed on the system. As examples, a processor, any portion of a processor, or any combination of processors presented in this disclosure may be implemented as a microprocessor, microcontroller, digital signal processor (DSP), field programmable gate array (FPGA), programmable logic device (PLD), state machine, gate logic, discrete hardware circuits, and other suitable processing components configured to perform the various functions described in this disclosure. The functionality of a processor, any portion of a processor, or any combination of processors given in this disclosure may be implemented as software executed by a microprocessor, microcontroller, DSP, or other suitable platform.

Software shall be taken broadly to mean instructions, instruction sets, code, code segments, program code, programs, subroutines, software modules, applications, software applications, software packages, routines, subroutines, objects, threads of execution, procedures, functions, etc. The software may reside on a computer readable medium. The computer readable medium can include, for example, memory, which can be, for example, a magnetic storage device (e.g., hard disk, floppy disk, magnetic strip), an optical disk, a smart card, a flash memory device, random access memory (RAM), read only memory (ROM), programmable ROM (PROM), erasable PROM (EPROM), electrically erasable PROM (EEPROM), registers, or a removable disk. Although memory is shown as being separate from the processor in various aspects of the present disclosure, memory may also be located internal to the processor (eg, cache or registers).

The above description is provided to enable any person skilled in the art to practice the various aspects described herein. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects. Accordingly, the claims are not intended to be limited to the aspects shown herein. All structural and functional equivalents to the elements of the described aspects of this disclosure that are known or come to be known to those skilled in the art are intended to be covered by the claims.

Claims (20)

1. A method for list extraction and visualization in a web page, comprising:

detecting at least one anchor element group in a target webpage, wherein the at least one anchor element group comprises a first anchor element group;

performing boundary detection on a plurality of anchor elements in the first anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to a first original list in the target webpage;

obtaining multiple groups of representative metadata corresponding to the multiple items respectively from the target webpage by utilizing boundaries of the multiple items; and

the plurality of sets of representative metadata are visualized as a structured list.

2. The method of claim 1, wherein the detecting at least one anchor element group comprises:

identifying a plurality of html elements meeting anchor element constraints in the target webpage as a plurality of identified anchor elements;

extracting an attribute set of each identified anchor element in the plurality of identified anchor elements from the target webpage; and

the plurality of identified anchor elements are clustered into the at least one anchor element group based on a plurality of attribute sets of the plurality of identified anchor elements.

3. The method of claim 2, wherein,

the anchor element constraint includes at least one of: html elements have image tags; html elements have a title tag; and html element represents date, and

the attribute set of each identified anchor element comprises at least one of html tag attribute, CSS category and XPath information of the identified anchor element.

4. The method of claim 1, wherein the boundary detection comprises:

based on a Document Object Model (DOM) tree corresponding to the target web page, performing iterative boundary expansion synchronously with the plurality of anchor elements as starting points, respectively, to obtain a plurality of item trees respectively derived from the plurality of anchor elements, wherein each item tree represents an item and comprises a plurality of nodes, and each node corresponds to an element determined via the iterative boundary expansion.

5. The method of claim 4, wherein the iterative boundary extension comprises:

for each item tree, in each iteration of steps, expanding to and including the next node into the item tree.

6. The method of claim 5, wherein the iterative boundary extension comprises at least one of:

Performing sibling node expansion to expand from the current node to the sibling node of the current node; and

parent node expansion is performed to expand to the parent node of the current node after all sibling nodes of the current node have been included in the item tree.

7. The method of claim 5, wherein the boundary detection comprises:

determining whether an iteration of the current step results in node overlap between the item tree and at least one other item tree of the plurality of item trees; and

in response to determining that the node overlap occurs, the iterative boundary expansion is stopped and nodes determined by the iteration of the current step are respectively excluded from the plurality of item trees.

8. The method of claim 7, further comprising:

if the iteration of the current step is a sibling expansion, a further iteration boundary expansion is performed on the plurality of item trees in a direction opposite to the direction of the iteration of the current step.

9. The method of claim 4, wherein the boundary detection comprises:

and performing similarity checking on the plurality of item trees.

10. The method of claim 9, wherein,

The similarity check is performed in response to determining that a number of nodes in at least one item tree of the plurality of item trees exceeds a node number threshold.

11. The method of claim 9, wherein the similarity test comprises:

calculating tree similarity between any two item trees in the plurality of item trees;

dividing the plurality of item trees into at least one tree set using at least a similarity threshold, the item trees in each of the at least one tree set having a tree similarity between each other that is not below the similarity threshold;

determining whether a number of item trees in a tree set of the at least one tree set that includes a maximum number of item trees is below a tree number threshold; and

in response to determining that the number of item trees is below the tree number threshold, the iterative boundary expansion is stopped and nodes determined by a predetermined number of iterations of the previous step are each excluded from the plurality of item trees.

12. The method of claim 11, wherein the computation tree similarity comprises at least one of:

calculating the tree similarity using at least matching weights calculated based on CSS similarity between root nodes of the two item trees; and

Calculating the tree similarity using nodes in the two item trees that are within a minimum depth level, the minimum depth level being defined such that: the number of visible nodes within the minimum depth level of an item tree reaches a predetermined proportion of the number of all visible nodes in the item tree.

13. The method of claim 11, further comprising:

resetting the plurality of item trees to a state at an iteration of a predetermined previous step; and

if the iteration of the next step subsequent to the iteration of the predetermined previous step is a sibling expansion, then a further iteration boundary expansion is performed on the plurality of item trees in a direction opposite to the direction of the iteration of the next step.

14. The method of claim 1, wherein the obtaining multiple sets of representative metadata comprises, for each item of the plurality of items:

identifying a set of leaf nodes in an item tree identified by a boundary of the item;

extracting a set of initial metadata corresponding to the set of leaf nodes;

determining a set of tags corresponding to the set of initial metadata;

sorting the set of initial metadata with the set of tags; and

One or more of the highest ranked initial metadata is selected as a representative set of metadata corresponding to the item.

15. The method of claim 14, wherein the determining a set of tags comprises:

forming a sequence of terms using the set of initial metadata, each term in the sequence of terms corresponding to one of the set of initial metadata;

calculating a feature set of each entry in the sequence of entries; and

the tag of each term is generated based on a plurality of feature sets of a plurality of terms in the sequence of terms by a pre-trained tagger model.

16. The method of claim 1, wherein,

the at least one anchor element group includes a second anchor element group,

the method further comprises the steps of: performing boundary detection on a plurality of anchor elements in the second anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to a second original list in the target webpage, and

the method further includes, prior to obtaining the plurality of sets of representative metadata, or prior to visualizing the plurality of sets of representative metadata as a structured list: determining visual features of the first original list and the second original list respectively by utilizing boundaries of items in the first original list and boundaries of items in the second original list; and determining that the first original list is a master list of the first original list and the second original list based on the visual features of the first original list and the visual features of the second original list.

17. The method of claim 16, wherein,

the visual features include at least one of: minimum boundary distance between adjacent items; list location; item content richness.

18. The method of claim 1, wherein,

the structured list is presented in a search results page provided by a search service.

19. An apparatus for list extraction and visualization in web pages, comprising:

at least one processor; and

a memory storing computer-executable instructions that, when executed, cause the at least one processor to:

detecting at least one anchor element group in a target webpage, the at least one anchor element group including a first anchor element group,

performing boundary detection on a plurality of anchor elements in the first anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to a first original list in the target webpage,

obtaining a plurality of groups of representative metadata corresponding to the plurality of items respectively from the target webpage by utilizing boundaries of the plurality of items, and

the plurality of sets of representative metadata are visualized as a structured list.

20. A computer program product for list extraction and visualization in web pages, comprising a computer program for execution by at least one processor for:

detecting at least one anchor element group in a target webpage, wherein the at least one anchor element group comprises a first anchor element group;

performing boundary detection on a plurality of anchor elements in the first anchor element group to obtain boundaries of a plurality of items respectively associated with the plurality of anchor elements, the plurality of items corresponding to a first original list in the target webpage;

obtaining multiple groups of representative metadata corresponding to the multiple items respectively from the target webpage by utilizing boundaries of the multiple items; and

the plurality of sets of representative metadata are visualized as a structured list.