JP2004501412A - Method and apparatus for flexibly assigning tokenization procedures - Google Patents

Abstract

One embodiment of the present invention is a system for tokenizing text of a document by converting the text into tokens according to a unit of text having individual meanings to facilitate searching for text in the document. I will provide a. The system operates by receiving a document to be tokenized and retrieving a set of token instructions associated with the document. The system then tokenizes the document by translating in a manner specified by the set of token instructions into tokens corresponding to a unit of text having individual meanings.
[Selection diagram] FIG.

Description

[0001]
(background)
The present invention relates to an index structure for facilitating computerized data search. More particularly, the present invention relates to a method and apparatus for flexibly assigning a tokenization procedure for converting a document into tokens associated with a unit of text having a discrete meaning, such as a character type or a number.
[0002]
The explosive growth of the Internet has been strongly tied to the development of search engines that allow users to quickly search vast amounts of text data from thousands and millions of different websites. Users interested in a particular topic only need to enter them into a search engine to receive links to various web pages containing multiple keywords.
[0003]
Search engines typically create an "index" of documents (such as web pages) that are being used on the WWW (world wide web). Typically, an index is to store a discrete group of characters (or other meaningful text strings) in a more compact and easily searchable form known as a "token".
[0004]
The fact that documents can have a wide variety of different formats that need to be indexed differently can complicate the process of building an effective index. For example, a valid index in a technical article may include the abstract and title of the technical article, but not the body of the technical article, while a valid index on a television schedule includes ratings in individual television programs. obtain.
[0005]
The process of generating the index is based on a common document format, such as Hypertext Markup Language (HTML) or Extensible Markup Language (XML), where a number of important information for search purposes is stored in attribute fields; Complicated by the fact that they are not usually stored in text.
[0006]
Further, the structure of a document can change over time, which can require a changing index structure. For example, assume that the product catalog structure is updated to include the consumer outlook on individual products. This change may require a changing index to include these consumer perspectives.
[0007]
Existing systems index documents using ad-hoc rules. For example, some ad hoc rules generate an index for all textual information that is not in an attribute field. Unfortunately, such ad hoc rules often contain a lot of insignificant information and often eliminate important information.
[0008]
A similar problem exists when converting a document into tokens (tokenify this document) in the index generation process. In this indexing process, relevant parts of the document are converted into tokens relating to units of text having individual meanings, for example, character form or numbers. In English, character forms are usually delineated with blanks and punctuation marks. Therefore, the tokenization process is relatively simple. In contrast, languages such as Japanese do not have such a line. As a result, this tokenization process depends on contextual information and can be very complicated.
[0009]
This tokenization process may also be domain dependent. For example, an email period such as "person.dept@companyx.com" is a connected component, while a period in other textual information typically delineates word and sentence boundaries.
[0010]
Thus, the tokenization process varies between languages and between domains.
[0011]
(Abstract)
One embodiment of the present invention provides a system for tokenizing text in a document by converting the text in a document into tokens corresponding to units of text having individual meanings to facilitate text search. The system operates by receiving a document to be tokenized and retrieving a set of tokenized instructions associated with the document. The system then tokenizes the document by translating in a manner specified by the set of token instructions into tokens corresponding to units of text having individual meanings.
[0012]
In one embodiment of the invention, tokenizing the document uses a first set of token instructions to tokenize a first section of the document, and tokenizing the second section of the document with a token. Using a second set of token instructions to generate
[0013]
In one embodiment of the invention, this set of tokenized instructions is included in a plug-in module.
[0014]
In one embodiment of the invention, this set of tokenized instructions is driven via objects defined in an object-oriented programming system.
[0015]
In some embodiments of the invention, the system further uses the tokenized document in indexing the document. In a variation of this embodiment, the system makes the index available to a search engine, which allows the search engine to scan the index.
[0016]
In one embodiment of the present invention, the system retrieves a set of tokenized instructions from a remote address over a network.
[0017]
In one embodiment of the invention, this set of tokenized instructions is added to this document.
[0018]
In one embodiment of the invention, the set of tokenization instructions is included in a tokenization procedure associated with the document.
[0019]
In one embodiment of the invention, the document is retrieved from the client at the tokenization server. In this embodiment, the tokenization server returns the tokenized document to the client.
[0020]
In one embodiment of the present invention, this set of tokenized instructions is provided over a network from a remote server.
[0021]
(Detailed description)
The following description sets out that any person skilled in the art can make and use the invention, and is given in connection with the specific application and its conditions. Various modifications of this disclosed embodiment will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and to other embodiments without departing from the spirit and scope of the invention. It can be applied to applications. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.
[0022]
The data structures and codes described in this detailed description are typically stored on computer readable storage media, and the media can be any device or code capable of storing code and / or data used by a computer system. It can be a medium. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tapes, CDs (compact disks), and DVDs (digital video disks), and further includes computer instruction signals embedded in transmission media. (This signal may or may not have a modulated carrier wave). For example, the transmission medium may include a communication network such as the Internet.
[0023]
(Distributed computer system)
FIG. 1 shows a distributed computer system 100 according to an embodiment of the present invention. The distributed computer system 100 includes clients 102 and 118, which connect an index server 112 and a search engine 122 via a network 110.
[0024]
Network 110 may include any wired or wireless communication channel that can connect computer nodes to each other. This includes, but is not limited to, a private network, a broadband network, or a combination of networks. In one embodiment of the present invention, network 110 includes the Internet.
[0025]
Clients 102 and 118 include the capabilities of a computer and may include any node on network 110 that includes a communication mechanism over network 110.
[0026]
Client 102 includes a plurality of documents 104-106, which are integrated into an index 116 in index server 112. Index server 112 may include a node on a computer network that includes a mechanism for servicing requests from clients for computing and / or data storage resources. More specifically, index server 112 includes resources for generating index 116 in database 114 to index documents 104-106. Database 114 may include any type of mechanism for storing data in a non-volatile format. In one embodiment of the present invention, database 114 includes an ORACLE8® database distributed by Oracle Corporation of Redwood Shores, California.
[0027]
Client 118 includes a browser 120 that communicates with search engine 122 to scan index 116. Browser 120 may include any type of browser capable of browsing websites, such as the INTERNET EXPLORER® browser distributed by Microsoft Corporation of Redmond, Washington. Search engine 122 may include any type of computer system or application application that can search data.
[0028]
In operation, index server 112 retrieves documents 104-106 from client 102 and utilizes documents 104-106 to generate index 116. Note that client 102 may send documents 104-106 to index server 112. Alternatively, index server 112 may collect documents 104-106 from client 102.
[0029]
Index server 112 tokenizes portions selected from documents 104-106, and generates index 116 by generating index 116 from the tokens. Note that client 102 may itself be one server that makes documents 104-106 available over network 110.
[0030]
After the index 116 is generated, the client 118 sends a query 124 to the search engine 122 via the browser 120. Query 124 may identify target keywords to user's client 118. In response to the query 124, the search engine 122 searches the index 116 for documents containing the matched keywords in the index 116. If such a document is located, the search engine 122 returns the document in the list of query hits 126 to the browser 120.
[0031]
(Index server)
FIG. 2 illustrates how the index server 112 generates indices for different document types according to an embodiment of the present invention. In FIG. 2, index server 112 receives a number of different documents from different resources. The index server 112 integrates these different types of documents into the index 116. Note that index 116 may include one index that includes many different document types. Also, index 116 may include a different index for each document type.
[0032]
An unlimited number of document types can be indexed. For example, FIG. 2 shows a news document 202, a product catalog 204, a television program schedule 206, a document 208 containing user documentation, and a document 210 containing financial information. Each of these different document types may have a different document structure, and this structure may be defined in a language such as XML. Each of these different document structures may be associated with a different indexing scheme. In some documents, certain attributes may be included in this index. For example, in the documentation of several types of users, it may be advantageous to index an attribute that indicates whether this user's documentation is suitable for a novice or professional user.
[0033]
(Index style sheet and tokenization procedure)
FIG. 3 illustrates how a style sheet for indexing and a procedure for tokenization are generated and used to index a document according to an embodiment of the present invention. In FIG. 3, an index construction mechanism 310 in the index server 112 receives a document 302 as input and generates an index 312 for the document 302. Index 312 enters into large index 116 for document collection, and this collection is included in database 114 (from FIG. 1).
[0034]
During the index construction process, the index constructor 310 references the index style sheet 304 and the tokenization procedures 306-307. Index style sheet 304 includes a set of instructions that generate index 312 for document 302. For example, index style sheet 304 can identify which sections of document 302 should be skipped in generating index 312. The index style sheet 304 can also specify attributes of the document 302 included in the index style sheet 304. For example, an attribute may specify a minimum security level for a person to have access to document 302. Another attribute may specify a content rating (G, PG-13, PG, R, X) for the document 302.
[0035]
Tokenization procedures 306-307 specify how certain portions of document 302 are tokenized. For example, the tokenization procedure 306 specifies how a first part of the document 302 is tokenized, while the tokenization procedure 307 specifies how a second part of the document 302 is tokenized. Most documents will probably use one tokenization procedure, but other documents may include parts in different languages or parts from different domains that require different tokenization procedures.
[0036]
Index style sheet 304 is similar to a style sheet in a format specified by the XML standard. The format style sheet is used to specify display attributes, such as font and color, for displaying the XML document. Similarly, the index stylesheet 304 specifies how the index for the document 302 is generated.
[0037]
Although FIG. 3 shows index and token instructions in the form of style sheets and procedures, it should be noted that other representations are possible. For example, the index and token instructions may be included in a plug-in module that may be plugged into index builder 310.
[0038]
These index and token instructions can be referenced via objects defined in the object-oriented programming system. For example, an index parameter object may include a method for retrieving this instruction to build an index for document 302.
[0039]
This token procedure 306-307 can also assume the form of a code module that includes tokenized instructions, or can be provided by a remote service over a network.
[0040]
Also note that the index stylesheet 304 may include a reference term that can identify where the tokenization procedures 306-307 can be retrieved.
[0041]
The index builder 310 includes a standardized interface that can receive input from many different index style sheets and tokenization procedures. This enables the index builder 310 to generate indexes for a number of different document types using a number of different tokenization rules.
[0042]
(Tokenization process)
FIG. 4 shows an example of this tokenization process. In this example, one text "MAY 7, 2000" is divided into three tokens 402-404. Token 402 contains the word "MAY." Token 403 contains the day number "7," and token 404 contains the year number "2000." Each of these tokens is associated with a unique token number, which is used to generate this index. Using token digits leads to a more compact re-expression, since the token digits pick up strings that are larger than uppercase and smaller than white space. Further, during this search process, it is easier to look up a digit string than a character string.
[0043]
(Index generation process)
FIG. 5 is a flowchart illustrating a process for generating an index according to an embodiment of the present invention. The system starts by downloading a configuration file (step 502). This process may include downloading the configuration file over a network. The system then parses the configuration file (step 504) and identifies the address of style sheet 304 of the index in the configuration file (step 506).
[0044]
The system then downloads the style sheet 304 for the index from the identified address (step 508). This involves retrieving this stylesheet over the network from the location specified by the Universal Resource Locator (URL). Alternatively, the style sheet can be added to this document, and in any case, the style sheet for this index can be easily retrieved.
[0045]
The system then parses the index's stylesheet 304 so that the instructions in the index's stylesheet can be used during the index generation process (step 510).
[0046]
The system similarly identifies the address of the tokenization procedure 306 (step 512). (The address of the tokenization procedure 306 may be included in this configuration file or in the style sheet 304 of the index). The system then downloads the tokenization procedure 306 from the identified address (step 514). In some embodiments of the present invention, the tokenization procedure 306 may be retrieved from the same location as the style sheet 304 of the index. In another embodiment of the invention, the tokenization procedure 306 may be retrieved from another location.
[0047]
The system then enters the plurality of documents into index 116. This is accomplished by downloading one document to the index builder 310 (step 518) and then parsing the document using the instructions specified in the index's stylesheet 304 (step 520). Can be The system converts the parsed document into a token using tokenization procedure 306 (step 522), and generates an index using the token (step 524). This process is repeated for each of the documents entered into index 116.
[0048]
After the index 116 is completed, the system makes the index 116 available to the search engine 122 (from FIG. 1) so that the search engine 122 can scan the index 116 for query processing (step 526).
[0049]
FIG. 6 is a flowchart illustrating a process for dynamically generating an index that is updated for a document in accordance with an embodiment of the present invention. For some types of searches, the data has a limited lifetime. For example, in searching for current weather data, old weather data is not of interest.
[0050]
In these environments, certain embodiments of the present invention operate as described below. The system receives a search request (step 602). In response to the search request, the system checks the document creation date and time for any documents included in the search (step 604). If the system determines that the document is out of date (perhaps by comparing the document year to the limit year), the system causes a new version of the document to be generated (eg, by collecting new weather data) (step 606). ). The system then generates an index for the new version of the document (step 608). The process silently removes old versions of the document (step 610). Finally, the system performs a search that includes the newly updated index.
[0051]
The foregoing description of the embodiments of the present invention has been presented for purposes of illustration and description only. They are exclusive and are not intended to limit the invention to the form disclosed. Accordingly, many modifications and variations may be apparent to practitioners skilled in the art.
[0052]
For example, although the invention has been described with reference to a distributed computer system including clients and servers, the invention is not necessarily limited to a distributed client-server computer system. In general, the invention is applicable to any system that generates an index for text information or any system that tokenizes text information.
[0053]
Moreover, the above disclosure is not intended to be limited to the present invention. The scope of the invention is defined by the appended claims.
[Brief description of the drawings]
FIG.
FIG. 1 shows a distributed computer system according to an embodiment of the present invention.
FIG. 2
FIG. 2 illustrates how an index server generates indexes for different document types according to an embodiment of the present invention.
FIG. 3
FIG. 3 illustrates how indexing style sheets and tokenization procedures are used to index documents according to embodiments of the present invention.
FIG. 4
FIG. 4 shows an example of the tokenization process.
FIG. 5
FIG. 5 shows a flowchart illustrating a process for generating an index according to an embodiment of the present invention.
FIG. 6
FIG. 6 shows a flowchart illustrating a process for dynamically generating an updated index for old documents according to an embodiment of the present invention.

Claims (33)

A method of tokenizing text in a document by converting the text into tokens corresponding to units of text having individual meanings to facilitate searching for the text in the document,
Receiving the document to be tokenized;
Retrieving a set of tokenized instructions associated with the document;
Tokenizing the document in a manner specified by the set of tokenizing instructions by translating the document into tokens corresponding to a unit of text having individual meanings. Tokenizing the document comprises using a first set of tokenizing instructions for tokenizing a first section of the document; and a second tokenizing instruction for tokenizing a second section of the document. Using a set of The method of claim 1, wherein the set of tokenized instructions is included in a plug-in module. The method of claim 1, wherein the set of tokenized instructions is driven via an object defined in an object-oriented programming system. The method of claim 1, further comprising using the tokenized document in generating an index for the document. 6. The method of claim 5, further comprising causing the search engine to utilize the index so that the search engine can scan the index. The method of claim 1, wherein retrieving the set of tokenized instructions comprises retrieving the set of tokenized instructions over a network from a remote address. The method of claim 1, wherein the set of tokenized instructions is added to the document. The method of claim 1, wherein the set of tokenization instructions is included in a tokenization procedure associated with the document. The method of claim 1, wherein the document is received from a client to a tokenization server, and further comprising returning the tokenized document from the tokenization server to the client. The method of claim 1, wherein the set of tokenized instructions is provided by a remote service over a network. When executed by a computer, the computer translates the text in the document by converting the text into tokens corresponding to units of text having individual meanings to facilitate searching for the text in the document. A computer readable storage medium storing instructions for performing a tokenizing method,
Receiving the document to be tokenized;
Retrieving a set of tokenized instructions associated with the document;
Tokenizing the document in a manner specified by the set of tokenizing instructions by translating the document into tokens corresponding to a unit of text having individual meanings. Tokenizing the document comprises using a first set of tokenizing instructions for tokenizing a first section of the document, and a second tokenizing instruction for tokenizing a second section of the document. Using the set of computer-readable storage media of claim 12. 13. The computer readable storage medium of claim 12, wherein the set of tokenized instructions is included in a plug-in module. 13. The computer readable storage medium of claim 12, wherein the set of tokenized instructions is driven via an object defined in an object-oriented programming system. 13. The computer readable storage medium of claim 12, further comprising using the tokenized document if the method generates an index for the document. 17. The computer readable storage medium of claim 16, wherein the method further comprises causing the search engine to utilize the index so that the search engine can scan the index. 13. The computer-readable storage medium of claim 12, wherein retrieving the set of tokenized instructions comprises retrieving the set of tokenized instructions from a remote address over a network. 13. The computer readable storage medium of claim 12, wherein the set of tokenized instructions is added to the document. 13. The computer readable storage medium of claim 12, wherein the set of tokenization instructions is included in a tokenization procedure associated with the document. Said document is received at a tokenization server from a client,
13. The computer readable storage medium of claim 12, wherein the method further comprises returning the tokenized document from the tokenizing server to the client. 13. The computer readable storage medium of claim 12, wherein the set of tokenized instructions is provided by a remote service over a network. An apparatus for tokenizing text in a document by converting the text into tokens corresponding to units of text having individual meanings to facilitate retrieval of the text in the document,
A receiving mechanism configured to receive the document to be tokenized;
An instruction receiving mechanism configured to retrieve a set of tokenized instructions associated with the document;
A tokenization mechanism configured to tokenize the document by translating the document in a manner specified by the set of tokenization instructions into tokens corresponding to units of text having individual meanings. apparatus. If the document is of a hybrid token type, the tokenization mechanism uses a first set of tokenization instructions that tokenize a first section of the document, and a tokenization instruction that tokenizes a second section of the document. 24. The apparatus of claim 23, wherein the apparatus is configured to use a set of two tokenized instructions. 24. The apparatus of claim 23, wherein the set of tokenized instructions is included in a plug-in module. 24. The apparatus of claim 23, wherein the instruction fetch mechanism is configured to fetch the set of tokenized instructions via an object defined in an object-oriented programming system. 24. The apparatus of claim 23, wherein generating an index for the document further comprises an index generation mechanism configured to use the tokenized document. 28. The apparatus of claim 27, further comprising an access mechanism configured to cause the search engine to utilize the index so that the search engine can scan the index. The apparatus of claim 23, wherein the instruction fetch mechanism is configured to fetch the set of tokenized instructions over a network from a remote address. The apparatus of claim 23, wherein the set of tokenization instructions is added to the document. The apparatus of claim 23, wherein the set of tokenization instructions is included in a tokenization procedure associated with the document. The device includes a tokenization server that receives the document from a client;
The apparatus of claim 23, wherein the tokenization server is configured to return the tokenized document to the client. The apparatus of claim 23, wherein the set of tokenization instructions is provided by a remote service over a network.

Images