DE69726463T2 - METHOD AND SYSTEM FOR ACCESSING NETWORK INFORMATION - Google Patents

Description

1. AREA THE INVENTION

The field of this invention relates access to information about Networks and in particular automatic localization and evaluation relevant information from sources of information about public or private networks are available in response to user requests.

2. BACKGROUND

The exponential growth of private Intranets and the public The Internet has a huge labyrinth of an increasing number of documents, databases and utilities. Almost every type of information is now available somewhere, however most users are unable to find what they are looking for search and even expert users waste a lot of time and Efforts for the search for suitable sources of information. There is a problem simply in the growing large Number of available Sources of information that go beyond the imagination of a individual user. A second problem in connection with this growing available Information and sources of information is a corresponding growth software supply facilities and methods to address them Manage, access, and present information. Each supply facility has a different and often unique Interface, instruction set and resources and is for a different Group of users and a different group of types of information suitable and sources. The bare Variety of available Utilities creates a problem for users that is comparable to that generated by the information explosion. Users are now faced with the double problem, which one Tool to use in which information source to search.

Efforts have been made in the past to provide users with automated computer-aided services that can help solve this dual problem of the network revolution. For example, AI researchers have developed several prototypes of software agents that help users filter email and network messages (Pattie Maes et al., 1993, Learning interface agents; Proceedings of AAAI-93), agents that search the world Support wide web (H. Liebermann, 1995, Letizia: An agent that assists web browsing, Proc. 15 ^th Int. Joint Conf. Via AI pages 924-929, Robert Armstrong et al., 1992, Webwatcher: A learning apprentice for the world wide web, AAAI Spring Symposium work announcements: Information Gathering from Heterogeneous, Distributed Environments, pages 6–12, Stanford University, AAAI Press), agents planning meetings (Lisa Dent et al., 1992, A personal learning apprentice, Proc ... 10 ^th Conf Nat about AI, pages 96-101; pattie Maes, 1994, Agents did reduce work and information overload, Comm 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 with which internet-related tasks can be carried out (O. Etzioni et al., 1994, A softbot-based interface to the Internet, CACM 37 (7): 72-75). The information that such agents must access is increasingly available on the World Wide Web. Unfortunately, even a domain as standardized as the WWW has been found to pose significant problems for automated software agents. Although websites are universally written in Hypertext Markup Language ("HTML"), this language only defines the format of the information display, however no attempts are made to indicate its meaning or its semantic content. There is currently no accepted "semantic markup language" for web editions, nor is it likely that one will be universally adopted. Thus, the Internet is expected to pose even greater problems.

Thus, the advent of intranets, the Internet, and the World Wide Web has raised numerous fundamental problems for automated services or agents designed to help users find relevant information. First, no such service has so far brought enough additional value to replace the use of a web browser that has access to existing directories and indexes, such as Yahoo or Lycos. Second, such services have not yet been able to understand relevant pertinent information from the responses returned by a wide variety of internet and web information sources, and to analyze it completely syntactically. Third, existing services and agents could not be easily adapted to the ever-increasing number of sources with their ever-changing response formats. The reason for this is the individualized, hand-coded interface to every Internet service and website that is used by existing agents (Yigal Arens et al., 1993; Retrieving and integrating data from multiple information sources, International Journal of Intelligent and Cooperative Information Systems 2 (2): 1270-158; O. 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 edition on Networked Information Discovery and Retrieval 5 (2); Mike Perkowitz et al., 1995, Category translation: Learning to understand information on the internet, Proc. 15 ^th Int. Joint Conf. via AI). Preferably, a service or agent should be able to access a new or changed Internet information source to automatically learn how to retrieve relevant information from the source. This would be an advantage even if such a facility were limited to groups of sources with response formats selected according to certain mandatory principles.

Y. Papakonstantinou et al .: "A query translation scheme for rapid implementation of wrappers". Deductive and object-oriented databases. Fourth International Conference, Dood 1995. Singapore; 4-seventh Dec. 1995, [Online] Pages 1-27, XP002179364 UCSD, USA, accessed from the Internet: URL: http .// www.db.ucsd.edu/publications/q uerytran.pdf [accessed on April 10, 2001] A method of assisting a user to find information available from sources of information connected to a network, the method comprising:
Selecting the one or more sources of information most relevant to a user request;
Formatting the user request for each relevant information source according to a description of each relevant information source written in a wrapper description language;
Transmitting the formatted request to each of the relevant information sources;
Extracting data fields relevant to the user request from responses returned from relevant information sources according to the description of the relevant information source that returns the respective response;
Representation of the relevant data fields for the user.

3. SUMMARY OF THE INVENTION

It is the overall goal of this Invention addresses these fundamental problems through a process and a System to solve which provide a personalized network machine called "Netbot". On Netbot works through as a user's intelligent assistant Track more available Network information sources that contain the relevant information and characteristics knows each special source and determines it based on a user request, what sources for a given query are relevant, the query is the most relevant Information sources forwards from each information source returned Understands answers and classifies the query results for the user and represents intelligently.

The netbots of this invention own various advantages including of the following. First, a netbot only gives the most relevant information back to the user. On the other hand, every user request only becomes the primary source of information forwarded, which were determined to be the most relevant. on the other hand responses from information sources are analyzed syntactically and understood that only the for the representation for data elements relevant to the user are extracted. double, uninteresting and irrelevant information elements are dropped. Second, a netbot is fast. Since it automatically gets the relevant primary Searched sources in parallel, he can present information so quickly, like the fastest primary Source returns an answer. Despite changing Conditions that cause that different Sources of information regarding fluctuate in speed, a Netbot integrator stays that fast like the fastest source. Sources that have no information, which they return on request do not slow the user down as the Netbot simply ignores them. Third, netbots are simply growing in numbers of network information sources with continuously changing Response formats adapted. Netbots use a new and novel declarative language Description of sources of information. A source description is short and easy to understand and is therefore simply written and groomed.

Therefore, the invention comprises in one aspect a procedure for effective access to information sources in a network, which preferably comprises one or more of the following steps: receiving a user request for Information; Determine the sources of information for this Query are most relevant; Get a description of everyone Source of information; Format the request according to this description in a Way that for any information source is suitable and transferring the formatted request to Source; Receiving responses from information sources, for each source, Understand and extract the relevant data fields according to the retrieved Description; and displaying the relevant data from each information source for the Users in an intelligent way, classified by an estimate of their Relevance. Advantageously, these steps are as far as possible Scope executed in parallel. In particular, at least all inquiries regarding all relevant Information sources transmitted in parallel, without waiting for intervening answers.

In another aspect, the invention includes a computer system and apparatus for performing one or more steps of the method of this invention. The user has a display device that is connected to a network to which a plurality of information is also available sources is connected. The presentation device receives user requests and displays Netbot responses. Furthermore, the display device performs one or more of the steps of the method of this invention. One or more of these steps, which are not carried out on this device, can advantageously be carried out on networked Netbot server computers which respond to functional requests from the user device. Optionally, the user device can be in the area between a hand-held portable terminal, a PC, and a workstation, etc.

According to another aspect comprises the invention a new language and language implementation to the Creation and maintenance of descriptions of information sources to simplify. It is essential that this language relevant data fields in responses returned from information sources is able to extract all such fields. In the preferred embodiment this language has an action instruction component and a regular expression component on. The regular one Expression component has novel features for creating modular hierarchical descriptions of regular expressions to match variables to tie correct sub-strings during a pattern match with a response from an information source to any Perform action language statements with multiple variable bindings and to determine detection of sub-strings without backtracking, wherever possible is.

4. SHORT DESCRIPTION THE DRAWINGS

These and other features of the viewpoints and advantages of the present invention will become apparent with reference to FIG the accompanying drawings by the description below and the attached Expectations easier to understand be, whereby:

1 generally illustrates a Netbot of this invention;

2A - B exemplary user interfaces of embodiments of the net bot of 1 illustrate;

3 exemplary functional components of the Netbot from 1 illustrated; and

4 alternative hardware versions of the Netbot from 1 illustrated.

5. DETAILED DESCRIPTION

The detailed description of a Netbots of this invention is provided for clarity of disclosure and without restriction as a method or process for Network information access, as a system or device that or those for an execution this method is implemented and as a novel language, which is designed to implement this method and systems as support to serve.

The following is first an overview of these Aspects of the invention indicated, secondly, a detailed discussion individual components follows.

5.1. OVERVIEW OF NETBOT ARCHITECTURE

A Netbot method or system of this invention includes software and hardware devices that work together on one or more networked computers to assist a user in accessing information residing on networked servers (herein referred to as "Sources of information" are referred to). 1 generally illustrates the relationships between a Netbot and a user and network information sources. For example, a user intervenes 1 on a user computer 3 via standard interface devices such as a monitor 2 , too. In the workflow, the user needs information from information sources 7 that are sent to the user computer via various network connections, such as network connections 4 and 6 , are connected. Since the sources of information are numerous, the user can benefit from assistance in finding the information required from relevant sources of information. This support is provided by a netbot 5 provided that guides the knowledge about available information sources and it over connections 6 on behalf of, or as an agent of the user. Alternatively, the Netbot 5 partially or completely in the user's computer 3 located or partially or completely distributed over the network, and it can be accessed by the user on the connection 4 be accessed.

Groups of sources 7 that include similar types of information are grouped into conceptual classes called information domains. For example, a domain can relate to that of electronic stores for a particular product. Another domain could include Internet indexes that contain information about the subject matter of various World Wide Web ("WWW") pages.

In a preferred embodiment, the Netbot is formed from three main functional modules: a user interface, an integrator and an I / O manager. This interacts briefly User interface module with the user to receive user requests for information and to format and present information responses from the information sources connected to the network. The user interface is advantageously adapted to the specific information domain that is being accessed. The integrator module accepts a user request from the user interface module, selects relevant information sources, formats them for network transmission to each relevant information source, receives responses from these sources, understands these responses, and returns the relevant portions of the responses to the user interface module for display to the user. The I / O manager module carries out a hardware, operation and network-specific coupling for the user interface and integrator modules, so that the porting of a net bot to different hardware platforms, operating systems or networks only requires changes in a well-modularized code.

For special alternative implementations can either be on the user interface or the I / O manager modules or to do without both. For example, the Functions of these modules already through other operating system components accomplished become. A Netbot can only use one or more of the facilities outlined deploy without providing others. For example, at some versions a netbot useful that performs query routing alone or in combination with a relevance ranking. at other versions a Netbot is only able to format queries and Understand answers. Furthermore, additional modules can be in a Netbot exist or can be accessed through the Netbot become. For example, there may be a learning module that ensures that a Netbot automatically the characteristics of a new network information source detected. Finally can like it is known to those skilled in the art the functions performed by the modules described in alternative ways a larger one or smaller number of modules can be distributed or grouped into such become.

There are no special preferences before, can the processes of this invention in a fully procedural manner Programming language, such as C, or in a perfect object-oriented programming language, such as C ++ implemented hardware configurations.

THE USER INTERFACE MODULE

The user interface module provides details both important functions that the Netbot user interfaces independently from the information domain, to which Netbots are directed, are common, as well as adaptations to the special information domain of a special netbot. First, turn to the preferred common Features too, such is the ability to adhere to preferences of a user for to remember the interaction with a Netbot. Such kept in mind preferences include, for example, whether a Netbot should fetch pages to their Determine relevance yourself, the number N or relevant information sources, to be queried, display characteristics, etc. A second such a common function is the gradual display of from one Information received. Since every request is usually one Caused Netbot to many independent Questioning information sources often results too received very different times. The immediate ad results not received at the same time would have undesirable effects, such as a flickering of the screen or a confusing rearrangement data already displayed. A gradual display bears on the one hand the wishes of a user to see information quickly, and on the other hand the wishes the user after a comprehensive overview of all information received, the according to their Relevance sorted, invoice.

The gradual display strategy preferably sees one or more windows on the screen of one User with multiple defined views of the fulfillment process the request together with certain general user control means, such as screen buttons, to manipulate these windows, before. That shows in a window User interface module Lists of information sources surveyed where each source is symbolic as, for example, a network address, a pictogram or other compact screen display, is shown. Then the appearance of its associated screen display z. B. by changing the intensity, changing the Color etc., changed, when a response is received from a particular source. As well becomes a count the total number of individual information pictograms that are currently were received. Optionally, a click on the screen display opens an information source another window with either information about this Source of information or an indication of the information received by it Responses, or access to the information source through the Network, etc.

One of the general control means is preferably implemented as an ordinary show-to-button, which, when activated, causes another window to be displayed in which a list of all the responses currently received, graded according to their estimated relevance for the request, is shown. Another general control means is preferably implemented as a multi-button in this last window, which, when activated, redisplays all previous data items combined with new elements received since the last window display. The newly received elements are included in the display list in order or relevance and are distinguished from previous elements, for example by their color or intensity, so that the user can avoid re-scanning previous elements. Optionally, clicking on a data element opens yet another information window, which either indicates the source of the element, a display of the response containing the element, or access via the network to the source of the element, etc.

In addition to such general ones Functions and control means are implemented by a Netbot user interface module preferably special designs, formatting and fields that are suitable for the information domain are for who designed it. For example, a netbot for one comparative shopping in an information domain of electronic shops on the Internet have a special interface representation that is sorted by product name, Contains designated fields for model and price. On the other hand, a Netbot for one Access to an information domain online internet indexes include an interface with fields, which are named with elements derived from the query.

In a Netbot version, most functions and modules are located on servers connected to a network, which a user can access remotely. For example, the user can access a Netbot over the Internet using the World Wide Web protocols using a web browser such as Netscape. In this case, the user interface builds HTML formatted pages that are transmitted over the network by the I / O manager. 2A generally illustrates the user display of an example of such an embodiment, which is further directed to the information domain of online electronic software stores. The Netbot ad from 2A is divided into three sections. The section 11 is a section of a title that generally indicates that this ad results from a shopping netbot, a "shopbot". A Netbot preferably has a special request entry screen. The section 12 represents the list of online shops that are currently being queried, by their WWW addresses 15 are shown, which can be selected to provide further information or direct WWW access. at 16 in the section 12 sources that have already returned query results are presented in a similar manner. The section 13 represents the results received so far formatted according to this special information domain in sections for the main PC operating systems. Each individual returned element, for example the element 16 , is formatted with the product name, price and an address of the source of the original information. In this implementation, the information display is controlled with the window rolling and control devices built into the web browser. This user interface is implemented as an HTML-formatted page that was created on the Netbot server and transferred to the web browser.

2 B generally illustrates the user display of another example of an embodiment of a web browser based user interface, 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. The section 71 displays a title for the Netbot, section 72 shows the status of the current search and section 73 displays the search results. The display of the section includes in more detail 71 a logo for this Netbot, where "MC" stands for "MetaCrawler", a name chosen because WWW search engines are also known as "Web Crawler", and controls access to certain display features of the system level, such as the MetaCrawler -Home and user feedback pages. The display of the section 72 includes the list 74 the search engines that are queried, identified by their common names, the status of the current query in general and at each search engine, and general user controls. In general, the pie chart pictogram summarizes 78 together that seven out of the eight search engines surveyed have already answered the query. At the search engine 75 Known as "Lycos", the check mark indicates that a response containing information items has already been received. At the search engine 76 Known as "Inktomi", the cross mark indicates that a response has already been received without any information elements. On the other hand, the search engine 77 , which is known as the "Galaxy", is visibly distinguished from the other search engines to indicate that it has not yet responded to the request. The general controls of the section 72 include a multi-button 79 to request the display of newly obtained search results and a search modification button 80 to request a new or modified request to be sent. Finally, the section display 73 the information items that are returned by the search engines. Each information element is shown separately and includes a title 81 , a description text 82 , if one is available, and a line 83 with the URL of the website for this element and the estimated relevance of this element for the request, which is "1000" here. The elements are sorted for display according to descending values of the estimated relevance. The displayed elements are rolled using control means provided by the web browser. This user interface is implemented as a Java applet, which is downloaded from a Netbot server and processed by the web browser. In this way, the interface of 2 B more interactivity than that of 2A in a position. For example, it can use the Net Poll the bot server regarding the current search status and update the status indicators accordingly without any user action.

Although the user interface is primarily in the form of windows and buttons it is for one skilled in the art recognizes that the Invention is adaptable to other display paradigms with which a display of information and input of user commands becomes. For example, the user interface module can the entire Control screen and graphic displays without the intervention of a windowing system represent.

The user interface module will preferably implemented with an object-oriented programming language, through a class library that provides windowing functions, added is. In a preferred implementation, the Java language used 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

3 illustrates the preferred functional modules, databases and their functional context in Netbot 30 in general and in an integrator module 37 particularly. The integrator preferably consists of three functions: a request router 39 , a wrapper database 40 and an aggregation machine 38 , These components are introduced here and described in detail below. At one of the user interface module 34 supplied user request 31 the integrator first calls the request router 39 to rank the network information sources known to a netbot in order of relevance and return the N more relevant sources. Next, the integrator retrieves the N wrappers from the N most relevant sources from the wrapper database 40 from. These wrappers, which are descriptions of the information source and its requirements, are written in the wrapper description language of this invention. The called wrappers are from the aggregation machine 38 firstly used to format the request in forms that are recognized by each information source and secondly to be used by each information source 33 understand the information returned in order to eliminate irrelevant information objects and to put the received information in a general format. This formatted information is then aggregated and sent to the user interface module for display 32 for the user according to a preferred gradual display method 36 passed. The user ad is also saved by user preferences 35 controlled.

THE INQUIRY ROUTER

A well-managed netbot should be preferred a scarce network bandwidth and resources for processing information sources use in a competent, efficient and economical way, At the same time, every user request is answered as best as possible. On such behavior minimizes the use of resources, and it will therefore be the best overall performance for both the individual Netbot for everyone as well Netbots working simultaneously on a network.

The request router is for reaching This behavior is important because it allows the Netbot to only make requests Sends information sources that are likely to be used for a request have relevant information. Determined from a user request the request router the relevance of each information source for the given Query and returns the N most relevant sources. N is a controllable according to user preference Parameters and can be very small, e.g. B. 1. This determination of relevance is preferably more inclusive as under-inclusive. Occasionally including an irrelevant source of information is opposite omitting a relevant and important source. It is further preferred that this Relevance determination can be estimated quickly and no complex Processing techniques required.

In a preferred embodiment the request router calculates a numerical relevance rank for every Information source used to estimate the relevance of the source. This calculation is based on the concept of "conceptual classes". Each will Information source marked in advance with the conceptual classes, for the it is relevant. The request router then forms each request the relevant ones conceptual classes and finds information sources with conceptual Classes, for who share the request. Mapping a request to yours Conceptual classes will preferably have a hash function executed.

AGGREGATION MACHINE

The aggregation machine is the coordinating function of the integrator module. It receives the user request from the user interface module and requests the request router to provide a list of the N information sources that are most relevant to the given request. It then calls the N wrappers for the N information sources from the wrapper database. Led by the N wrappers, the aggregation machine translates the request into the request formats that are accepted by each of the N information sources and transmits the N requests to the I / O manager for network transmission. For some sources, the request can be in the form 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 arranges it in a list of data fields called tuple format that are relevant to the particular information domain. Optionally, each tuple can be assigned a priority order using a method that is appropriate for the particular information domain. Finally, the aggregation engine passes the tuples, sorted in order of priority, if a priority has been determined, to the user interface module when the manager requests data to be presented to the user for the gradual display.

For example, if related to the information domain to Internet online software retailers , the tuples may contain relevant fields such as z. B. Product name, manufacturer, software version number, required Operating system, price, etc. An example priority order the tuple can, depending on user preference, according to the price, the delivery period or another factor.

If, as another example, the information domain in relation to search engines of the World Wide Web ("WWW") stands, whose index information pages generally on the WWW available the tuples may contain relevant fields such as z. B. the title of the indexed page, the Internet address (universal resource locator "URL") of this page, scores in terms of the relevance with which the relation of the indexed page to the request estimated will, descriptive text, etc. An example order of priority can be on the standardized relevance assessment through the netbot of the indexed page based on the request. If the netbot does not retrieve the indexed page, it sums the normalized relevance estimates for this Response returned by each of the search engines. If one Search engine a relevance assessment not returns a default setting value is used. The relevance assessments received are then like this by linearly adjusting the returned scores standardized that this a common maximum of z. B. 1000, and then the matched Multiplied scores by a probability factor. This probability factor, which is in the range from 0 to 1 is a predetermined estimate of reliability from certain relevance assessments specific to the information sources. For example, through practical experience with relevance assessments the source of information can be determined. Alternatively, the user can ask the Netbot to access the page to make its own relevance assessment. In an exemplary embodiment is for Requests in which the presence of either all query words or some query words is required by the estimate Scan the page and count the number of query words that actually exist and then scaling the count determined so that the Presence of all words for the common maximum relevance value leads. For inquiries, The estimation, for example, will require the existence of a sentence by subtracting from the common maximum of a normalized sum of the square of the distance of each word of the sentence in the page determined from the following word in the sentence. That is the relevance high if the sentence is contiguous appears on the page while The relevance is low if the words of the sentence are on the page are far apart.

In summary, for the majority of the information domains the order of priority from a relevance calculation, as in the example of the WWW search engine certainly. However, a priority order for certain domains such as online software retailers from the values of one or more numeric fields of the answer tuple be determined.

THE WRAPPER DATABASE

The preferred way of sources of information and their skills in particular to describe your request formats and response formats, are compact modular explanatory Descriptions called wrappers. Because a netbot on several can access a hundred to several thousand sources of information, the descriptions of the sources are preferably compact and require a minimum of storage space. In addition, since often new Sources of information are generated and existing sources their format change frequently is easy maintenance of source descriptions of importance. A modular explanatory Description instead of a complex procedure-oriented description facilitates such care. When executing this Invention can Wrapper through a separate module for information sources that sufficiently regular formats have to be taught.

• 1. Die Internetadresse (Universal Resource Locator "URL") der Informationsquelle;
• 2. Die konzeptionellen Klassen der Quelle;
• 3. Eine Beschreibung der Abbildung aus Anfrageargumenten, z. B. Worten oder Sätzen, auf Felder der Anfrage oder eine HTML-definierte Form, die verwendet wird, um die Quelle abzufragen (einschließlich einer Siteunterstützung für beliebige, alle, Satz- oder Nahanfragen);
• 4. eine Beschreibung des Formats der Anfrageantwort oder des HTML-Seitenlayouts, das eine syntaktische Analyse relevanter Information gegenüber anderer Information und irrelevantem Formatierungsinhalt ermöglicht.

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

• 1. The Internet address (Universal Resource Locator "URL") of the information source;
• 2. The conceptual classes of the source;
• 3. A description of the mapping from query arguments, e.g. B. words or sentences, on fields of the query, or an HTML-defined form used to query the source (including site support for any, all, sentence, or close queries);
• 4. A description of the format of the query response or the HTML page layout, which enables a syntactical analysis of relevant information against other information and irrelevant formatting content.

At least points 3 and 4 will be advantageously in the wrapper description language of this invention written.

A netbot can wrapper on different Retrieve wise men. In one execution the source of information can put its own wrapper on one Deliver a request from a Netbot. In an alternative execution can the Netbot deliver its own wrappers in a number of ways. For example, wrappers be built into the Netbot itself, especially if the Netbot only accesses few sources of information. You can also use wrappers in a local Database can be stored or can be requested from a centralized Database can be downloaded.

The wrapper description language (hereinafter referred to as "WDL") this invention facilitates the semantic description of requests, Shapes and pages using an explanatory description format, the grammar features and ordinary expressions combined. The following is an example of this description language explained. A detailed description will be given in a later section presents. The syntax used follows conventions known to experts Determination of grammar, including ordinary ones Express. See e.g. B. Schwartz, 1993, Learnin Perl, O'Reilly & Associates, Inc., Chapter 7; Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co., section 3.3.

The following is an example Description in WDL of a typical WWW search engine returned Page specified. The WDL interpreter uses the page description, to parse a page and specify specific ones Execute action instructions. Note that "stuff" is reserved in the WDL Word is that every character string until the first occurrence of a mandatory string literals.

This describes a page which among other data from a sequence of zero or more elements is constructed. In detail is for one side determines that it from stuff, then the string <dl>, then zero or more Elements, then zero or more characters ("."), then finally the end of the page ("$"). In general comprises An element has three relevance fields, which are labeled (Stuff) and sequentially referred to as $ 0, $ 1 and $ 2, the through the "output () "Statement issued when an item is recognized. In detail is for an item determines that it from stuff, then the string <dt>, then another stuff, then the string '=' '', then the first field of interest, followed by $ 0 Is referenced, then the string '' '> <strong>', then the second field of interest, on that later is referred to as $ 1, then the string '' </strong> </a> '', then another stuff, then the string "<dd>", then the third Field of Interest referred to below as $ 2 then the string "<br>" exists. The instruction in the Parentheses, which in this case output the variables $ 0, $ 1 and $ 2 with the ties determined if a <item> matches is is executed when every element is recognized.

THE NETBOT SYSTEM

The preferred functional structure of a net bot can be assigned to system hardware components according to various alternatives. In any case, the preferred alternative depends on the allocation of functions with which a quick response and reasonable costs can be achieved. 4 generally illustrates exemplary Netbot hardware designs and options in light of the foregoing general description. It illustrates the connection between the user computer elements 51 - 56 , the network 57 , the source of information 58 and the Netbot server computer 59 - 61 , The computer 51 is a user computer that includes a processor, memory, and various attached peripherals. Such peripheral devices include a display device 52 or another device for interacting with a user, a network connection 54 , an optional hard disk space 53 etc. The computer 51 can be older natively a network device without permanent memory, a PC, a workstation or an even more powerful computer. It is preferred that the computer 51 is a PC or workstation running one of the Windows operating systems, the Macintosh operating system, or UNIX. In the memory of the user's computer 51 the local Netbot software can be found under other software 55 and local system components 56 , The local Netbot software implements one or more of the Netbot functions. The local system components can include, for example, a web browser.

The network 57 can be any network with a plurality of connected information sources 58 that may be conceptually classified into information domains by the content. In a preferred embodiment, the network is 57 the public Internet or a private intranet that supports the TCP / IP sequence of protocols including user level protocols such as FTP, HTTP, etc. The sources of information are server computers that use their stored information through the network 57 make supported protocols accessible. Such information may be databases of magazines, newspapers, etc., information about certain commercial, educational or other types of organizations, electronic commerce facilities, etc. or information produced by them.

In such a network, a netbot can have different designs. In a completely local version, Netbot functions are located in local Netbot software 55 on the user's computer 51 which must have sufficient processing and storage capabilities in this embodiment. In alternative embodiments, one or more of the Netbot functions described can be distributed to other computers connected to the network.

For example, the computer 59 a wrapper server to accept requests to download wrappers from its wrapper database. The wrapper database may be stored in memory or on a disk using any data management system that is capable of storing and retrieving compact textual descriptions. The computer 60 is a request server for performing request routing by accepting requests and returning the N most relevant sources of information out of the tens or hundreds of thousands about which it stores information. The computer 61 is a Netbot server to perform the integrator module function by accepting user requests and returning search results, possibly using the wrapper server facilities 59 and the request server 60 , With these network servers, the local Netbot software preferably only supports the user interface, which can be completely delegated to a web browser. Alternatively, it can also include the aggregation engine, the request routing requests to the request server 59 and wrapper requests to the wrapper server 60 provides. It can also include one or both of these latter functions.

The different computers one Netbot systems can be softwareed to either implement the methods of this invention of computer-readable media or by loading via a network. This Invention is in known magnetic and optical media, such as Plates, tapes and Customizable CD-ROM.

5.2. THE I / O MANAGER

The I / O manager module does that Hardware, operating system and network-specific interface for the integrator module out. The network coupling includes the tasks of sending requests and receiving responses from information sources connected to the network. An important Application of the Netbots of this invention is information on the Internet retrieve. In this application, the I / O manager is responsible for the relevant protocols of the WWW, Gopher, FTP, the Internet tools etc. to implement. Optionally, he can temporarily save pages and other data, to improve the response time.

Operating system interfacing includes the task a window manager for the user interface module and access to the wrapper database, if it exists.

Preferably the I / O manager from commercially available Protocol stacks, windowing libraries such as the Java.awt package and other tools. In some implementations can more or less I / O manager functions through other system components on the computer connected to the network. Optionally, the I / O manager is designed to be scalable for numerous machines is therefore no multi-path operation or re-entry invariant Code is required to be cross-platform and persistent.

5.3. THE AGGREGATION MACHINE

• 1. Empfange eine Nutzeranfrage vom Nutzerschnittstellenmodul;
• 2. Führe ein Anfrage-Routing durch, um die für die Nutzeranfrage N relevantesten Informationsquellen zu ermitteln;
• 3. Für jede der N relevanten Informationsquellen:
• A. Rufe den Wrapper von dieser Informationsquelle ab (beispielsweise von der Quelle selbst oder von einer lokalen oder entfernten Wrapper-Datenbank);
• B. Geführt durch den Wrapper, formatiere die Nutzeranfrage in der Form oder dem Format, das für die Informationsquelle erforderlich ist;
• C. Übertrage den übersetzten Befehl zum I/O-Modul zur Übertragung zur Informationsquelle;
• 4. Initialisiere die Liste von Antworten, so daß sie leer ist;
• 5. Bis ein nutzerspezifiziertes Zeitlimit erreicht ist, führe aus:
• A. Wenn eine Antwort einer Informationsquelle vom I/O-Modul empfangen wurde und zum Integrator übertragen wurde, dann:
• i. Geführt durch den Wrapper für diese Informationsquelle, analysiere die Syntax der Antwort, um die zurückgegebene Information zu verstehen, streiche den sitespezifischen Formatierungstext und anderen irrelevanten Inhalt, und sammle relevante Felder in Tupel;
• ii. Füge jedes Tupel zur Liste von Tupeln hinzu, wobei optional eine Bestimmung einer Prioritätsreihenfolge, ein Löschen von Duplikaten, etc. ausgeführt wird,
• B. Warte auf die nächste Antwort;
• 6. Füge die Liste erzeugter Tupel zum Nutzerschnittstellenmodul auf eine Aufforderung hin hinzu, die beispielsweise auf Grund einer Nutzeraktivierung der Zeige-Knopf- oder Mehr-Knopf-Steuerungsmittel erfolgen kann.

In the preferred embodiment, the functions previously identified for the aggregation machine component of this invention are performed by the following process. Search processes for the Information source run in parallel, since all requests are transmitted without waiting for any answers.

• 1. Receive a user request from the user interface module;
• 2. Perform request routing to determine the most relevant information sources for user request N;
• 3. For each of the N relevant information sources:
• A. Retrieve the wrapper from this source of information (for example, from the source itself or from a local or remote wrapper database);
• B. Led by the wrapper, format the user request in the form or format required for the information source;
• C. Transfer the translated command to the I / O module for transfer to the information source;
• 4. Initialize the list of answers so that it is empty;
• 5. Until a user specified time limit is reached, do:
• A. If a response from an information source was received by the I / O module and transmitted to the integrator, then:
• i. Guided by the wrapper for this information source, analyze the syntax of the response to understand the information returned, delete the site-specific formatting text and other irrelevant content, and collect relevant fields in tuples;
• ii. Add each tuple to the list of tuples, optionally determining a priority order, deleting duplicates, etc.
• B. Waiting for the next answer;
• 6. Add the list of generated tuples to the user interface module upon request, which can be done, for example, due to user activation of the pointing button or multi-button control means.

If multiple sources of information are queried, the user interface module is preferred in step 6 and thus present the user with a single, assembled list of tuples, which are taken from the answers and according to an estimate of the Significance or relevance of each tuple are sorted for the user. Such an estimate is preferably according to methods the for the information domain, to which the Netbot is directed. For certain domains can make a significance assessment directly from the value of one or more data fields in the tuples be formed. For example, according to the user preference in a domain of electronic shopping the significance only with the price or the delivery date. However, for most Domains one significance assessment executed according to the relevance of the information returned by Check of responses from every source.

In a preferred embodiment Such a relevance determination gives the user the choice of whether he has the Netbot check all information pages himself or not. If the user this chooses the relevance is determined by the Netbot according to a domain-specific analysis function determined. In a domain of An exemplary analysis function finds information requests The number and location of the query words in the response returned. For keyword requests are answers in which more keywords with greater frequency are more relevant. For on sentences based answers are answers in which the words of the sentence have a smaller distance, for example in a single one Sentence or even in a coherent sequence, relevant. For other domains suitable analysis functions are provided.

If the user decides that the Netbot doesn't check the answers lets is the netbot on relevance assessments instructed that are returned from the information sources. If one certain source does not return a relevance estimate, becomes a default setting value used. These estimates are then normalized so that they between z. B. 0 and 1000 are and are with a probability factor multiplied. This probability factor, which is in the range is from 0 to 1 is a predetermined estimate of reliability the for a certain information source own relevance assessments. For example, through practical experience with the estimates the source can be determined. Where the same tuple of two or returned more sources the relevance values from all these sources are combined. Optional are the relevance assessments made by each source returned are so tuned that they have a uniform distribution in the standardization area.

In a particularly detailed embodiment, this determination is carried out according to the following process. Here, a list of K information sources, source_k with k from 1 to K, was determined by query routing, and their degrees of confidence, crank_k, were returned. Each of these sources was queried, returned responses, and K lists of information tuples, tupels_j, where j is from 1 to length_k, were extracted from these answers. The user's preference for a Netbot analysis is recorded in the verification bit switch V. The variable t.score represents the composite relevance score for the tuple t, the variable t.sourcescore_k represents the relevance estimate for the answer from which the tuple t was taken, returned by the information source source_k.

Entry: List of K sources with their confidence level pairs (source_k, crank_k), the received from the request routing system, K ordered lists of Tuples tuples_k of length length_k obtained from source source_k and the verification bit switch V (Boolean) obtained from user preferences.

Edition: Merged list all tuples sorted by relevance.

For Those skilled in the art will recognize that these processes change can be subjected to routine and improvements which perform the same functions in the same way. In particular can other values for the normalization range and another standard setting value for the relevance assessments the information source can be used. This invention includes such changes the routine. These processes are preferably implemented in C ++, can however alternatively in any procedure-oriented or Object-oriented programming language can be implemented.

5.4 THE INQUIRY ROUTER

The request router receives as Enter a user request formulated as a list of words or keywords and returns as output a list of N information sources that ordered according to their likely relevance to the input request are. The determination of these sources of information is related to Speed and optimized for over-inclusiveness. An occasional involvement of an irrelevant source of information is opposite omitting a relevant source.

The preferred request router is based on the principle of assigning relevant concepts to information sources and query words. In advance, a set of concepts is chosen to describe the information sources of the one or more information domains, to which one or more netbots are aimed. For every source of information in the domains becomes the relevance of this source for each of the chosen concepts assessed. Furthermore, every word that occurs in possible queries can, checked to to determine which of the chosen Concepts for the word is relevant. Then on receiving the words or Keywords of an inquiry related to these words standing concepts and then the relevant for these concepts Sources of information found. The graded relevance of each source is done by combining the individual relevance of the source for all concepts the request. The case of requests based on sentences will preferably by generating separate data for it Request type handled.

In the preferred implementation In this process, four tables are used, the relevance information contain. In the following, W is chosen slightly larger, e.g. B. 10% as the number of words in possible Inquiries can occur. C is the number selected Concepts and S is the number of sources of information in the information domain. WORD2CONCEPT [] is a table of W vectors of C bits, the C bits of the Vector for display a word which of the C concepts is relevant to the word. CONCEPT2SOURCE [] [] is a C on S table. For each of the C concepts and each of the S sources contains the corresponding entry this table the relevance value of this source for this concept. In particular the jth information source has a relevance weight of 5 in relation to the i-th concept if the entry <i, j> is 5. CONCEPT2SOURCE [] [] is used when searching for words. Connects for searching with sentences the table CONCEPT2PHRASE [] [] similarly concepts and Swell. Finally comprises DEFAULT-RELEVANCE [] a default relevance weight for each of the S sources of information.

• 1. Für jede der S Informationsquellen setze RELEVANCE[j] = DEFAULT-RELEVANCE[j];
• 2. Für jedes Wort in der Nutzeranfrage führe aus:
• A. Berechne eine Hash-Funktion auf das Wort, womit eine Zahl M zwischen Null und W erhalten wird. Für diesen Prozeß ist jede geeignete Hash-Funktion verwendbar. Eine beispielhafte Hash-Funktion ist in Sedgewick, 1990, Algorithms in C, Addison-Wesley Publishing Co., Kapitel 16, offenbart.
• B. Der C-Bit-Vektor V sei gleich WORD2CONCEPT[M];
• C. Kombiniere die Relevanzen für alle Konzepte in V zur Relevanz für die Informationsquellen durch Ausführen von: Für i von 0 bis C, führe aus:
  
  Eine andere monoton ansteigende Funktion als "+" kann ebenso verwendet werden, um die individuellen Konzeptrelevanzen zu einer endgültigen Relevanz zu kombinieren;
• D. Kombiniere die Relevanzen für alle Worte in der Nutzeranfrage, indem sie beispielsweise addiert werden.
• 3. In dem Fall einer Suche mit Sätzen führe zusätzlich aus:
• A. Verknüpfe alle Worte des Nutzeranfragesatzes;
• B. Berechne die Hash-Funktion auf den Satz und erhalte M und setze den C Bit-Vektor V gleich WORD2CONEPT[M];
• C. Kombiniere die Relevanzen für alle Konzepte in V zur Relevanz für die Informationsquellen durch Ausführen von: Für i von 0 bis C, führe aus:
  
• 4. Sortiere die Informationsquellen basierend auf ihrer RELEVANCE und gebe die N-relevantesten Quellen zurück.

In the preferred implementation, the following process is performed.

• 1. For each of the S information sources set RELEVANCE [j] = DEFAULT-RELEVANCE [j];
• 2. For each word in the user request, do:
• A. Compute a hash function on the word, giving a number M between zero and W. Any suitable hash function can be used for this process. An exemplary hash function is disclosed in Sedgewick, 1990, Algorithms in C, Addison-Wesley Publishing Co., Chapter 16.
• B. The C-bit vector V is equal to WORD2CONCEPT [M];
• C. Combine the relevance for all concepts in V to the relevance for the information sources by executing: For i from 0 to C, do:
  
  A monotonically increasing function other than "+" can also be used to combine the individual conceptual relevance to a final relevance;
• D. Combine the relevance for all words in the user query, for example by adding them together.
• 3. In the case of a search with sentences, also do the following:
• A. Link all the words in the user request record;
• B. Compute the hash function on the set and get M and set the C bit vector V equal to WORD2CONEPT [M];
• C. Combine the relevance for all concepts in V to the relevance for the information sources by executing: For i from 0 to C, do:
  
• 4. Sort the information sources based on their RELEVANCE and return the N most relevant sources.

For one skilled in the art will recognize that there are changes to this process regarding the routine and improvements can be made at which same functions are performed in the same way. This invention encompasses such changes the routine.

This process is preferably done in C ++ implemented, but can alternatively be in any procedure-oriented or object-oriented programming language can be implemented. In the case of a request router that has information about a size Number, e.g. B. has ten thousand sources of information the request router preferably as a server process on a Server computers implemented to deal with the size of the required data structures and the processing requirements of the request routing to become.

An exemplary construction of the WORD2CONCEPT table begins with the selection of concepts to characterize the information domain that is of interest and the determination of words and sentences that are likely to occur in user requests. The following actions are performed for each concept. The words and sentences that are associated with this concept or to which the concept is related are assigned to the string fields KEYS [] and PHRASES []. Then the following process is carried out.
FOR i equal to 1 up to the number of elements in KEYS [], DO Apply the previously used hash function to KEYS [i] to get a number between 0 and W SET the bit that corresponds to the current concept in WORD2CONCEPT [ M] fits together.
FOR j equals 1 up to the number of elements in PHRASES [], DO Apply the previously used hash function to KEYS [i] to get a number between 0 and W SET the bit that corresponds to the current concept in WORD2CONCEPT [M] fits together.

These actions are for everyone elected Repeats concept. Alternatively, the concept information can be put together with the string information using either the open or closed hashing can be saved for precise matching to get from string and concept.

5.5. WRAPPER DEFINITION LANGUAGE

This first section introductory Material about explained the use of the WDL in wrappers. Then the two main Components of the WDL - the Action language and the regular Expression language - in Details described. Finally, an example embodiment the WDL set out.

• 1) WDL-Beschreibungen sind einfach zu schreiben, d. h. einfacher als beispielsweise in C++. Dies ist von Bedeutung, da neue Informationsquellen häufig generiert werden und bestehende Dienste ihr Format häufig ändern. Optional können Wrapper-Beschreibungen automatisch unter Verwendung von Maschinenunterrichtungstechniken in Informationsdomänen generiert werden, wo Antworten ein reguläres vorbestimmtes Format aufweisen.
• 2) Wrapper-Beschreibungen sind kurz. Dies ist wichtig, damit sie beispielsweise lokal in einer Datenbank gespeichert werden können oder rasch von einem Server zu einem Netbot, der in einem Client läuft, selbst über eine langsame Netzverbindung übertragen werden können. Optional können Informationsquellen ihre eigenen Wrapper auf eine Aufforderung hin liefern.
• 3) WDL-Beschreibungen können automatisch in schnelle endliche Automaten kompiliert werden, die die von den Informationsquellen zurückgegebenen Informationen schnell syntaktisch analysieren.
• 4) Eine Verwendung von Wrappern mit WDL ermöglicht, daß sich Netbots an neue Arten von Informationsformaten und neue Typen von Informationsserverinteraktionen in der Zukunft anpassen.

A wrapper is a description of a source of information and how a netbot should interact with it, especially how requests to it should be formatted and how responses should be understood by it. Netbots must be effective with several hundred to several thousand information sites in one Interact network. This interaction shows two requirements: first, a compact storage of a description of an information source using a representation coded in the WDL; and second, using this description to understand the source of information. For example, netbots must continually format requests to a source and parse useful information from the pages returned by the source while ignoring irrelevant formatting information. As information sources become more and more functional, it will be necessary for Netbots to process more complex interactions than simple query-response pairs. Therefore, the wrapper and the WDL preferably have the following characteristics:

• 1) WDL descriptions are easy to write, ie easier than, for example, in C ++. This is important because new sources of information are generated frequently and existing services change their format frequently. Optionally, wrapper descriptions can be automatically generated using machine education techniques in information domains where responses are in a regular, predetermined format.
• 2) Wrapper descriptions are short. This is important so that they can be stored locally in a database, for example, or can be transferred quickly from a server to a Netbot running in a client, even over a slow network connection. Optionally, information sources can deliver their own wrappers upon request.
• 3) WDL descriptions can be automatically compiled into fast finite automata that quickly parse the information returned from the information sources.
• 4) Using wrappers with WDL enables netbots to adapt to new types of information formats and new types of information server interactions in the future.

The wrapper description at least lays two processes are established: first, requesting information from an information source, e.g. B. how to format the correct HTML Page is retrieved from a source; and second, how returned Pages are parsed to get the relevant data refer to. To perform the first process, the WDL includes an action language component, which is an expandable language of off and instructions. Around performing the second process involves the WDL a regular Expression language component, which is a large one and novel means for determining regular expression matching devices is.

In alternative implementations can Netbots use alternative pattern matching facilities that Are known to experts. For example, the regular expression component through a context-free language specification ("CFL") be replaced. In this case, you can in the implementation of the WDL for the construction of compilers known techniques, such as YACC, are followed. however will be where possible is due to its simple specification and rapid processing a regular Expression pattern matching preferred.

AN EXAMPLE THE REGULAR EXPRESSION OF THE COMPONENTS

Regular expressions are used to describe the Format of the information returned by many information sources Advantage. The regular one Expression component of the WDL extends the previous regular expression matching facilities in different new ways. First, it enables programming of language facilities of the action language, e.g. B. Instructions and expressions, to execute that are when regular expressions are recognized, and with variable bindings that are partially matched to be determined during of overall recognition. Second, the preferred Implementation regular expressions compiled into compact and efficient finite state machines. thirdly becomes the effective and intuitive expression of a complex regular expression supported in a nested manner. And fourth, she owns an effective backtracking-free filling device.

An example wrapper follows, the for a search engine for Internet information suitable and written in the WDL. The The meaning of each section is described in comments, which are enclosed with "/ *" and "* /".

5.5.1. DESCRIPTION OF WDL COMPONENTS

In this section are the preferred ones Features of the action language and the regular expression components of the WDL described. This invention is not based on the descriptions set forth limited. Known methods of describing are described in these descriptions of grammars including from regular Express used and for it will be apparent to those skilled in the art that there are many essentially equivalent thereto Descriptions there. Such equivalents Descriptions include those resulting from the renaming of those described syntactic elements or from the use of known grammatical However, transformations to the presented syntax result not limited to that. This invention closes these are also essentially equivalent Descriptions.

THE ACTION LANGUAGE COMPONENT

The language of action includes certain preferred properties at the base level: an assignment instruction; Sequencing instructions such as "if" and "while" constructs, a tuple output instruction; String and numeric expressions; String, numeric and boolean operators; and certain built-in Functions. For Experts it is understandable that a Action language at the basic level with an equivalent semantic expressiveness with a slight various selection of features can be built. For example the while statement can be replaced by a goto statement. The action language component of this invention includes such known equivalents Formulations of the disclosed semantics. Furthermore, in optional embodiments the preferred properties at the base level through additional ones Features are expanded, such as: additional sequencing instructions, such as "for" or "repeat" loops; user-defined functions; additional String, numeric and Boolean expressions and operators like them can be found, for example, in C or C ++; additional built-in functions and array variables. Such additional Characteristics can can be added to the preferred base level language in a known manner. S. z. B. Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co.

The preferred base-level action language syntax is by the following grammar expressed in standard notation given.

Thus, the action language component with instructions and expressions Are defined. An instruction can be: an assignment instruction that assigns a new value to a scalar variable; an if statement; a while loop; a compound statement that is a consequence other instructions enclosed by "{" and "}", or an output instruction. With the exception of the output instruction, the instructions work in the same way as with other procedure-oriented programming languages, e.g. B. C, C ++ or Pascal. For the if and while statements will use the conditional argument as considered true if it is either a number that is not the same Is zero or a string that is not zero, i.e. H. is not the empty string "". The OUTPUT statement enables the existence Wrapper information that matches responses from the information source, return to the Netbot module that can process the wrapper. For example, processing the statement "output (arg_1, ..., arg_n) ", that this Tuple <arg_1, ..., arg_n> from the wrapper to the netbot returned becomes.

An expression can be: a string constant, which is a character string surrounded by quotation marks; a floating point number; a variable name, which is a name or a whole Is a number preceded by a dollar sign; an insert operator, applied to two enclosing sub-terms; a sub-expression, the bordered is between "(" and ")", or a call to a built-in function.

• 1) +, –, *, /: Ausführen der angegebenen arithmetischen Operation auf die einfassenden Ausdrücke;
• 2) .: Verketten der einfassenden Strings:
• 3) ==, <=, >=, <, >, !=: Durchführen des angegebenen numerischen Vergleichs der einfassenden Zahlen und Zurückgeben der Fließkommawerte 0,0 oder 1,0 in entsprechender Weise;
• 4) eq, le, ge, lt, gt, ne: Durchführen des angegebenen Vergleichs der ASCII-Codes der einfassenden Strings Schriftzeichen-für-Schriftzeichen und Zurückgeben der Fließkommawerte 0,0 oder 1,0 in entsprechender Weise;
• 5) !: Zurückgeben von 1, falls das Argument die Zahl 0 ist oder der String "", ansonsten Zurückgeben von 0;
• 6) &&: Evaluieren des ersten Arguments, falls das erste Argument Null ist oder "", Anhalten und Zurückgeben dieses Wertes, ansonsten Evaluieren des zweiten Argumentes und Zurückgeben des letzteren Wertes;
• 7) ||: Evaluieren des ersten Arguments, falls das erste Argument weder Null noch "" ist, unmittelbar Anhalten und Zurückgeben dieses Werts; ansonsten Evaluieren des zweiten Arguments und Zurückgeben des letzteren Wertes.

In addition, the procedure-oriented programming language language provides standard operators including the following:
arithmetic operators ("+", "-", "*", "/"); numerical comparison operators ("<", "=", ">", "<=", ">=","!="); String comparison operators ("lt", "eq", "gt", "le", "ge", "ne"); a string concatenation operator (".") and Boolean operators ("&&", "||", "!"). These operators have the following semantics:

• 1) +, -, *, /: perform the specified arithmetic operation on the enclosing expressions;
• 2).: Concatenating the enclosing strings:
• 3) ==, <=,> =, <,>,! =: Perform the specified numerical comparison of the enclosing numbers and return the floating point values 0.0 or 1.0 accordingly;
• 4) eq, le, ge, lt, gt, ne: performing the specified comparison of the ASCII codes of the enclosing strings character by character and returning the floating point values 0.0 or 1.0 in a corresponding manner;
• 5)!: Return 1 if the argument is 0 or the string "", otherwise return 0;
• 6) &&: evaluating the first argument if the first argument is zero or "", stopping and returning this value, otherwise evaluating the second argument and returning the latter value;
• 7) ||: Evaluate the first argument if the first argument is neither zero nor "", immediately stop and return this value; otherwise evaluate the second argument and return the latter value.

• 1. jeder Ausdruck in Klammern (höchste Priorität)
• 2. *, /
• 3. +, –, .
• 4. ==, <=, >=, <, >, !=, ne, eq, le, lt, gt, ge
• 5. ! (Boolesches Nein)
• 6. && (Boolesches Und)
• 7. || (Boolesches Oder) (niedrigste Priorität).

In order from highest to lowest, these operators have the following priority:

• 1. every expression in parentheses (highest priority)
• 2. *, /
• 3. +, -,.
• 4. ==, <=,> =, <,>,! =, Ne, eq, le, lt, gt, ge
• 5th! (Boolean no)
• 6. && (Boolean And)
• 7. || (Boolean Or) (lowest priority).

All operators are associative on the left.

There are no variable declarations needed. First, all the variables in the action language are distinguished by that them preceded by a "$". This special variables denote the substrings that are marked by a regular Expression matched consist of a "$" followed by an integer, such as $ 0 or $ 1 follows. Second, automatic type conversions at runtime between string and floating point types made dynamically. If an operator expects a number, however receives a string the string by calling the C library function atof () in a Number converted to the ASCII representation a number in its internal floating point representation transforms. If an operator expects a string argument, however get a number he uses the C library function sprintf (..., "% I") to put it into a Convert string. Third, variables are referenced that have not yet been mapped to the default setting values 0 or "" set if this is appropriate.

• 1) argc(), argv(): Wenn ein Netbot einen Wrapper abarbeitet, kann er dem Wrapper eines oder mehrere Argumente geben. Diese stellen gewöhnlich Anfrageparameter, Anfrageworte oder Anfragestichworte dar, die vom Benutzer geliefert werden. Auf diese Argu mente wird von innerhalb der Wrappersprache durch die Funktionen argc(), die die Anzahl von an den Wrapper weitergegebenen Argumenten zurückgibt, und argv(n), die das n-te Argument zurückgibt, zugegriffen.
• 2) fetch(): Diese Funktion ist vorzugsweise mit dem I/O-Modul gekoppelt, um einen String, der die Netzadresse einer Informationsquelle enthält, und möglicherweise Anfrageparameter über ein Netz zur adressierten Informationsquelle gemäß dem richtigen Protokoll zu übertragen, und gibt einen String zurück, der die Antwort der Informationsquelle enthält. Wrapper verwenden diese Funktion, um Informationsquellen abzufragen und Seiten abzurufen.
• 3) parse(<string>,<nonterminal>): Diese Funktion nimmt einen String und versucht ihn mit dem regulären Ausdruck abzugleichen, der dem gegebenen <nonterminal> entspricht, der durch die reguläre Ausdruckssprachenkomponente der WDL definiert ist. Diese Funktion gibt „1" zurück, falls der Abgleich erfolgreich war, oder „0", falls der String nicht mit dem regulären Ausdruck zusammenpaßt. Wrapper verwenden diese Funktion, um die Antwort einer Informationsquelle syntaktisch zu analysieren.

The action language component has several built-in functions. The following functions are preferred built-in functions of the basic level.

• 1) argc (), argv (): When a netbot processes a wrapper, it can give the wrapper one or more arguments. These usually represent query parameters, query words or query keywords that are supplied by the user. These arguments are accessed from within the wrapper language by the argc () function, which returns the number of arguments passed to the wrapper, and argv (n), which returns the nth argument.
• 2) fetch (): This function is preferably coupled to the I / O module to transmit a string containing the network address of an information source and possibly request parameters over a network to the addressed information source according to the correct protocol and gives a string that contains the response from the information source. Wrappers use this function to query information sources and to retrieve pages.
• 3) parse (<string>, <nonterminal>): This function takes a string and tries to match it with the regular expression that matches the given <nonterminal> defined by the WDL's regular expression language component. This function returns "1" if the match was successful, or "0" if the string does not match the regular expression. Wrappers use this function to parse the response of an information source.

An exemplary wrapper includes the following Sequence of action language instructions. At the beginning is a series of statements using argc () and argv (), to get the user request parameters and a string variable, z. B. $ url, where a string is the URL of the relevant page at the information source along with an appropriately formatted Contains request. Next gets the assignment instruction "$ html_text = fetch ($ url) "the Request response page in another string variable, e.g. B. $ html_text. Finally tries the function parse ($ html_text, <page>) the returned html text with the regular Expression <page> that is the one you are looking for Page describes to match.

THE REGULAR EXPRESSION LANGUAGE

The regular expression ("reg-exp") component of the WDL is like strings against regular ones Expressions. It has been found that regular expressions do this are capable of describing the format of responses provided by a big one Amount of information sources are returned. However is The reg-exp language of this invention is capable of this information to adjust so that relevant Fields can be extracted in a faster and more convenient way can, than this earlier Languages and systems such as AWK or Perl can. The regular Expression component includes novel facilities that solve the problems of previous matching systems and thereby enable their use by Netbots.

A first novel facility allows the description of regular expressions to be broken up into pieces in a manner similar to a context-free grammar that defines a language through a set of rules for non-terminals in the grammar. See e.g. B. Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co., Section 4.2. Writing a single regular expression to represent the format of a page from a source of information, as in previous sys required often leads to a very broad and bulky expression, ie one that is difficult to write, understand and maintain. To solve this problem of existing systems, the reg-exp component determines a regular expression by a set of rules for components of the regular expression. These components are marked by non-terminals. However, unlike context-free grammars, the set of rules in the reg-exp component is not allowed to be recursive or mutually recursive. In other words, the rule for a particular non-terminal cannot directly or indirectly refer to other rules that relate to that particular non-terminal.

wodurch spezifiziert wird, daß die Antwort eine Seite ist, die aus einem Kopf gefolgt von null oder mehr Elementen, gefolgt von einem Schwanz besteht. Das Stichwort „END" kennzeichnet das Ende einer Regel bzw. Vorschrift. Die Non-Terminals der zweiten Ebene auf der rechten Seite („RHS") dieser Vorschrift <head>, <item> und <tail> sind durch ihre eigenen Vorschriften definiert:The use of a set of rules and non-terminals is exemplified below. A top-level non-terminal that defines an information response can be:

thereby specifying that the answer is a page consisting of a head followed by zero or more elements followed by a tail. The keyword "END" denotes the end of a rule or regulation. The non-terminals of the second level on the right ("RHS") of this regulation <head>, <item> and <tail> are defined by their own regulations:

To implement these rules, substituted the reg-exp component compiler the RHSs of the regulations for <head>, <item> and <tail> into the RHS of <page>. The result is, as if the wrapper was the big, bulky one compound rule at the highest Level would include:

If the regulations of the second Level would have contained further non-terminals on their RHSs, the Compilers continue to make appropriate substitutions until it no further non-terminals on the RHS of the composite regulation for the Regulation at the highest Level. Due to lack of recursion or mutual recursion ends this substitution.

wobei „stuff" ein reserviertes Wort ist. Stuff ist so definiert, daß es mit allen Schriftzeichen vom momentanen Schriftzeichen bis zum ersten Auftreten des Strings "literal-string", wobei dieser nicht umfaßt ist, zusammenpaßt, wobei es sich um einen wörtlichen String handeln muß. Dieses Konstrukt ermöglicht eine kompakte, effiziente und Backtracking-freie Implementierung dieses gebräuchlichen allgemeinen und wichtigen Idioms.A second novel facility allows groups of characters to be dropped into a string without backtracking. In previous regular expression matching systems, this relatively conventional requirement is implemented in a manner that requires storing many backtracking points in a stack and that can result in excessive backtracking. For example, the Perl idiom ", *"'' of the prior art, which matches any number of appearances of each character, or the Perl idiom "[^ \ d] * \ d, which corresponds to all non-character characters until the first occurrence one place, causing excessive backtracking during a match. This is inefficient and is not preferred because information responses should be parsed quickly. See e.g. B. Schwartz, 1993, Learning Perl, O'Reilly & Associates, Inc., Chapter 7. To solve this problem, the reg-exp component introduces a simple and direct syntax for this common idiom:

where "stuff" is a reserved word. Stuff is defined to match all characters from the current character to the first occurrence of the string "literal-string", which is not included, which is a literal string This construct enables a compact, efficient and backtracking-free implementation of this common and important idiom.

A third new facility allows that relevant Data fields can be taken from any complex regular expressions. Action language statements can Then on the RHS of a non-terminal for processing be embedded when this non-terminal is synchronized and with the variable bindings that occur each time a match occurs of this non-terminal are up to date. In the case of the previous example can expand the definition for <item> as follows become:

Whenever <item> matched , $ 0 becomes the string matched by stuff in parentheses set and then the output instruction is processed. In this In this case, $ 0 is bound to characters followed by "Data:" and which the newline character precedes.

Prior art systems such as AWK and Perl have no such facility on. Although they set variables such as $ 0, $ 1, etc., this only happens after the only compound regular expression that defines <page> is matched. In other words, the entire page is matched before variables are set. Therefore, the relevant data fields in AWK and Perl are lost in all but the last <item> if there is more than one <item> on the <page>. The reg-exp component of the WDL solves this problem by allowing a specification of actions that are executed multiple times, once for each non-terminal comparison and each time with different variable bindings.

The following is the description considered the reg-exp language. This includes certain preferred ones Basic level features: definition of regular non-terminal expressions; Embed action language instructions in regular expression rules; Operators for expressing a change and a repetition and a literal String matching. For It becomes understandable to experts be that one preferred reg-exp Base level language with equivalents semantic possibilities of expression using a slightly different selection of features can be designed, and that the reg-exp language component of the WDL such well-known equivalents includes. In particular, the reg-exp language renaming of variables and known grammatical Transformations based on the following rules or regulations be applied.

With optional versions can the preferred basic features expanded with additional features such as: a special disjunction ("||"); Repetition of one any integer; Matching with character classes; one local string memory; Anchor character. Such additional Features are standard with the exception of the special disjunction, which causes the listed alternatives are compared at the same time, if the string regarding the syntax is analyzed, being the first appropriate alternative returned becomes. In contrast, it fits the regular Disjunction with any alternative in the listed sequence together, with backtracking until success is achieved. The additional Characteristics can be added to the base level language in a known manner. See e.g. B. Schwartz, 1993, Learning Perl, O'Reilly & Associates, Inc .; Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co .; Hopcroft et al., Introduction to Automata Theory, Language Computation, Addison Wesley Publishing Co.

In another alternative embodiment can Explanations added to control the backtracking to control how the regular Match the expressions to improve. If from a specific part of a regulation would be known that he no backtracking required the section between specifications to be placed by the compiler and instruct interpreters to use a finite state machine without provision generating a backtracking. This enables part of the regulation to be more efficient than is otherwise compared.

The preferred action language syntax the base level is by the following in standard notation expressed Given grammar.

In a few words, a regulation specifies a certain <nonterminal> in such a way that it recognizes a certain regular expression. A regular expression can include: disjunctions ("|");sequences; zero or more repetitions ("+"); one or more repetitions ("+"); and zero or a repeat ("?"). Expressions can be: literal strings enclosed in double quotes; the special character stuff; parenthesized regular expressions; Non-terminals defi by another regulation must be kidneyed; or instructions written in the action language.

THE WRAPPER DESCRIPTION LANGUAGE

A finished wrapper description may be:

Thus, the preferred WDL entities include one Statement in the action language, typically a sequence of action language instructions, which is an optional group of regulations in the reg-exp language that follows a regular expression to match a response returned from information sources.

A finished wrapper description to process the instruction as described below processed. Typically, the statement includes, among other things Call to the built-in functions fetch () and parse (). The built-in The parse () function tries one returned by fetch () Answer by calling a non-terminal through the attached regulations is defined to match, each with a regular expression Are defined. If the regular expression match is successful, are all of the action language instructions typically found in regular expression are embedded, executed, typically some action instructions that are in non-terminals are embedded at a lower level, multiple times with the current one Operand bindings are processed each time a match occurs and the function parse () returns the value "1". If the comparison is not successful, none of the embedded ones Instructions processed and the function parse () returns the value "0".

5.5.2. IMPLEMENTATION THE WDL COMPONENT

The preferred implementation of the WDL is described in this section under the following headings: (1) Parsing or syntactic analysis of regular expression rules, (2) Intermediate code generation for regular expressions (3) runtime interpretation of regular expressions, (4) action language code generation and runtime interpretation. Note that this preferred implementation of the WDL is exemplary. It is known to those skilled in the art that alternatives to those herein described implementation exist. For example, the described processes are implemented differently, e.g. B. with different variables and different orders of individual steps. The processes can also be alternative Use algorithms to achieve the same effects e.g. B. for string matching to achieve. As another example, the disclosed discloses Implementation processes for the interpretation of different intermediate codes. Different intermediate codes can be used. For the regular Expression types are possible in different types of nodes, including z. B. nodes that have a variable list of successor states, to avoid that a Backtracking stack for successor states supports must become. For the Action language could equivalent to the disclosed address-based intermediate code an inverted batch-based Polish intermediate code can be used. Finally is it possible instead of an interpretation using the disclosed syntax-based methods directly into a Compile machine language.

In the rest of this section, a Parse tree node that has a "1" flag, Data "d" and derived Node "c_1, ..., c_n ", labeled" 1 <d; c_1, ..., c_n> ". These parse tree nodes can be constructed in a manner known in the prior art and it can then in a known manner z. B. by a pointer to a data area, that contains node data, Be referenced.

SYNTACTIC ANALYSIS OF REGULAR EXPRESSION REGULATORY

The first step in the preferred Implementation of compiling a wrapper description is a syntactic analysis of the regulations of the reg-exp language and the instructions of the action language. The input to this step are the regulations of the reg-exp language that are to be compared regular Define expression. The output of this step is an intermediate code in the form of a set of parsing trees, one parsing tree for the Regulation of the highest Level and additional Parse trees for every Regulation of a lower level are provided.

In a preferred embodiment, the processing of this step is carried out by syntactical analysis in accordance with a recursive descending syntactic analysis algorithm (parser) and outputting the syntax analysis tree in accordance with a syntax-oriented translator. Experts are familiar with the construction of a recursive descending compiler for the syntax of the reg-exp language described above. For example, it is understandably illustrated with examples in textbooks such as Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co. in sections 2.4 and 4.4. A syntax-oriented structure of syntax analysis trees is covered by examples in section 5.2. This Invention is not limited to this preferred embodiment. Alternative syntactic analysis techniques are known in the art and this invention encompasses implementations using such techniques as LL or LR parsing. In general, see also Aho et al., Chapter 4. This invention also encompasses alternative techniques of intermediate code generation that are known in the art. In general, see also Aho et al., Chapter 5.

• 1. Rule: Erzeuge den Knoten "Rule <nonterminal-Name; node-for-regexp>." Dies ist der Knoten für eine gesamte Vorschrift, die mit ihrem Non-Terminal-Namen gekennzeichnet ist.
• 2. Regexp: Erzeuge den Knoten "alternatives <node_for_sequence_1, ..., node_for_sequence_n>". Das ist der Knoten für eine Disjunktion ("|") für alternative reguläre Ausdrücke, die auf eine Übereinstimmung in der aufgelisteten Reihenfolge getestet werden, wobei die erste erfolgreiche Übereinstimmung zurückgegeben wird.
• 3. Sequence: Erzeuge den Knoten "Sequence <node_for_repetition_1 ..., node_for_repetition_n>." Das ist der Knoten für eine Sequenz regulärer Ausdrucksmuster, von welchen jedes sequentiell übereinstimmen muß.
• 4. Repetition: Erzeuge den Knoten "Repetition <type; node_for_term>." Das ist der Knoten für eine Wiederholung, wobei type ein Element ist, aus der Gruppe bestehend aus "?" (0 oder 1 Wiederholung), "+" (eine oder mehrere Wiederholungen) und "*" (0 oder mehr Wiederholungen).
• 5. String_In_Double_Quotes: Erzeuge den Knoten "String <literal_string>." Dies ist der Knoten, um einen wörtlichen String abzugleichen.
• 6. Stuff: Erzeuge den Knoten "Stuff<>" für das reservierte Wort "stuff".
• 7. (Regexp): Erzeuge den Knoten "Sequence <OpenParenthesis<i>, node_for_Regexp, CloseParenthesis<i>>." Dies ist der Knoten, der eine Zuordnung zu einer sequentiell numerierten Variable auf einen Abgleich durch "Regexp" bewirkt. Der Knoten "OpenParenthesis<n>" ist ein Knoten, der die n-te offene Klammer darstellt, die bei der sequentiellen syntaktischen Analyse der RHS der momentanen Vorschrift angetroffen wird. Die Vorschrift "CloseParenthesis<n>" ist ein Knoten, der die entsprechende n-te schließende Klammer darstellt, die angetroffen wird.
• 8. <nonterminal>: Erzeuge den Knoten "Nonterminal <nonterminal_name>," als ein Beispiel eines Non-Terminal.
• 9. Action: Erzeuge den Knoten "Action <node_for_action_language_statement>."

The specification for the parsing analysis includes rules for the parsing tree nodes to be generated when each parsing rule is recognized by the parsing algorithm. For each of the previous reg-exp syntax rules, the following nodes, which are identified by the non-terminal of the rule, are created:

• 1. Rule: Create the node "Rule <nonterminal name; node-for-regexp>." This is the node for an entire rule that is identified by its non-terminal name.
• 2. Regexp: Create the node "alternative <node_for_sequence_1, ..., node_for_sequence_n>". This is the node for a disjunction ("|") for alternative regular expressions that are tested for a match in the order listed, returning the first successful match.
• 3. Sequence: Create the node "Sequence <node_for_repetition_1 ..., node_for_repetition_n>." This is the node for a sequence of regular expression patterns, each of which must match sequentially.
• 4. Repetition: Create the node "Repetition <type;node_for_term>." This is the node for a repetition, where type is an element from the group consisting of "?" (0 or 1 repetition), "+" (one or more repetitions) and "*" (0 or more repetitions).
• 5. String_In_Double_Quotes: Create the node "String <literal_string>." This is the node for matching a literal string.
• 6. Stuff: Create the node "Stuff <>" for the reserved word "stuff".
• 7. (Regexp): Create the node "Sequence <OpenParenthesis <i>, node_for_Regexp, CloseParenthesis <i>>." This is the node that causes an assignment to a sequentially numbered variable on a comparison by "Regexp". The "OpenParenthesis <n>" node is a node that represents the nth open parenthesis encountered in the sequential parsing of the RHS of the current regulation. The "CloseParenthesis <n>" rule is a node that represents the corresponding nth closing bracket that is encountered.
• 8. <nonterminal>: Create the node "Nonterminal <nonterminal_name>," as an example of a non-terminal.
• 9. Action: Create the node "Action <node_for_action_language_statement>."

This is a node of an example an action language instruction in which the node_for_action_language_statement an intermediate code for represents the action language instruction.

These regulations that worked through if the analysis algorithm has the appropriate reg-exp language syntax rule recognizes, generate a parsing tree that is out the listed node types is formed in a true structure are connected. This parsing tree will be in subsequent steps entered this process.

BETWEEN CODE PRODUCTION FOR REGULAR EXPRESSIONS

• 1. Spezielle Vorverarbeitung von Stuff-Knoten;
• 2. Eliminierendes Auftreten von Non-Terminals auf der RHS des Non-Terminals der obersten Ebene; und
• 3. Umwandeln der resultierenden RHS der Vorschrift der obersten Ebene in einen endlichen Automaten ("FSA").

Code generation in the preferred embodiment involves the following three steps:

• 1. Special preprocessing of stuff nodes;
• 2. Eliminating occurrence of non-terminals on the RHS of the top-level non-terminals; and
• 3. Convert the resulting RHS of the top level rule into a finite state machine ("FSA").

First, these steps become general and secondly described in detail.

First is a preprocessing of Stuff knot necessary to later the preferred counter-traversal method of generation of the FSA. Because an FSA isn't for a stuff element alone an FSA is required for the combination of a stuff node and the knot of the literal string, which must follow each stuff element, and only open and closing parentheses can be used between a stuff knot and its subsequent literal String. To achieve this, the parsing tree traverses and each stuff knot with the following literal String by replacing both nodes with a new Stuff_and_String node connected. The new nodes considered also parentheses in between.

The second step in code generation substitutes all non-terminals on the RHS of the non-terminal of the highest level with their respective RHSs to form a single composite regulation for the to generate entire regular expression. During this substitution, it is necessary to renumber the occurrences of variables into action language instructions.

For example, consider that wrapper:

Here, $ 2 refers to the output instruction in <page> on ("dan") while $ 0 in the output instruction in <a> refers to (stuff "cody"). After Substitution would the RHS of <page> expanded as follows if the variables in the output instruction are not renumbered would be:

Here, however, $ 0 refers to ("dave") instead of (stuff "cody") while looking $ 2 refers to (stuff "cody") instead of ("dan"). To one To maintain correct variable assignment, the variable references must can be renumbered as follows:

• 1. Char_branch: Verzweigt zu einem der 256 möglichen Nachfolgezustände, die von dem momentanen Schriftzeichen abhängen und rückt die momentane Leseposition vor;
• 2. Action: Führt einen Block von Aktionssprachenanweisungen aus;
• 3. Marker: Zeichnet die momentane Eingabestringposition plus oder minus eines bestimmten Versatzes auf einem Markierungsstapel auf;
• 4. Success: Wenn erreicht, war die syntaktische Analyse erfolgreich;
• 5. Fail: Wenn erreicht, ist der momentane Versuch der syntaktischen Analyse fehlgeschlagen und der FSA muß entweder zum vorherigen Backtracking-Punkt zurückverfolgen oder fehlschlagen, falls keine Backtracking-Punkte verfügbar sind;
• 6. Push: Schiebt eine Konfiguration, die einen FSA-Zustand und die momentane Eingabestringposition umfaßt, auf den Backtracking-Stapel für ein späteres Backtracking.

In the third step in the preferred embodiment of the code generation process, the processed and expanded RHSs are converted to an FSA by performing an opposite traverse of the parsing tree, which is the top level regulation RHS, while each node is in turn converted to an FSA. The FSAs have several types of states, the most important of which are:

• 1. Char_branch: branches to one of the 256 possible successor states that depend on the current character and advances the current reading position;
• 2. Action: Executes a block of action language instructions;
• 3. Marker: records the current input string position plus or minus a certain offset on a marker stack;
• 4. Success: If reached, the parsing was successful;
• 5. Fail: If reached, the current attempt at parsing has failed and the FSA must either trace back to the previous backtracking point or fail if no backtracking points are available;
• 6. Push: Pushes a configuration that includes an FSA state and the current input string position onto the backtracking stack for later backtracking.

Code Generation STEP 1: PRE-PROCESSING

The preferred preprocessing of Stuff node begins with expanding or flattening nested ones Sequences, d. H. Sequence <> elements in other Sequence <> elements are. This is done according to the following Process executed:

Next, each occurrence of a stuff node is replaced by a stuff_and_string node, which also takes into account the following literal string and all parentheses in between. On each occurrence of "stuff" in a wrapper is followed by a literal string with the semantic result that "stuff" matches all characters from the current position up to, but not including, the first occurrence) of the following literal string. Only open and closing brackets can appear between stuff and the literal string. In the preferred embodiment, this replacement is preferably done according to the following process:

This process links the stuff node, the literal String node c_j, and all parentheses in between, ... c_j - 1, to the only Stuff_and_String node; c_i + 1, ..., c - j - 1>.

Code Generation STEP 2: SUBSTITUTION AND VARIABLE RENAME

After the preprocessing is completed is, non-terminals on the RHS are the highest level requirement preferably substituted and all action statement variables renumbered. For the substitution and variable numbering preferably a process is used of the two functions EXPAND_REC and EXPAND_ACTION and a global one PAREN_COUNT variable used. EXPAND_REGEXP is called recursively, to substitute RHS non-terminals, with a call to the non-terminal the highest Level is started. PAREN_COUNT is initialized to zero and incremented with substitution on each encountered "(". PAREN_COUNT thus includes a count the total number of "(" that have been encountered so far were. Then during the parentheses found in the substitution from their previous number renumbered to the current value of PAREN_COUNT and variables in renumbered the action instructions in an appropriate manner. For example, if PAREN-COUNT is currently eight, an OpenParenthesis <2> node is replaced by one OpenParenthesis <8> node replaced and an Output ($ 2) statement is replaced by an Output ($ 8) statement. EXPAND_ACTION is leading one Renumber the action instruction variable by. These processes are preferably carried out as follows:

CODE GENERATION PART 3: GENERATION OF A FINAL MACHINE

In the final step of code generation in the preferred embodiment, an FSA is generated that represents the substituted and processed regular expression. Although algorithms for generating such FSAs are known, they have not provided any facilities in the past, for example, to embed action language instructions in such FSAs. Accordingly, the fol Description to these new features of the preferred embodiment of this process, which are directed to the support of the action language instructions and the other novel features of the reg-exp language.

• (1) Char_branch<next_state_0, ..., next_state_225>: Wenn der momentane Zustand ein char_branch- Zustand ist, wird der nächste Zustand gemäß dem ASCII-Wert i des momentanen Eingabeschriftzeichens als next_state_i ausgewählt und der Eingabezeiger wird auf das nächste Schriftzeichen im Eingabestring vorgerückt.
• (2) Marker<num, open/close_flag, offset, next_state>: Wenn der momentane Zustand ein Markierungszeichenzustand ist, wird ein Datensatz auf einen Laufzeitstapel geschoben, der als der Markierungsstapel bekannt ist, der die Schriftzeichenposition einer Klammer enthält, die im Eingabestring angetroffen wird, plus dem angezeigten Versatz und einer Kennzeichnung, ob diese Klammer offen oder geschlossen ist, und der nächste Zustand wird auf next_state gesetzt. Eine beispielhafte Markierung kann einen Datensatz verschieben, der anzeigt, daß die fünfte offene Klammer an der momentanen Eingabeposition aufgetreten ist.
• (3) Action<complied_action_statements, next_state>: Wenn der momentane Zustand ein Aktionszustand ist, werden die Aktionssprachenanweisungen abgearbeitet, die durch compiled_action_statements dargestellt sind und der nächste Zustand wird auf next_state gesetzt.
• (4) Success<>: Wenn der momentane Zustand der Erfolgszustand ist, wurde ein String erfolgreich abgeglichen und dieser FSA endet.
• (5) Push<state, next_state>: Wenn der momentane Zustand ein Verschiebezustand ist, wird die momentane Konfiguration des FSA auf einen Laufzeitstapel verschoben, der als der Backtracking-Stapel bekannt ist, und der nächste Zustand wird auf next_state gesetzt. Eine FSA-Konfiguration ist ein Datensatz, der eine Identifizierung zumindest des momentanen Zustands zusammen mit der momentanen Position in dem Eingangsstring enthält. Push wird verwendet, um die nicht-deterministischen Konstrukte in der regulären Ausdruckssprache zu unterstützen. Ein beispielhaftes nicht-deterministisches Konstrukt ist die Disjunktion "reg-expr1|reg-expr2", die durch einen FSA abgeglichen wird, der erstens einen Backtracking-Zustand auf den Backtracking-Stapel schiebt, und dann zweitens versucht, den FSA entsprechend zu reg-expr1 zu starten. Falls dies fehlschlägt, verfolgt er zurück und (c) versucht den endlichen Automaten entsprechend zu reg-expr2 zu starten.
• (6) Failure<>: Wenn der momentane Zustand der Fehlerzustand ist, wird ein Backtracking-Datensatz aus dem Backtracking-Stapel angehoben und der nächste Zustand und der momentane Eingabezeiger werden auf die Inhalte des Backtracking-Datensatzes gesetzt. Falls der Backtracking-Stapel leer ist, konnte der FSA den Eingabestring nicht abgleichen und endet.

An FSA output from this process begins processing in an initial state, placing an input pointer at the beginning of the input string and then repeatedly executing one of six basic procedures according to its current state. These procedures set a new current state and typically affect one or more of the data structures accessed by the FSA. The six types of states and their procedures are as follows:

• (1) Char_branch <next_state_0, ..., next_state_225>: If the current state is a char_branch state, the next state is selected as next_state_i according to the ASCII value i of the current input character and the input pointer becomes the next character in the input string advanced.
• (2) Marker <num, open / close_flag, offset, next_state>: If the current state is a marker character state, a record is pushed onto a runtime stack known as the marker stack that contains the character position of a parenthesis found in the input string , plus the displayed offset and an indication of whether this bracket is open or closed, and the next state is set to next_state. An exemplary marker can move a record that indicates that the fifth open bracket has occurred at the current input position.
• (3) Action <complied_action_statements, next_state>: If the current state is an action state, the action language instructions represented by compiled_action_statements are processed and the next state is set to next_state.
• (4) Success <>: If the current state is the success state, a string has been successfully compared and this FSA ends.
• (5) Push <state, next_state>: If the current state is a move state, the current configuration of the FSA is shifted to a runtime stack known as the backtracking stack, and the next state is set to next_state. An FSA configuration is a data record that contains an identification of at least the current status together with the current position in the input string. Push is used to support the non-deterministic constructs in the regular expression language. An exemplary non-deterministic construct is the disjunction "reg-expr1 | reg-expr2", which is compared by an FSA, which firstly pushes a backtracking state onto the backtracking stack and then secondly tries to regulate the FSA accordingly. start expr1. If this fails, it traces back and (c) tries to start the finite machine accordingly to reg-expr2.
• (6) Failure <>: If the current state is the fault state, a backtracking data set is raised from the backtracking stack and the next state and the current input pointer are set to the contents of the backtracking data set. If the backtracking stack is empty, the FSA could not match the input string and ends.

The generation of the FSA for one entered regular Expression is made using an opposite traverse of the parsing tree previously produced. If the parse tree is traversed, a finite automaton is added to each node v matches with the subexpression that goes through the subtree is shown, which is rooted at v. This finite automaton is the one Value of the v.machine variable. The final FSA edition is the FSA, which is appended to the root of the parsing tree when the creation process ends.

While the crossing becomes certain finite automata for professionals already known methods generated. These machines recognize regular standard expression constructs and can with known methods are established. General reference sources for the Generation of such finite standard machines include the following: Aho et al., 1974, The Design And Analysis Of Computer Algorithms, Addison Wesley Publishing Co., Chapter 9, Aho et al., 1986, Compilers Principles, Techniques, and Tools, Addison Wesley Publishing Co., Chapter 3; Hopcroft et al., 1979, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., section 2.5; Sedgewick, 1990, Algorithms in C, Addison-Wesley Publishing Co., Chapter 16.

Furthermore, the disclosed Process determined Adopt construction methods that are advantageous for a alternative execution changed could be. For example, the machine that represents a literal string can according to the Boyer Moore or another string matching algorithm. Please refer z. B. Sedgewick Chapter 19.

The preferred process is:

This process uses a MAKE_SEQUENCE function, which put together machines from a series of sub-machines builds. The assembled machine works each of the sub-machines in the sequence until a sub-machine fails, whereby in this If the assembled machine also fails, or all sub-machines are successful, in which case the composite automaton is successful. In other words, the compound starts Automat the first submachine. If this is successful, he starts the second. If it is successful, it starts the third etc.

If any sub-machine fails, d. H. reached a Failure <> status, fails the composite machine as well.

This is the preferred setup from FSAen, the regular expressions that of the reg-exp language of this invention. Next up described the FSA processing.

LAUFZEITINTERPRETIERUNG FROM REGULAR EXPRESS

In a preferred embodiment the FSA, the one regular Represents expression by interpreting those in the previous code generation steps generated structure processed. The interpreter prefers to intervene to multiple data structures including the current state the FSA, a pointer to the current character position the input string, a backtracking stack, and a marker stack to. The backtracking stack contains records that characterize the interpretation status of the FSA and will open a way known in the art used to backtracking to implement if an attempted partial comparison of the input string fails. Configuration records include the current state and the current input position. In an alternative version can shifting states by implementing states avoided with a list of possible next states become.

In the preferred implementation the new variable binding and action instruction features The reg-exp language of this invention becomes an additional one Stack using marker sign stack. The semantics of this Characteristics requires that none Actions performed until the entire regular expression matching process is successful. Upon success, all actions are then linked to the variable abge who works during the syntactic analysis have occurred. That means a single Variable, e.g. B. $ 1, different ties in the same action instruction may have worked through several times if the comparison was successful can be.

This semantics is preferred in the execution using the marker character stack in the following Way implemented. If the current interpreted state is on Action <> state is being the action language instruction was not processed immediately. Much more the action instruction code on the marker stack pushed. Similar if the current state is a flag state, which is a bracket in the regular Expression definition represents the information contained in the marker stack is present, pushed onto the stack of marking characters. This information allows finding the position of the beginning or end of a current one Variable binding in an input string. To process a Prevent action language instructions from occurring during a failed attempted partial adjustment taken into account the marker stack will be at an appropriate level raised when the FSA is backtracking. Thus include the machine configuration and the configuration record on the backtracking stack of the the current position in the marker stack.

Action language instructions will be to a final one Matching success by scanning the stack of markers from worked from bottom to top. With this scanning, variable bindings are set, as identified by the marker state records, and Actions processed as identified by the action status records is. In the event of a match failure, no action language instructions are provided processed.

In detail, execution of the preferred implementation works as follows:
GLOBAL VARIABLE current_state = initialized to the initial automatic state
GLOBAL VARIABLE input_pos = initialized to the address of the beginning of the input string
GLOBAL VARIABLE BT_STACK = initialized to an empty stack
GLOBAL VARIABLE MARK_STACK = initialized to an empty batch
REPEAT UNTIL one of the following clauses gets out

For example, in the previous FOR loop, the binding of $ 2 to the sub-string of the input string set that starts with open_marks [2] and starts with close_marks [2] ends.

ACTION LANGUAGE Code Generation AND DURATION INTERPRETATION

In a preferred embodiment Action language instructions in a bytecode type with variable Length one Intermediate language compiled by a bytecode interpreter is processed with runtime. The syntax of the previously described Action language is known by any suitable syntactic Analysis technology, for example by a syntactic LL or LR analysis parsed. Appropriate syntactical analysis techniques are illustrated with examples in Aho et al., 1986, Compiler Principles, Techniques, and Tools, Addison Wesley Publishing Co., Chapter 4. While The syntactic analysis will include all those occurring in the wrappers Assigned unique numbers to variables. According to a preferred one Assignment are named variables, e.g. B. $ x, $ abc, in order, in which they are encountered, consecutive, positive integers assigned and the numeric variables, the matched sub-strings, e.g. B. $ 0, Denote $ 1, $ 2, etc., assigned consecutive, negative integers, where the numeric variable $ i is assigned to the number (i + 1).

• 1. Funktionsaufrufe: Kodierung: 0 funcode numargs <var_0> <var_1> ... <var_numargs> Bedeutung: var0 ist das Ergebnis der Funktion zugeteilt, identifiziert durch „funcode" auf die Argumente var_1, ..., var_numargs der Zahl „numargs". Jede eingebaute Funktion, z. B. agrc, argv, etc. und jeder Operator, z. B. "+", "–", "*", etc. der Sprache weist ihre eigene eindeutige ganze Zahl „funcode" auf.
• 2. Verzweigungsbefehle: Kodierung: 1 <offset> <var0> Bedeutung: falls var0 wahr ist, verzweige um einen relativ zum Verzweigungsbefehl versetzten Betrag. Kodierung: 2 <offset> <var0> Bedeutung: falls var0 falsch ist, verzweige um einen relativ zum Verzweigungsbefehl versetzten Betrag. Kodierung: 3 <offset> Bedeutung: verzweige immer um einen relativ zum Verzweigungsbefehl versetzten Betrag.
• 3. Lade Konstante Befehle: Kodierung: 4 <var0> <null-terminated-string> Bedeutung: var0 wird die null-terminated-string-Konstante zugeteilt. Kodierung: 5 <var0> <floating-point-constant> Bedeutung: var0 wird die Fließkommakonstante zugeteilt
• 4. Bewege Befehle: Kodierung: 6 <var0> <var1> Bedeutung: var0 wird von var 1 kopiert.
• 5. Ausgabebefehle: Kodierung: 7 <var0> Bedeutung: gibt ein Element var0 zum momentanen Tupel aus Kodierung: 8 Bedeutung: beendet das momentane Tupel, bewirkt, daß es zum Netbot zurückgegeben wird
• 6. Syntaxanalysebefehle: Kodierung: 9 <var0> <var1> <Adresse des endlichen Automatens für <nt>> Bedeutung: var0 wird das Ergebnis der syntaktischen Analyse von var1 gemäß dem regulären Ausdruck zugeteilt, der mit <nt> gekennzeichnet ist.
• 7. Verlasse Befehle: Kodierung: 10 Bedeutung: Verlasse den momentanen Aktionssprachenblock

An intermediate code is generated by known translation techniques aimed at the syntax. Suitable syntax-based translation techniques are exemplified in Aho et al. set out in Chapter 8. The preferred intermediate code is shown below. In this representation, commands of the intermediate language have the format of a command code with possibly modifying information, followed by zero or more arguments. The variables are labeled <var>, where var is the integer 2-byte coding of the variable. The relative branch offsets are encoded as whole 4-byte numbers. All branches are relative to the current instruction address, ie the address of the branch instruction itself, so that the byte code can be relocated.

• 1. Function calls: Coding: 0 funcode numargs <var_0><var_1> ... <var_numargs> Meaning: var0 is the result of the function assigned, identified by "funcode" to the arguments var_1, ..., var_numargs of the number "numargs ". Every built-in function, e.g. B. agrc, argv, etc. and any operator, e.g. B. "+", "-", "*", etc. of the language has its own unique integer "funcode".
• 2. Branch instructions: Coding: 1 <offset><var0> Meaning: if var0 is true, branch by an amount offset relative to the branch instruction. Coding: 2 <offset><var0> Meaning: if var0 is wrong, branch by an amount offset relative to the branch instruction. Coding: 3 <offset> Meaning: always branch by an amount offset relative to the branch instruction.
• 3. Load constant commands: Coding: 4 <var0><null-terminated-string> Meaning: var0 is assigned the null-terminated-string constant. Coding: 5 <var0><floating-point-constant> Meaning: var0 is assigned the floating point constant
• 4. Move commands: Coding: 6 <var0><var1> Meaning: var0 is copied from var 1.
• 5. Output commands: Coding: 7 <var0> Meaning: outputs an element var0 to the current tuple Coding: 8 Meaning: ends the current tuple, causes it to be returned to the Netbot
• 6. Syntax analysis commands: Coding: 9 <var0><var1><address of the finite state machine for <nt>> Meaning: var0 is assigned the result of the syntactical analysis of var1 according to the regular expression, which is marked with <nt>.
• 7. Leave commands: Coding: 10 Meaning: Leave the current action language block

In alternative versions can different intermediate codes or even no intermediate code used become. For example equivalent to the address-based intermediate code disclosed above an inverted batch-based Polish intermediate code can be used. optional no intermediate code is used and the action language instructions are compiled directly into a machine language. These two Alternatives can using the disclosed syntax-based methods be implemented. See e.g. B. Aho et al.

A processing of wrapper actions is in a preferred embodiment carried out in several steps. First memory is allocated to all variables and all variable values save. The number of variables is known after the Action instructions were parsed. All variables are initialized to an unallocated value. Next up a CURRENT_INSTRUCTION pointer initialized to point to the next Command of the bytecode to be processed shows. Then the interpreter kicks in in a loop that retrieves the work code to the one by CURRENT_INSTRUCTION is shown leads the encoded simple action according to the above bytecode language described and updates CURRENT_INSTRUCTION so that this either on the next command shows, or with accepted branch instructions with the offset value is modified. The interpreter ends the processing as soon as he meets an exit command.

The built-in syntax analysis function is processed at runtime by calling the FSA interpreter to get the compiled regular To interpret the expression code that describes the finite automaton. Output (a_1, ..., a_n) instructions are translated and then processed of the bytecode instruction code 7 for each variable in the output list is processed, whereupon a bytecode command code 8 follows that ends the current tuple, i.e. H. the end of the output instruction marked.

6. SPECIAL VERSIONS leadership OF REFERENCES

The present invention is in its scope is not due to the special designs described here, limited. For professionals various modifications of the invention will become apparent those described in the foregoing description and the accompanying figures. It is intended that such Modifications fall within the scope of the appended claims.

Claims (16)

A wrapper description language process, which formatting and / or recognizing a string according to a Has description written in a wrapper description language the wrapper description language is suitable for a entire regular Expression as regular expression components to describe in such a way that recognizing a single regular expression component of the entire regular Expressive actions can be performed with variables that for example for the recognition time of the regular Expression components are bound, these actions actually only accomplished if the entire regular Expression is also recognized. The wrapper description language method of claim 1, further comprising the step of executing one or more instructions written in an action language, the actions language is capable of specifying the effects of operators on variables, the effects of functions on variables, and of the sequence of instructions, the instructions of the action language being further adapted to the wrapper description language for specifying the effects due to of recognizing the regular expression components occur to be embedded. Method for assisting a user in querying of information available from information sources connected to a network, the method comprising: Select the one or more sources of information that are most relevant to a user query are; Format the user query for each relevant information source according to a description of each relevant information source, the in the wrapper description language is written using the method of claim 1; Transfer the formatted query for each of the relevant information sources; Extract of data fields for the user query are relevant, from answers provided by the relevant Sources of information returned were, according to the description the relevant source of information that returns the response; and represent the relevant data fields for the user. The method of claim 3, which further comprises an estimate of an extraction the relevance of the answers for has the user query. The method of claim 3 or 4, wherein selecting the further features: Determining one or more concepts, to which the user query is related; and Pick one Information source as relevant if the information source is too is related to certain concepts. The method of claim 3, wherein a description an information source includes: an address of the information source in the network; a determination of one or more conceptual Classes for the source of information is descriptive; an implementation of Query arguments in selected User query fields as supplied to the information source; and a description of a format for displaying an answer on the user query, which can be parsed to data fields, the for the user query are relevant to extract. The method of claim 3, wherein the extracting from for the user query relevant data fields from responses by the relevant information sources were returned, furthermore having: in response to recognizing an entire regular expression, which is defined in the description of a relevant information source is run of at least one action that is in the entire regular expression is included on the response from the relevant information source returned was, using data from a relevant data field the answer to variables that are included in the action to tie. The method of claim 7, further comprising: Converting the whole regular Expression in a finite state machine and execution of the finite state machine, to the data fields for the user query are relevant to extract. Computer program product having commands to cause one or more computers to complete the process according to one of the preceding claims perform. A system for assisting a user to query information available from sources of information connected to a network, the system comprising: first processor means for selecting the one or more sources of information most relevant to a user query; second processor means for formatting the user query for each relevant information source in accordance with a description of each relevant information source written in a wrapper description language and for transmitting the formatted query to each of the relevant information sources, the wrapper description language means for specifying an overall regular Expression in the form of regular expression components, where actions can be performed with variables that are related to the recognition time of the regular expression component, the Aktio actually only be executed if the entire regular expression is also recognized; third processor means for extracting data fields on the user query from responses returned from the relevant information sources in accordance with the description of the relevant information sources returning the respective response; and a fourth processor means for displaying the relevant data fields for the user. The system of claim 10, wherein the first, second, third and fourth processor means in a single to a network connected computer, the computer being a CPU and has a memory. The system of claim 10, wherein the first, second, third and fourth processor means in separate to a network connected computers, with each of the computers one CPU and a memory. The system of claim 10, 11 or 12, wherein the fourth Processor means the relevant data fields by applying a Represents world wide web browser. The system of claim 10, 11, 12 or 13 which furthermore a first storage means connected to a network to save the descriptions of the information sources and Providing the descriptions on request of the second or third processor means. Combination of computer program products by a single or multiple computers connected to a network executable is to support a user to query information from information sources available which are connected to the network, the computer program products exhibit: a query router that receives the user query and the one or more sources of information that are most relevant to the user query are selected; a wrapper description database that has a description of each which contains sources of information, each description in a wrapper description language below Use of the method according to claim 1 is written; a Aggregation machine that contains the relevant information sources from the query router receives and the user query for each relevant information source as described in the description of each relevant Information source formatted in the wrapper description database, and which are the data fields for the user query are relevant, from answers provided by everyone of relevant information sources are returned, as described the relevant source of information that the respective answer returns extracted; and an input / output manager that formats the Query on each of the relevant information sources about the Network transfers and the Responses to the user query from the relevant information sources returned are delivered to the aggregation machine. Combination of computer program products according to claim 15, which further comprises: a user interface module, that receives the user query and deliver them to the query router, and that from the aggregation machine extracted data fields received and her for displays the user.