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

• US 6,377,945 B1
• Filed: 03/09/2000
• Issued: 04/23/2002
• Est. Priority Date: 07/10/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Fast Search & Transfer ASA (Microsoft Corporation)
• Inventors: Risvik, Knut Magne
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US09/486,726
• Time in Patent Office: 775 Days
• Field of Search: 707/2-6, 707/102, 707/104.1, 704/9, 704/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A search system for information retrieval includes a data structure in the form of a non-evenly spaced sparse suffix tree for storing suffixes of words and/or symbols, or sequences thereof, in a text T, a metric M including combined edit distance metrics for an approximate degree of matching respectively between words and/or symbols, or between sequences thereof, in the text T and a query Q, the latter distance metric including weighting cost functions for edit operations which transform a sequence S of the text into a sequence P of the query Q, and search algorithms for determining the degree of matching respectively between words and/or symbols, or between sequences thereof, in respectively the text T and the query Q, such that information R is retrieved with a specified degree of matching with the query Q. Optionally the search system also includes algorithms for determining exact matching such that information R may be retrieved with an exact degree of matching with the query Q.

Claims

1. 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.

2. 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.

3. 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).

4. 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)<sub>j−

i</sub>;

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₁=D[i−

1,j]+c_ins(m_j);

 

c₂=D[i,j−

1]+c_del(p_i);

 

c₃=D[i−

1,j−

1]+c_change(p_i,m_j);

 

c₄=D[i−

2,j−

2]+c_transpose(p_i,m<sub>j−

1</sub>);

 

D[i,j]←

c_fraction(j/l)·

min(c₁,c₂,c₃,c₄);

if D[i,j]>

k

 

return ∞

;

// No distance below k

return D[i,j].

5. 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₁,p₂, ,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 ApproxMatchRest2 (v,P,k,startError) then

matches←

∪

v;

startError←

startError+c_del (p_startIndex);

startIndex←

startIndex+1.

6. 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₂ 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₁=D[i−

1,j]+c_ins(m_j);

 

c₂=D[i,j−

1]+c_del(p_i);

 

c₃=D[i−

1,j−

1]+c_change(p_i,m_j);

 

c₄=D[i−

2,j−

2]+c_transpose(p_i,m<sub>j−

1</sub>);

 

D[i,j]←

c_fraction(j/l)·

min(c₁,c₂,c₃,c₄);

if D[i,j]>

k

 

return ∞

;

// No distance below k

return D[i,j].

7. 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).

8. 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₁,root);

if |P|>

1 then

 

if v ? NIL then

list←

UnorderedOccurrenceList (v);

for all u ε

list do

 

if NextKeyword(u)=p₂ then

if MatchRest (p₃ 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.

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

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.