Abstract:
Systems and methods for indexing and searching the inner structure of a string over a language having a vocabulary and a grammar using bit vectors. The index preserves the inner grammatical structure of the string while allowing for a fast search. 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. When a string is indexed, the index maintains a compositional representation and the grammatical relationship between the elements of the vocabulary according to the language. The string is then indexed on different levels by disregarding some of the grammatical relationships of component levels.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     This invention relates to systems and methods for analyzing strings over a language. 
     2. Description of Related Art 
     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. 
     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. 
     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. 
     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&#39;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. 
     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. 
     SUMMARY OF THE DISCLOSURE 
     This invention provides systems and methods for creating an index of a document. 
     This invention separately provides systems and methods for indexing a document that preserves grammatical relationships between elements of the document. 
     This invention separately provides systems and methods for indexing a document that preserves relationships between and/or within portions of the document. 
     This invention separately provides systems and methods for creating an index that allows portions of a document to be separately searched. 
     This invention separately provides systems and methods for creating an index from a document that separately indexes various document portions. 
     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. 
     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). 
     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. 
     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. 
     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. 
     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. 
     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. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various exemplary embodiments of systems and methods according to this invention will be described in detail, with reference to the following figures, wherein: 
         FIGS. 1 and 2  are a flowchart outlining one exemplary embodiment of a method for indexing an exemplary document according to this invention; 
         FIGS. 3-4  show an exemplary representation of some of the grouped units of the first sentence of the exemplary document; 
         FIG. 5  shows an exemplary representation of some of the grouped units of the second sentence of the exemplary document; 
         FIGS. 6-7  show an exemplary representation of some of the grouped units of the third sentence of the exemplary document; 
         FIG. 8  shows an exemplary representation of some of the grouped units of the fourth sentence of the exemplary document; 
         FIGS. 9-14  show the elements of the exemplary document; 
         FIG. 15  shows a table containing the various bit indices and associations for the exemplary document; 
         FIG. 16  shows a table containing the various bit indices and associations for the paragraph of the exemplary document; 
         FIG. 17  shows a table containing the various bit indices and associations for the first sentence of the exemplary document; 
         FIG. 18  shows a table containing the various bit indices and associations for the second sentence of the exemplary document; 
         FIG. 19  shows a table containing the various bit indices and associations for the third sentence of the exemplary document; 
         FIG. 20  shows a table containing the various bit indices and associations for the fourth sentence of the exemplary document; 
         FIG. 21  is a block diagram outlining one exemplary embodiment of a string indexing system according to this invention; 
         FIGS. 22-25  are a flowchart outlining an exemplary embodiment of a method for searching indexed documents according to this invention; and 
         FIG. 26  is a block diagram outlining an exemplary embodiment of a document searching system according to this invention, 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       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 S 100  and continues to step S 110 , where a new document is input. For the purposes of explanation, assume the new document contains the following paragraph: 
     “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.” 
     Then, in step S 120 , 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 L 6  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 L 21  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.” 
     After the document has been parsed into grouped units, operation continues to step S 130 , 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 S 140 . 
     In step S 140 , 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 S 150 . Otherwise, operation jumps to step S 170 . 
     In step S 150 , 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 S 160 , 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 S 210 . 
     In contrast, in step S 170 , the constituent elements of the new document are compared with the elements in the already-existing master element index. Then, in step S 180 , 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 S 190 , 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 S 200 . 
     In step S 200 , 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 S 210 , 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 L 1046  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. 
     Essentially, the bit index for an element is determined by dividing that element&#39;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&#39;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 16  (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. 
     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&#39;s index number, and n is the number of bits in each bit string. Similarly, the element “mean” in row L 1160  of  FIG. 12  is stored in the 15th bit of the bit string ranked 9. Operation then continues to step S 220 . 
     In step S 220 , 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 L 7  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 S 230 , 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 S 240 , 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 S 250 , 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 S 260 . 
     In step S 260 , 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 S 270 , 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 S 280 , a bit index is assigned to the new document by unioning the bit indices of each paragraph within that new document. Then, in step S 290 , the bit index for the new document is recorded in the master bit index. Operation then continues to step S 300 , where the operation of the method ends. 
       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). 
     As shown in  FIGS. 15-20 , the various bit indices for each document, paragraph and sentence contain an D) 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. 
     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 16 −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 3 −1). As can be inferred from the first sentence&#39;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 . 
     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. 
       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. 
     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 . 
     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 . 
     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. 
     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 . 
     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 
     The parsing circuit, routine, or application  140  inputs a document or other string and outputs that document&#39;s or string&#39;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. 
     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 . 
     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 . 
     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 . 
     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 . 
     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 . 
     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 . 
     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 . 
     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 . 
     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 . 
     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. 
     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. 
       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 S 1000  and continues to step S 1010 , 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. 
     Then, in step S 1020 , 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 S 1020 , 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. 
     Next in step S 1030 , 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 S 1040 . 
     In step S 1040 , a first or next document is selected from a corpus of documents as the current document. Then, in step S 1050 , the intersection of the search string bit index and the current document bit index is determined. Next, in step S 1060 , 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 S 1070 . 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 S 1230 . 
     In step S 1070 , the document is marked as a match. Then, in step S 1080 , the first/next paragraph of the current document is selected as the current paragraph. Next, in step S 1090 , the intersection of the search string bit index and the current paragraph bit index is determined. Then, in step S 1100 , 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 S 1120 . 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 S 110 . 
     In step S 1110 , 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 S 1080  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 S 1230 . 
     In step S 1120 , the current paragraph is marked as a match. Then, in step S 1130 , the first/next sentence of the current paragraph is selected as the current sentence. Next, in step S 1140 , the intersection of the search string bit index and the current sentence bit index is determined. Then, in step S 1150 , 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 S 1170 . 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 S 1160 . 
     In step S 1160 , 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 S 1080  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 S 1110 , where the determination is made again whether every paragraph in the current document has been selected as the current paragraph. 
     In step S 1170 , the current sentence is marked as a match. Then, in step S 1180 , the first/next grouped unit of the current sentence is selected as the current grouped unit. Next, in step S 1190 , the intersection of the search sting bit index and the current grouped unit bit index is determined. Then, in step S 1200 , 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 S 1210 . 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 S 1220 . 
     In step S 1210 , the current grouped unit is marked as a match. Then, in step S 1220 , 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 S 1180 , 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 S 1160 , where the determination is made again whether every sentence in the current paragraph has been selected as the current sentence. 
     In step S 1230 , 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 S 1040 , where the next document is selected as the current document. If every document has been selected as the current document, operation jumps to step S 1240 , where the method ends. 
     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. 
       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. 
     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 . 
     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. 
     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. 
     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 
     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. 
     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 . 
     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. 
     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 . 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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 may be considered substantially equal. These embodiments would yield a larger number of less accurate search results. 
     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. 
     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.