| 摘要 |
<p>[Problem to be Solved] To provide a technique for enabling context surrounding a search result to be appropriately brought together in a limited range and displayed. [Solution] An area covered by a character string s in an entire set of context strings C {c 1 , ..., c n } is defined by the product of the number of c having s as a prefix and the length of s. In a set of the maximum number K of character strings having lengths less than or equal to L, character strings that as a whole cover the maximum area in the entire set of context strings is determined under the constraint that a substring of another character string should not be selected. According to the present invention the problem can be efficiently solved using dynamic programming on a frequency-ordered context tree, which is a trie of the entire context. According to another aspect of the present invention, when the maximum area is determined by the dynamic programming, an upper limit area that can be obtained by a search is estimated to enable substantial pruning of the search, thereby speeding up the process. Furthermore, child nodes in a suffix tree of a document are arranged in the order of frequency of occurrences to build a frequency-ordered suffix tree, thereby enabling faster searching and determination of the maximum area.</p> |
