WO2012017782A1 - 文字列生成方法、プログラム及びシステム - Google Patents

文字列生成方法、プログラム及びシステム Download PDF

Info

Publication number
WO2012017782A1
WO2012017782A1 PCT/JP2011/065802 JP2011065802W WO2012017782A1 WO 2012017782 A1 WO2012017782 A1 WO 2012017782A1 JP 2011065802 W JP2011065802 W JP 2011065802W WO 2012017782 A1 WO2012017782 A1 WO 2012017782A1
Authority
WO
WIPO (PCT)
Prior art keywords
character string
context
dynamic programming
search
frequency
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2011/065802
Other languages
English (en)
French (fr)
Inventor
裕也 海野
祐太 坪井
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Priority to KR1020137004451A priority Critical patent/KR101498396B1/ko
Priority to CA2804514A priority patent/CA2804514A1/en
Priority to CN201180037655.0A priority patent/CN103052951B/zh
Priority to EP11814412.0A priority patent/EP2602724A4/en
Priority to JP2012527648A priority patent/JP5337308B2/ja
Publication of WO2012017782A1 publication Critical patent/WO2012017782A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33—Querying
    • G06F16/338—Presentation of query results

Definitions

  • This invention relates mainly to a character string search technique for natural language text, and more particularly to a technique for displaying a search result.
  • the context before and after the hit position gives useful information. For example, when searching for “button”, check whether the expression of the document is uniform or whether a definite article is added to a specific English proper noun depending on whether “click” or “press” continues.
  • the context information before and after the hit position is also important for confirmation and other collocation and person name searches.
  • KWIC KeyWord In Context
  • buttons ... I write it on the button ... Click the button ... Click the button below ... Click the button ... I can't click the button ... You can click the button ... Click the button. ... When you press the button ... Press the button ... Let me push the button ... Try to press the button ...
  • an object of the present invention is to provide a technique that makes it possible to appropriately aggregate and display the peripheral context of search results within a limited range.
  • the present invention covers the area covered by the entire bag under the restriction that a partial character string of another character string is not selected from a character string set of up to K characters and length L or less for all context sets. It is a technique for finding what is to be maximized. According to the knowledge of the present invention, this problem can be solved efficiently by dynamic programming on a frequency-ordered context tree with all contexts set to TRIE.
  • the upper limit of the area obtained by the search can be estimated, so that the search can be greatly pruned, and the processing can be performed. Speed can be increased.
  • the above processing can be naturally applied not only to the backward context but also to the forward context.
  • word breaks since word breaks are not used, it can be applied to analysis of arbitrary language data including English and event sequences with time.
  • FIG. 4 is a diagram showing a comparison of a context display between a conventional typical technique and a technique according to an embodiment of the present invention.
  • FIG. 1 there is shown a block diagram of computer hardware for realizing a system configuration and processing according to an embodiment of the present invention.
  • a CPU 104 a main memory (RAM) 106, a hard disk drive (HDD) 108, a keyboard 110, a mouse 112, and a display 114 are connected to the system path 102.
  • CPU 104 is preferably based on a 32-bit or 64-bit architecture, for example, Intel Pentium TM 4, Core TM 2 Duo, Xeon TM, AMD Athlon TM. Etc. can be used.
  • the main memory 106 preferably has a capacity of 2 GB or more.
  • the hard disk drive 108 preferably has a capacity of, for example, 320 GB or more so that a large amount of document data and frequency-ordered suffix tree data for searching can be stored.
  • the hard disk drive 108 stores an operating system in advance, although not individually illustrated.
  • the operating system is any suitable for the CPU 104, such as Linux (trademark), Windows (trademark) 7, Microsoft XP (trademark), Windows (trademark) 2000, or Mac OS (trademark) of Apple Computer. Good.
  • the hard disk drive 108 further includes text data to be searched, a frequency order suffix tree creation module that generates frequency order suffix tree data from the text data, and a frequency created by the frequency order suffix tree creation module.
  • a context character string is obtained by the technique of the present invention, and the character string search module that outputs the character string in a compressed form of the display, and the character string search module output A GUI module for displaying the character string displayed on the display 114 is stored.
  • the keyboard 110 and the mouse 112 are loaded into the main memory 106 from the operating system or the hard disk drive 108, and start a program (not shown) displayed on the display 114 or input characters for searching. Used for.
  • the display 114 is preferably a liquid crystal display, and an arbitrary resolution such as XGA (1024 ⁇ 768 resolution) or UXGA (1600 ⁇ 1200 resolution) can be used.
  • Text file 202 is a large file stored on hard disk drive 108 and preferably includes natural language text data.
  • the frequency order suffix tree construction module 204 reads the text file 202 and stores it in the hard disk drive 108 as frequency order suffix tree data 206.
  • the processing of the frequency order suffix tree construction module 204 will be described in more detail later with reference to the flowchart of FIG.
  • the character string search module 208 includes a function related to processing that forms a main part of the present invention, and searches for a context character string based on a keyword input by the user, and further, based on that, displays a compressed display character string. Calculate and give The processing of the character string search module 208 will be described in more detail later with reference to the flowchart of FIG.
  • the GUI module 210 has a function of passing the character string input by the user using the keyboard 110 and the mouse 112 to the character string search module 208 and displaying the output of the context character string of the character string search module 208 on the display 114.
  • the frequency order suffix tree construction module 204, the character string search module 208, and the GUI module 210 can be written in an existing programming language such as C, C ++, C #, Java (trademark).
  • the GUI module 210 is preferably programmed to call API functions provided by the operating system to read the user's string input or display the output of the context string on the display 114.
  • the frequency-order suffix tree is a TRIE created for all suffixes in a document.
  • the full suffix is a set of character strings after all positions in the document. Therefore, n exists for a document of length n.
  • the child nodes of each node of TRIE are sorted in descending order of the total number of leaves.
  • the general suffix tree is sorted alphabetically, not by the total number of leaves.
  • the size is the same as the suffix tree, O (n), and at most 2n nodes.
  • the frequency order suffix tree construction module 204 reads the text file 202 in step 302 in FIG. 3 and constructs a suffix array in step 304.
  • This processing uses, for example, techniques described in Ge Nong, Sen Zhang, Wai Hong Chan, “Two Efficient Algorithms for Linear Suffix Array Construction”, IEEE Transactions on Computers, 2008.
  • the frequency order suffix tree construction module 204 calculates the maximum prefix length. For example, Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and It Use the techniques described in 181-192. 2001.
  • the frequency order suffix tree construction module 204 sets n as the first node in the return order. For example, Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its procsnn Symposium on Combinatorial Pattern Matching, pp. 181-192. 2001.
  • step 310 the frequency order suffix tree construction module 204 determines whether n is the last node in the order of return, and if so, the process ends.
  • step 312 the frequency order suffix tree construction module 204 sorts the n child nodes in frequency order, and in step 314 outputs the n child nodes to a file, which is the frequency order suffix.
  • the dictionary data 206 is saved in the hard disk drive 108.
  • step 316 the node next to n is substituted for n, and the process returns to the determination in step 310.
  • FIG. 4 (a) is a diagram showing an example of a tree structure of a frequency-order suffix tree constructed in this way.
  • “bo”, “ta”, and the like are nodes of the frequency order suffix tree, and the numbers shown above the nodes indicate appearance answers.
  • an area indicated by reference numeral 402 indicates a frequency-order context tree for “button”. If the frequency-order suffix tree is created once for a given text file to be searched and saved in the hard disk drive 108, it will not be recreated unless the text file changes. Can be used for searching even once.
  • FIG. 4B is a diagram showing an example of a frequency order context tree.
  • the frequency ordered context tree is dynamically generated on main memory or hard disk drive 108 by searching the frequency ordered suffix tree for a particular keyword.
  • the dynamic programming method of the present invention which will be described later, is executed on the frequency order context tree thus dynamically generated.
  • the search on the frequency order suffix tree can be executed in the same way as the suffix tree. However, since the child nodes are not arranged in alphabetical order, a linear search is necessary. At this time, if the child nodes are continued in the data structure, the search can be performed only by random access in the number proportional to the query length. Then, the subtree whose root is the node that has been searched becomes a frequency-order context tree.
  • FIG. 5 shows a process for searching the frequency order suffix tree data 206 constructed by the process of FIG.
  • This process is preferably implemented as search (), which is one of the functions as a subroutine that the character string search module 208 has.
  • step 502 the root node (ROOT) is substituted for n.
  • the process then returns to step 508.
  • the subtree of the frequency-order suffix tree rooted at the return value n is the main memory 106 or the hard disk, as the frequency-order context tree as illustrated in FIG. Built on drive 108.
  • FIG. 6 is a flowchart of the entire search and optimum context search process executed by the character string search module 208.
  • step 602 the character string search module 208 calls the function search (s) shown in the flowchart of FIG. 5 and returns the result to n.
  • s is a query character string, which is input by the user via the GUI module 210.
  • the character string search module 208 determines in step 604 whether n is null, and if so, in step 606, outputs that the character string is not found and ends the process. This processing is typically performed by the character string search module 208 passing a message to the GUI module 210 and causing the display 114 to display the message.
  • step 608 the character string search module 208 performs a search process using dynamic programming in step 608.
  • the character string search module 208 uses the dynamic programming function f (n, K) described later based on the flowchart of FIG. 7 or the flowcharts of FIGS. 8 and 9 as the dynamic programming.
  • One or both of the functions g (n, K, 0) of dynamic programming with pruning, which will be described later, may be provided as subroutines.
  • K is the maximum number of selected character strings.
  • dynamic programming is applied on the frequency order context tree constructed by search (s) in step 602.
  • Gg (n, K, 0) is suitable for searching a frequency-ordered context tree that is larger than f (n, K) by the process with pruning. Therefore, the character string search module 208 applies g (n, K, 0) when the frequency order context tree is larger than a predetermined scale, and applies f (n, K) otherwise. Also good.
  • the string search module 208 determines the node that returned the maximum value for (n, K) in step 610. Restore with function r. The processing of the function r will be described in detail later with reference to the flowchart of FIG.
  • the character string search module 208 passes these character strings to the GUI module 210 in step 612 and displays them on the display 114.
  • m ⁇ K and len (s) ⁇ L.
  • len (s) is the length of the character string s.
  • any character string in S is not a prefix of other character strings. This is to prevent similar character strings such as “to”, “use”, and “when to use” from appearing.
  • an area A (S, C) where S covers C is defined by the following equation.
  • CP (s, C) is the number of s prefixed with s. Therefore, what we want to find is to find S that maximizes the area for a certain C, that is, argmax S A (S, C).
  • f (n, k) is a function that returns the maximum area that can be obtained when the maximum number k is selected from node n, its children, and its younger brother.
  • n null
  • the process proceeds to step 706, where it is determined whether (n, k) has been processed. If (n, k) has been processed, the function f () returns a and ends at step 708 using the value of (n, k) at the previous processing as a.
  • sib (n) is the next sibling node of n.
  • s (n) is an area covered by the node n when the area defined above is used.
  • the calculation result at step 712 is assumed to be * A.
  • chd (n) is the first child node of node n.
  • the calculation result at step 722 is * B.
  • (n, k) is processed in step 726, and function f () returns with a and ends.
  • any function that returns a value greater than or equal to the true maximum value f (n, k) can be applied. For example, use heuristics such as the value when “k siblings including myself have reached the maximum length” and the minimum value among the upper limits when k, k + 1,. Like that. At this time, the fact that the child nodes are arranged in order of frequency indicates that the upper limit of the true value is reached. Moreover, since the calculation amount does not depend on the number of search hits, the efficiency is high.
  • step 806 it is determined whether (n, k) has been processed. If (n, k) has been processed, in step 808, the value of the previous processing for (n, k) is used as a, and function g () returns a and ends.
  • upper [n, k] is the upper limit value of the function f (n, k) described with reference to FIG. 7, and in a two-dimensional array, each element is initialized with a value that is systematically considered as ⁇ . Yes.
  • U (n, k) is an appropriate function such that u (n, k) ⁇ f (n, k), an example of which will be described later with reference to the flowchart of FIG.
  • sib (n) is the next sibling node of n.
  • s (n) is an area covered by the node n as described above.
  • su su
  • u su
  • kc su
  • the result of recursive call to g () is assigned to cs.
  • L is the maximum character string length.
  • Count (m) is the number of occurrences of m.
  • K is the maximum number of selected character strings.
  • Steps 920 and 922 are repeated, and if it is determined in Step 918 that k ′> K, the function u () returns v and ends.
  • the function u (n, k) is a function that satisfies the upper limit of the function f (n, k), that is, the condition u (n, k) ⁇ f (n, k). If this condition is satisfied, the algorithm of the present invention operates correctly, but pruning works more efficiently as u (n, k) -f (n, k) is smaller. That is, the smaller the u value is, the better it is, and the best is when it matches the true value f (n, k).
  • Upper [n, k] stores the upper limit calculated in the past, and as described above, the initial value is ⁇ , that is, upper [n, k] ⁇ f (n, k) always holds. In other words, u is designed using upper.
  • f (n, k) increases as k increases. Therefore, if k ⁇ k ', then f (n, k) ⁇ f (n, k'). Therefore, f (n, k) ⁇ f (n, k ′) ⁇ upper [n, k ′]. That is, upper [n, k ′] satisfies the upper limit condition of f (n, k). Since the value of k is up to K at the maximum, the smallest upper [n, k '] among the values of k' between k and K is adopted as the output of the function u (n, k).
  • the function r takes a node n and an integer k as arguments.
  • step 1004 it is determined whether (n, k) is the maximum at * A.
  • the function f (n, k) in FIG. 7 is used in dynamic programming, this determination is made by comparing the calculation result of step 712 with the calculation result of step 722, and the maximum calculation result of step 712. Means that the value has been calculated.
  • the function g (n, k, m) in FIG. 8 is used as a dynamic programming method with pruning, the calculation result of step 816 and the calculation result of step 830 are compared, and the calculation result of step 816 is used. It means that the maximum value has been calculated.
  • step 1004 When it is determined in step 1004 that (n, k) is the maximum at * A, n is added to the node set in step 1006, and in step 1008, r (sib (n), k-1) r () is called recursively and the function r ends.
  • step 1004 If it is determined in step 1004 that (n, k) is not the maximum at * A, the process proceeds to step 1010 where it is determined whether (n, k) is the maximum at * B.
  • the function f (n, k) in FIG. 7 is used in dynamic programming, this determination is made by comparing the calculation result of step 712 with the calculation result of step 722, and the maximum calculation result of step 722. Means that the value has been calculated.
  • the function g (n, k, m) in FIG. 8 is used as a dynamic programming method with pruning, the calculation result of step 816 and the calculation result of step 830 are compared, and the calculation result of step 830 is used. It means that the maximum value has been calculated.
  • step 1010 If it is determined in step 1010 that (n, k) is the maximum at * B, r (chd (n), c) is recursively called in step 1012. In step 1014, r (sib (n ), kc), r () is called recursively, and the function r ends.
  • c is a value when the maximum value of a is calculated at step 722 after that in the flowchart of FIG. 7, and is initialized at step 818 in the flowchart of FIG. This is the value when the maximum value of a is given in step 830.
  • step 1010 If it is determined in step 1010 that (n, k) is not * B at maximum, the function r is immediately terminated. The node restored in this way is passed to the GUI module 210 in step 612 of FIG.
  • FIG. 12 compares the result of searching for a specific manual document with a query “database” using a conventional typical technique as described in the background art and the result of searching with the technique of the present invention.
  • FIG. 12 compares the result of searching for a specific manual document with a query “database” using a conventional typical technique as described in the background art and the result of searching with the technique of the present invention.
  • FIG. 12 compares the result of searching for a specific manual document with a query “database” using a conventional typical technique as described in the background art and the result of searching with the technique of the present invention.
  • FIG. 12 compares the result of searching for a specific manual document with a query “database” using a conventional typical technique as described in the background art and the result of searching with the technique of the present invention.
  • FIG. 12 compares the result of searching for a specific manual document with a query “database” using a conventional typical technique as described in the background art and the result of searching with the technique of the present invention.
  • FIG. 12 compare
  • the technique of the present invention collects and counts “start database server”, “database server stop”, etc. into “database server”, so the frequent context is easy to understand.
  • the total number of frequently occurring words is counted so that the worst and frequent contexts cannot be found.
  • the experiment succeeded in speeding up to 20 times as much as 20 MB of data compared to dynamic programming without pruning. .
  • creating a frequency-order suffix tree in advance is more efficient than creating a frequency-order context tree after searching with an N-gram index. Therefore, it will be able to withstand a large scale.
  • the present invention can be advantageously applied to expression unification and case search in manuals and business documents.
  • Some text mining programs use an algorithm that displays the top K frequencies, but at that time, the aggregation unit becomes a word unit, and it is not necessarily suitable for the user's interest.
  • the present invention makes it possible to display the top K variable lengths that appropriately express a certain context, and can be expected to be applied to a text mining program.
  • the frequency order prefix tree is constructed.
  • a suffix tree with the document reversed. Doing this can summarize the forward context. For example, it is possible to return “mail server”, “NFS server”, “web server”, etc. in response to the query “server”.
  • the specific processing consists of constructing a frequency-ordered suffix tree with the document turned backwards, the query string turned backwards, the area maximizing context set searched, and the search results reversed. It is to be.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

　検索結果の周辺文脈を、限られた範囲内で適切に集約して表示することを可能ならしめる技法を提供すること。　全文脈文字列C={c1, …, cn}に対して、文字列sがカバーする面積を、sをプリフィックスとするcの数とsの長さの積で定義する。そして、全文脈の集合に対して、最大K個、長さL以下の文字列集合の内、他の文字列の部分文字列を選択しない制約下で、 全体でカバーする面積を最大にするものを求める。本発明によれば、この問題は全文脈をTRIEにした頻度順文脈木上の動的計画法で効率的に解ける。本発明の別の知見によれば、動的計画法で最大面積を求める際に、探索で得られる面積の上限を見積もることで、大幅な探索の枝刈りが可能になり、以って処理を高速化できる。さらにまた、文書の接尾辞木の子ノードを出現頻度順に並べた、頻度順接尾辞木を作ることで、検索と最大面積を求めることの両方を高速化することが可能となる。

Description

文字列生成方法、プログラム及びシステム
　この発明は、主として自然言語テキストの文字列検索技術に関し、特に、検索結果を表示するための技術に関するものである。
　テキストの文字列検索において、ヒット位置の前後の文脈は、有用な情報を与える。例えば、「ボタン」を検索したときに、その後に「クリックする」が続くか「押す」が続くかなどにより、文書の表現の統一を調べたり、特定の英語の固有名詞に定冠詞がつくかどうか確認したり、その他、連語や人名検索などでも、ヒット位置の前後の文脈の情報は重要である。
　そこで、従来技術において、検索単語の前後に出現する文字列をソートして表示する，ＫＷＩＣ（KeyWord In Context）が知られている。
　ＫＷＩＣにおいて、「ボタン」で検索したときの全文脈の例は、次のとおりである。
ボタンが大きくて・・・
ボタンが赤い．・・・
ボタンという表・・・
ボタンに書いてあ・・・
ボタンをクリックしたら・・・
ボタンをクリックして下・・・
ボタンをクリックしよう・・・
ボタンをクリックできな・・・
ボタンをクリックできま・・・
ボタンをクリック．・・・
ボタンを押したら・・
ボタンを押しては・・・
ボタンを押せませ・・・
ボタンを押そうと・・・
　しかし、ＫＷＩＣは、ヒット数が多すぎるときに全体の傾向を一目で把握できないという問題点があった。
　山本真人, 田中久美子, 中川裕志. 検索エンジンに基づく多言語用例指南ツール：KIWI. 言語処理学会全国大会2005、及び特開２００４－１６４１３３号公報によって開示されている技術は、ＫＷＩＣを拡張した手法を提案し、すなわち、表示する文脈の重要度を測ることを可能ならしめる。しかし、この拡張された手法も、複数文脈の最適な組み合わせを選択することは可能ではなく、類似文書が多数表示されるという問題が残る。
特開２００４－１６４１３３号公報
山本真人, 田中久美子, 中川裕志. 検索エンジンに基づく多言語用例指南ツール：KIWI. 言語処理学会全国大会2005
　従って、本発明の目的は、検索結果の周辺文脈を、限られた範囲内で適切に集約して表示することを可能ならしめる技法を提供することにある。
　本発明においては、先ず、全文脈文字列C={c1, …, cn}に対して、文字列sがカバーする面積を、sをプリフィックスとするcの数とsの長さの積で定義する。
　すると、本発明は、全文脈の集合に対して、最大K個、長さL以下の文字列集合の内、他の文字列の部分文字列を選択しない制約下で、 全体でカバーする面積を最大にするものを求める技法である。本発明の知見によれば、この問題は全文脈をTRIEにした頻度順文脈木上の動的計画法で効率的に解ける。
　本発明の別の知見によれば、動的計画法で最大面積を求める際に、探索で得られる面積の上限を見積もることで、大幅な探索の枝刈りが可能になり、以って処理を高速化できる。
　さらにまた、文書の接尾辞木の子ノードを出現頻度順に並べた、頻度順接尾辞木を作ることで、検索と最大面積を求めることの両方を高速化することが可能となる。
　以上の処理は、後方文脈のみではなく前方文脈に対しても自然に適応可能である。また、単語区切りを利用していないため、英語をはじめとした任意の言語データ、さらに時刻付きのイベント列などの解析にも適応できる。
　この発明によれば、検索結果を、限られた領域に出来るだけ沢山の情報を与えるように圧縮して表示する技法が提供される。しかも、動的計画法を使うことで、そのための計算が、高速化される。
本発明を実施するためのハードウェア構成のブロック図である。 本発明を実施するための機能構成のブロック図である。 頻度順接尾辞木を構築する処理のフローチャートを示す図である。 頻度順接尾辞木と、頻度順文脈木の例を示す図である。 頻度順接尾辞木データを検索するための処理を示す図である。 検索と最適文脈の探索全体の処理のフローチャートを示す図である。 動的計画法を使った探索の処理のフローチャートを示す図である。 枝刈り付き動的計画法を使った探索の処理のフローチャートを示す図である。 枝刈り付き動的計画法を使った探索の処理のフローチャートを示す図である。 最大面積ノード集合の復元処理のフローチャートを示す図である。 ＫＷＩＣの非可逆圧縮表示の例を示す図である。 従来の典型的な技法と、本発明の実施例の技法との文脈表示の比較を示す図である。
　以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
　図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標）　４、Ｃｏｒｅ（商標）２　Ｄｕｏ、Ｘｅｏｎ（商標）、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、大量の文書データ及び検索のための頻度順接尾辞木データを格納できるように、例えば、３２０ＧＢ以上の容量をもつものであることが望ましい。
　ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システムが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ（商標）７、Ｗｉｎｄｏｗｓ　ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ　ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。
　ハードディスク・ドライブ１０８にはさらに、検索されるテキスト・データと、テキスト・データから頻度順接尾辞木データを生成する頻度順接尾辞木作成モジュールと、頻度順接尾辞木作成モジュールによって作成された頻度順接尾辞木データと、ユーザが指定したキーワードに基づき、本発明の技法によって文脈文字列を求め、表示を圧縮した態様で文字列を出力する文字列検索モジュールと、文字列検索モジュールによって出力された文字列を、ディスプレイ１１４に表示するためのＧＵＩモジュールが保存されている。これらのデータ及びモジュールについては、図２の機能ブロック図を参照して、後で、より詳しく説明する。
　キーボード１１０及びマウス１１２は、オペレーティング・システムまたは、ハードディスク・ドライブ１０８から主記憶１０６にロードされ、ディスプレイ１１４に表示されたプログラム（図示しない）を起動したり、検索するための文字を打ち込んだりするために使用される。
　ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。
　次に、図２の機能ブロック図を参照して、本発明の処理のための機能要素について説明する。テキスト・ファイル２０２は、ハードディスク・ドライブ１０８に保存された大容量ファイルであり、好適には自然言語テキスト・データを含む。
　頻度順接尾辞木構築モジュール２０４は、テキスト・ファイル２０２を読み取って、頻度順接尾辞木データ２０６として、ハードディスク・ドライブ１０８に保存する。頻度順接尾辞木構築モジュール２０４の処理については、図３のフローチャートを参照して、後でより詳細に説明する。
　文字列検索モジュール２０８は、本発明の要部をなす処理に関する機能を含むものであって、ユーザーが入力したキーワードに基づき、文脈文字列を検索し、さらに、それを基に、圧縮表示文字列を計算して与える。文字列検索モジュール２０８の処理は、図６以下のフローチャートを参照して、後でより詳細に説明する。
　ＧＵＩモジュール２１０は、キーボード１１０及びマウス１１２を用いてユーザーが入力した文字列を文字列検索モジュール２０８に渡し、文字列検索モジュール２０８の文脈文字列の出力を、ディスプレイ１１４に表示する機能をもつ。
　頻度順接尾辞木構築モジュール２０４、文字列検索モジュール２０８、及びＧＵＩモジュール２１０は、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などの既存のプログラム言語で書くことができる。ＧＵＩモジュール２１０は、ユーザーの文字列入力を読み込み、あるいは、文脈文字列の出力を、ディスプレイ１１４に表示するために、好適には、オペレーティング・システムが提供するＡＰＩ関数を呼び出すようにプログラミングされる。
　次に、図３のフローチャートを参照して、頻度順接尾辞木構築モジュール２０４が頻度順接尾辞木データを作成して出力する処理について説明する。この処理は、従来技術の範囲であって、本発明の特徴を構成するものでないことを理解されたい。
　頻度順接尾辞木とは、文書の全接尾辞に対してＴＲＩＥを作ったものである。全接尾辞とは、文書の全ての位置以降の文字列の集合のことである。よって、長さnの文書に対して、n個存在する。但し、ＴＲＩＥの各ノードの子ノードは、葉の総数が多い順にソートする。葉の総数でなく、アルファベット順にソートしたのが、一般の接尾辞木である。サイズは、接尾辞木と同じＯ(n)であり、最大でも2n個のノードである。
　さて、頻度順接尾辞木構築モジュール２０４は、図３のステップ３０２において、テキスト・ファイル２０２を読取って、ステップ３０４で、接尾辞配列構築を行う。この処理は例えば、Ge Nong, Sen Zhang, Wai Hong Chan, "Two Efficient Algorithms for Linear Suffix Array Construction", IEEE Transactions on Computers, 2008に記述されている技法を使う。
　ステップ３０６において、頻度順接尾辞木構築モジュール２０４は、最大接頭辞長の計算を行う。この処理は例えば、Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In proc. of 12th Annual Symposium on Combinatorial Pattern Matching, pp. 181-192. 2001に記述されている技法を使う。
　ステップ３０８において、頻度順接尾辞木構築モジュール２０４は、帰りがけ順で最初のノードをnとおく。接尾辞配列を帰りがけ順に辿る処理も、例えば、Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In proc. of 12th Annual Symposium on Combinatorial Pattern Matching, pp. 181-192. 2001に記述されている。
　ステップ３１０では、頻度順接尾辞木構築モジュール２０４は、nが帰りがけ順で最後のノードであるかどうかを判断し、もしそうなら、処理を終わる。
　そうでなければ、ステップ３１２に進み、頻度順接尾辞木構築モジュール２０４は、nの子ノードを頻度順にソートし、ステップ３１４で、nの子ノードをファイルに出力し、これは、頻度順接尾辞木データ２０６としてハードディスク・ドライブ１０８に保存される。
　ステップ３１６では、nにnの次のノードが代入されて、処理は、ステップ３１０の判断に戻る。
　図４(a)は、このようにして構築された頻度順接尾辞木の一例の木構造を示す図である。図４において、「ボ」「タ」などはそれぞれ、頻度順接尾辞木のノードであり、ノードの上に示された数字は、出現回答を示す。特に図４で、参照番号４０２で示した領域は、「ボタン」に対する頻度順文脈木を示す。頻度順接尾辞木は、所定の検索すべきテキスト・ファイルに対して、一度だけ作成して、ハードディスク・ドライブ１０８に保存しておけば、テキスト・ファイルが変わらない限り作成し直さないで、何度でも検索に使用することができる。
　一方、図４(b)は、頻度順文脈木の例を示す図である。頻度順文脈木は、特定のキーワードで、頻度順接尾辞木を検索することによって、主記憶またはハードディスク・ドライブ１０８上に動的に生成される。後述する、本発明の動的計画法は、このように動的に生成された頻度順文脈木上で実行される。
　頻度順接尾辞木上での検索は、接尾辞木と同様の方法で実行可能である。但し、各子ノードは、アルファベット順に並んでいないので、線形探索が必要である。このとき、子ノードをデータ構造中に連続させておけば、クエリ長に比例した回数のランダムアクセスだけで検索可能である。そして、検索し終わったノードをルートとする部分木が、頻度順文脈木となる。
　次に、図３の処理によって構築された頻度順接尾辞木データ２０６を検索するための処理を、図５に示す。この処理は、好適には、文字列検索モジュール２０８がもつサブルーチンとしての関数の１つであるsearch()として実装される。
　図５のsearchという関数のフローチャートにおいて、sをクエリ文字列とする。ステップ５０２では、nにルートノード(ROOT)が代入される。ステップ５０４では、p = 0と置かれ、ステップ５０６では、p = |s|かどうかが判断される。ここで、|s|とは、sの長さである。もしp = |s|であるなら、関数searchは、nを返して終了する。
　もしp = |s|でないなら、ステップ５０８に進み、そこでn = nullかどうかが判断される。もしn = nullなら、関数searchは、nを返して終了する。
　もしn = nullでないなら、ステップ５１０に進み、そこで、c = get_char(n)が実行される。get_char(n)は、ノードnに対する文字を返す。
　ステップ５１２では、s[p] = cかどうかが判断される。ここで、s[p]とは、文字列sのp番目の文字である。もしs[p] = cであるなら、ステップ５１４で、p = p + 1によりpが増分され、ステップ５１６で、n = chd(n)により、nの最初の子ノードであるchd(n)がnに代入される。そうして処理は、ステップ５０６に戻る。
　ステップ５１２で、s[p] = cでないなら、ステップ５１８で、n = sib(n)により、nの次の兄弟ノードであるsib(n)がnに代入される。そうして処理は、ステップ５０８に戻る。このsearch(s)の実行後、戻り値のnをルートとする頻度順接尾辞木の部分木が、図４(b)に例示するような頻度順文脈木として、主記憶１０６または、ハードディスク・ドライブ１０８上に構築される。
　図６は、文字列検索モジュール２０８が実行する、検索と最適文脈の探索全体の処理のフローチャートを示す図である。
　文字列検索モジュール２０８は、ステップ６０２で、図５のフローチャートで示す関数search(s)を呼び出して、その結果をnに返す。ここで、sはクエリ文字列であり、ＧＵＩモジュール２１０を介してユーザが入力したものである。
　文字列検索モジュール２０８は、ステップ６０４でnがnullであるかどうかを判断し、もしそうなら、ステップ６０６で、文字列が見つからない旨を出力して処理を終わる。この処理は典型的には、文字列検索モジュール２０８がＧＵＩモジュール２１０にメッセージを渡して、ディスプレイ１１４に表示させることによって行われる。
　文字列検索モジュール２０８がステップ６０４でnがnullでないと判断すると、ステップ６０８で、文字列検索モジュール２０８は、ステップ６０８で、動的計画法を使った探索の処理を行う。この実施例では、文字列検索モジュール２０８は、動的計画法として、図７のフローチャートに基づき後で説明する動的計画法の関数f(n,K)または、図８及び図９のフローチャートに基づき後で説明する枝刈り付き動的計画法の関数g(n,K,0)をどちらか一方、または両方をサブルーチンとしてもつようにしてよい。なお、ここで、Kは最大文字列選択数である。このステップでは、ステップ６０２で、search(s)が構築した頻度順文脈木上で、動的計画法が適用される。
　g(n,K,0)は、枝刈り付き処理により、f(n,K)よりも大規模な頻度順文脈木に対する探索に適合する。従って、文字列検索モジュール２０８は、頻度順文脈木が所定の規模よりも大きい場合にg(n,K,0)を適用し、そうでない場合にf(n,K)を適用するようにしてもよい。
　ステップ６０８で、f(n,K)またはg(n,K,0)の一方を実行した後、文字列検索モジュール２０８は、ステップ６１０で、(n,K)に関して最大値を返したノードを関数rで復元する。関数rの処理は、図１０のフローチャートを参照して、後で詳細に説明する。
　こうして、各ノードに対応する文字列が得られると、文字列検索モジュール２０８は、それらの文字列を、ステップ６１２でＧＵＩモジュール２１０に渡して、ディスプレイ１１４に表示させる。
　次に、本発明の動的計画法の処理に関する説明に移るが、その前に、本発明における面積、及び面積最大化の定義について説明する。
　先ず、最大で縦K行、横L文字の表示域に文脈の要約を表示するとする。そこで、n件の文脈集合C = {c1,...,cn}と、m件の文字列集合S = {s1,...,sm}とする。但し、m ≦ K, len(s) ≦ Lとする。ここで、len(s)は、文字列sの長さである。
　また、S中の任意の文字列は、他の文字列のプリフィックスではないとする。これは、「を」と「を使う」と「を使うとき」のような類似文字列がでるのを防ぐためである。
　そこで、SがCをカバーする面積A(S,C)を、下記の式で定義する。
Figure JPOXMLDOC01-appb-M000001


　ここで、CP(s,C)は、C中でsをプリフィックスとするものの個数である。そこで、求めたいのは、あるCに対して、面積を最大にするS、つまりargmax S A(S,C)を求めることである。
　しかし一般的に、Sの候補は膨大なので、本発明では、動的計画法を適用して計算合理的にSを求めるようにする。
　以上の定義の下で、図７のフローチャートを参照して、f(n,k)の処理を説明する。f(n,k)とは、ノードn、その子、その弟のうち、最大k個を選択したとき得られる最大面積を返す関数である。
　ステップ７０２では、変数aについて、a = 0と置かれる。ステップ７０４では、n = nullかどうかが判断される。もしn = nullなら、関数f()は、aを返して終了する。
　もしn = nullでないなら、ステップ７０６に進み、(n,k)は処理済かどうか判断される。もし(n,k)が処理済なら、ステップ７０８で、aとして(n,k)についての前回処理時の値を用いて、関数f()は、aを返して終了する。
　(n,k)が処理済でないなら、ステップ７１０で、ss = f(sib(n),k-1)によって、f()が再帰呼び出しされ、それの戻り値がssに代入される。ここで、sib(n)は、nの次の兄弟ノードである。
　ステップ７１２では、a = s(n) + ssによって、計算された値がaに代入される。ここで、s(n)とは、上記で定義した面積を用いた場合の、ノードnがカバーする面積である。ステップ７１２での計算結果を、*Aとする。
　次に、ステップ７１４ではc = 0と置き、ステップ７１６からステップ７２４までは、cを1つずつ増分しつつ、ステップ７１６でc > kと判断されるまで、処理を繰り返す。
　すなわち、ステップ７１８では、cs = f(chd(n),c)によって、計算された値がcsに代入される。ここで、chd(n)とは、ノードnの最初の子ノードである。
　ステップ７２０では、ss = f(sib(n),k-c)によって、計算された値がssに代入される。
　ステップ７２２では、a = max(a, cs + ss)によって、計算された値がaに代入される。ステップ７２２での計算結果を、*Bとする。
　ステップ７２４では、c = c + 1によってcが増分されて、ステップ７１６での判断に戻る。ループが廻ってステップ７１６でc > kとなると、ステップ７２６で(n,k)を処理済にして、関数f()は、aを返して終了する。
　次に、図８及び図９のフローチャートを参照して、枝刈り付き動的計画法の関数g(n,k,m)の処理について説明する。図７で説明した関数fは最大値を取る組み合わせを探索する関数であったため、関数gは、探索途中での最大値を渡し、残りの処理を続けてもこれに達しないことがわかれば処理を中断してもよいという方針で処理する。そのため、真の最大値の上限を見積もり、これが探索途中での最大値を超えなければ処理を中断する。すなわち、効率よく枝刈りするためには、真の最大値をなるべく先に探索し、またなるべく真の最大値に近い上限値を、効率よく計算する必要がある。
　このとき、計算する順番は、経験的に、c(子ノードへの割当て)が少ない場合が最適値をとることが多いため、cを昇順に探索するのが望ましい。
　また、上限値u(n, k)は真の最大値f(n, k)以上の値を返す任意の関数を適用できる。例えば、「自分を含めたk個の兄弟が最大長までに達した」場合の値と、k, k+1,・・・のときの上限値のうちの最小値、というようなヒューリスティックスを使うようにする。このとき、子ノードが頻度順に並んでいる性質によって、真の値の上限になっていることが示される。また、計算量が検索ヒット数に依存しないので、効率がよい。
　このような前提で、枝刈り付き動的計画法の関数g(n,k,m)の処理が構成されている。
　ステップ８０２では、変数aについて、a = 0と置かれる。ステップ８０４では、n = nullかどうかが判断される。もしn = nullなら、関数g()は、aを返して終了する。
　図８において、もしn = nullでないなら、ステップ８０６に進み、(n,k)は処理済かどうか判断される。もし(n,k)が処理済なら、ステップ８０８で、aとして(n,k)についての前回処理時の値を用いることにし、関数g()は、aを返して終了する。
　さて、(n,k)が処理済でないなら、ステップ８１２で、u(n,k) <= mかどうか判断され、もしそうなら、ステップ８１０で、upper[n,k] = u(n,k)として、関数g()は、aを返して終了する。ここでupper[n,k]は、図７に関して説明した関数f(n,k)の上限値であり、２次元配列で、各要素は、システム的に∞とみなされる値で初期化されている。また、u(n,k)は、u(n,k) ≧ f(n,k)なる適当な関数であり、その一例を後で、図９のフローチャートを参照して説明する。ステップ８１２で、u(n,k) <= mでないと判断されると、ステップ８１４で、ss = g(sib(n),k-1,m-s(n))によって、g()が再帰呼び出しされ、それの戻り値がssに代入される。ここで、sib(n)は、nの次の兄弟ノードである。また、s(n)は、上述のように、ノードnがカバーする面積である。
　ステップ８１６では、a = max(m,s(n) + ss)によって、値がaに代入される。この値は、*Aとして、一旦保存される。
　次のステップ８１８では、c = 0とセットされ、c > kとなるまで、ステップ８２０～８３２が繰り返される。
　すなわち、ステップ８２２では、su = u(sib(n),k-c)によって、計算された値がsuに代入され、ステップ８２４では、cs = g(chd(n),c,a-su)により、g()を再帰呼び出しして計算した結果がcsに代入される。
　ステップ８２６では、cs <= a - suかどうか判断し、そうでなければ、ステップ８２８に進み、ss = g(sib(b),k-c,a-cs)計算された値がssに代入され、ステップ８３０で、a = max(a,cs + ss)によって、計算された値がaに代入される。この値は、*Bとして、一旦保存される。次にステップ８３２で、c = c + 1でcが増分され、ステップ８２０に戻る。
　ステップ８２６では、cs <= a - suであると判断されると、直接ステップ８３２に行って、c = c + 1でcが増分され、ステップ８２０に戻る。
　ステップ８２０で、c > kであると判断されると、ステップ８３４で、a <= mかどうか判断され、もしそうなら、ステップ８３６で、upper[n,k] = mとして、関数g()は、aを返して終了する。
　ステップ８３４で、a <= mであると判断されるなら、ステップ８３８で(n,k)を評価済みにし、ステップ８４０で、upper[n,k] = aとして、関数g()は、aを返して終了する。
　次に、図９のフローチャートを参照して、関数g()から呼び出される関数u(n,k)の処理を説明する。まず、ステップ９０２でv = 0、ステップ９０４でm = n、ステップ９０６でi = 1、と変数がセットされる。
　ステップ９０８では、i > kかどうか判断され、そうでないなら、ステップ９１０で、 v = v + count(m) * Lによって、計算された値がvに代入される。ここでLとは、最大文字列長である。また、count(m)とはmの出現回数である。次に、ステップ９１２では、m = sib(m)によって、mが、その次の兄弟ノードに置き換えられる。そして、ステップ９１４、i = i + 1で増分されて、ステップ９０８に戻る。
　ステップ９０８で、i > kであると判断されると、ステップ９１６に進んで、そこで、k' = kと代入し、次に、ステップ９１８では、k' > Kであるかどうかが判断される。ここでKとは、最大文字列選択数である。
　ステップ９１８で、k' > Kでないと判断されると、ステップ９２０で、v = min(v,upper[n,k'])によって、計算された値がvに代入される。そして次に、k' = k' + 1でk'が増分されて、ステップ９１８に戻る。
　こうして、ステップ９２０とステップ９２２が繰り返されて、ステップ９１８で、k' > Kであると判断されると、関数u()は、vを返して終了する。
　ところで、関数u(n,k)は、関数f(n,k)の上限、つまり必ずu(n,k) ≧ f(n,k)の条件が成り立つような関数である。この条件さえ満たせば、本発明のアルゴリズムは正しく動くが、u(n,k)-f(n,k)が小さいほど枝刈りが効率的に働く。つまり、uの値は条件を満たす中で小さければ小さいほどよく、真の値f(n,k)と一致しているときが最良である。
　upper[n,k]は過去に計算した上限を保存したもので、上述したように初期値は∞、つまり、upper[n,k]≧f(n,k)が必ず成り立つ。すなわち、upperを使って、uを設計している。
　さて、kは選択する行数なので、kが大きいほどf(n,k)は大きな値になる。従って，k < k'ならf(n,k) < f(n,k')である。そのため、f(n,k) < f(n,k') ≦ upper[n,k']となる。つまり，upper[n,k']はf(n,k)の上限の条件を満たす。kの値は最大でもKまでなので，k以上K以下のk'の値の中で一番小さなupper[n,k']を関数u(n,k)の出力として採用している。
　それならば、upper[n,k]が一番小さくなるのではと思われるかもしれないが、計算順序の関係で、先に大きなkの値に対して上限を計算することがありえる。この計算結果が再利用されている。
　次に、図１０のフローチャートを参照して、図６のフローチャートにおける(n,K)に関して最大値を返したノードを関数rで復元、とある関数rの処理を説明する。関数rは、ノードnと、整数kを引数とする。
　ステップ１００２では、n = nullかどうかが判断される。もしそうなら、関数rは、直ちに終了する。
　ステップ１００４では、(n,k)が*Aで最大かどうか判断される。この判断は、図７の関数f(n,k)が動的計画法で使われた場合は、ステップ７１２の計算結果と、ステップ７２２の計算結果を比較して、ステップ７１２の計算結果で最大値を計算したことを意味する。図８の関数g(n,k,m)が枝刈り付き動的計画法として使われた場合は、ステップ８１６の計算結果と、ステップ８３０の計算結果を比較して、ステップ８１６の計算結果で最大値を計算したことを意味する。
　ステップ１００４で、(n,k)が*Aで最大であると判断されると、ステップ１００６でnがノード集合に追加され、ステップ１００８では、r(sib(n),k-1)により、r()が再帰的に呼び出されて、関数rは終了する。
　ステップ１００４で、(n,k)が*Aで最大でないと判断されると、ステップ１０１０に進み、そこで、(n,k)が*Bで最大であるかどうかが判断される。この判断は、図７の関数f(n,k)が動的計画法で使われた場合は、ステップ７１２の計算結果と、ステップ７２２の計算結果を比較して、ステップ７２２の計算結果で最大値を計算したことを意味する。図８の関数g(n,k,m)が枝刈り付き動的計画法として使われた場合は、ステップ８１６の計算結果と、ステップ８３０の計算結果を比較して、ステップ８３０の計算結果で最大値を計算したことを意味する。
　ステップ１０１０で、(n,k)が*Bで最大であると判断されると、ステップ１０１２でr(chd(n),c)が再帰的に呼び出され、ステップ１０１４では、r(sib(n),k-c)により、r()が再帰的に呼び出されて、関数rは終了する。ここでcとは、図７のフローチャートでは、ステップ７１４で初期化され、その後ステップ７２２でaの最大値を計算したときの値であり、図８のフローチャートでは、ステップ８１８で初期化され、その後ステップ８３０でaの最大値を与えたときの値である。
　ステップ１０１０で、(n,k)が*Bで最大でないと判断されると、関数rは、直ちに終了する。このようにして復元されたノードが、図６のステップ６１２でＧＵＩモジュール２１０に渡されて、ディスプレイ１１４に表示される。
　図１１は、背景技術のところで示したＫＷＩＣを、本発明の技法に従い、K = 3という極端に狭い領域に圧縮して表示する例である。この例では、K = 3でも、「ボタンをクリックし・・・」「ボタンをクリックでき・・・」「ボタンを押・・・」で、示されているＫＷＩＣのよい要約になっていることが見て取れる。
　図１２は、ある特定のマニュアル文書に対して、「データベース」というクエリで、背景技術で記述したような従来の典型的に技法でサーチした結果と、本発明の技法でサーチした結果を比較する図である。特に、長さL（=10）で切って、出現頻度の多いK（=10）件を表示した例で比較している。「22:」などと表示されているのは、出現頻度である。
　本発明の技法は、「データベース・サーバーを起動」「データベース・サーバーが停止する」などを「データベース・サーバー」に集約してカウントするので、頻出文脈が分かりやすい。一方、従来技術では、頻出単語の出現総数が少なく数えられて、最悪、頻出文脈が発見できないということもある。
　また、特に、枝刈り付き動的計画法を使った実施例の場合、実験では、20MB程度のデータに対して、枝刈りなしの動的計画法に比べ、最大20倍の高速化に成功した。
　さらに、事前に頻度順接尾辞木を作ることで、Nグラムインデックスなどで検索してから頻度順文脈木を作るよりも効率的である。そのため、大規模化に耐えられるようになる。
　本発明は、マニュアルやビジネス文書における、表現統一や事例検索にも、有利に適用することができる。
　テキストマイニング・プログラムで、頻度トップのK個を表示するアルゴリズムを用いているものがあるが、その際、集計単位は単語単位となり必ずしもユーザの興味と合わないことが問題となっている。本発明は、ある文脈を適切に表現する可変長のトップK個を表示することが可能になり、テキストマイニング・プログラムでの応用も期待できる。
　尚、上記実施例では、頻度順接頭辞木を構築したが、文書を逆向きにして、接尾辞木を構築することも可能である。これを行うと前方文脈を纏め上げることができる。例えば「サーバー」というクエリに対して「メールサーバー」「NFSサーバー」「ウェブサーバー」などを返すことが可能となる。
　その具体的な処理は、文書を逆向きにして頻度順接尾辞木を構築することと、クエリ文字列を逆向きにし、面積最大化の文脈集合を探索し、探索結果を逆向きにして表示することである。
　以上、本発明の実施例を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを理解されたい、また、日本語以外の任意の言語に適用可能であることも、この分野の当業者なら、理解するであろう。
１０２　システム・パス
１０４　ＣＰＵ
１０６　主記憶
１０８　ハードディスク・ドライブ
１１０　キーボード
１１２　マウス
１１４　ディスプレイ
２０２　テキスト・ファイル
２０４　頻度順接尾辞木構築モジュール
２０６　頻度順接尾辞木データ
２０８　文字列検索モジュール
２１０　ＧＵＩモジュール

Claims (12)

  1. 　コンピュータの処理によって、表示すべき文字列を生成する方法であって、
    　キーワードに従い、文書に対する検索によって、前記キーワードを含む、n個(nは、1以上の整数)の要素cからなる文脈文字列Cを得るステップと、
    　文字列sが文脈文字列Cをカバーする面積を、sをプリフィックスとする、Cの要素であるcの数とsの長さの積で定義したとき、表示される文字列の最大数がK個(Kは、1以上の整数)以下であるとの条件の下で、前記面積の和を最大にするsの集合を求めるステップとを有する、
    　文字列生成方法。
  2. 　前記sの集合を求めるステップは、動的計画法に基づく、請求項１に記載の方法。
  3. 　検索すべき文書集合が、頻度順接尾辞木データとして構成され、前記動的計画法は、前記頻度順接尾辞木に対する検索結果から得られた頻度順文脈木データ上の動的計画法である、請求項２に記載の方法。
  4. 　前記動的計画法は、頻度順文脈木データ上の探索途中の最大値を渡し、上限がそこに達しなければあきらめる、枝刈り処理を行う、請求項３に記載の方法。
  5. 　コンピュータの処理によって、表示すべき文字列を生成するプログラムであって、
    　前記コンピュータをして、
    　キーワードに従い、文書に対する検索によって、前記キーワードを含む、n個(nは、1以上の整数)の要素cからなる文脈文字列Cを得るステップと、
    　文字列sが文脈文字列Cをカバーする面積を、sをプリフィックスとする、Cの要素であるcの数とsの長さの積で定義したとき、表示される文字列の最大数がK個(Kは、1以上の整数)以下であるとの条件の下で、前記面積の和を最大にするsの集合を求めるステップを実行させる、
    　文字列生成プログラム。
  6. 　前記sの集合を求めるステップは、動的計画法に基づく、請求項５に記載のプログラム。
  7. 　検索すべき文書集合が、頻度順接尾辞木データとして構成され、前記動的計画法は、前記頻度順接尾辞木に対する検索結果から得られた頻度順文脈木データ上の動的計画法である、請求項６に記載のプログラム。
  8. 　前記動的計画法は、頻度順文脈木データ上の探索途中の最大値を渡し、上限がそこに達しなければあきらめる、枝刈り処理を行う、請求項７に記載のプログラム。
  9. 　コンピュータの処理によって、表示すべき文字列を生成するシステムであって、
    　キーワードに従い、文書に対する検索によって、前記キーワードを含む、n個(nは、1以上の整数)の要素cからなる文脈文字列Cを得る手段と、
    　文字列sが文脈文字列Cをカバーする面積を、sをプリフィックスとする、Cの要素であるcの数とsの長さの積で定義したとき、表示される文字列の最大数がK個(Kは、1以上の整数)以下であるとの条件の下で、前記面積の和を最大にするsの集合を求める手段を有する、
    　文字列生成システム。
  10. 　前記sの集合を求める手段は、動的計画法に基づく、請求項９に記載のシステム。
  11. 　検索すべき文書集合が、頻度順接尾辞木データとして構成され、前記動的計画法は、前記頻度順接尾辞木に対する検索結果から得られた頻度順文脈木データ上の動的計画法である、請求項１０に記載のシステム。
  12. 　前記動的計画法は、頻度順文脈木データ上の探索途中の最大値を渡し、上限がそこに達しなければあきらめる、枝刈り処理を行う、請求項１１に記載のシステム。
PCT/JP2011/065802 2010-08-06 2011-07-11 文字列生成方法、プログラム及びシステム Ceased WO2012017782A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
KR1020137004451A KR101498396B1 (ko) 2010-08-06 2011-07-11 문자열 생성 방법, 프로그램 및 시스템
CA2804514A CA2804514A1 (en) 2010-08-06 2011-07-11 Character string generation method, program and system
CN201180037655.0A CN103052951B (zh) 2010-08-06 2011-07-11 字符串生成方法和系统
EP11814412.0A EP2602724A4 (en) 2010-08-06 2011-07-11 METHOD FOR GENERATING A STRUCTURE AND A PROGRAM AND SYSTEM THEREFOR
JP2012527648A JP5337308B2 (ja) 2010-08-06 2011-07-11 文字列生成方法、プログラム及びシステム

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2010-177996 2010-08-06
JP2010177996 2010-08-06

Publications (1)

Publication Number Publication Date
WO2012017782A1 true WO2012017782A1 (ja) 2012-02-09

Family

ID=45556879

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2011/065802 Ceased WO2012017782A1 (ja) 2010-08-06 2011-07-11 文字列生成方法、プログラム及びシステム

Country Status (7)

Country Link
US (1) US8954402B2 (ja)
EP (1) EP2602724A4 (ja)
JP (1) JP5337308B2 (ja)
KR (1) KR101498396B1 (ja)
CN (1) CN103052951B (ja)
CA (1) CA2804514A1 (ja)
WO (1) WO2012017782A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114722815A (zh) * 2022-04-18 2022-07-08 上海喜马拉雅科技有限公司 词缀确定方法、装置、电子设备及存储介质

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20150161266A1 (en) * 2012-06-28 2015-06-11 Google Inc. Systems and methods for more efficient source code searching
CN103390044B (zh) * 2013-07-19 2017-02-08 百度在线网络技术（北京）有限公司 一种连锁类兴趣点数据识别方法及装置
US9824160B2 (en) * 2014-06-02 2017-11-21 SynerScope B.V. Computer implemented method and device for accessing a data set
CN108073679B (zh) * 2017-11-10 2021-09-28 中国科学院信息工程研究所 一种串匹配场景下随机模式串集合生成方法、设备和可读存储介质
CN109189828A (zh) * 2018-08-16 2019-01-11 国云科技股份有限公司 一种基于复杂网络的业务部门间数据价值评估的方法
US11106642B2 (en) * 2018-12-26 2021-08-31 Io-Tahoe LLC. Cataloging database metadata using a probabilistic signature matching process
EP4040304A4 (en) * 2019-09-30 2022-09-14 Fujitsu Limited SAMPLE SEARCH PROGRAM, SAMPLE SEARCH DEVICE AND SAMPLE SEARCH PROCEDURE
CN112966505B (zh) * 2021-01-21 2021-10-15 哈尔滨工业大学 一种从文本语料中提取持续性热点短语的方法、装置及存储介质
US12061637B2 (en) * 2022-09-11 2024-08-13 Microsoft Technology Licensing, Llc Heuristic identification of shared substrings between text documents

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004164133A (ja) 2002-11-11 2004-06-10 Hiroshi Nakagawa 抽出装置、用例検索装置、ならびに、プログラム
JP2005222263A (ja) * 2004-02-05 2005-08-18 Hitachi Ltd 用語閲覧型情報アクセス支援システム
JP2007213157A (ja) * 2006-02-07 2007-08-23 Just Syst Corp 用例文検索装置および用例文検索方法

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7124199B2 (en) * 2001-12-28 2006-10-17 Autodesk, Inc. Turn restriction handling enhancement
US7269548B2 (en) * 2002-07-03 2007-09-11 Research In Motion Ltd System and method of creating and using compact linguistic data
US20060106769A1 (en) * 2004-11-12 2006-05-18 Gibbs Kevin A Method and system for autocompletion for languages having ideographs and phonetic characters
US7461056B2 (en) * 2005-02-09 2008-12-02 Microsoft Corporation Text mining apparatus and associated methods
GB2452760A (en) * 2007-09-14 2009-03-18 Data Connection Ltd Storing and searching data in a database tree structure for use in data packet routing applications.
JP5434408B2 (ja) * 2009-05-15 2014-03-05 富士通株式会社 携帯型情報処理装置、コンテンツ再生方法およびコンテンツ再生プログラム
US8996550B2 (en) * 2009-06-03 2015-03-31 Google Inc. Autocompletion for partially entered query

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004164133A (ja) 2002-11-11 2004-06-10 Hiroshi Nakagawa 抽出装置、用例検索装置、ならびに、プログラム
JP2005222263A (ja) * 2004-02-05 2005-08-18 Hitachi Ltd 用語閲覧型情報アクセス支援システム
JP2007213157A (ja) * 2006-02-07 2007-08-23 Just Syst Corp 用例文検索装置および用例文検索方法

Non-Patent Citations (8)

* Cited by examiner, † Cited by third party
Title
GE NONG; SEN ZHANG; WAI HONG CHAN: "Two Efficient Algorithms for Linear Suffix Array construction", IEEE TRANSACTIONS ON COMPUTERS, 2008
HIROSHI NAKAGAWA: "Kiwi: Tagengo Yorei Kensaku System", JOURNAL OF JAPAN ASSOCIATION FOR EAST ASIAN TEXT PROCESSING, vol. 6, 1 October 2005 (2005-10-01), pages 116 - 123, XP055132296 *
KUMIKO TANAKA ET AL.: "Multi-lingual Dynamic KWIC based on Internet Search", IPSJ SIG NOTES, vol. 2002, no. 104, 13 November 2002 (2002-11-13), pages 115 - 121, XP008170985 *
MASATO YAMAMOTO; KUMIKO TANAKA; HIROSHI NAKAGAWA: "KIWI: A Multilingual Usage Consultation Tool based on Internet Searching", ANNUAL MEETING OF THE ASSOCIATION FOR NATURAL LANGUAGE PROCESSING, 2005
MINORU YOSHIDA ET AL.: "Mining Numbers in Text Using Suffix Arrays and Clustering Based on Dirichlet Process Mixture Models", IPSJ SIG NOTES, HEISEI 21 NENDO (4), vol. 6119, 15 December 2009 (2009-12-15), pages 230 - 237, XP019144442 *
See also references of EP2602724A4 *
TORU KASAI; GUNHO LEE; HIROKI ARIMURA; SETSUO ARIKAWA; KUNSOO PARK: "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications", PROCEEDINGS OF 12TH ANNUAL SYMPOSIUM ON COMBINATORIAL PATTERN MATCHING, 2001, pages 181 - 192
YUYA UMINO ET AL.: "Mojiretsu Kensaku Kekka ni Taisuru Compact na Bunmyaku Shugo no Kosoku Chushutsu", NLP WAKATE NO KAI DAI 5 KAI SYMPOSIUM, September 2010 (2010-09-01), pages 1 - 16, XP055135006, Retrieved from the Internet <URL:http://yans.anlp.jp/symposium/2010/paper/Yans2010 No7.pdf> *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114722815A (zh) * 2022-04-18 2022-07-08 上海喜马拉雅科技有限公司 词缀确定方法、装置、电子设备及存储介质

Also Published As

Publication number Publication date
EP2602724A4 (en) 2016-08-17
JPWO2012017782A1 (ja) 2013-10-03
CN103052951A (zh) 2013-04-17
CN103052951B (zh) 2016-01-06
KR20130108537A (ko) 2013-10-04
EP2602724A1 (en) 2013-06-12
CA2804514A1 (en) 2012-02-09
JP5337308B2 (ja) 2013-11-06
US8954402B2 (en) 2015-02-10
US20120036149A1 (en) 2012-02-09
KR101498396B1 (ko) 2015-03-03

Similar Documents

Publication Publication Date Title
JP5337308B2 (ja) 文字列生成方法、プログラム及びシステム
Ahonen et al. Applying data mining techniques for descriptive phrase extraction in digital document collections
US6882747B2 (en) Text mining method and apparatus for extracting features of documents
Chung Four proofs for the Cheeger inequality and graph partition algorithms
US20110078152A1 (en) Method and system for processing text
Gawrychowski Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
JP2002169834A (ja) 文書のベクトル解析を行うコンピュータおよび方法
Michailidis et al. On-line string matching algorithms: Survey and experimental results
US12197479B2 (en) Semantic matching and retrieval method and apparatus and non-transitory computer-readable medium
WO2000033215A1 (en) Term-length term-frequency method for measuring document similarity and classifying text
Heres Source code plagiarism detection using machine learning
Bille et al. Compressed subsequence matching and packed tree coloring
Mohammadi et al. Variational characterization of real eigenvalues in linear viscoelastic oscillators
JP2008282328A (ja) テキスト分類装置、テキスト分類方法及びテキスト分類プログラム並びにそのプログラムを記録した記録媒体
Watson et al. A Boyer–Moore-style algorithm for regular expression pattern matching
JP4349480B2 (ja) 重要句・文抽出方法及び装置
Jasila et al. Ontology Based Document Clustering-An Efficient Hybrid Approach
CN113297854A (zh) 文本到知识图谱实体的映射方法、装置、设备及存储介质
Jain et al. A comparative performance analysis of approximate string matching
Fadlil et al. Similarity Identification Based on Word Trigrams Using Exact String Matching Algorithms
JP5416680B2 (ja) 文書分割検索装置及び方法及びプログラム
Chung Four Cheeger-type inequalities for graph partitioning algorithms
Xylogiannopoulos et al. Sequential all frequent itemsets detection: A method to detect all frequent sequential itemsets using LERP-Reduced Suffix Array data structure and ARPaD algorithm
JP4592556B2 (ja) 文書検索装置、文書検索方法および文書検索プログラム
JP5362649B2 (ja) 文字列ベクトル変換装置、文字列ベクトル変換方法、プログラム、及びプログラムを格納したコンピュータ読み取り可能な記録媒体

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201180037655.0

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 11814412

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2804514

Country of ref document: CA

WWE Wipo information: entry into national phase

Ref document number: 2012527648

Country of ref document: JP

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 20137004451

Country of ref document: KR

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 2011814412

Country of ref document: EP