A Novel Search Mechanism

FIELD OF THE INVENTION

The present invention pertains to a novel time-efficient search methodology for static data

BACKGROUND OF THE INVENTION

One of the most used and common functions within any system is that of searching within an ordered list or search space. Ordinarily, the list or search space comprises of a set of characters and a required string is searched from within this set. Also, the string to be located is searched by consecutively matching characters from the ordered list
Since such a function is to be used repeatedly, it must consume the least amount of time. For an efficient mechanism for searching, either the search space / ordered list of characters must be organized in a manner that allows for an efficient search or the methodology used for the search must identify the location of the string to be found taking the least possible time

SUMMARY OF THE INVENTION

It is an objective of the present invention to provide a method for creating a searchable data dictionary, comprising the steps of receiving an ordered set of values to populate the data dictionary, entering each unique value into separate slots of the data dictionary, attaching an inner array to each of the entered slots; and entering one or more positions of one or more occurrences of the values into the inner array corresponding to the value

It is also an objective of the present invention to provide a method for searching within the data dictionary comprising the steps of receiving a string which is to be searched in the data dictionary, traversing the data dictionary to locate a slot whose value matches with the first character of the string, matching the inner array of the slot with the first two adjacent characters of the string, identifying the best match from the inner array which matches the maximum number of characters; and providing as output positions of one or more located matches and the length of the maximum matched string

BRIEF DESCRIPTION OF THE DRAWINGS

The following is a brief description of the preferred embodiments with reference to the accompanying drawings. It is to be understood that the features illustrated in and described with reference to the drawings are not to be construed as limiting of the scope of the invention.

In the accompanying drawings:

Figure 1 illustrates a structure of the searchable data dictionary

Figures 2a and 2b illustrate a method for performing a search in the data dictionary in accordance with a preferred embodiment of the invention

Figure 3 illustrates a system architecture diagram for compressing/decompressing a message using the data dictionary

DETAILED DESCRIPTION OF THE DRAWINGS

In a preferred embodiment, the data is stored in a data dictionary that has 256 slots/entries since the size of each character is 8 bits and an 8-bit position index can represent 256 types of characters.

Each slot in the main data dictionary has an inner array of a defined size, which is an array to store the position/address of the indexed character. The index/position of the character in the main data dictionary is the same as the value of the character since the 256 types of representation of an 8 bit character are mapped one-to-one on the 256 slots of the main data dictionary. Figure 1 pictorially represents this structure.

The position in the inner array is calculated from the value of the next two adjacent characters of a defined length and the length in a preferred embodiment is the minimum length of a string to be found using the searching technique. The position / address of the indexed character present in the main data dictionary corresponding to the main data dictionary position and the inner array is also stored
During the search process, the string to be found is taken and the search is started by taking the first character of the string to be found and doing a look-up in the main data dictionary. Once the first character of the search string is matched to a position in the main data dictionary, the next step is to match the inner array for that slot. Once the inner array is matched, the next step is to identify the element in the inner array with the maximum match. Once the inner array with the maximum match is identified, the position / offset and the length of the maximum matched string is taken as the output of this search operation.

The maximum time taken for a string search is M * N where M is in the input string size and N is the number of occurrences of the sub-string in the stored data which falls in the same inner array as the given input string.

The search operation is then continued with the next immediate unmatched character of the input string. It is also possible to define the upper and lower limit for searching the stored data. FIGURES 2a and 2b depict this methodology pictorially

EXAMPLE

The following example explains the data dictionary and searching technique of the invention:

Values in the searchable data dictionary: {a0, bd, c0, 3c, a0, If, 3c, 7c, 4d, c0, a0, bd, c0, 4d}
Positio I PI I P2 I P3 I P4 I P5 I P6 I P7 I P8 I P9 I PI I PI I PI I PI I PI
n 0 12 3 4
Value a0 bd c0 3c a0 1f 3c 7c 4d c0 a0 bd c0 4d

Since there are seven unique entries, which are aO, bd, cO, 3c, If, 7c and 4d the data dictionary would have 7 filled entries each of which would be located at index position equivalent to their values

The main slot for aO in the data dictionary will contain a total of 3 entries in the inner array. The position for the inner array is calculated from the value of the next adjacent characters of a defined length and the length is the minimum length of a match string. Therefore for main index aO, the position is calculated taking the next adjacent 2 characters into account - referring to the text in bold here - aO (PI), bd, cO, 3c, a0(P5), 1f, 3c, 7c, 4d, cO, aO (P11), bd, cO, 4d,

In this case, in the inner array for aO, though there are a total of 3 entries for aO, these will fall only into 2 entries

Inner Array Slot 1 - Position 1 & Position 11 of aO in data dictionary since the next 2 adjacent characters are the same for aO in the data dictionary

Inner Array Slot 2 - Position 5 of aO in the data dictionary

Data Dictionary
1
Position Position y Position z
x
aO
Inner P1 P11 1.1.1
Array Slot
255
I 1
Inner P5 1.1.2 1.1.3
Array Slot
2
Inner 1.1.4. 1.1.5. 1.1.6.
Array Slot
m

The present invention is not intended to be restricted to any particular form or arrangement, or any specific embodiment, or any specific use, disclosed herein, since the same may be modified in various particulars or relations without departing from the spirit or scope of the claimed invention hereinabove shown and described of which the apparatus or method shown is intended only for illustration and disclosure of an operative embodiment and not to show all of the various forms or modifications in which this invention might be embodied or operated.

In a preferred embodiment, the present invention is applied in the compression of a given input byte stream using a static dictionary. It provides an efficient mechanism of performing a static dictionary lookup to find the maximum matching string's position in the reference static dictionary. This string position is in-turn used in compression mechanism to fetch the appropriate symbols used for compression.
In an embodiment, the present invention can be extended for encoding/compressing a message comprising of a string of multiple characters and also for the corresponding decoding/decompressing technique via the system depicted in FIGURE 3. The dictionary handler (101) is configured to create and maintain a searchable data dictionary using the above-described technique and to store the entire message as a string. In a preferred embodiment, it is configured to generate a hash of the keywords as a sum of the ASCII values of the letters in the keyword. Using the searchable data dictionary, it is configured to determine the offset and length for each keyword in the data dictionary. The compressor (102) is connected to the dictionary handler (101) and is configured to retrieve the offset/length pair for each keyword from the dictionary handler (101) and replace them in the message with the byte code, offset and length to get the compressed message.

At the other end, the system comprises of a virtual machine (103) which communicates with the dictionary handler (101) to decompress the message. It is configured to match and execute a list of byte codes and using the offset and length access the compressed message loaded it its memory for fetching the keywords and decompressing the message

The embodiments described above and illustrated in the figures are presented by way of example only and are not intended as a limitation upon the concepts and principles of the present invention. As such, it will be appreciated by one having ordinary skill in the art that various changes in the elements and their configuration and arrangement are possible without departing from the spirit and scope of the present invention.

We claim:

1. A method for creating a searchable data dictionary, comprising the steps of:

- receiving an ordered set of values to populate the data dictionary;

- entering each unique value into separate slots of the data dictionary;

- attaching an inner array to each of the entered slots; and

- entering one or more positions of one or more occurrences of the values into the
inner array corresponding to the value;

2. A method as claimed in claim 1, wherein the data dictionary comprises of a maximum of 256 slots

3. A method as claimed in any of the previous claims, wherein each value is entered
into a slot whose position in the data dictionary corresponds to the value

4. A method as claimed in any of the previous claims, wherein each position of the
value is entered into the inner array at the position corresponding to the hash of the
next adjacent values of a defined length

5. A method as claimed in claim 4, wherein the defined length corresponds to the
minimum length which is to be matched while searching in the data dictionary

6. A method for searching within a data dictionary created as claimed in claim 1,
comprising the steps of:

- receiving a string which is to be searched in the data dictionary;

- traversing the data dictionary to locate a slot whose value matches with the first character of the string;

- matching the inner array of the slot with the first two adjacent characters of the string;

- identifying the best match from the inner array which matches the maximum number of characters; and

- providing as output positions of one or more located matches and the length of the maximum matched string;

7. A method as claimed in claim 6, wherein upper and lower limits are defined for searching the data dictionary