Systems and methods for indexing each level of the inner structure of a string over a language having a vocabulary and a grammar

[0001] 1. Field of Invention

[0002] This invention relates to systems and methods for analyzing strings over a language.

[0003] 2. Description of Related Art

[0004] There are many conventional systems and methods for storing and indexing each level of the inner structure of a string over a language having a vocabulary and a grammar. The most familiar are the various “search engines” that are available for use on the Internet. Conventional search engines typically allow a user to input a search string. Then, the search string is compared against the text of an entire document or a summary of its contents. Unfortunately, accurately searching the entire text of a large number of documents is extremely resource intensive. Therefore, conventional search engines are limited by two major design constraints, accuracy and speed. As a result, for example, many search engines available to search Internet web pages, typically return far less than all of the possible web pages that match the search string, in order to cut down on the time required for the search.

[0005] Equally disadvantageous, many of the conventional search engines return results in which only the vocabulary of the search string is matched. Typically, the conventional search engine returns documents containing the same words or string of words, however, the grammatical relationship between the words in the search string is ignored. As a result, many documents returned as a match may contain a random combination of the terms in the search string but in a totally unrelated context.

[0006] Some search engines have tried to preserve a crude representation of the grammatical relationships in the search string while searching documents by returning documents in which the words of the search string are only separated by a user defined number of words, for instance, ten words. However, this system requires complex operators within the search string to define the acceptable distance between words of the search string in the document. Furthermore, it does not preserve the actual grammatical relationship between the words in the search string, but only attempts to very roughly approximate a grammatical relationship due to the proximity of the words.

[0007] Other conventional and somewhat more complex indexing systems use “tokens” to define an axis in a multi-vector environment. An example of one such system is the SMART system. In SMART, a “token” is a single word or multi-word expression. According to the SMART system, each token defines an axis in a multi-vector environment. A document is first decomposed into a list of its tokens. Each token is used to define a vector that specifies the position of that document in the multi-axis representation. Each non-zero value of a vector corresponds to a token that is actually present in the document. A value of a vector is computed on the basis of the number of times a token occurs in a document compared to the number of times that token occurs in all of the indexed documents. When a query is matched against a set of documents during a search, a specific vector is computed for the query. Then, the cosine of the query's vector is compared to the cosine of each of the document vectors as an approximation of the proximity between the query and the document.

[0008] The primary disadvantage of these vector based systems is that the comparison approximating the similarity between a query and documents is made through a global calculus. Once that global calculus is made, each document that was determined to be similar must be individually reanalyzed to determine which sub-parts match. Furthermore, the vector systems do not maintain the grammatical relationship between the words of a document, but rely on token phrases to approximate grammatical relationships. Frequently these token phrases do not accurately represent the specific grammatical relationship of the search string.

[0009] This invention provides systems and methods for creating an index of a document.

[0010] This invention separately provides systems and methods for indexing a document that preserves grammatical relationships between elements of the document.

[0011] This invention separately provides systems and methods for indexing a document that preserves relationships between and/or within portions of the document.

[0012] This invention separately provides systems and methods for creating an index that allows portions of a document to be separately searched.

[0013] This invention separately provides systems and methods for creating an index from a document that separately indexes various document portions.

[0014] Various exemplary embodiments of the systems and methods according to this invention index the inner structure of a string over a language having a vocabulary and a grammar (e.g., a document with text) while preserving the inner grammatical structure of the string and/or allowing for a fast search. In various exemplary embodiments, a single search provides immediate access to every level of a document, without having to re-search a single string to determine which sub-parts of that string match the search string.

[0015] In various exemplary embodiments of the systems and methods according to this invention, when a string is indexed, the index maintains a compositional representation of the structural units of the string. In various exemplary embodiments, the index maintains the grammatical relationship between the elements of the vocabulary according to the language within the documents. The string is then indexed on different levels (n) by disregarding some of the grammatical relationships of component levels (n−1).

[0016] A textual document written in contemporary English is one example of a particular string over a language having a vocabulary and a grammar. The document (string) contains a vocabulary, i.e. the English words that compose the various sentences and paragraphs, and a grammar, i.e., the English grammar rules that dictate the placement of the various words. In various exemplary embodiments of the systems and methods according to this invention, the document is indexed on a number of levels according to the grammar of the language. For example, the index may contain a representation of the entire document, a representation of each-paragraph within the document, a representation of each sentence within each paragraph, and/or a representation of each of the particular grammatical relationships with each sentence. In various exemplary embodiments, the structure of the document is preserved by maintaining an index for each level of the document. By searching the various levels of an indexed document, it is possible, in various exemplary embodiments of the systems and methods according to this invention, to return accurate results based not only on the vocabulary, but also on the grammatical and/or structural relationships between the various words.

[0017] Various exemplary embodiments of the systems and methods according to this invention use binary bit vectors to index and/or to search both the vocabulary and grammar of a particular string. In various exemplary embodiments of the systems and methods according to this invention, a particular string is broken down into small units that represent one or more elements of the vocabulary and a relationship or quality of those one or more elements according to the grammar. Then, these units are broken down into their respective elements. An element is one or more words according to the vocabulary or one or more relationships according to the grammar.

[0018] Then, in various exemplary embodiments, each element is represented by a bit vector. The bit vectors for the elements are then unioned for each grouped unit, i.e., the various bit vectors for the elements of a particular grouped unit are unioned resulting in a bit vector for each grouped unit. The process continues, such that the bit vector for each sentence is determined by unioning the bit vectors of each grouped unit within that sentence, the bit vectors for each paragraph is determined by unioning the bit vectors of each sentence within that paragraph, and the bit vectors for the document is determined by unioning the bit vectors of each paragraph within that document.

[0019] In the various exemplary embodiments of systems and methods according to this invention, when a corpus of documents is searched, the documents are searched in a top down manner. First, the search string is translated into a bit vector, in the same manner as an indexed document is translated into a bit vector. Then, the search string bit vector is intersected with the document bit vector for each document of the corpus. When the intersection of a document bit vector and the search string bit vector equals the search string bit vector, the document is a match. The paragraphs of that document can then be searched in the same manner, i.e., the search string bit vector is intersected with the paragraph bit vector for each paragraph of that document. When the intersection of a paragraph bit vector and the search string bit vector equals the search string bit vector, that paragraph is a match. The sentences of that paragraph can then be searched. In the various exemplary embodiments of the systems and methods according to this invention, the bit vector is used to search a corpus of documents as a single search that loops through each document in a top down fashion. The search proceeds to a component level of a string (the document) only if the previous level was determined to be a match.

[0020] These and other features and advantages of various exemplary embodiments of systems and methods according to this invention are described in, or are apparent from, the following detailed description of various exemplary embodiments of the systems and methods according to this invention.

[0037] FIG. 1 is a flowchart outlining one exemplary embodiment of a method for storing and indexing each level of the inner structure of a document or other text string or other type of string over a language having a vocabulary and a grammar according to this invention. For ease of explanation, in this exemplary embodiment, the string is a document containing text. In general, in the following description, these strings will be referred to as “documents,” even though the strings need not be documents. As shown in FIG. 1, operation of the method begins in step S100 and continues to step S110, where a new document is input. For the purposes of explanation, assume the new document contains the following paragraph:

[0038] “Showers continued throughout the week in the Bahia cocoa zone, alleviating the drought since early January and improving prospects for the coming temporao, although normal humidity levels have not been restored, Commissary Smith said in its weekly review. The dry period means the temporao will be late this year. Arrivals for the week ended February 22 were 155,221 bags of 60 kilos making a cumulative total for the season of 5.93 mln against 5.81 at the same stage last year. Again it seems that cocoa delivered earlier on consignment was included in the arrivals figures.”

[0039] Then, in step S120, the new document is parsed into grouped units. A grouped unit includes at least one word and/or number and at least one grammatical or textual relationship or quality of the word(s) and/or number(s) of the grouped unit within the language of the string. FIGS. 3–8 show a representative listing of some of the grouped units contained in each sentence of the exemplary document. For instance, for the phrase “weekly review,” in row L6 of FIG. 3, the grouped unit “MOD (review, weekly)” defines a modifying relationship in this language, (represented by “MOD”), between the words “review” and “weekly,” where “weekly”is a modifying adjective for the noun “review.” Similarly, for the phrase “Commissary Smith said,” in row L21 of FIG. 3, “SUBJ (said, Smith)” represents the grammatical relationship in this language between the words “Smith” and “said”, where, in this language, “Smith” is the subject (represented by SUBJ) of the verb “said.”

[0040] After the document has been parsed into grouped units, operation continues to step S130, where each grouped unit is broken into its constituent elements. Referring to FIGS. 3–8, each grouped unit includes at least one word and/or number and the at least one grammatical or textual relationship or quality of those word(s) and/or number(s) in the language. Each word or number in a particular grouped unit is represented by an element of the group. Likewise, the at least one grammatical or textual relationship or quality is represented by an element of the group. FIGS. 9–14 are a table of the various elements that make up the exemplary new document. Operation then continues to step S140.

[0041] In step S140, a determination is made whether a master element index exists. If the exemplary new document is the first document to be stored and indexed of a corpus of documents to be analyzed using the same index, then a master element index containing elements from previously-analyzed documents may not exist. If the master element index does not already exist, operation continues to step S150. Otherwise, operation jumps to step S170.

[0042] In step S150, each constituent element is assigned a different index number. In various exemplary embodiments, the index numbers are integers consecutively assigned to each element in the order in which that element appears in the new document. As shown in FIGS. 9–14, each element has been assigned an index number from 0 to 224. Then, in step S160, each constituent element and its corresponding index number are recorded in the master element index. The table in FIGS. 9–14 represent one example of a master element index. However, it should be appreciated that the master element index can take any appropriate form. Operation then jumps to step S210.

[0043] In contrast, in step S170, the constituent elements of the new document are compared with the elements in the already-existing master element index. Then, in step S180, each constituent element of the new document that already exists in the master element index is assigned its corresponding index number from the master element index. Next, in step S190, each constituent element that does not already exist in the master element index is assigned a different index number that is not already in the master element index. In various exemplary embodiments, the new index numbers are also integers (generally, these will be consecutively assigned) assigned to each constituent element that does not already exist in the master element index, beginning with the smallest integer not already in the master element index. Operation then continues to step S200.

[0044] In step S200, each constituent element that did not already exist in the master element index and its corresponding new index number are recorded in the master element index. Next, in step S210, the bit index for each constituent element is determined by setting a bit in a bit string at a location in the bit string corresponding to the index number of that constituent element. For ease of explanation, the exemplary embodiment will be described using bit strings that are 16 bits long, i.e., where each bit string can each represent up to 16 constituent elements. However, it should be appreciated that much larger bit strings may be used. Therefore, in this exemplary embodiment, the element “improve” in row L1046 of FIG. 10 would have a bit index in which the 14th bit of the third 16-bit bit string would be set to 1.

[0045] Essentially, the bit index for an element is determined by dividing that element's index number, plus 1, by n, (where n is the number of bits in each bit string), to obtain both the number of the particular n-bit bit string and the particular bit position in that bit string that is to be set to 1 for this element. In various exemplary embodiments, the bit string number is determined as “Int ((i+1)/n)+1.” The bit position is, in various exemplary embodiments, determined as Mod_n (i+1), where i is that element's index number, and n is the number of bits in each bit string. In the case of “improve”, which is the 46th element and which has an index number of “45”, Int ((45+1)/16)+1, i.e., (45+1) divided by 16, plus 1, equals 3, while Mod₁₆ (45+1) returns a value of 14. Therefore, the first two bit strings are completely filled with zeros and the 14th bit of the third bit string is set to 1. Note that it is necessary to add 1 to the index number because the index numbers begin with zero. If the index numbers instead began with 1, it would not be necessary to add 1 to i in these functions.

[0046] In this exemplary embodiment, and as discussed later with reference to FIGS. 15–20, the various 16-bit bit-strings are referred to by their rank. In various exemplary embodiments, the first bit string has a rank of 0, the second bit string has a rank of 1, the third bit string has a rank of 2, and so on. Therefore, for 16-bit bit-strings, the element “improve” is indexed by the 14th bit of the bit string with a rank of 2, i.e., Int ((i+1)/n), where i is that element's index number, and n is the number of bits in each bit string. Similarly, the element “mean” in row L1160 of FIG. 12 is stored in the 15th bit of the bit string ranked 9. Operation then continues to step S220.

[0047] In step S220, for each grouped unit, a bit index value is assigned to that grouped unit of the exemplary new document by unioning the bit index of each element within that grouped unit. For example, referring to FIG. 3, the grouped unit “MOD (zone, Bahia)”, in row L7 is represented by a bit index that is the union of the bit indices for the elements “MOD,” “zone,” and “Bahia.” Therefore, the bit index for the element “MOD (zone, Bahia)” would be the union of the first bit of the 0-ranked bit string and the fifth and sixth bits of the 3-rank bit string. Next, in step S230, the bit index for each grouped unit is recorded in a master bit index, associating each grouped unit with the sentence, paragraph, and document to which it belongs. Then, in step S240, a bit index is assigned to each sentence of the new document by unioning the bit index of each grouped unit within that sentence. Next, in step S250, the bit index for each sentence of the new document is recorded in the master bit index, associating each sentence with the paragraph and document to which it belongs. Operation then continues to step S260.

[0048] In step S260, a bit index is assigned to each paragraph of the new document by unioning the bit indices of each sentence within that paragraph. Then, in step S270, the bit index for each paragraph of the new document is recorded in the master index, associating each paragraph with the document to which it belongs. Next, in step S280, a bit index is assigned to the new document by unioning the bit indices of each paragraph within that new document. Then, in step S290, the bit index for the new document is recorded in the master bit index. Operation then continues to step S300, where the operation of the method ends.

[0049] FIGS. 15–20 show a number of tables representing the bit indices for each sentence of the exemplary new document, the paragraph forming the exemplary new document, and the whole of the exemplary new document. It should be noted that because the exemplary document contains only one paragraph, the document index and the paragraph index for the exemplary new document are identical. Furthermore, because, for this exemplary embodiment, the new exemplary document is the only document that has been indexed, both the document index and paragraph index contain every element in the index. Therefore every bit of the first 14 bit-strings is set to 1 and the first bit of the 15^th bit string (rank 14) is set to 1, as the entire index contains 225 elements ((16×14)+1).

[0050] As shown in FIGS. 15–20, the various bit indices for each document, paragraph and sentence contain an ID file column indicating to which file or document the paragraph or sentence belongs; an ID paragraph column, indicating to which paragraph the sentence belongs; an ID sentence column, indicating the number of the sentence; a rank column, indicating the rank of the bit-string in the bit index for each limit; and a value column, indicating the decimal value described by the binary representation of each bit-string. For the purpose of clarity, a binary column has been added to FIGS. 15–20 to show the binary data of each bit-string.

[0051] However, in various exemplary embodiments, the binary data itself is not stored. Rather, only the decimal value of the binary bit string is recorded. For illustrative purposes, note that the first sentence is indexed over ten bit strings, ranks 0 to 9. Each bit in the first nine 16-bit bit-strings is set to 1. Therefore, the decimal value for each of those 16-bit bit-strings is 65,535 (2^l6−1). The tenth 16-bit bit-string, i.e., the 9-rank bit-strong, has only the first three bits set to 1 and its corresponding decimal value is 7 (2³−1). As can be inferred from the first sentence's bit index, the first sentence contains the first 146 elements of the exemplary new document. The first nine 16-bit bit-strings represent the elements with index numbers 0 to 143 ((16×9)−1), while the tenth 16-bit bit-string represents the elements with index numbers 144, 145, and 146.

[0052] Similarly, the second sentence contains elements in the first eleven 16-bit bit-strings of the master bit index. As can be inferred from FIGS. 17 and 18, the second sentence shares a fair amount of its elements with the first sentence, as many of the bits in the first ten 16-bit bit-strings are set to 1. However, it does not contain every element, as many of the bits in the first ten 16-bit bit-strings are set to “0.” Furthermore, the second sentence contains new elements having index numbers 147 to 161. These elements are stored within the fourth through 16th bits of the 9-rank bit-string and the first two bits of the 10-rank bit-string. The bit indices for the third and fourth sentences are similarly constructed. It should be appreciated that the table shown in FIG. 20, representing the fourth sentence of the exemplary document, does not include a row for the 10th ranked bit-string because none of the elements indexed in the 10th ranked bit string are present in the fourth sentence.

[0053] FIG. 21 is an exemplary embodiment of a functional block diagram of one exemplary embodiment of a string indexing system 100 that is usable to index a string over a language having a grammar according to the invention. As shown in FIG. 21, the string indexing system 100 includes an input/output interface 110, a controller 120, a memory 130, a parsing circuit, routine, or application 140, a deconstructing circuit, routine, or application 150, a comparing circuit, routine, or application 160, an element index assigning circuit, routine, or application 170, an index converting circuit, routine, or application 180, and a unioning circuit, routine, or application 190, each appropriately interconnected by one or more data/control busses and/or application programming interfaces 195 or the like.

[0054] In this exemplary embodiment, the input/output interface 110 is connected to a data source 200 over a link 210. The data source 200 can be a locally or remotely located laptop or personal computer, a personal digital assistant, a tablet computer, a device that stores and/or transmits electronic data, such as a client or a server of a wired or wireless network, such as for example, an intranet, an extranet, a local area network, a wide area network, a storage area network, the Internet (especially the World Wide Web), and the like. In general, the data source 200 can be any known or later-developed source that is capable of providing string data to the input/output interface 110.

[0055] In this exemplary embodiment, the input/output interface 110 is connected to one or more input devices 102 over one or more links 104. The input device(s) 102 can be one or more of a keyboard, a mouse, a track ball, a track pad, a touch screen, or any other known or later-developed device for inputting data and/or control signals to the string indexing system 100. In this exemplary embodiment, the input/output interface 110 is connected to one or more data sinks 220 over one or more links 230. The data sink(s) 220 can be a locally or remotely located laptop or personal computer, a personal digital assistant, a tablet computer, a device that receives and stores, and/or transmits electronic data, such as for example, a client or a server of a wired or wireless network, an intranet, an extranet, a local area network, a wide area network, a storage area network, the Internet (especially the World Wide Web), and the like. In general, the data sink(s) 220 can be any device that is capable of receiving and transmitting and/or storing the indexed string data that is provided by the one or more links 230.

[0056] Each of the various links 104, 210, and 230 can be any known or later-developed device or system for connecting the input device(s) 102, the data source 200 and/or the data sink(s) 220, respectively, to the input/output interface 110. In particular, the links 104, 210, and 230 can each be implemented as one or more of a direct cable connection, a connection over a wide area network, a local area network or a storage area network, a connection over an intranet, a connection over an extranet, a connection over the Internet, a connection over any other distributed processing network or system, and/or an infrared, radio-frequency or other wireless connection.

[0057] As shown in FIG. 21, the memory 130 contains a number of different memory portions, including a master element index portion 131, a master bit index portion 132, an associations portion 133, a document text portion 134, and a temporary portion 135. The master element index portion 131 of the memory 130 stores the master element index. The master bit index portion 132 of the memory 130 stores the master bit index. The associations portion 133 of the memory 130 stores the associations between elements, grouped units, sentences, paragraphs, and documents. The document text portion 134 of the memory 130 stores the text of each document that has been indexed. Finally, the temporary portion 135 temporarily saves various data necessary for the operation of the string indexing system 100.

[0058] The memory 130 shown in FIG. 21 can be implemented using any appropriate combination of alterable, volatile or non-volatile memory or non-alterable, or fixed, memory. The alterable memory, whether volatile or non-volatile, can be implemented using any one or more of static or dynamic RAM, a floppy disk and disk drive, a writeable or re-re-writeable optical disk and disk drive, a hard drive, flash memory or the like. Similarly, the non-alterable or fixed memory can be implemented using any one or more of ROM, PROM, EPROM, EEPROM, an optical ROM disk, such as CD-ROM or DVD-ROM disk, and disk drive or the like

[0059] The parsing circuit, routine, or application 140 inputs a document or other string and outputs that document's or string's grouped units. The deconstructing circuit, routine, or application 150 inputs one or more grouped units and breaks each such grouped unit into its constituent elements. The comparing circuit, routine, or application 160 inputs an element or a group of elements and determines whether each element of that group is present on the master element index. The element index assigning circuit, routine, or application 170 inputs an element or a group of elements that has been determined by the comparing circuit, routine or application 160 not to be present on the master element index and assigns each such element an index number on the appropriate index, respectively. The index converting circuit, routine, or application 180 inputs an element index or group of element indices and converts each element index into its corresponding bit in a bit-string, i.e., its bit index. Finally, the unioning circuit, routine, or application 190 inputs two or more bit indices and outputs a bit index representing the union of the input bit indices.

[0060] In operation, the exemplary embodiment of the string indexing system 100 shown in FIG. 21 operates by inputting a new document from the data source 200 across the link 210 via the input/output interface 110 as a current document. Again, for ease of explanation, for this exemplary embodiment, the string over a language having a vocabulary and a grammar is a document containing text. Under control of the controller 120, the current document is stored in the document text portion 134 of the memory 130. Then, under control of the controller 120, the current document is input by the parsing circuit, routine, or application 140. The parsing circuit, routine, or application 140 parses the current document into its grouped units. Under control of the controller 120, the parsing circuit, routine or application 140 outputs the grouped units to the temporary portion 135 of the memory 130 and data representing the sentence, paragraph and document to which each element belongs to the associations portion 133 of the memory 130. Next, under control of the controller 120, the deconstructing circuit, routine, or application 150 inputs the grouped units, either directly from the parsing circuit, routine, or application 140 or from the temporary portion 135 of the memory 130. The deconstructing circuit, routine, or application 150 breaks down the grouped units into elements. Under control of the controller 120, the deconstructing circuit, routine or application 150 outputs the elements to the temporary portion 135 of the memory 130 and/or to the comparing circuit, routine or application 160.

[0061] The controller 120 next determines whether the master element index that is to be used with or for this document already exists. If such a master element index already exists, the comparing circuit, routine or application 160, under control of the controller 120, inputs the existing master element index from the master element index portion 131. Then, under control of the controller 120, the comparing circuit, routine, or application 160 inputs the elements stored in the temporary portion 135 of the memory 130.

[0062] The comparing circuit, routine, or application 160 compares the elements in the input master element index with the elements input from the temporary portion 135 of the memory 130. Under control of the controller 120, the elements that were stored in the temporary portion 135 of the memory 130 that do not match any elements in the master element index portion 131 of the memory 130 are output by the comparing circuit, routine, or application 160, either directly or indirectly, to the element index assigning circuit, routine, or application 170. The element index assigning circuit, routine, or application 170 assigns each such element a different element index number that is not already in the master element index portion 131 of the memory 130. Under control of the controller 120, the element index assigning circuit, routine, or application 170 adds the elements and the element index numbers to the master element index stored on the master element index portion 131 of the memory 130.

[0063] However, if a master element index does not exist, because, for example, no data has yet been stored in the master element index portion 131 of the memory 130, under control of the controller 120, the element index assigning circuit, routine, or application 170, under control of the controller 120, inputs every element stored in the temporary portion 135 of the memory 130. The element index assigning circuit, routine, or application 170 again assigns each element a different index number, and, under control of the controller 120, creates a master element index, stores it into the master element index portion 131 and adds the elements and index numbers to the master element index stored in the master element index portion 131 of the memory 130.

[0064] Next the index converting circuit, routine, or application 180, under control of the controller 120, inputs the elements of the current document and their respective index numbers. The index converting circuit, routine, or application 180 converts the index number of each element into a corresponding bit in a bit string, i.e., its bit index. The corresponding bit index, described in various exemplary embodiments by a rank and a location in a bit-string that corresponds to the index number, as shown in FIG. 21, is output by the index converting circuit, routine or application 180, under control of the controller 120, to the master bit index portion 132 of the memory 130, and/or to the unioning circuit, routine or application 190.

[0065] Then, under control of the controller 120, the unioning circuit, routine or application 190 inputs the elements of the current document and their respective bit indices from the master bit index portion 132 of the memory 130 and the associations data from the associations portion of the memory 130. The unioning circuit, routine, or application 190 assigns a bit index to each grouped unit of the new document by unioning the bit indices of all of the elements within that grouped unit according to the associations data. Then, under control of the controller 120, the unioning circuit, routine or application 190 outputs the bit index for each grouped unit to the master bit index portion 132 of the memory 130 and outputs cross-references for the bit indices for those grouped units to their associated sentence, paragraph, and document information stored in the associations portion 133 of the memory 130.

[0066] Subsequently, under control of the controller 120, the unioning circuit, routine or application 190 inputs the bit indices of the grouped units for a selected sentence from the master bit index portion 132 of the memory 130 and the association data from the associations portion 133 of the memory 130. For each selected sentence, the unioning circuit, routine, or application 190 then assigns a bit index to the selected sentence of the current document by unioning the bit indices of the grouped units contained in that sentence according to the associations data. Under control of the controller 120, the unioning circuit, routine or application 190 outputs the index for each sentence of the current document to the master bit index portion 132 of the memory 130, and outputs cross-references for the bit indices of the sentences to their associated paragraphs and documents to the associations portion 133 of the memory 130.

[0067] Next, under control of the controller 120, the unioning circuit, routine or application 190 inputs the master bit index of each sentence for a selected paragraph of the current document from the master bit index 132 of the memory 130 and of the association data from the associations portion 133 of the memory 130. For each selected paragraph, the unioning circuit, routine, or application 190 then assigns a bit index to the selected paragraph of the current document by unioning the bit indices of all of the sentences within that paragraph according to the association data. Then, under control of the controller 120, the unioning circuit, routine or application 190 outputs the master bit index for each paragraph of the current document to the master bit index portion 132 of the memory 130 and outputs cross references for each paragraph to the document to which it belongs to the associations portion 133 of the memory 130.

[0068] Finally, under control of the controller 120, the unioning circuit, routine or application 190 inputs the bit indices for all of the paragraphs stored in the master bit index portion 132 of the memory 130 and the association data stored in the associations portion 133 of the memory 130. The unioning circuit, routine, or application 190 next assigns a bit index to the current document by unioning the indices of all of the paragraphs in the current document according to the associations data. Then, under control of the controller 120 the unioning circuit, routine or application 190 outputs the index of the current document to the master bit index portion 132 of the memory 130.

[0069] As a result of the above-described operations of the exemplary embodiment of the string indexing system 100 shown in FIG. 21, the master bit index portion 132 of the memory 130 contains a complete bit index of the current document. The complete bit index contains each element and its respective bit index properly associated with the grouped unit(s) to which it belongs, the sentence(s) to which it belongs, the paragraph(s) to which it belongs, and the document(s) to which it belongs. Similarly, the master bit index contains the bit index for each sentence of the current document, properly associated with the paragraph(s) to which it belongs and the document(s) to which it belongs. The master bit index also contains the bit index for each paragraph of the current document, properly associated with that document. Finally, a master bit index portion 132 of the memory 130 contains the bit index for the current document.

[0070] It should be appreciated that, depending on cost or other design constraints, one or more of the above-described elements of the string indexing system 100 may be combined into a single element or divided into multiple elements where appropriate.

[0071] FIGS. 22–25 describe a flowchart outlining one exemplary embodiment of a method for searching a corpus of at least one string, such as at least one document, according to this invention. As shown in FIGS. 22–25, operation of the method begins in step S1000 and continues to step S1010, where a search string is input. The search string may include search terms, natural language, search terms linked by Boolean operators, specific field queries, or any other known or later-developed search technique, operator, element or the like that may be broken down into elements of a particular language having a vocabulary and a grammar and/or relationships between the words according to the grammar of the language.

[0072] Then, in step S1020, the bit index for each element in the search string is determined or identified. The elements of the search string may be determined in a number of ways, depending upon the type of search string. For example, if the search string includes natural language elements, the search string will be parsed into its grouped units and the grouped units broken into the constituent elements in the same manner, as outlined above, that documents are indexed. Alternatively, if a Boolean search string is used, the elements will simply be the words of the language contained in the Boolean search string. In various exemplary embodiments of step S1020, the master bit index is searched for each element of the search string. When an element of the search string is located in the master bit index, that element of the search string will be assigned the corresponding bit index from the master bit index. However, if the element does not exist in the master bit index, it will be assigned a unique bit index not contained in the master bit index. In various exemplary embodiments, the assigned bit index will be the next consecutive bit that is not already part of the index set to one. For example, assuming that FIGS. 9–14 represented the total bit index, the next element of the search string to be indexed that did not already exist in the index would be the 225^th element and would be represented by the second bit of the 14^th ranked integer set being set to 1.

[0073] Next in step S1030, the bit index for the search string as a whole is determined by unioning the bit index of each element of the search string. It should be noted that, if a Boolean search string containing the operator “OR” is input, more than one bit index will be created containing the alternative element combinations. Operation then continues to step S1040.

[0074] In step S1040, a first or next document is selected from a corpus of documents as the current document. Then, in step S1050, the intersection of the search string bit index and the current document bit index is determined. Next, in step S1060, a determination is made whether the intersection of the search string bit index and the current document bit index is sufficiently equal to the search string bit index. If the intersection of the search string bit index and the current document bit index is sufficiently equal to the search string bit index, the current document contains each element of the search string. Accordingly, operation continues to step S1070. If the intersection of the search string bit index and the current document bit index is not sufficiently equal to the search string bit index, the current document does not contain each element of the search string and operation jumps to step S1230.

[0075] In step S1070, the document is marked as a match. Then, in step S1080, the first/next paragraph of the current document is selected as the current paragraph. Next, in step S1090, the intersection of the search string bit index and the current paragraph bit index is determined. Then, in step S1100, a determination is made whether the intersection of the search string bit index and the current paragraph bit index is sufficiently equal to the search string bit index. If the intersection of the search string bit index and the current paragraph bit index is sufficiently equal to the search string bit index, the paragraph contains all of the elements of the search string. Therefore, operation jumps to step S1120. However, if the intersection of the search string bit index and the paragraph bit index is not sufficiently equal to the search string bit index, the paragraph does not contain all of the elements of the search string and operation continues to step S1110.

[0076] In step S1110, a determination is made whether all paragraphs of the current document have been selected as the current paragraph. If every paragraph of the current document has not been selected as the current paragraph, operation returns to step S1080 where the next paragraph is selected as the current paragraph. If every paragraph of the current document has been selected as the current paragraph, operation again jumps to step S1230.

[0077] In step S1120, the current paragraph is marked as a match. Then, in step S1130, the first/next sentence of the current paragraph is selected as the current sentence. Next, in step S1140, the intersection of the search string bit index and the current sentence bit index is determined. Then, in step S1150, a determination is made whether the intersection of the search string bit index and the current sentence bit index is sufficiently equal to the search string bit index. If the intersection of the search string bit index and the current sentence bit index is sufficiently equal to the search string bit index, the sentence contains all of the elements of the search string. Therefore, operation jumps to step S1170. However, if the intersection of the search string bit index and the sentence bit index is not sufficiently equal to the search string bit index, the sentence does not contain all of the elements of the search string and operation continues to step S1160.

[0078] In step S1160, a determination is made whether all sentences of the current paragraph have been selected as the current sentence. If every sentence of the current paragraph has not been selected as the current sentence, operation returns to step S1080 where the next sentence is selected as the current sentence. If every sentence of the current paragraph has been selected as the current sentence, operation returns to step S1110, where the determination is made again whether every paragraph in the current document has been selected as the current paragraph.

[0079] In step S1170, the current sentence is marked as a match. Then, in step S1180, the first/next grouped unit of the current sentence is selected as the current grouped unit. Next, in step S1190, the intersection of the search string bit index and the current grouped unit bit index is determined. Then, in step S1200, a determination is made whether the intersection of the search string bit index and the current grouped unit bit index is sufficiently equal to the search string bit index. If the intersection of the search string bit index and the current grouped unit bit index is sufficiently equal to the search string bit index, the grouped unit contains all of the elements of the search string. Therefore, operation continues to step S1210. However, if the intersection of the search string bit index and the grouped unit bit index is not sufficiently equal to the search string bit index, the current grouped unit does not contain all of the elements of the search string and operation jumps to step S1220.

[0080] In step S1210, the current grouped unit is marked as a match. Then, in step S1220, a determination is made whether every grouped unit in the current sentence has been selected as the current grouped unit. If every grouped unit in the current sentence has not been selected as the current grouped unit, operation returns to step S1180, where the next grouped unit of the current sentence is selected as the current grouped unit. However, if every grouped unit in the current sentence has been selected as the current grouped unit, operation returns to step S1160, where the determination is made again whether every sentence in the current paragraph has been selected as the current sentence.

[0081] In step S1230, a determination is made whether every document in the corpus of documents has been selected as the current document. If every document has not been selected as the current document, operation returns to step S1040, where the next document is selected as the current document. If every document has been selected as the current document, operation jumps to step S1240, where the method ends.

[0082] Again, it should be noted that, when the input search string contains the Boolean operator “OR,” or its equivalent the various search strings representing each alternative group of elements will be searched independently of one another. Once each alternative search string has been searched, the results will be unioned, representing the cumulative results of the entire Boolean search string.

[0083] FIG. 26 shows an exemplary embodiment of a string searching system 400 usable to search each level of the inner structure a corpus of documents or the like that have been indexed according to this invention. As shown in FIG. 26, the string searching system 400 includes an input/output interface 410, a controller 420, a memory 430, a bit index determining circuit, routine, or application 440, a comparing circuit, routine, or application 460, an intersecting circuit, routine, or application 470, and a marking circuit, routine, or application 480, each appropriately interconnected by one or more data/control busses and/or application programming interfaces 495, or the like. The input/output interface 410 is connected to one or more data sources 500 over a link 510. The data source 500 can be any device suitable for storing and/or transmitting electronic data, such as a client or server of a network, or the Internet, and especially the World Wide Web. The data source 500 can be any known or later-developed data source that is capable of providing indices for a corpus of documents or the like that have been indexed according to this invention to the input/output interface 410 of the string searching system 400 according to this invention.

[0084] The input/output interface 410 is connected to one or more input devices 402 over a link 404. The input device(s) 402 can be one or more of a keyboard, a mouse, a track ball, a track pad, a touch screen, or any other known or later-developed device for inputting data and/or control signals to the string searching system 400. Furthermore, in this exemplary embodiment, the input/output interface 410 is connected to a data sink 520 over a link 530. In general, the data sink 520 can be can be a locally or remotely located laptop or personal computer, a personal digital assistant, a tablet computer, a device that receives and stores and/or transmits electronic data, such as for example, a client or a server of a wired or wireless network, an intranet, an extranet, a local area network, a wide area network, a storage area network, the Internet (especially the World Wide Web), and the like. In general, the data sink 520 can be any device that is capable of receiving and transmitting and/or storing the indexed string data that is provided by the one or more links 230.

[0085] Each of the various links 404,510 and 530 can be implemented using any known or later-developed device or system for connecting the data source 500, the data sink 520, and/or the input device(s) 402, respectively, to the input/output interface 410. In particular, the links 404, 510 and 530 can each be implemented as one or more of a direct cable connection, a connection over a wide area network, a local area network, a connection over an intranet, a connection over an extranet, a connection over the Internet, a connection over any other distributed processing network or system, or an infrared, radio-frequency, or other wireless connection.

[0086] As shown in FIG. 26, the memory 430 contains a number of different memory portions, including a master element index portion 431, a master bit index portion 432, an associations portion 433, a document text portion 434, a search string portion 435, a number portion 436, and a results portion 437. The master element index portion 431 of the memory 430 stores the master element index. The master bit index portion 432 of the memory 430 stores the master bit index. The associations portion 433 of the memory 430 stores the associations between elements, grouped units, sentences, paragraphs, and/or documents. The document text portion 434 of the memory 430 stores the text of each document or the like that has been indexed. The search string portion 435 stores both the text and bit index of the search string. Finally, the results portion 436 of the memory 430 stores the search results.

[0087] The memory 430 shown in FIG. 26 can be implemented using any appropriate combination of alterable, volatile or non-volatile memory or non-alterable, or fixed, memory. The alterable memory, whether volatile or non-volatile, can be implemented using any one or more of static or dynamic RAM, a floppy disk and disk drive, a writeable or re-re-writeable optical disk and disk drive, a hard drive, flash memory or the like. Similarly, the non-alterable or fixed memory can be implemented using any one or more of ROM, PROM, EPROM, EEPROM, an optical ROM disk, such as CD-ROM or DVD-ROM disk, and disk drive or the like

[0088] The bit index determining circuit, routine, or application 440 inputs a search string and determines its bit index or indices. The comparing circuit, routine, or application 460 inputs at least two bit indices and determines whether the bit indices are sufficiently equal to one another (or if one bit index is contained entirely within the other bit index). The intersecting circuit, routine, or application 470 inputs two or more bit indices and determines their intersection. Finally, the marking circuit, routine, or application 480 marks a grouped unit, a sentence, a paragraph, and/or a document that has been determined to be a match.

[0089] In operation, the string searching system 400 inputs a search string from the one or more input device(s) 402 across the link 404 via the input/output interface 410. Alternatively, the search string may be received from the data source 500 across the link 510 via the input/output interface 410. Under control of the controller 420, the search string is stored in the search string portion 435 of the memory 430. Then, the bit index determining circuit, routine, or application 440, under control of the controller 420, inputs the search string. The bit index determining circuit, routine, or application 440 determines a bit index of the search string. Next, in various exemplary embodiments, under control of the controller 420, the search string bit index is stored in the search string portion 435 of the memory 430.

[0090] After the search string bit index has been determined, the search string is input, under control of the controller 420, either from the search string portion 435 of the memory 430, or directly from the bit index determining circuit, routine, or application 440, into the intersecting circuit, routine, or application 470. Then, under control of the controller 420, the first document bit index is selected from the master bit index portion 432 of the memory 430 as the current document bit index and input to the intersecting circuit, routine, or application 470. The intersecting circuit, routine, or application 470 determines the intersection of the search string bit index and the current document bit index.

[0091] Next, under control of the controller 420, the intersection of the search string bit index and the current document bit index and the search string bit index are input into the comparing circuit, routine, or application 460. The comparing circuit, routine, or application 460 determines whether the intersection of the search string bit index and the current document bit index is sufficiently equal to the search string bit index. When the intersection of the search string bit index and the current document bit index is not sufficiently equal to the search string bit index, the next document bit index is selected from the master bit index portion 432 of the memory 430 as the current document bit index. When every document bit index has been selected, or if the index portion 432 is empty, the search is complete and, under control of the controller 420, all of the marked grouped units, sentences, paragraphs, and documents are stored in the results portion 436 of the memory 430.

[0092] Whenever the intersection of the search string bit index and the current document bit index is sufficiently equal to the search string bit index, the marking circuit, routine, or application 480 marks the current document in the master bit index portion 432 of the memory 430 to indicate that that document matches the search string. Then, under the control of the controller 420, the first paragraph bit index of the matching current document is selected as the current paragraph bit index and input from the master bit index portion 432 of the memory 430 into the intersecting circuit, routine, or application 470. The intersecting circuit, routine, or application 470 determines the intersection of the search string bit index and the current paragraph bit index.

[0093] Next, under control of the controller 420, the intersection of the search string bit index and the current paragraph bit index is are input into the comparing circuit, routine, or application 460. The comparing circuit, routine, or application 460 determines whether the intersection of the search string bit index and the current paragraph bit index is sufficiently equal to the search string bit index. When the intersection of the search string bit index and the current paragraph bit index is not sufficiently equal to the search string bit index, the next paragraph bit index of the current document is selected from the master bit index portion 432 of the memory 430 as the current paragraph bit index. Once every paragraph bit index of the current document has been searched, the next document bit index is selected from the master bit index portion 432 of the memory 430, as described above.

[0094] Whenever the intersection of the search string bit index and the current paragraph bit index is sufficiently equal to the search string bit index, the marking circuit, routine, or application 480 marks the current paragraph in the master bit index portion 432 of the memory 430 to indicate that the current paragraph matches the search string. Then, under the control of the controller 420, the first sentence bit index of the matching current paragraph is selected as the current sentence bit index and input from the master bit index portion 432 of the memory 430 into the intersecting circuit, routine, or application 470. The intersecting circuit, routine, or application 470 determines the intersection of the search string bit index and the current sentence bit index.

[0095] Next, under control of the controller 420, the intersection of the search string bit index and the current sentence bit index is input into the comparing circuit, routine, or application 460. The comparing circuit, routine, or application 460 determines whether the intersection of the search string bit index and the current sentence bit index is sufficiently equal to the search string bit index. When the intersection of the search string bit index and the current sentence bit index is not sufficiently equal to the search string bit index, the next sentence bit index of the current paragraph is selected from the master bit index portion 432 of the memory 430 as the current sentence bit index. When every sentence bit index of the current paragraph has been searched, the next paragraph bit index is selected from the master bit index portion 432 of the memory 430, as described above.

[0096] Whenever, the intersection of the search string bit index and the current sentence bit index is sufficiently equal to the search string bit index, the marking circuit, routine, or application 480 marks the current sentence in the master bit index portion 432 of the memory 430 to indicate that the sentence matches the search string. Then, under the control of the controller 420, the first grouped unit bit index of the matching current sentence is selected as the current grouped unit bit index and input from the master bit index portion 432 of the memory 430 into the intersecting circuit, routine, or application 470. The intersecting circuit, routine, or application 470 determines the intersection of the search string bit index and the current grouped unit bit index.

[0097] Next, under control of the controller 420, the intersection of the search string bit index and the current grouped unit bit index is input into the comparing circuit, routine, or application 460. The comparing circuit, routine, or application 460 determines whether the intersection of the search string bit index and the current grouped unit bit index is sufficiently equal to the search string bit index. When the intersection of the search string bit index and the current grouped unit bit index is not sufficiently equal to the search string bit index, the next grouped unit bit index of the current sentence is selected from the master bit index portion 432 of the memory 430 as the current grouped unit bit index.

[0098] If the intersection of the search string bit index and the current grouped unit bit index is sufficiently equal to the search string bit index, the marking circuit, routine, or application 480 marks the current grouped unit in the master bit index portion 432 of the memory 430 to indicate that the current grouped unit matches the search string. Then, under the control of the controller 420, the next grouped unit bit index of the matching current sentence is selected as the current grouped unit bit index and searched, as above. When every grouped unit bit index of the current sentence has been searched, the next sentence bit index is selected from the master bit index portion 432 of the memory 430 as described above.

[0099] It should be appreciated that, depending on cost or other design constraints, one or more of the above-described elements of the string searching system 400 may be combined into a single element or divided into multiple elements where appropriate.

[0100] It should be appreciated that the systems and methods according to this invention are not limited to the above-described exemplary embodiments. For instance, in various exemplary embodiments, the comparing circuit, routine, or application might determine that a grouped unit, sentence, paragraph, or document is sufficiently equal only if 100% of the intersection of the search string bit index and the grouped unit, sentence, paragraph, or document bit index and the search string bit index are equal. These embodiments would yield a number of accurate search results. However, in other various exemplary embodiments some percentage less than 100% (determined, for example, by a confidence value) of the intersection of the search string bit index and the grouped unit, sentence, paragraph, or document bit index and the search string bit index maybe considered substantially equal. These embodiments would yield a larger number of less accurate search results.

[0101] Furthermore, it should be appreciated that systems and methods according to this invention are not specifically limited to documents containing text. For example, a graphic document such as a photograph may be appropriately broken down into a language and grammar and indexed in a similar manner. For instance, the subject, location, background, foreground, colors, and various other characteristics of the image correspond to, or constitute the elements. The elements would be assigned bit indices and indexed in a master bit index. Then, a user would be able to enter a search string, for example, “girl in Paris.” According to the language, the search string would be converted into a bit index representing the union of girl, subject, Paris, and location or background (assuming that in the relevant language and grammar “girl” is the “subject” of the photo and “Paris” is the “location” or “background” of the photo). Then, a device according this alternative exemplary embodiment would return as a match each indexed graphic document containing a girl in Paris.

[0102] While this invention has been described in conjunction with the exemplary embodiments outlined above, various alternatives, modifications, variations, improvements, and/or substantial equivalents, whether known or that are or may be presently unforeseen, may become apparent to those having at least ordinary skill in the art. Accordingly, the exemplary embodiments of the invention, as set forth above, are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention. Therefore, the invention is intended to embrace all known or later-developed alternatives, modifications variations, improvements, and/or substantial equivalents.