Symbol dictionary compiling method and symbol dictionary retrieving method

Abstract

If the character string is long, and when retrieving symbols containing characters of high frequency of appearance or character chain, high speed retrieval is possible up to infix matching, and a symbol dictionary of small capacity can be compiled. In the symbol dictionary compiling method of the invention, each symbol in symbol data is covered with shorter symbols called “meta-symbols” for covering the symbol in the symbol data, and the information showing how each symbol is covered is obtained by preparing meta-symbol appearance information recorded in each meta-symbol, and therefore high speed retrieval including up to infix matching is possible, and a symbol dictionary of small capacity can be compiled.

1 . A method of retrieving a complete match to an arbitrary character string query using a symbol dictionary containing a meta-symbol information and a meta-symbol appearance information, comprising the steps of: 
 (a) retrieving meta-symbol information in said symbol dictionary,    (b) searching for a covering the query character string Q by duplicate longest match word extraction method that is, covering elements of pair (m, s, e) of meta-symbol m collating with a partial character string, collating a character start position s, and collating an end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and a set containing any character of Q in at least one covering element,    (c) storing the results of the search of step (b) in the working area/storage/memory,    (d) terminating the retrieval if there is no covering such that, if there is no set of covering elements of pair (m, s, e) of meta-symbol m collating with said partial character string, collating said character start position s, and collating said end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and containing at least one covering element for each character of Q, and    (e) retrieving the meta-symbol appearance information in said symbol dictionary and if there is only one symbol number contained commonly in all elements in said covering result, it is issued as the retrieval result and the retrieval process is terminated, and if there is no symbol number contained commonly in all elements in said covering result, the retrieval process is terminated as being no retrieval result.    
   
   
       2 . A method of retrieving by forward coincidence a response to an arbitrary character string query using a symbol dictionary storing meta-symbol information and meta-symbol appearance information, that is, retrieving all symbols having said queried character string in the beginning portion, comprising the steps of: 
 a first step of symbol dictionary retrieval in which (a) a question character string covering means retrieves meta-symbol information in said symbol dictionary and searches covering in the query character string Q by longest match overlapped longest match word extraction method that is, covering elements of pair (m, s, e) of meta-symbol m collating with a partial character string, collating a character start position s, and collating an end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and a set containing any character of Q in at least one covering element, (b) the retrieval is terminated as being no retrieval result if there is no covering elements of pair (m, s, e) of meta-symbol m collating with said partial character string, said collating character start position s, and collating said end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and there is no set containing any character of Q in at least one covering element, and (c) if there is covering, the covering result is recorded,    a second step of symbol dictionary retrieval in which (d) a right extended meta-symbol assessing means retrieves meta-symbol information in said symbol dictionary, retrieves, in said covering result, all meta-symbols x of right extended meta-symbols, that is, meta-symbols containing character string R in the beginning portion of j-th rightmost portion character string of said query character string R such that a partial character string from the j-th character (1≦j≦|Q|) to a final character in query character string, out of extended meta-symbols of meta-symbol Z of covering elements of which collating said start character position is 1, that is, meta-symbols containing Z, and adds elements (x, j, |R|+j) to said covering result and records, and    a third step of symbol dictionary retrieval in which a symbol number set assessing means retrieves said meta-symbol appearance information in said symbol dictionary while systematically compiling a set C of elements in said covering result, covering said query character string or an arbitrary right extended character string, collects a symbol number set SC commonly contained in all elements of C, records as part of said retrieval result, and issues the sum set of all SCs as a final retrieval result.    
   
   
       3 . A method of retrieving, by backward coincidence, a response to an arbitrary character string query using a symbol dictionary storing meta-symbol information and meta-symbol appearance information, that is, retrieving all symbols having said queried character string in the end portion, comprising the steps of: 
 a first step of symbol dictionary retrieval in which (a) a queried character string covering means retrieves meta-symbol information in said symbol dictionary and searches covering in the queried character string Q by longest match overlapped longest match word extraction method that is, covering elements of pair (m, s, e) of a meta-symbol m collating with a partial character string, collating a character start position s, and collating an end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and a set containing any character of Q in at least one covering element, (b) the retrieval process is terminated as being no retrieval result if there is no covering, that is, covering elements of pair (m, s, e) of meta-symbol m collating with partial character string, collating character start position s, and collating end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and there is no set containing any character of Q in at least one covering element, the retrieval process is terminated as being no retrieval result, and (c) if there is covering, the covering result is recorded,    a second step of symbol dictionary retrieval in which (d) a left extended meta-symbol assessing means retrieves meta-symbol information in said symbol dictionary, retrieves, in said covering result, all meta-symbols x of a left extended meta-symbols that is, meta-symbols containing a character string L in the end portion) of j-th leftmost portion character string of said queried character string that is, the partial character string from the first character to the j-th character (1≦j≦|Q|) in question character string L, out of an extended meta-symbols of meta-symbol Z of covering elements of which collating end character position is |Q|+1 [(] that is, meta-symbols containing Z, and adds elements (x, j+1−|L|, j+1) to said covering result and records, and    a third step of symbol dictionary retrieval in which a symbol number set assessing means retrieves said meta-symbol appearance information in said symbol dictionary while systematically compiling a set C of elements in said covering result covering said queried character string or an arbitrary left extended character string, collects a symbol number set SC commonly contained in all elements of C, records as part of retrieval result, and issues the sum set of all SCs as a final retrieval result.    
   
   
       4 . A method of retrieving, by intermediate coincidence, to an arbitrary character string query using a symbol dictionary storing meta-symbol information and meta-symbol appearance information, that is, retrieving all symbols having said queried character string, comprising: 
 a first step of symbol dictionary retrieval in which a question character string covering means retrieves said meta-symbol information in said symbol dictionary and searches covering in the queried character string Q by longest matchoverlapped longest match word extraction method that is, covering elements of pair (m, s, e) of a meta-symbol m collating with a partial character string, collating a character start position s, and an collating end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and a set containing any character of Q in at least one covering element, the retrieval process is terminated with no retrieval result if there is no covering that is, covering elements of pair (m, s, e) of said meta-symbol m collating with said partial character string, collating said character start position s, and collating said end character position e (1≦s<e≦|Q|+1) in the character string to be covered, and there is no set containing any character of Q in at least one covering element, and if there is covering, the covering result is recorded,    a second step of symbol dictionary retrieval in which a right extended meta-symbol assessing means retrieves meta-symbol information in said symbol dictionary, retrieves, in said covering result, all meta-symbols x of a right extended meta-symbols, that is, meta-symbols containing a character string R in the beginning portion, of j-th rightmost portion character string of said queried character string R, that is, the partial character string from the j-th character (1≦j≦|Q|) to a final character in queried character string R, out of extended meta-symbols of meta-symbol Z of covering elements of which collating said start character position is 1, that is, meta-symbols containing Z, and adds elements (x, j, |R|+j) to said covering result and records,    a third step of symbol dictionary retrieval in which a left extended meta-symbol assessing means retrieves meta-symbol information in said symbol dictionary, retrieves, in said covering result, all meta-symbols x of a left extended meta-symbols, that is, meta-symbols containing a character string L in the end portion, of j-th leftmost portion character string of said queried character string, that is, the said partial character string from a first character to the j-th character (1≦j≦|Q|) in question character string L, out of extended meta-symbols of meta-symbol Z of covering elements of which collating said end character position is |Q|+1, that is, meta-symbols containing Z, and adds elements (x, j+1−|L|, j+1) to said covering result and records,    a fourth step of symbol dictionary retrieval in which an extended meta-symbol assessing means retrieves the meta-symbol information, retrieves both the extended meta-symbols of Q and X that is, meta-symbols containing character string Q in the portion from the j-th character to the j+|Q|-th character, where 1<j, and X, adds elements (X, 1−j, 1−j+|X|) to said covering result and records, and    a fifth step of symbol dictionary retrieval in which a symbol number set assessing means retrieves said meta-symbol appearance information in said symbol dictionary while systematically compiling a set C of elements in said covering result covering said queried character string or an arbitrary extended character string, collects a symbol number set SC commonly contained in all elements of C, records as part of said retrieval result, and issues the sum set of all SCs as a final retrieval result.