US6377945B1 — Search system and method for retrieval of data, a…

Claim 1

Independent Claim 551 words

A search system for information retrieval, particularly information stored in form of text, wherein a text T comprises words and/or symbols s and sequences S thereof, wherein the information retrieval takes place with a given or varying degree of matching between a query Q, wherein the query Q comprises words and/or symbols q and sequences thereof P, and retrieved information R comprising words and/or symbols and sequences thereof from the text T, wherein the search system comprises a data structure for storing at least a part of the text T, and a metric M which measures the degree of matching between the query Q and retrieved information R, and wherein the search system implements search algorithms for executing a search, particularly a full text search on the basis of keywords kw, characterized in that the data structure comprises a tree structure in the form of a non-evenly spaced sparse suffix tree ST(T) for storing suffixes of words and/or symbols s and sequences S thereof in the text T, that the metric M comprises a combination of an edit distance metric D(s,q) for an approximate degree of matching between words and/or symbols s;q in respectively the text T and a query Q and an edit distance metric D ws (S,P) for an approximate degree of matching between sequences S of words and/or symbols s in the text T and a query sequence P of words and/or symbols q in the query Q, the latter edit distance metric including weighting cost functions for edit operations which transform sequences of words and/or symbols s in the text T into the sequence P of words and/or symbols q in the query Q, the weighting taking place with a value proportional to a change in the length of the sequence S upon a transformation or dependent on the size of the words and/or symbols s;q in sequences S;P to be matched, that the implemented search algorithms comprise a first algorithm for determining the degree of matching between words and/or symbols s;q in the suffix tree representation of respectively the text T and a query Q, and a second algorithm for determining the degree of matching between sequences S;P of words and/or symbols s;q in the suffix tree representation of respectively the text T and the query Q, said first and/or second algorithms searching the data structure with queries Q in the form of either words, symbols, sequences of words or sequences of symbols or combinations thereof, such that information R is retrieved on the basis of query Q with a specified degree of matching between the former and the latter, and that the search algorithms optionally also comprise a third algorithm for determining exact matching between words and/or symbols s;q in the suffix tree representation of respectively the text T and the query Q and/or a fourth algorithm for determining exact matching between sequences S;P of words and/or symbols s;q in the suffix tree representation of respectively the text T and the query Q, said third and/or fourth algorithms searching the data structure with queries Q in the form of either words, symbols, sequences of words, or sequences of symbols or combinations thereof, such that information R is retrieved on the basis of the query Q with an exact matching between the former and the latter.

Claim 2

Dependent Claim 551 words

A search system for information retrieval, particularly information stored in form of text, wherein a text T comprises words and/or symbols s and sequences S thereof, wherein the information retrieval takes place with a given or varying degree of matching between a query Q, wherein the query Q comprises words and/or symbols q and sequences thereof P, and retrieved information R comprising words and/or symbols and sequences thereof from the text T, wherein the search system comprises a data structure for storing at least a part of the text T, and a metric M which measures the degree of matching between the query Q and retrieved information R, and wherein the search system implements search algorithms for executing a search, particularly a full text search on the basis of keywords kw, characterized in that the data structure comprises a tree structure in the form of a non-evenly spaced sparse suffix tree ST(T) for storing suffixes of words and/or symbols s and sequences S thereof in the text T, that the metric M comprises a combination of an edit distance metric D(s,q) for an approximate degree of matching between words and/or symbols s;q in respectively the text T and a query Q and an edit distance metric D ws (S,P) for an approximate degree of matching between sequences S of words and/or symbols s in the text T and a query sequence P of words and/or symbols q in the query Q, the latter edit distance metric including weighting cost functions for edit operations which transform sequences of words and/or symbols s in the text T into the sequence P of words and/or symbols q in the query Q, the weighting taking place with a value proportional to a change in the length of the sequence S upon a transformation or dependent on the size of the words and/or symbols s;q in sequences S;P to be matched, that the implemented search algorithms comprise a first algorithm for determining the degree of matching between words and/or symbols s;q in the suffix tree representation of respectively the text T and a query Q, and a second algorithm for determining the degree of matching between sequences S;P of words and/or symbols s;q in the suffix tree representation of respectively the text T and the query Q, said first and/or second algorithms searching the data structure with queries Q in the form of either words, symbols, sequences of words or sequences of symbols or combinations thereof, such that information R is retrieved on the basis of query Q with a specified degree of matching between the former and the latter, and that the search algorithms optionally also comprise a third algorithm for determining exact matching between words and/or symbols s;q in the suffix tree representation of respectively the text T and the query Q and/or a fourth algorithm for determining exact matching between sequences S;P of words and/or symbols s;q in the suffix tree representation of respectively the text T and the query Q, said third and/or fourth algorithms searching the data structure with queries Q in the form of either words, symbols, sequences of words, or sequences of symbols or combinations thereof, such that information R is retrieved on the basis of the query Q with an exact matching between the former and the latter.

Claim 3

Dependent Claim 36 words

A search system according to claim 1 , wherein the non-evenly spaced sparse suffix tree ST(T) is a word-spaced sparse suffix tree SST ws (T) comprising only a subset of the suffixes in the text T.

Claim 4

Dependent Claim 26 words

A search system according to claim 2 , wherein the word-spaced sparse suffix tree SST ws (T) is a keyword-spaced sparse suffix tree SST kws (T).

Claim 5

Dependent Claim 181 words

A search system according to claim 3 , wherein the first algorithm for detecting the degree of keyword matching in a keyword-spaced sparse suffix tree SST kws (T) is implemented in pseudo-code as follows: FindApproximate (root,p,k) node←root; i←1; nodes←Children (node); // A stack of nodes for all v ε nodes do if IsLeaf (v) then for j←i to length (Suffix(node)) do w j ←Suffix(node) j−i ; if w j =‘$’ then // ‘$’ is a stopchar output W l j ; return; if EditDist (i)=∞ then break; else //Internal node i←i+1; w i ←label (v) if EditDist (i)=∞ then break; nodes←Children (v) ∪ nodes; // end for EditDistance(j) // Calculates jth row for i←1 to length (P) do if p i =w j then ∂←0 else ∂←1; c 1 =D[i−1,j]+c ins (m j ); c 2 =D[i,j−1]+c del (p i ); c 3 =D[i−1,j−1]+c change (p i ,m j ); c 4 =D[i−2,j−2]+c transpose (p i ,m j−1 ); D[i,j]←c fraction (j/l)·min(c 1 ,c 2 ,c 3 ,c 4 ); if D[i,j]>k return ∞; // No distance below k return D[i,j].

Claim 6

Dependent Claim 78 words

A search system according to claim 3 , wherein the second algorithm for determining the degree of keyword sequence matching in a keyword-spaced sparse suffix tree SST kws (T) is implemented in code as follows: ApproxSequenceMatch_ED (root, P(=p 1 ,p 2 , ,P m ),k) m←|p| matches←Ø startError←0 startIndex←1 while startError≦k OR startIndex≦m do startNode←FindExact (p startIndex ); list←UnorderedOccurrenceList (startNode); for all v ε lists do if ApproxMatchRest 2 (v,P,k,startError) then matches←∪v; startError←startError+c del (p startIndex ); startIndex←startIndex+1.

Claim 7

Dependent Claim 125 words

A search system according to claim 5 , wherein the ApproxMatchRest subroutine of the second algorithm is implemented in pseudo-code as follows: ApproxMatchRest (u,P,K,startError) error←startError; lastError←startError; column←O; node←u; for v←p 2 to p |p| do node←NextOccurrence(node); word←Keyword(node); lastError←error; error←startError+EditDistance (column); if error >k AND lastError >k then return false; return true; EditDistance(j) // Calculates jth row for i←1 to length (P) do if p i =w j then ∂←0 else ∂←1; c 1 =D[i−1,j]+c ins (m j ); c 2 =D[i,j−1]+c del (p i ); c 3 =D[i−1,j−1]+c change (p i ,m j ); c 4 =D[i−2,j−2]+c transpose (p i ,m j−1 ); D[i,j]←c fraction (j/l)·min(c 1 ,c 2 ,c 3 ,c 4 ); if D[i,j]>k return ∞; // No distance below k return D[i,j].

Claim 8

Dependent Claim 64 words

A search system according to claim 3 , wherein the third algorithm for determining an exact keyword matching in a keyword-spaced sparse suffix tree SST kws (I) is implemented in pseudo-code as follows: FindExact (root,p) i←1; node←Find Child (root,p i ); while node AND i ≦length (p) do if IsLeaf(node) AND Suffix(node)=P i P m then return node; i←i+1 node←FindChild (node, p i ).

Claim 9

Dependent Claim 92 words

A search system according to claim 3 , wherein the fourth algorithm for determining an exact keyword sequence matching in a keyword-spaced sparse suffix tree SST kws (T) is implemented in pseudo-code as follows: MatchSequenceExact (P, root) matches←Ø; v←FindExact (p 1 ,root); if |P|>1 then if v ? NIL then list←UnorderedOccurrenceList (v); for all u ε list do if NextKeyword(u)=p 2 then if MatchRest (p 3 p m ,u) then matches←matches ∪ Occurrence(u); return matches; MatchRest (P,u) node←u; for v←p l to p |p| do node←NextOccurrence(node); word←Keyword(node); if v≠word then return false.

Claim 10

Dependent Claim 15 words

The use of a search system according to claim 1 in an approximate search engine.

Claim 11

Independent Claim 451 words

A method in a search system for information retrieval, particularly information stored in form of text, wherein a text T comprises words and/or symbols s and sequences S thereof, wherein the information retrieval takes place with a given or varying degree of matching between a query Q, wherein the query Q comprises words and/or symbols q and sequences P thereof, and retrieved information R comprising words and/or symbols and sequences thereof from the text T, wherein the search system comprises a data structure for storing at least a part of the text T, and a metric M which measures the degree of matching between the query Q and retrieved information R, and wherein the search system implements search algorithms for executing a search, particularly a full text search on the basis of keywords kw, wherein the information in the text T is divided into words s and word sequences S, the words being substrings of the entire text separated by word boundary terms and forming a sequence of symbols, and wherein each word is structured as a sequence of symbols, characterized by generating the data structure as a word-spaced sparse suffix tree SST ws (T) of a text T for representing all the suffixes starting at a word separator symbol in the text T, storing sequence information of the words s in the text T in the word-spaced sparse suffix tree SST ws (T), generating a combined edit distance metric M comprising an edit distance metric D(s,q) for words s in the text T and a query word q in a query Q and a word-size dependent edit distance metric D ws (S,P) for sequences S of words s in the text T and a sequence P of words q in the query Q, the edit distance metric D ws (S,P) being the minimum sum of costs for edit operations transforming a sequence S into the sequence P, the minimum sum of costs being the minimum sum of cost functions for each edit operation weighted by a value proportional to the change in the total length of the sequence S or by the ratio of the current word length and average word length in the sequences S;P, and determining the degree of matching between words s,q by calculating the edit distance D(s,q) between the words s of the retrieved information R and the word q of a query Q, or in case the words s,q are more than k errors from each other, determining the degree of matching between the word sequences S R ; P Q of retrieved information R and a query Q respectively by calculating the edit distance D ws (S R ,P Q ) for all matches.

Claim 12

Independent Claim 451 words

A method in a search system for information retrieval, particularly information stored in form of text, wherein a text T comprises words and/or symbols s and sequences S thereof, wherein the information retrieval takes place with a given or varying degree of matching between a query Q, wherein the query Q comprises words and/or symbols q and sequences P thereof, and retrieved information R comprising words and/or symbols and sequences thereof from the text T, wherein the search system comprises a data structure for storing at least a part of the text T, and a metric M which measures the degree of matching between the query Q and retrieved information R, and wherein the search system implements search algorithms for executing a search, particularly a full text search on the basis of keywords kw, wherein the information in the text T is divided into words s and word sequences S, the words being substrings of the entire text separated by word boundary terms and forming a sequence of symbols, and wherein each word is structured as a sequence of symbols, characterized by generating the data structure as a word-spaced sparse suffix tree SST ws (T) of a text T for representing all the suffixes starting at a word separator symbol in the text T, storing sequence information of the words s in the text T in the word-spaced sparse suffix tree SST ws (T), generating a combined edit distance metric M comprising an edit distance metric D(s,q) for words s in the text T and a query word q in a query Q and a word-size dependent edit distance metric D ws (S,P) for sequences S of words s in the text T and a sequence P of words q in the query Q, the edit distance metric D ws (S,P) being the minimum sum of costs for edit operations transforming a sequence S into the sequence P, the minimum sum of costs being the minimum sum of cost functions for each edit operation weighted by a value proportional to the change in the total length of the sequence S or by the ratio of the current word length and average word length in the sequences S;P, and determining the degree of matching between words s,q by calculating the edit distance D(s,q) between the words s of the retrieved information R and the word q of a query Q, or in case the words s,q are more than k errors from each other, determining the degree of matching between the word sequences S R ; P Q of retrieved information R and a query Q respectively by calculating the edit distance D ws (S R ,P Q ) for all matches.

Claim 13

Dependent Claim 55 words

The method according to claim 10 , further comprising additionally weighting an edit operation which changes a word s into word q with a parameter for the proximity between the characters of the words s;q, thus taking the similarity of the words s;q in regard when determining the cost of the edit operation in question.

Claim 14

Dependent Claim 39 words

The method according to claim 10 , further comprising limiting the number of matches by calculating the edit distance D ws (S R ,P Q ) for restricted number of words in the query word sequence P Q .

Claim 15

Dependent Claim 35 words

A method according to claim 10 , further comprising defining the edit distance D(s,q) between words s and a word q recursively and calculating the edit distance D(s,q) by means of a dynamic programming procedure.

Claim 16

Dependent Claim 39 words

A method according to claim 10 , further comprising defining the edit distance D ws (S,P) between sequences S and a sequence P recursively and calculating the edit distance D ws (S,P) by means of a dynamic programming procedure.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2005-04-22	2005-10-22	2006-04-23	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2009-04-22	2009-10-22	2010-04-23	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2013-04-22	2013-10-22	2014-04-23	$7700.00	Window Closed / Lapsed

Search system and method for retrieval of data, and the use thereof in a search engine

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag