Method and system using information written in a wrapper description language to execute query on a network

Abstract

This invention provides assistance to a user in accessing network attached information sources. In one aspect, the invention is a method for intelligently routing a user query to information sources relevant to that query, extracting relevant data fields from received responses, and intelligently presenting the extracted data in order of estimated relevance. The system of this invention implements one or more steps of the method in a centralized or distributed manner on one or more network attached computers. Further, this invention provides a novel language and implementation that facilitates easily written and maintained descriptions of information source query and response formats.

Claims

What is claimed is:

1. A wrapper description language method comprising recognizing a string by scanning the string as a regular expression written in a regular expression language, the regular expression language capable of specifying an entire regular expression in terns of component regular expressions such that, upon recognition of one component regular expression of the entire regular expression, actions can be executed with variables bound as of the time of recognition of the component regular expression, the actions actually being executed only if the entire regular expression is also recognized.

2. The wrapper description language method of claim 1 further comprising the step of executing one or more statements written in an action language, the action language capable of specifying the actions of operators on variables, the actions of functions on variables, and of the sequence of statements the statements of the action language being further capable of being embedded in the regular expression language for specifying the actions occurring on the recognition of the component regular expressions.

3. A computer readable medium containing computer executable instructions for causing one or mote computers to perform a wrapper description language method comprising recognizing a string by scanning the string as a regular expression written in a regular expression language, the regular expression language capable of specifying an entire regular expression in terms of component regular expressions such that, upon recognition of one component regular expression of the entire regular expression, actions can be executed with variables bound as of the time of recognition of the component regular expression, the actions actually being executed only if the entire regular expression is also recognized.

4. A computer program product stored on a computer readable medium, and including computer executable instructions for causing one or more computers to interpret strings written in a regular expression language by, performing the steps of:

receiving a string written in the regular expression language;

scanning the string to recognize a plurality of component regular expressions;

binding variables defined in thc component regular expressions as the component regular expressions are recognized: and

upon recognition of an entire regular expression containing the plurality of recognized component regular expressions, executing at least one action using the bound variables from the component regular expressions.

Description

1. FIELD OF THE INVENTION

The field of this invention relates to information access over networks, and specifically to the automatic location and evaluation of relevant information available over public or private networks from information sources in response to user queries.

2. BACKGROUND

The exponential growth of private intranets and the public Internet has produced a daunting labyrinth of increasingly numerous documents, databases and utilities. Almost any type of information is now available somewhere, but most users cannot find what they seek, and even expert users waste copious time and effort searching for appropriate information sources. One problem is simply the increasingly large number of available information sources that are beyond the comprehension of a single user. A second problem, along with this growth in available information and information sources, is a commensurate growth in software utilities and methods to manage, access, and present this information. Each utility has a different and often unique interface and set of commands and capabilities, and is appropriate for a different set of users and a different set of information types and sources. Thus sheer diversity of available utilities creates problem for users comparable to that created by information explosion. Users are now faced with the twin problems of which tool to use to inquire at which information source.

In the past efforts have been made to provide users with automatic, computer assisted services that can help solve these twin problems of the network revolution. For example, AI researchers have created several prototype software agents that help users with e-mail and netnews filtering (Pattie Maes et al., 1993, Learning interface agents, Proceedings of AAAI-93), agents that assist with World Wide Web browsing (H. Lieberman, 1995, Letizia: An agent that assists web browsing, Proc. 15th Int. Joint Conf. on A.I. pp. 924-929; Robert Armstrong et al., 1992, Webwatcher: A learning apprentice for the world wide web, Working Notes of the AAAI Spring Symposium: Information Gathering from Heterogeneous, Distributed Environments, pp. 6-12, Stanford University, AAAI Press), agents that schedule meetings (Lisa Dent et al., 1992, A personal learning apprentice, Proc. 10th Nat. Conf. on A.I., pp. 96-103; Pattie Maes, 1994, Agents that reduce work and information overload, Comm. of the ACM 37(7):31-40, 146; Tom Mitchell et al., 1994, Experience with a learning personal assistant, Comm. of the ACM 37(7):81-91), and agents that perform internet-related tasks (0. Etzioni et al., 1994, A softbot-based interface to the internet, CACM, 37(7):72-75). Increasingly, the information such agents need to access is available on the World Wide Web. Unfortunately, even a domain as standardized as the WWW has turned out to pose significant problems for automatic software agents. For one, although Web pages are universally written in Hypertext Markup Language ("HTML"), this language merely defines the format of information display, making no attempt to hint at its meaning or semantic content. Currently, no accepted "semantic markup language" for the Web exits, nor is one likely to adopted universally. The Internet can be expected to pose even greater problems.

Thus, the advent of intranets, the Internet, and the World Wide Web have posed several fundamental problems for the automatic services or agents designed to assist users to find relevant information. First, no one such service has heretofore provided sufficient additional value to replace the use of a Web browser having access to existing directories and indices such as Yahoo or Lycos. Second, such services have not yet been able to understand and competently parse relevant information from the responses returned from a wide variety of Internet and Web information sources. Third, existing services and agents have not been easy to adapt to the ever-increasing numbers of sources with their ever-changing response formats. This is due to the individualized, hand-coded interface to each Internet service and Web site utilized by existing agents (Yigal Arens et al., 1993, Retrieving and integrating data from multiple information sources, International Journal on Intelligent and Cooperative Information Systems 2(2):127-158; 0. Etzioni et al., 1994, A softbot-based interface to the internet, CACM 37(7):72-75; B. Krulwich, 1995, Bargain finder agent prototype, Technical report, Anderson Consulting; Alon Y. Levy et al., 1995, Data model and query evaluation in global information systems, Journal of Intelligent Information Systems, Special Issue on Networked Information Discovery and Retrieval 5(2); Mike Perkowitz et al., 1995, Category translation: Learning to understand information on the internet, Proc. 15th Int. Joint Conf. on A.I.). Preferably, a service or agent should be able to access a new or changed Internet information source in order to automatically learn how to retrieve relevant information from the source. This would be advantageous even if such a facility were limited to groups of sources with response formats selected according to certain constraining principles.

3. SUMMARY OF THE INVENTION

It is a broad object of this invention to solve these fundamental problems by a method and system that provide a personalized network robot, called a "netbot." A netbot acts as a user's intelligent assistant by tracking available network information sources, knowing the relevant information and features of each particular source, and upon user request determining which sources are relevant to a given query, forwarding the query to the most relevant information sources, understanding the responses returned from each source, and integrating and intelligently presenting the query results to the user.

The netbots of this invention possess several advantages, including the following. First, a netbot returns only the most relevant information to the user. On the one hand, each user query is forwarded only to the primary information sources determined to be most relevant. On the other hand, information source responses are parsed and understood so that only the relevant data items are extracted for user presentation. Duplicate, stale, and irrelevant information items are discarded. Second, a netbot is fast. Since it automatically searches the relevant primary sources in parallel, it can present information as quickly as the fastest primary source returns a response. Despite changing conditions which cause different information sources to fluctuate in speed, a netbot integrator remains as fast as the fastest source. Sources that have no information to return to a query do not slow the user since the netbot simply ignores them. Third, netbots are easily adapted to the ever-increasing number of network information sources with ever-changing response formats. Netbots utilize a new and novel declarative language for describing information sources. A source description is short and easily understandable, and therefore is easily written and maintained.

Therefore, in one aspect the invention includes a method for efficient access to information sources on a network comprising preferably ana or more of the following steps: receiving a user query for information; determining the information sources most relevant to this query; retrieving a description of each information source; formatting the query according to this description in a manner suitable for each information source and transmitting the formatted query to the source; receiving responses from the information sources; for each source, understanding and extracting the relevant data fields according to the retrieved description; and presenting to the user the relevant data from each information source in an intelligent manner ranked by an estimate of its relevance. Advantageously, these steps are performed in parallel to the greatest extent possible. In particular, at least, all queries are transmitted to all relevant information sources in parallel without waiting for intervening responses.

In another aspect the invention comprises a computer system and apparatus for performing one or more steps of the method of this invention. The user has a presentation device attached to a network to which is also attached a plurality of information sources. The presentation device receives user queries and displays netbot responses. Further, the presentation device performs one or more of the steps of the method of this invention. One or more of those steps not performed on this device can advantageously be performed on network attached netbot server computers, which respond to functional requests from the user device. Optionally, the user device can range from a diskless hand-held terminal, to a PC, to a workstation, and so forth.

In a further aspect the invention comprises a new language and language implementation to facilitate the creation and maintenance of descriptions of information sources. Importantly, this language recognizes relevant data fields in responses returned from information sources and is capable of extracting all such fields. In the preferred embodiment this language has an action statement component and a regular expression component. The regular expression component has novel features for creating modular hierarchical descriptions of regular expressions, for binding variables to the correct sub-strings recognized during pattern match to a response of an information source, for performing arbitrary action language statements with multiple variable bindings, and for specifying backtrack free recognition of sub-strings where possible.

4. BRIEF DESCRIPTION OF THE DRAWINGS

These and other features, aspects, and advantages of the present invention will become better understood by reference to the accompanying drawings, following description, and appended claims, where:

FIG. 1 illustrates generally a netbot of this invention;

FIGS. 2A-B illustrate exemplary user interfaces of embodiments of the netbot of FIG. 1;

FIG. 3 illustrates exemplary functional components of the netbot of FIG. 1; and

FIG. 4 illustrates alternative hardware embodiments of the netbot of FIG. 1 .

5. DETAILED DESCRIPTION

For clarity of disclosure, and not by way of limitation, the detailed description of a netbot of this invention is presented as a method or process for network information access, as a system or apparatus implemented to perform that method, and as a novel language designed to assist in implementing this method and system.

In the following, first an overview of these aspects of the invention is presented followed, second, by a detailed discussion of individual components.

5.1. OVERVIEW OF NETBOT ARCHITECTURE

A netbot method or system of this invention comprises software and hardware facilities that function together in one or more network attached computers to assist a user in access to information present in network attached servers (known herein as "information sources"). FIG. 1 generally illustrates the relationships of a netbot to a user and to networked information sources. For example, user 1 accesses user computer 3 through standard interface devices, such as monitor 2. In the course of work, the user needs information from information sources 7, attached to the user computer through various network links, such as network links 4 and 6. Since the information sources are many, the user can benefit from assistance in finding needed information from relevant information sources. This assistance is provided by netbot 5, which maintains an awareness of available information sources and queries them through links 6 on behalf of, or as an agent of, the user. Alternatively, netbot 5 can partly or wholly reside on user computer 3 or be partially or wholly distributed on the network and accessed by the user through link 4.

Groups of sources 7 having similar sorts of information are grouped into conceptual classes called information domains. For example, one domain can be that of electronic stores for a particular product; another domain might include Internet indexes containing information on the keyword content of various World Wide Web ("WWW") pages.

In a preferred embodiment, the netbot is composed of three major functional modules: a user interface, an integrator, and an I/O manager. Briefly, the user interface module interacts with the user to receive user queries for information, and to format and present information responses received from the network attached information sources. Advantageously, the user interface is adapted to the specific information domain being accessed. The integrator module accepts a user query from the user interface module, selects relevant information sources, formats it for network transmission to each relevant information source, receives responses from these sources, understands these responses, and passes the relevant portions of the responses back to the user interface module for display to the user. The I/O manager module performs hardware, operating system, and network specific interfacing for the user interface and integrator modules so that porting a netbot to different hardware platforms, operating systems, or networks requires changes only in well-modularized code.

In particular alternative implementations, either or both of the user interface or the I/O manager modules may be absent. For example, the functions of these modules might be already performed by other operating system components. A netbot can be provide only one or more of the facilities disclosed without providing others. For example, in some embodiments, a netbot is useful that preforms query routing, alone or in combination with relevance ranking. In other embodiments, a netbot can simply format queries and understand responses. Further, additional modules may be present in or accessed by a netbot. For example, a learning module can be present which provides for a netbot to acquire automatically the characteristics of a new network information source. Finally, as is known to those of skill in the art, the functions performed by the described modules may be divided or grouped in alternative fashions among a greater or lesser number of modules.

In the absence of specific preferences, the processes of this invention can be implemented in complete procedural programming language, such as c, or a complete object oriented programming language, such as C++, on the disclosed hardware configurations.

The User Interface Module

In more detail, the user interface module has both important functionality that is common to netbot user interfaces, whatever the information domain to which netbots are directed, and also has adaptations to the particular information domain of a particular netbot. Turning first to the preferable common functions, one such is the ability to remember a user's preferences for interacting with a netbot. Such remembered preferences include, for example, whether a. netbot is to fetch pages in order to calculate their relevance itself, the number N or relevant information sources to query, display characteristics, etc. A second such common function is incremental display of information received from a query. Since each query usually causes a netbot to consult many independent information sources, results are often received at widely varying times. Immediate display of asynchronously received results would cause such undesirable effects as screen flicker or disorienting rearrangement of already displayed data. Incremental display accommodates, on the one hand, user desires to view information quickly with, on the other hand, user desires for a comprehensive view of all received information, sorted according to relevance.

The incremental display strategy preferably provides one or more windows on the user's screen with several defined views of the query satisfaction process along with certain common user controls, such as screen buttons, for manipulating these windows. In one window, the user interface module presents lists of the information sources being consulted with each source symbolically represented as, for example, a network address, an icon, or another compact screen representation. Then, as an answer is received from a particular source, its associated screen representation changes appearance, e.g., by changing intensity, changing color, etc. Also displayed is a count of the total number of unique information items received currently. Optionally, clicking on the screen representation of an information source opens a further window with either information about this information source, or a display of the responses received from it, or access to the information source over the network, etc.

One of the common controls is preferably implemented as a common show-me-button that when activated causes display of another window in which a list of all currently received responses is presented ranked according to their estimated relevance to the query. Another common control is preferably implemented as a more-button in this latter window that when activated, causes re-display of all prior data items merged with items newly received since the last window display. The newly received items are merged into the display list in order or relevance, and distinguished from prior items by, for example, their color or intensity so that the user can avoid scanning prior items again. Optionally, clicking on a data item opens a still further informational window giving either the source of the item, a display of the response containing the item, or access over the network to the source of the item, etc.

In addition to such common functions and controls, a netbot user interface module preferably implements specific designs, formatting, and fields suitable to the information domain for which it is designed. For example, a netbot for comparison shopping in an information domain of electronic stores on the Internet can have a particular interface presentation containing labeled fields for product name, model, and price. On the other hand a netbot for access to an information domain of online Internet indexes can have an interface with fields labeled with elements derived from the query.

In one netbot embodiment, most functions and modules reside on network attached servers which a user accesses remotely. For example, the user may access a netbot over the Internet with the World Wide Web protocols utilizing a web browser, such as Netscape. In this case the user interface builds HTML formatted pages which are transmitted over the network by the I/O manager. FIG. 2A generally illustrates the user display from an example of such an embodiment, which is further directed to the information domain of online, electronic software stores. The netbot display of FIG. 2A is divided into three sections. Section 11 is a title section generally indicating that this display has results from a netbot for shopping, a "ShopBot." A netbot preferably also has a specific input query screen. Section 12 presents the list of online stores currently being consulted represented by their WWW addresses 15, which are selectable to provide further information or direct WWW access. At 16 in section 12, those sources which have already returned query results are similarly represented. Section 13 presents the results received so far formatted in accordance with this particular information domain into sections for the major PC operating systems. Each individual item returned, for example item 16, is formatted with product name, price, and an address for the originating information source. In this implementation, information display is controlled with the window scrolling and control facilities built into the web browser. This user interface is implemented as a HTML formatted page created at a netbot server and transmitted to the web browser.

FIG. 2B generally illustrates the user display from another example of a web-browser-based user interface embodiment, which in this case, is directed to an information domain of WWW indexes or search engines. This display is also generally divided into three sections. Section 71 displays a title for the netbot; section 72 displays the status of the current search; and section 73 displays the search results. In more detail, the display of section 71 includes a logo for this netbot, "MC" standing for "MetaCrawler," a name chosen since WWW search engines are also known as "web crawlers," and controls to access certain. system level presentation features, such the MetaCrawler home page and user feedback pages. The display of section 72 includes list 74 of the search engines being queried identified by their common names, the status of the current query in general and at each search engine, and common user controls. Generally, pie-chart icon 78 summarizes that 7 of the 8 search engines queried have already responded to the query. At search engine 75, known as "Lycos," the check mark indicates that a response containing information items has already been received. At search engine 76, known as "Inktomi," the cross mark indicates that a response without any information items has already been received. On the other hand, search engine 77, known as "Galaxy," is visibly distinguished from the other search engines to indicate that it has not yet responded to the query. The common controls of section 72 include more-button 79 to request the display of newly arrived search results, and modify-search-button 80 to request a new or modified query be sent. Lastly, the display of section 73 includes the information items returned from the search engines. Each information item is displayed separately and includes title 81, descriptive text 82 if available, and line 83 with the URL of the web page for this item and the estimated relevance of this item to the query, here "1000."The items are sorted for display by descending values of the estimated relevance. The displayed items are scrolled using controls provided by the web browser. This user interface is implemented as a Java applet downloaded from a netbot server and executed by the web-browser. In this manner, the interface of FIG. 2B is capable of greater interactivity than that of FIG. 2A. For example, it can poll the netbot server for current search status and update the status displays accordingly without user action.

Although the user interface is described primarily in terms of windows and buttons, one of skill in the art will recognize that this invention is adaptable to other display paradigms that provide for display of information and input of user commands. For example, the user interface module can control the entire screen and present graphical displays without intervention of a windowing system.

The user interface module is preferentially implemented with an object orient programming language supplemented with a class library providing windowing functions. A preferable implementation uses the Java language together with the java.awt package. See, for example, Flanagan, 1996, Java In A Nutshell, O'Reilly & Associates, sections 5 and 19.

The Integrator Module

FIG. 3 illustrates the preferred functional modules, data bases, and their functional interrelationship of netbot 30 in general and of an integrator module 37 in particular. The integrator preferably consists of three functions: a query router 39, a wrapper database 40, and an aggregation engine 38. These components are introduced here and described in detail in the following. Given user query 31 delivered from user interface module 34, the integrator first calls query router 39 to rank the network information sources known to a netbot in order of relevance and to return the N more relevant sources. Next the integrator retrieves the N wrappers for the N most relevant sources from wrapper database 40. These wrappers, which are descriptions of the information source and its requirements, are written in the wrapper description language of this invention. The retrieved wrappers are used by aggregation engine 38, first, to format the query into forms recognized by each information source, and second, to understand the information returned by each information source 33 in order to eliminate extraneous formatting matter and to put the received information into a common format. This formatted information is then aggregated and passed to the user interface module for presentation 32 to the user according to preferred incremental display method 36. The user display is also controlled by stored user preferences 35.

The Query Router

A well-behaved netbot should preferably use scarce network bandwidth and information source processing resources in a competent and efficient and frugal manner, while at the same time best answering each user query. Such behavior minimizes resource usage, and thus achieves best overall performance, both for the individual netbot and for all netbots functioning simultaneously on a network.

The query router is important to achieving this behavior because it permits the netbot to send requests only to information sources likely to have information relevant to a query. From a user query, the query router determines the relevance of each information source to the given query and returns the N most relevant sources. N is a parameter controllable at user preference and can be as small as 1. This relevance determination is preferably over inclusive rather than under inclusive. Occasionally including an irrelevant information source is preferable to missing a relevant and important source. Further, it is preferable that this relevance determination be quick to compute, not requiring costly processing techniques.

In a preferred embodiment, the query router calculates a numerical relevance rank value for each information source that estimates the source's relevance. This calculation is based on the concept of "conceptual classes." Thus each information source is tagged in advance with the conceptual classes for which it is relevant. Then the query router maps each query to the conceptual classes relevant to it, and finds information sources with conceptual classes shared by the query. The mapping of a query to its conceptual classes is preferably done with a hash function.

Aggregation Engine

The aggregation engine is the coordinating function of the integrator module. It receives the user query from the user interface module and requests the query router to provide a list of the N information sources most relevant to the given query. Then it retrieves the N wrappers for the N information sources from the wrapper database. Guided by the N wrappers, the aggregation engine translates the query into the request formats accepted by each of the N information sources and transfers the N requests to the I/O manager for network transmission. For some sources, the query may be in the format of a form to be returned. When a response is received from an information source, the aggregation engine, again guided by the appropriate wrapper, extracts data from the response and places it into a list of data fields, called a tuple format, relevant to the particular information domain. Optionally, each tuple can be assigned a priority order using a method appropriate to the particular information domain. Finally when the incremental display manager requests data to present to the user, perhaps in response to a more-button request, the aggregation engine passes the tuples to the user interface module, sorted in priority order if a priority is determined

For example, if the information domain relates to Internet online software vendors, then the tuples optionally contain such relevant fields as product name, manufacturer, software version number, operating system required, price, etc. An exemplary priority order of the tuples can be by price, by delivery delay, or other factor at user preference.

For a further example, if the information domain relates to World Wide Web ("WWW") search engines, which index information pages available generally on the WWW, then the tuples optionally contain such relevant fields as title of the indexed page, the universal resource locator ("URL") of that page, relevance scores estimating the relation of the indexed page to the query, descriptive text, etc. An exemplary priority order can be based on the netbot's normalized estimate of the relevance of the indexed page to the query. If the netbot does not retrieve the indexed page, then it sums the normalized relevance estimates for this response that are returned from each of the search engines. If a search engine does not return a relevance estimate, a default value is used. The obtained relevance estimates are then normalized by linearly adjusting the returned scores to have a common maximum of, e.g., 1000, and then multiplying the adjusted scores by a confidence factor. This confidence factor, ranging from 0 to 1, is a predetermined estimate of the reliability of d particular information sources own relevance estimates. For example, it can be determined by practical experience with the information source's relevance estimates. Alternately, the user can request the netbot to retrieve the page in order to do its own relevance estimate. In an exemplary embodiment, for queries requesting the presence either of all query words or of any query words, the estimate is determined by scanning the page and counting the number of query words actually present, and then scaling the count so that the presence of all words results in the common maximum relevance value. For queries requesting the presence of a phrase, the estimate is determined, for example, by subtracting from the common maximum a normalized sum of the square of the distance in the page of each word of the phrase from its successor word in the phrase. Thereby, if the phrase appears contiguously in the page the relevance is high, whereas if the words of the phrase are widely separated on the page, the relevance is low.

In summary, for the majority of information domains, the priority order is determined from a relevance computation, as in the WWW search engine example. However, for certain domains such as online software vendors, a priority order can be simply determined from the values of one or more numeric fields of the response tuples.

The Wrapper Database

The preferred manner of describing information sources and their capabilities, in particular their query formats and response formats, is with compact, modular, declarative descriptions called wrappers. Since a netbot can access from several hundred to many thousands of information sources, the descriptions of the sources are preferably compact, requiring a minimum of storage. Further, since new information sources are frequently created and existing sources frequently change their format, easy maintenance of source descriptions is important. A modular, declarative description, instead of a complex procedural description, facilitates such maintenance. In one embodiment of this invention, wrappers can be learned by a separate module for information sources having sufficiently regular formats.

For each information source, in an exemplary embodiment, each wrapper advantageously includes the following information:

1. The Universal Resource Locator ("URL") address of the information source;

2. The conceptual classes of the source;

3. A description of the mapping from query arguments, e.g. words or phrases, to fields of the query or HTML defined form used to interrogate the source (including site support for any, all, phrase, or proximity queries);

4. A description of the format of the query response or HTML page layout that enables parsing of relevant information from other information and extraneous formatting matter.

At least items 3 and 4 are advantageously written in the wrapper description language of this invention.

A netbot can retrieve wrappers in various manners. In one embodiment, the information source itself can supply its own wrapper upon request from a netbot. In an alternative embodiment, the netbot can provide its own wrappers in various manners. For example, wrappers can be built in the netbot itself, especially where the netbot accesses only a few information sources. Also, wrappers can be stored in a local database or can be downloaded on demand from a centralized database.

The wrapper description language (hereinafter referred to as the "WDL") of this invention facilitates the semantic description of queries, forms, and pages by using a declarative description format that combines features from grammars and regular expressions. Here an example of this description language is presented. A detailed description is set forth in a later section. Syntax used follows conventions known to those of skill in the art for specifying grammars, including regular expressions. See, e.g., Schwartz, 1993, Learning Perl, O'Reilly & Associates, Inc., chapter 7; Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co., section 3.3

An exemplary description in WDL of a typical page returned from an WWW search engine follows here. The WDL interpreter uses the page description to parse a page and to execute any specified action statements. Note that "stuff" is a reserved word in the WDL that matches any character string up to the first occurrence of a mandatory following string literal.

    ______________________________________
    <page>::= stuff "<dl>" <item>* .*$
    <item>::= stuff "<dt>" stuff "=$"" (stuff) "$"><strong>"
    (stuff) "</strong></a>" stuff "<dd>" (stuff)
    "<br>" { output($0, $1, $2, 500) }
    ______________________________________

    ______________________________________
    Input:
          List of K sources with their confidence rank pairs
          (source.sub.-- k, crank.sub.-- k), obtained from the query
          routing system; K ordered lists of tuples,
          tuples.sub.-- k, of length length.sub.-- k, obtained from source
          source.sub.-- k; and the verification flag V (Boolean),
          obtained from user preferences
    Output:
          Merged list of all tuples sorted by relevance.
    /* Main routine */
    IF (V is true) THEN
    FOREACH k = 1 . . . K
    FOREACH tuple t n tuples.sub.-- k
    page = the HTML page that tuple t points to,
    downloaded if necessary
    t.score = Analyze(page);,
    ELSE /* V is false */
    FOREACH k = 1 . . . K
    NormalizeScores (tuples.sub.-- k)
    AdjustByHeight (tuples.sub.-- k)
    AdjustByServiceRanking(tuples.sub.-- k)
    /* Merge result tuples, t, into MERGED.sub.-- LIST and
    determine a composite relevance score, t.score, from the
    scores returned by the information sources,
    t.sourcescore.sub.-- k; the same tuple returned from multiple
    sources has its composite score incremented by the
    source score from each source */
    FOREACH k = 1 . . . K
    FOREACH tuple t in tuples.sub.-- k
    IF t is not in the MERGED.sub.-- LIST THEN
    Add t to the MERGED.sub.-- LIST
    t.score = t.sourcescore.sub.-- k
    ELSE
    t.score = t.score + t.sourcescore.sub.-- k
    ENDIF
    ENDIF
    SORT all tuples t by. t.score and discard duplicates
    OUTPUT sorted tuples
    EXIT /* finished relevance ranking */
    /* Subroutines */
    SUBROUTINE NormalizeScores (tuples.sub.-- k)
    /* If information source.sub.-- k returns relevance estimates,
    normalize them to fall in the range from 0 to 1000;
    otherwise, use a default relevance estimate */
    /* "s" is the k'th information source's relevance score
    for the first tuple on the list of tuples from source.sub.-- k
    */
    s = tuples.sub.-- k[1].sourcescore.sub.-- k
    IF (s == 0) THEN
    /* this information source returns no scores,
    therefore use default */
    FOREACH tuple t in tuples.sub.-- k
    t.sourcescore.sub.-- k = 1000
    ELSE
    scaling.sub.-- factor = 1000.0 / s;
    FOREACH tuple t in tuples.sub.-- k
    t.sourcescore.sub.-- k = t.sourcescore.sub.-- k *
    scaling factor;
    ENDIF
    ENDSUB
    SUBROUTINE AdjustByHeight (tuples.sub.-- k)
    /* Adjust the source scores to have a uniform percentile
    distribution; for example for 10 tuples, the first tuple's.
    source score is adjusted to 100% of its source score, the
    second tuple's source score is adjusted to 90% of its source
    score, etc. */
    percent.sub.-- step = 100 / Length.sub.-- k;
    percent.sub.-- off = 0;
    FOREACH tuple t in tuples.sub.-- k
    t.sourcescore.sub.-- k = t.sourcescore.sub.-- k * (100 -
    percent.sub.-- off) / 100;
    percent.sub.-- off = percent.sub.-- off + percent.sub.-- step;
    ENDSUB
    SUBROUTINE AdjustByServiceRanking (tuples.sub.-- k)
    /* Each Service is assigned a percentile ranking indicating
    the confidence given to its returned source scores; this
    ranking is used to scale the returned source scores for each
    tuple; for example, a 90% confidence ranking means that each
    source score is scaled by 0.9 */
    FOREACH tuple t in tuples.sub.-- k
    t.sourcescore k = t.sourcescore.sub.-- k * crank.sub.-- k
    ENDSUB
    ______________________________________

    ______________________________________
    For i from 0 to C. do:
    If (i-th bit of V is '1') THEN
            FOR j = 1 to S DO
            RELEVANCE[j] = RELEVANCE[j] +
                CONCEPT2SOURCE[i,j]
    ______________________________________

    ______________________________________
    For i from 0 to C, do:
    If (i-th bit of V is '1') THEN
            FOR j = 1 to S DO
            RELEVANCE[j] = CONCEPT2PHRASE[i,j]
    ______________________________________

    ______________________________________
    FOR i equals 1 to the number of elements in KEYS[ ], DO
    Apply the previously used hash function to KEYS[i]
           to obtain a number between 0 and W
    SET the bit matching the current concept in
    WORD2CONCEPT[M].
    FOR j equals 1 to the number of elements in PHRASES[ ],
    DO
    Apply the previously used hash function to KEYS[i]
           to obtain a number between 0 and W
    SET the bit matching the current concept in
           WORD2CONCEPT[M].
    ______________________________________

    ______________________________________
    $url    =     "http://searcher.source.com/searcher.cgi?query
                  =" . $keywords . "&onlyrr=0";
    ______________________________________

    ______________________________________
    <page>     ::=   stuff 'results returned, ranked by'
                     <item> * END
    ______________________________________

    ______________________________________
    <item>   ::=   stuff '<hr>' stuff '<center><b><a href="'
                   (stuff) '"' stuff '>' (stuff) '</a>'
                   stuff '<font size=-1>' (stuff) '</font>'
                   { output ($0, $1, $2, 500); } END
    ______________________________________

    ______________________________________
    Statement ::=
    $VariableName "=" Expression ";"
    .linevert split.
            "if" Expression Statement [ "else" Statement ]
    .linevert split.
            "while" Expression Statement
    .linevert split.
            "{" Statement* "}"
    .linevert split.
            "output" "(" [ Expression {","Expression }* ] ")" ";"
    Expression ::=
    string-constant
    .linevert split.
            float-constant
    .linevert split.
            $variableName
    .linevert split.
            Expression op Expression
    .linevert split.
            "(" Expression ")"
    .linevert split.
            functionName "(" [ Expression {","Expression }*
    ______________________________________
            ] ")"

    ______________________________________
    <head>       ::= "Results of your search:.backslash.n" END;
    <item>       ::= "Data: . . ..backslash.n" END;
    <tail>       ::= "No more results.backslash.n" END.
    ______________________________________

    ______________________________________
    <page>       ::= "Results of your search:$n" ("Data:
                 . . .$n")* "No more results$n" END
    ______________________________________

    ______________________________________
    Rule         ::= <nonterminal> "::="Regexp "END"
    Regexp       ::= Sequence (".vertline." Sequence )*
    Sequence     ::= Repetition+
    Repetition   ::= Term "?"
                 .vertline. Term "*"
                 .vertline. Term "+"
                 .vertline. Term
    Term         ::= String.sub.-- In.sub.-- Double.sub.-- Quotes
    .vertline. "stuff"
    .vertline. "("Regexp")"
    .vertline. <nonterminal>
    .vertline. Action
    Action       ::= "{" Statement* ")"
    ______________________________________

    ______________________________________
    <page>       ("dave") ("bill") <a> ("dan") {
                 output($2); } END
    <a>          "oren" (stuff "cody") {output($0); } END
    ______________________________________

    ______________________________________
    <page>       ("dave") ("bill") "oren" (stuff "cody") {
                 output($0); } ("dan") { output($2); }
    ______________________________________

    ______________________________________
    <page>       ::= ("dave") ("bill") "oren" (stuff "cody") {
                 output($2); } ("dan") { output($3); }
    ______________________________________

    ______________________________________
    FOR nonterminal PERFORM a POSTORDER traversal of its
    parse tree
    At each parse tree node v
    IF (v=Sequence<c.sub.-- 1, . . . , c.sub.-- n>) THEN
    WHILE (there is an i, 1<=i<=n, such that
    c.sub.-- i=Sequence<d.sub.-- 1, . . . , d.sub.-- m>) DO
    Replace node v with a new node
    Sequence <c.sub.-- 1, . . . , c.sub.-- i-1, d.sub.-- 1, . . . ,
    d.sub.-- m, c.sub.-- i+1, . . . , c.sub.-- n>
    ______________________________________

    ______________________________________
    FOR nonterminal PERFORM a POSTORDER traversal of its
    parse tree.
    At each node v of the parse tree
    IF (v=Sequence<c.sub.-- 1, . . . , c.sub.-- n>) THEN
    WHILE (there is an i, 1<=i<=n, such that
    c.sub.-- i=Stuff<>) Do
    Let j be the smallest j>i such that
    c.sub.-- j=String<s>for some string s.
    IF there is no such j THEN signal an
    error.
    ELSE IF (any element ck (where i<k<j) is
    NOT either an OpenParenthesis or
    CloseParenthesis) THEN signal an
    error
    /* cj is node for the string */
    ELSE replace node v with a new node =
    Sequence <c.sub.-- 1, . . . , c.sub.-- i-1,
    Stuff.sub.-- And.sub.-- String<c.sub.-- j; c.sub.-- i+1, . . . ,
    c.sub.-- j-1>, c.sub.-- j+1, . . . , c.sub.-- n>
    ______________________________________

    ______________________________________
    GLOBAL VARIABLE integer PAREN.sub.-- COUNT;
    FUNCTION EXPAND.sub.-- REGEXP ( <nt>: nonterminal) : RETURNS a
    parse tree with renumbered variables
    /* an array of integers with new variable numbers
    /*
    LOCAL VARIABLE new.sub.-- names[]
    LET T = parse tree for the RHS of rule for <nt>
    PERFORM a PREORDER traversal of T.
    At each node v of tree T
    IF (v=OpenParenthesis<i>) THEN
    new.sub.-- names[i] = PAREN.sub.-- COUNT;
    REPLACE node v with
    OpenParenthesis<PAREN.sub.-- COUNT>
    PAREN.sub.-- COUNT = PAREN COUNT + 1;
    ELSE IF (v=CloseParenthesis<i>) THEN
    REPLACE node v with
    CloseParenthesis<new.sub.-- names[i]>
    ELSE IF (v=Nonterminal<x>) THEN
    REPLACE node v with EXPAND.sub.-- REGEXP(x)
    ELSE IF (v=Action<x>) THEN
    REPLACE node v with EXPAND.sub.-- ACTION (x,
    new.sub.-- names[])
    FUNCTION EXPAND.sub.-- ACTION (T : parse tree T for action
    language statement; new.sub.-- names[]) : RETURNS a parse
    tree with renumbered variables
    PERFORM a PREORDER traversal of the parse tree T.
    At each node v,
    IF (v denotes variable name $i (i an integer)
    THEN
    REPLACE node v with a new node with $i
    replaced by $(new.sub.-- names[i]).
    ______________________________________

    ______________________________________
    PERFORM a POSTORDER traversal of the tree.
    At each node v, Do:
    IF (v=OpenParenthesis<n>) THEN
    SET v.machine = Marker<n, "open", 0,
    Success<>>
    ELSE IF (v=CloseParenthesis<n>) THEN
    SET v.machine = Marker<n, "close", 0,
    Success<>>
    ELSE IF
    (v=Action<node.sub.-- for.sub.-- the.sub.-- action.sub.-- language.sub.--
    statements>)
    THEN
    SET v.machine =
    Action<compiled.sub.-- action.sub.-- statements,
    Success<>>
    ELSE IF (v=String<literal.sub.-- string>) THEN
    SET len = length (the-string)
    FOR i = 1 to len DO
    branch.sub.-- state[i] = Char.sub.-- branch <s.sub.-- 0, s.sub.-- 1,
    . . . , s.sub.-- 255>, where all the s.sub.-- j's are
    Failure<>EXCEPT the s.sub.-- j where j is
    the ASCII code for the i'th
    character of the-string which is
    Success<>
    SET v.machine = MAKE.sub.-- SEQUENCE
    (branch.sub.-- state[1], . . . ,
    branch.sub.-- state[len]).
    ELSE IF
    (v=Stuff.sub.-- And.sub.-- String<the-string,par.sub.-- 1, . . . ,
    par.sub.-- k>)
    THEN
    /* m.sub.-- 1 can be constructed according to known
    methods disclosed in the previously cited
    references */
    SET m.sub.-- 1 = a finite state machine that scans
    the input string for the first occurrence of
    the-strlng and stops as soon as it comes to
    the end of this first occurrence.
    FOR i = 1 to k DO
    SET par.sub.-- i.machine = marker state
    appropriate to parenthesis par.sub.-- i and
    having an off set of
    length (the-string).
    SET v.machine = MAKE.sub.-- SEQUENCE (m.sub.-- 1,
    par.sub.-- 1.machine, . . . , par.sub.-- k.machine).
    ELSE IF (v=Sequence<element.sub.-- 1, . . . , element.sub.-- k>)
    THEN
    FOR i = 1 to k DO
    SET element.sub.-- i.machine = machine
    constructed according to this
    process for element.sub.-- i
    SET v.machine = MAKE.sub.-- SEQUENCE
    (element.sub.-- 1.machine, . . . ,
    element.sub.-- k.machine)
    /* a disjunction, ".vertline." */
    ELSE IF (v=Alternatives<element.sub.-- 1, . . . , element.sub.-- k>)
    THEN
    FOR i = 1 to k DO
    SET element.sub.-- i.machine = machine
    constructed according to this
    process for element.sub.-- i
    SET v.machine = element.sub.-- k.machine
    FOR i = k-1 downto 1 DO
    v.machine = Push<v.machine,
    element.sub.-- i.machine>
    /* type is "?", "+", or "*" */
    ELSE IF (v=Repetition<type, element>)) THEN
    SET element.machine = machine constructed
    according to this process for element
    SET v.machine = a finite state machine
    constructed according to methods
    disclosed in the previously cited
    references for this type of repetition
    element.machine
    ______________________________________

    ______________________________________
    FUNCTION MAKE.sub.-- SEQUENCE (machine m.sub.-- 1, m.sub.-- 2, . . . ,
    m.sub.-- k)
    RETURNS machine.
    new.sub.-- m m.sub.-- 1;
    FOR i = 2 to k DO
            Traverse the states of new.sub.-- m and replace
            any Success< >states with m.sub.-- i
    RETURN new m
    ______________________________________

    ______________________________________
    GLOBAL VARIABLE current.sub.-- state = initialized to the
    initial machine state
    GLOBAL VARIABLE input.sub.-- pos = initialized to the address
    of the beginning of the input string
    GLOBAL VARIABLE BT.sub.-- STACK = initialized to an empty stack
    GLOBAL VARIABLE MARK.sub.-- STACK = initialized to an empty
    stack
    REPEAT UNTIL one of the following clauses exits
    CASE (current.sub.-- state) IS
    Char.sub.-- branch<state.sub.-- 0, . . . , state.sub.-- 255>:
    current.sub.-- state = state.sub.-- (ASCII value of the
    current input character)
    input.sub.-- pos = input.sub.-- pos + 1
    Marker<num, open/close.sub.-- flag, offset, nextstate>:
    push ("mark", num, open/close.sub.-- flag,
    input.sub.-- pos+offset) onto MARK.sub.-- STACK
    current.sub.-- state = nextstate
    Action<complied.sub.-- action.sub.-- code, nextstate>:
    push ("action", compiled.sub.-- action.sub.-- code) onto
    MARK.sub.-- STACK
    current.sub.-- state = nextstate
    Push<state, nextstate>:
    push (state, input.sub.-- pos, height(MARK.sub.-- STACK))
    onto BT.sub.-- STACK
    current.sub.-- state = nextstate
    /* exit the REPEAT statement on final success */
    Success<>: GOTO done
    Failure<>:
    /* match finally fails if backtracking is
    attempted and the backtrack stack is empty */
    IF BT.sub.-- STACK is empty THEN
    RETURN "fail"
    ELSE
    pop BT.sub.-- STACK record into variables st,
    ip, msh
    current.sub.-- state = st
    input.sub.-- pos = ip
    pop MARK.sub.-- STACK down to height msh
    END CASE
    /* when parsing succeeds, scan MARK.sub.-- STACK and execute
    actions with variable bindings indicated by the marks */
    done:
    LOCAL VARIABLE open.sub.-- marks[], close.sub.-- marks()
    FOR element = bottom of MARK.sub.-- STACK up to top of
    MARK.sub.-- STACK DO:
    IF (element=("mark",num,"open",pos)) THEN
    SET open.sub.-- marks[num] = pos
    IF (element=("mark",num,"close",pos)) THEN
    SET close.sub.-- marks[num] = pos
    IF (element=("action",compiled.sub.-- action.sub.-- code)) THEN
    SET values of $0, $1, . . . , $n to the positions
    in the input string indicated by
    open.sub.-- marks[n] and close.sub.-- marks[n]
    RUN compiled.sub.-- action.sub.-- statement using these
    bindings of $0, $1, . . . , $n
    END FOR
    /* match succeeded and all action executed */
    RETURN "succeed"
    ______________________________________

• Inventors
  Christianson, David; Doorenbos, Robert B.; Etzioni, Oren; Kwok, Chung; Lauckhart, Gregory; Selberg, Erik; Weld, Daniel S.;
• Assignee
  Netbot, Inc. (Seattle, WA)
• Published
  Aug-15-2000
• Current US Classes:
  707/10
  707/103R
  707/2
  715/513
  717/146
• Application #
  310899
• International Classes
  G06F 017/30
• Field of Search
  707/1-9 707/100-104 707/200-205 717/1-11
• Examiner
  Choules; Jack M.
• Agent
  Fenwick & West LLP
• US Patent References:
  5495409
  5600831
  5680619
  5721908
  5724567
  5761436
  5768578
  5801689
  5826258
  5889992
  5913214
  6006224