Incremental search of keyword strings
First Claim
Patent Images
1. A method for creating a keyword string database, the method comprising:
- determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
1 Assignment
0 Petitions
Accused Products
Abstract
An incremental keyword search may be performed by receiving an input keyword string comprising one or more words having one or more symbols, creating a bit vector based at least in part on the input keyword string, comparing the bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors and applying a conventional keyword matching algorithm to the at least one candidate keyword string represented by the matching bit vectors. Any matching candidate keyword strings are presented.
-
Citations
206 Claims
-
1. A method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols; and
receiving in response to said submitting at least one candidate keyword string having a bit vector that matches a bit vector of said input keyword string. - View Dependent Claims (11, 12)
-
-
13. A method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols;
creating a bit vector based at least in part on said input keyword string;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (14, 15, 16)
-
-
17. A method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said bit vector having a bit position for each symbol in an alphabet and having bits set for bit positions corresponding to at least one symbol representing the first symbol of a word in said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
18. A method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols; and
receiving in response to said submitting at least one candidate keyword string where the first symbol of at least one word in each of said at least one candidate keyword string matches the first symbol of the corresponding word in said input keyword string. - View Dependent Claims (19, 20)
-
-
21. A method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols;
creating a bit vector based at least in part on said input keyword string, said bit vector having a bit position for each symbol in an alphabet and having bits set for positions corresponding to at least one symbol representing the first symbol of a word in said input keyword string;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (22, 23, 24)
-
-
25. A method for comparing keyword strings, the method comprising:
-
determining a relative frequency of use for at least one symbol in a language;
assigning a statistical weighting to said at least one symbol based at least in part on a relative frequency of use of said at least one symbol;
assigning each of said at least one symbol to one of a plurality of groups; and
comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (26, 27)
-
-
28. A method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or more bit vectors corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to the first symbol of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
29. A method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string; and
receiving in response to said submitting at least one candidate keyword string where the first symbol of each word in each candidate keyword string is comprised by a group comprising said one or more symbols. - View Dependent Claims (30, 31)
-
-
32. A method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to said one or more symbols being set;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (33, 34, 35)
-
-
36. A method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or bit vector corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a symbol of a prefix of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
37. A method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols; and
receiving in response to said submitting at least one candidate keyword string where a prefix of a word of a matching candidate keyword string comprises at least one symbol that belongs to the same symbol group as the corresponding symbol of the corresponding word in said input keyword string. - View Dependent Claims (38, 39)
-
-
40. A method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols;
creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a prefix of a word in said one or more symbols being set;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (41, 42, 43)
-
-
44. A method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
receiving a hierarchy, elements of said hierarchy comprising intermediate nodes and leaf nodes representing one or more keyword strings comprising one or more words comprising one or more symbols;
creating hierarchy bit vectors corresponding to said one or more keyword strings in said hierarchy;
searching said hierarchy bit vectors for a match with said input keyword string, said searching comprising, for each of said elements of said hierarchy;
saving said input keyword string;
applying a logical “
AND”
operation to the bit vector of the element and a bit vector based at least in part on said input keyword string, said applying producing a result;
if said result is nonzero, removing from said input keyword string any words in said input keyword string that are prefixes of words in the element;
if said input keyword string is empty, adding said element to a list of matched items; and
restoring said input keyword string; and
rendering said list of matched items.
-
-
45. A method for creating a keyword string database, the method comprising:
-
step for determining one or more candidate keyword strings to store in said database;
step for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
step for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database. - View Dependent Claims (46, 47, 48, 49, 50, 51, 52, 53)
-
-
54. A method for incremental keyword search, the method comprising:
-
step for submitting an input keyword string comprising one or more words comprising one or more symbols; and
step for receiving in response to said submitting at least one candidate keyword string having a bit vector that matches a bit vector of said input keyword string. - View Dependent Claims (55, 56)
-
-
57. A method for incremental keyword search, the method comprising:
-
step for receiving an input keyword string comprising one or more words comprising one or more symbols;
step for creating a bit vector based at least in part on said input keyword string;
step for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
step for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
step for presenting any matching candidate keyword strings. - View Dependent Claims (58, 59, 60)
-
-
61. A method for creating a keyword string database, the method comprising:
-
step for determining one or more candidate keyword strings to store in said database;
step for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said bit vector having a bit position for each symbol in an alphabet and having bits set for bit positions corresponding to at least one symbol representing the first symbol of a word in said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
step for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
62. A method for incremental keyword search, the method comprising:
-
step for submitting an input keyword string comprising one or more words comprising one or more symbols; and
step for receiving in response to said submitting at least one candidate keyword string where the first symbol of at least one word in each of said at least one candidate keyword string matches the first symbol of the corresponding word in said input keyword string. - View Dependent Claims (63, 64)
-
-
65. A method for incremental keyword search, the method comprising:
-
step for receiving an input keyword string comprising one or more words comprising one or more symbols;
step for creating a bit vector based at least in part on said input keyword string, said bit vector having a bit position for each symbol in an alphabet and having bits set for positions corresponding to at least one symbol representing the first symbol of a word in said input keyword string;
step for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
step for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
step for presenting any matching candidate keyword strings. - View Dependent Claims (66, 67, 68)
-
-
69. A method for comparing keyword strings, the method comprising:
-
step for determining a relative frequency of use for at least one symbol in a language;
step for assigning a statistical weighting to said at least one symbol based at least in part on a relative frequency of use of said at least one symbol;
step for assigning each of said at least one symbol to one of a plurality of groups; and
step for comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (70, 71)
-
-
72. A method for creating a keyword string database, the method comprising:
-
step for determining one or more candidate keyword strings to store in said database;
step for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or more bit vectors corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to the first symbol of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
step for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
73. A method for incremental keyword search, the method comprising:
-
step for submitting an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string; and
step for receiving in response to said submitting at least one candidate keyword string where the first symbol of each word in each candidate keyword string is comprised by a group comprising said one or more symbols. - View Dependent Claims (74, 75)
-
-
76. A method for incremental keyword search, the method comprising:
-
step for receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
step for creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to said one or more symbols being set;
step for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
step for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
step for presenting any matching candidate keyword strings. - View Dependent Claims (77, 78, 79)
-
-
80. A method for creating a keyword string database, the method comprising:
-
step for determining one or more candidate keyword strings to store in said database;
step for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or bit vector corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a symbol of a prefix of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
step for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
81. A method for incremental keyword search, the method comprising:
-
step for submitting an input keyword string comprising one or more words comprising one or more symbols; and
step for receiving in response to said submitting at least one candidate keyword string where a prefix of a word of a matching candidate keyword string comprises at least one symbol that belongs to the same symbol group as the corresponding symbol of the corresponding word in said input keyword string. - View Dependent Claims (82, 83)
-
-
84. A method for incremental keyword search, the method comprising:
-
step for receiving an input keyword string comprising one or more words comprising one or more symbols;
step for creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a prefix of a word in said one or more symbols being set;
step for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
step for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
step for presenting any matching candidate keyword strings. - View Dependent Claims (85, 86, 87)
-
-
88. A method for incremental keyword search, the method comprising:
-
step for receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
step for receiving a hierarchy, elements of said hierarchy comprising intermediate nodes and leaf nodes representing one or more keyword strings comprising one or more words comprising one or more symbols;
step for creating hierarchy bit vectors corresponding to said one or more keyword strings in said hierarchy;
step for searching said hierarchy bit vectors for a match with said input keyword string, said step for searching comprising, for each of said elements of said hierarchy;
step for saving said input keyword string;
step for applying a logical “
AND”
operation to the bit vector of the element and a bit vector based at least in part on said input keyword string, said applying producing a result;
step for if said result is nonzero, removing from said input keyword string any words in said input keyword string that are prefixes of words in the element;
step for if said input keyword string is empty, adding said element to a list of matched items; and
step for restoring said input keyword string; and
step for rendering said list of matched items.
-
-
89. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database. - View Dependent Claims (90, 91, 92, 93, 94, 95, 96, 97)
-
-
98. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols; and
receiving in response to said submitting at least one candidate keyword string having a bit vector that matches a bit vector of said input keyword string. - View Dependent Claims (99, 100)
-
-
101. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols;
creating a bit vector based at least in part on said input keyword string;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (102, 103, 104)
-
-
105. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said bit vector having a bit position for each symbol in an alphabet and having bits set for bit positions corresponding to at least one symbol representing the first symbol of a word in said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
106. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols; and
receiving in response to said submitting at least one candidate keyword string where the first symbol of at least one word in each of said at least one candidate keyword string matches the first symbol of the corresponding word in said input keyword string. - View Dependent Claims (107, 108)
-
-
109. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols;
creating a bit vector based at least in part on said input keyword string, said bit vector having a bit position for each symbol in an alphabet and having bits set for positions corresponding to at least one symbol representing the first symbol of a word in said input keyword string;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (110, 111, 112)
-
-
113. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for comparing keyword strings, the method comprising:
-
determining a relative frequency of use for at least one symbol in a language;
assigning a statistical weighting to said at least one symbol based at least in part on a relative frequency of use of said at least one symbol;
assigning each of said at least one symbol to one of a plurality of groups; and
comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (114, 115)
-
-
116. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or more bit vectors corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to the first symbol of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
117. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string; and
receiving in response to said submitting at least one candidate keyword string where the first symbol of each word in each candidate keyword string is comprised by a group comprising said one or more symbols. - View Dependent Claims (118, 119)
-
-
120. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to said one or more symbols being set;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (121, 122, 123)
-
-
124. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for creating a keyword string database, the method comprising:
-
determining one or more candidate keyword strings to store in said database;
creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or bit vector corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a symbol of a prefix of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
125. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
submitting an input keyword string comprising one or more words comprising one or more symbols; and
receiving in response to said submitting at least one candidate keyword string where a prefix of a word of a matching candidate keyword string comprises at least one symbol that belongs to the same symbol group as the corresponding symbol of the corresponding word in said input keyword string. - View Dependent Claims (126, 127)
-
-
128. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols;
creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a prefix of a word in said one or more symbols being set;
comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
presenting any matching candidate keyword strings. - View Dependent Claims (129, 130, 131)
-
-
132. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for incremental keyword search, the method comprising:
-
receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
receiving a hierarchy, elements of said hierarchy comprising intermediate nodes and leaf nodes representing one or more keyword strings comprising one or more words comprising one or more symbols;
creating hierarchy bit vectors corresponding to said one or more keyword strings in said hierarchy;
searching said hierarchy bit vectors for a match with said input keyword string, said searching comprising, for each of said elements of said hierarchy;
saving said input keyword string;
applying a logical “
AND”
operation to the bit vector of the element and a bit vector based at least in part on said input keyword string, said applying producing a result;
if said result is nonzero, removing from said input keyword string any words in said input keyword string that are prefixes of words in the element;
if said input keyword string is empty, adding said element to a list of matched items; and
restoring said input keyword string; and
rendering said list of matched items.
-
-
133. An apparatus for creating a keyword string database, the apparatus comprising:
-
means for determining one or more candidate keyword strings to store in said database;
means for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
means for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database. - View Dependent Claims (134, 135, 136, 137, 138, 139, 140, 141)
-
-
142. An apparatus for incremental keyword search, the apparatus comprising:
-
means for receiving an input keyword string comprising one or more words comprising one or more symbols;
means for creating a bit vector based at least in part on said input keyword string;
means for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
means for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
means for presenting any matching candidate keyword strings. - View Dependent Claims (143, 144, 145)
-
-
146. An apparatus for creating a keyword string database, the apparatus comprising:
-
means for determining one or more candidate keyword strings to store in said database;
means for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, said bit vector having a bit position for each symbol in an alphabet and having bits set for bit positions corresponding to at least one symbol representing the first symbol of a word in said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
means for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
147. An apparatus for incremental keyword search, the apparatus comprising:
-
means for receiving an input keyword string comprising one or more words comprising one or more symbols;
means for creating a bit vector based at least in part on said input keyword string, said bit vector having a bit position for each symbol in an alphabet and having bits set for positions corresponding to at least one symbol representing the first symbol of a word in said input keyword string;
means for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
means for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
means for presenting any matching candidate keyword strings. - View Dependent Claims (148, 149, 150)
-
-
151. An apparatus for comparing keyword strings, the apparatus comprising:
-
means for determining a relative frequency of use for at least one symbol in a language;
means for assigning a statistical weighting to said at least one symbol based at least in part on a relative frequency of use of said at least one symbol;
means for assigning each of said at least one symbol to one of a plurality of groups; and
means for comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (152, 153)
-
-
154. An apparatus for creating a keyword string database, the apparatus comprising:
-
means for determining one or more candidate keyword strings to store in said database;
means for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or more bit vectors corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to the first symbol of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
means for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
155. An apparatus for incremental keyword search, the apparatus comprising:
-
means for receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
means for creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to said one or more symbols being set;
means for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
means for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
means for presenting any matching candidate keyword strings. - View Dependent Claims (156, 157, 158)
-
-
159. An apparatus for creating a keyword string database, the apparatus comprising:
-
means for determining one or more candidate keyword strings to store in said database;
means for creating one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or bit vector corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a symbol of a prefix of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
means for storing said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
160. An apparatus for incremental keyword search, the apparatus comprising:
-
means for receiving an input keyword string comprising one or more words comprising one or more symbols;
means for creating a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a prefix of a word in said one or more symbols being set;
means for comparing said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors;
means for applying a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors; and
means for presenting any matching candidate keyword strings. - View Dependent Claims (161, 162, 163)
-
-
164. An apparatus for incremental keyword search, the apparatus comprising:
-
means for receiving an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
means for receiving a hierarchy, elements of said hierarchy comprising intermediate nodes and leaf nodes representing one or more keyword strings comprising one or more words comprising one or more symbols;
means for creating hierarchy bit vectors corresponding to said one or more keyword strings in said hierarchy;
means for searching said hierarchy bit vectors for a match with said input keyword string, said means for searching comprising, for each of said elements of said hierarchy;
means for saving said input keyword string;
means for applying a logical “
AND”
operation to the bit vector of the element and a bit vector based at least in part on said input keyword string, said applying producing a result;
means for if said result is nonzero, removing from said input keyword string any words in said input keyword string that are prefixes of words in the element;
means for if said input keyword string is empty, adding said element to a list of matched items; and
means for restoring said input keyword string; and
means for rendering said list of matched items.
-
-
165. An apparatus for creating a keyword string database, the apparatus comprising:
-
a memory for storing said keyword string database; and
a processor configured to;
determine one or more candidate keyword strings to store in said database;
create one or more bit vectors based at least in part on said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
store said one or more bit vectors and a reference to said one or more candidate keyword strings in said database. - View Dependent Claims (166, 167, 168, 169, 170, 171, 172, 173)
-
-
174. An apparatus for incremental keyword search, the apparatus comprising:
-
a user interface configured to receive an input keyword string comprising one or more words comprising one or more symbols, said user interface further configured to present any matching keyword strings; and
a search engine in communication with said user interface and configured to;
create a bit vector based at least in part on said input keyword string;
compare said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors; and
apply a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors. - View Dependent Claims (175, 176, 177)
-
-
178. An apparatus for creating a keyword string database, the apparatus comprising:
-
a memory for storing said keyword string database; and
a processor configured to;
determine one or more candidate keyword strings to store in said database;
create one or more bit vectors based at least in part on said one or more candidate keyword strings, said bit vector having a bit position for each symbol in an alphabet and having bits set for bit positions corresponding to at least one symbol representing the first symbol of a word in said one or more candidate keyword strings, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
store said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
179. An apparatus for incremental keyword search, the apparatus comprising:
-
a user interface configured to receive an input keyword string comprising one or more words comprising one or more symbols, said user interface further configured to present any matching keyword strings; and
a search engine in communication with said user interface and configured to;
create a bit vector based at least in part on said input keyword string, said bit vector having a bit position for each symbol in an alphabet and having bits set for positions corresponding to at least one symbol representing the first symbol of a word in said input keyword string;
compare said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors; and
apply a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors. - View Dependent Claims (180, 181, 182)
-
-
183. An apparatus for comparing keyword strings, the apparatus comprising:
-
a memory for storing at least one relative frequency of use for at least one symbol in a language; and
a processor configured to;
determine a relative frequency of use for at least one symbol in a language;
assign a statistical weighting to said at least one symbol based at least in part on a relative frequency of use of said at least one symbol;
assign each of said at least one symbol to one of a plurality of groups; and
compare a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (184, 185)
-
-
186. An apparatus for creating a keyword string database, the apparatus comprising:
-
a memory for storing said keyword string database; and
a processor configured to;
determine one or more candidate keyword strings to store in said database;
create one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or more bit vectors corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to the first symbol of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
store said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
187. An apparatus for incremental keyword search, the apparatus comprising:
-
a user interface configured to receive an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string, said user interface further configured to present any matching keyword strings; and
a search engine in communication with said user interface and configured to;
create a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to said one or more symbols being set;
compare said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors; and
apply a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors. - View Dependent Claims (188, 189, 190)
-
-
191. An apparatus for creating a keyword string database, the apparatus comprising:
-
a memory for storing said keyword string database; and
a processor configured to;
determine one or more candidate keyword strings to store in said database;
create one or more bit vectors based at least in part on said one or more candidate keyword strings, each bit of said one or bit vector corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a symbol of a prefix of a word in said one or more candidate keyword strings being set, said one or more bit vectors for use in comparing an input bit vector with said one or more bit vectors to indicate whether an input keyword string represented by said input bit vector matches said one or more candidate keyword strings; and
store said one or more bit vectors and a reference to said one or more candidate keyword strings in said database.
-
-
192. An apparatus for incremental keyword search, the apparatus comprising:
-
a user interface configured to receive an input keyword string comprising one or more words comprising one or more symbols, said user interface further configured to present any matching keyword strings; and
a search engine in communication with said user interface and configured to;
create a bit vector based at least in part on said input keyword string, each bit corresponding to one or more symbols in an alphabet, bits having a bit position corresponding to a prefix of a word in said one or more symbols being set;
compare said bit vector with one or more other bit vectors representing at least one candidate keyword string to create a set of matching bit vectors; and
apply a conventional keyword matching algorithm to said at least one candidate keyword string represented by said set of matching bit vectors. - View Dependent Claims (193, 194, 195)
-
-
196. An apparatus for incremental keyword search, the apparatus comprising:
-
a user interface configured to receive an input keyword string comprising one or more words comprising one or more symbols, said user interface further configured to present any matching keyword strings; and
a search engine in communication with said user interface and configured to;
receive an input keyword string comprising one or more words comprising one or more symbols, each symbol representing the first symbol of a word in a search string;
receive a hierarchy, elements of said hierarchy comprising intermediate nodes and leaf nodes representing one or more keyword strings comprising one or more words comprising one or more symbols;
create hierarchy bit vectors corresponding to said one or more keyword strings in said hierarchy;
search said hierarchy bit vectors for a match with said input keyword string, said apparatus further configured to, for each of said elements of said hierarchy;
save said input keyword string;
apply a logical “
AND”
operation to the bit vector of the element and a bit vector based at least in part on said input keyword string, said applying producing a result;
if said result is nonzero, remove from said input keyword string any words in said input keyword string that are prefixes of words in the element;
if said input keyword string is empty, add said element to a list of matched items; and
restoring said input keyword string; and
render said list of matched items; and
apply a conventional keyword matching algorithm to said at least one keyword string represented by one or more element in said list of matched items.
-
-
197. A method for comparing keyword strings, the method comprising:
-
assigning each of at least one symbol in a language to one of a plurality of groups; and
comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (198)
-
-
199. A method for comparing keyword strings, the method comprising:
-
step for assigning each of at least one symbol in a language to one of a plurality of groups; and
step for comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (200)
-
-
201. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for comparing keyword strings, the method comprising:
-
assigning each of at least one symbol in a language to one of a plurality of groups; and
comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (202)
-
-
203. An apparatus for comparing keyword strings, the method comprising:
-
means for assigning each of at least one symbol in a language to one of a plurality of groups; and
means for comparing a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (204)
-
-
205. An apparatus for comparing keyword strings, the apparatus comprising:
-
a memory for storing said keyword strings; and
a processor configured to;
assign each of at least one symbol in a language to one of a plurality of groups; and
compare a first keyword string and a second keyword string based at least in part on whether at least one symbol of said first keyword string is assigned to the same group as at least one corresponding symbol of said second keyword string. - View Dependent Claims (206)
-
Specification