JP3628565B2 - Dictionary search method, device, and recording medium recording dictionary search program - Google Patents

Description

【００１９】
「くるまえび」には「くるま」へのポインタが記載されており、「くるま」には「くる」へのポインタが記載されており、「でし」と「でんたく」には「で」へのポインタが記載されている。
【００２０】
「で」は助詞の「で」と助動詞「だ」の連用形の２種類があるが、このような同形語の場合、辞書には１つのエントリのみを設ける。辞書検索終了後に複数の語に展開するのが容易なことは明らかである。
【００２１】
まず、ステップ２０１で「くるまでまつ」が入力され、ステップ２０２で「くるまでまつ」が検索される。辞書順の比較で（「くるまでまつ」＜「で」）で、かつ（「くるまえび」＜「くるまでまつ」）であるので、「３：くるまえび」を得る。次に、ステップ２０３で「くるまでまつ」と「くるまえび」が比較され、「くるまえび」は「くるまでまつ」の先頭部分と完全一致しないので、ステップ２０４でポインタをたどり、「２：くるま」を得る。ステップ２０５で「くるまでまつ」と「くるま」を比較し、「くるま」は「くるまでまつ」の先頭部分と完全一致するので、ステップ２０８で「２：くるま」を検索語リスト１０３に格納する。ステップ２０９で「２：くるま」のポインタをたどり、「１：くる」を得、ステップ２１０で「１：くる」を検索語リスト１０３に格納する。「１：くる」のポインタには記載がないので、ステップ２１１に進み、検索語リスト１０３の「２：くるま」と「１：くる」を出力する。
【００２２】
図３は本発明の第２の実施形態の辞書検索装置の構成図である。
【００２３】
本実施形態の辞書検索装置は、文を入力するための入力装置３０１と、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタが記載されている辞書３０２と、検索語リスト３０３と、入力文の先頭部分と完全一致する語を辞書３０２から検索し、検索した語を検索語リスト３０３に記憶し、以降入力文の先頭の１文字ずらした各文について同様の処理を行う処理装置３０４と、検索語リスト３０３の内容を出力（表示または印字）する出力装置３０５で構成されている。
【００２４】
図４は処理装置３０４の処理内容を示すフローチャートである。ステップ４０１〜４１０，４１３の処理は図２中のステップ２０１〜２１０，２１１と同じである。本実施形態では、ステップ４１０の後、ステップ４１１で、入力文を１文字ずらし、すなわち先頭の１文字を削除した文についてステップ４０２以降の処理を、入力文が無くなるまで繰り返す。
【００２５】
次に、本実施形態２の辞書検索装置を同様に日本語の検索に用いた場合で、「くるまでまつ」を検索した場合を例にとって本辞書検索装置の動作を説明する。辞書３０２として第１の実施形態と同じ辞書１０２を用いる。
【００２６】
まず、「くるまでまつ」が入力され、ステップ４０２で「くるまでまつ」が検索される。以下、第１の実施形態と同様の処理がされて「１：くる」と「２：くるま」の２語が得られ、この２語が検索語リスト３０３に格納される。ステップ４１１で入力文「くるまでまつ」を１文字ずらし「るまでまつ」で辞書３０２を検索する。「るまでまつ」を辞書検索にかけるが、語の候補は得られない。次に、「までまつ」を辞書検索にかけ、「３：まで」の１語が得られ、検索語リスト３０３に格納される。次に、「でまつ」を辞書検索にかける。この場合、ステップ４０２の検索では「５：でし」が得られるが、入力文の先頭部分とは完全一致しないのでステップ４０４で短い語をたどり、「４：で」を得、この語は先頭部分と完全一致するので「４：で」の１語が出力される。したがって、検索語リスト３０３には「４：で」の１語が格納される。次に、「まつ」を辞書検索にかけ、「７：まつ」の１語が得られ、検索語リスト３０３に格納される。次に、「つ」を辞書検索にかけるが、語の候補は得られない。
【００２７】
結果として、検索語リスト３０３には、表２の語が得られ、「くるまでまつ」に含まれる可能性のある語がすべて得られている。
【００２８】
【表２】

【００２９】
図５は本発明の第３の実施形態の辞書検索装置の構成図である。
【００３０】
本実施形態の辞書検索装置は、文を入力するための入力装置５０１と、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の２文字目以降を先頭に持つ語である可能後続語（ＦＬ）が記載されている辞書５０２と、可能後続語リスト５０３と、検索語リスト５０４と、入力文の先頭部分と完全一致する語を辞書５０２から検索し、検索した語を検索語リスト５０４に記憶し、また完全一致した語の、辞書５０２に記載されている可能後続語を可能後続語リスト５０３に記憶する処理装置５０５と、検索語リスト５０４と可能後続語リスト５０３の内容を出力（表示または印字）する出力装置５０６で構成されている。
【００３１】
図６は処理装置５０５の処理内容を示すフローチャートである。ステップ６０１〜６０７，６０９，６１０の処理は図２中のステップ２０１〜２０７，２０９，２１０と同じである。本実施形態では、ステップ６０３で完全一致するならば、ステップ６０８で、辞書５０２に記載されている、完全一致する語の可能後続語を可能後続語リスト５０３に格納する。最後のステップ６１１では、可能後続語リスト５０３と検索語リスト５０４に格納された語を全て出力する。
【００３２】
なお、ステップ６０１と６０２は順序が入れ替ってもよく、またステップ６０８はステップ６１０の後でもよい。
【００３３】
次に、本実施形態の辞書検索装置を同様に日本語の検索に用いた場合で、「くるまでまつ」を辞書５０２中の全語から検索した場合を例にとって本辞書検索装置の動作を説明する。辞書５０２には表３の語があったものとする。なお、括弧内の記述は動作の説明のために記載したもので、辞書検索装置の動作には関係がない。
【００３４】
【表３】

【００３５】
「くる」の可能後続語としては、「９：るまん」と「１０：るもい」が記載されている。これは「くる」の２文字目から始まる語としてはこの２語の可能性があることを示している。「くるま」の可能後続語としては、「９：るまん」のみが記載されている。これは「くるま」の２文字目から始まる語としては「るまん」のみが可能性があることを示している。「くるまえび」の場合には、２文字目から始まる、すなわち「るまえび」で始まる語が辞書５０２に存在していないため、可能後続語欄には“なし”と記載されている。同様に、「まで」の可能後続語には「４：で」から「６：でんたく」の語が記載されており、その他の語が「まで」の２文字目（で）から始まる可能性がないことを示している。
【００３６】
まず、ステップ６０１で「くるまでまつ」が入力される。ステップ６０２で第１の実施形態のステップ２０２と同様の処理で「３：くるまえび」を得、ステップ６０３〜６０７で第１の第１の実施形態のステップ２０３〜２０７と同様の処理で、「２：くるま」を得る。ステップ６０８では「２：くるま」に記載されている可能後続語「９：るまん」を可能後続語リスト５０３に格納する。ステップ６０９，６１０では第１の実施形態のステップ２０９，２１０と同様の処理で、検索語リスト５０４に「２：くるま」と「１：くる」の２語を格納する。ステップ６１１では、検索語として「２：くるま」と「１：くる」の２語を、可能後続語として「９：るまん」を出力装置５０６に出力する。
【００３７】
図７は本発明の第４の実施形態の辞書検索装置の構成図である。
【００３８】
本実施形態の辞書検索装置は、文を入力するための入力装置７０１と、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の可能後続語（ＦＬ）が記載されている辞書７０２と、可能後続語リスト７０３と、検索語リスト７０４と、入力文の先頭部分と完全一致する語を辞書７０２から検索し、検索した語を検索語リスト７０４に記憶し、また完全一致した語の、辞書７０２に記載されている可能後続語を可能後続語リスト７０３に記憶し、以後入力文を１文字ずらし、すなわち先頭の１文字を順次除いた文について同様の処理を行う処理装置７０５と、検索語リスト７０４と可能後続語リスト７０３の内容を出力（表示または印字）する出力装置７０６で構成されている。
【００３９】
図８は本実施形態の処理装置７０５の処理内容を示すフローチャートである。図８中、ステップ８０１、８０３〜８０８、８１０〜８１２、８１６の処理は図６中のステップ６０１、６０２〜６０７、６０８〜６１０、６１１と同じである。ステップ８０２では辞書７０２の検索範囲を「辞書中の全語」に初期化する。ステップ８０９で検索語が無かった場合、ステップ８１３で辞書７０２の検索範囲を「辞書中の全語」に設定する。ステップ８１４，８１５の処理は図４中のステップ４１１，４１２と同じである。
【００４０】
なお、ステップ８０１と８０２の順序が入れ替っていてもよい。
【００４１】
次に、同様に、本実施形態の辞書検索装置を日本語の検索に用いた場合で、「くるまでまつ」を検索した場合を例にとって本辞書検索装置の動作を説明する。辞書７０２として第３の実施形態と同じ辞書５０２を用いる。
【００４２】
まず、ステップ８０１で「くるまでまつ」が入力され、ステップ８０２で検索範囲は「辞書中の全語」、すなわち（１〜１０）と初期化される。ステップ８０３で「くるまでまつ」が検索範囲の中から検索される。検索によって前記実施形態と同様の処理をして「１：くる」と「２：くるま」の２語と可能後続語リスト（９〜９）が得られる。ステップ８１０で（９〜９）を可能後続語リスト７０３に格納する。ステップ８１２で「１：くる」と「２：くるま」の２語を検索語リスト７０４に格納する。
【００４３】
次に、ステップ８１４で入力文を１文字ずらし、「るまでまつ」を与える。ステップ８０３では、「るまでまつ」を範囲（９〜９）から検索する。この場合、「るまん」は「るまでまつ」の先頭部分と完全一致しないので、語の候補が得られないことが、辞書全体から検索するよりも狭い検索範囲で判明する。検索語がなかったのでステップ８１３で検索範囲を「辞書中の全語」に設定する。
【００４４】
次に、「までまつ」を辞書検索にかけ、「辞書中の全語」から検索する。その結果「８：まで」の１語が得られ、検索語リスト７０４に格納される。次に、「でまつ」を検索する。同様に、「４：で」から「６：でんたく」の範囲から検索し、「４：で」の１語が検索され検索語リスト７０４に格納される。
【００４５】
次に、「まつ」を辞書検索にかけ、「４：で」の可能後続語（１〜１０）のすべてから検索し、「７：まつ」の１語が得られ、検索語リスト７０４に格納される。
【００４６】
「７：まつ」の可能後続語は“なし”と記載されているため、ステップ８０３で「つ」から始まる語は存在しないことを即座に判定し、語の候補は得られない。
【００４７】
結果として、第２の実施形態と同様に表２の検索結果リストが得られ、「くるまでまつ」に含まれる可能性のある語がすべて得られている。
【００４８】
図９は第１の実施形態の辞書検索装置をパソコン等のコンピュータで実施する場合の構成図である。
【００４９】
入力装置９０１は入力装置１０１に対応し、キーボード等である。記憶装置９０２，９０３はそれぞれ辞書１０２、検索語リスト１０３に相当する。記憶装置９０４はハードディスクである。出力装置９０５は出力装置１０５に相当し、プリンタ、ディスプレイ等である。記録媒体９０６は処理装置１０４の処理（図２）を辞書検索プログラムとして記録した、フロッピィ・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク等の記録媒体である。データ処理装置９０７は記録媒体９０６から辞書検索プログラムを読み込んで、これを実行するＣＰＵである。
【００５０】
なお、第２、第３、第４の実施形態の辞書検索装置も同様に、パソコン等のコンピュータ上で実施することができる。
【００５１】
【発明の効果】
以上説明したように、本発明によれば、下記のような効果がある。
【００５２】
請求項１の発明では、各文字から始まる語の検索の際に自動的に後続語の可能 性の範囲が絞られるため、２文字目以降の辞書検索でより効率的な辞書検索が 実現できる。請求項２の発明によって、さらに高速な形態素解析が実現できる 。
【図面の簡単な説明】
【図１】本発明の第１の実施形態の辞書検索装置の構成図である。
【図２】第１の実施形態の処理の流れを示すフローチャートである。
【図３】本発明の第２の実施形態の辞書検索装置の構成図である。
【図４】第２の実施形態の処理の流れを示すフローチャートである。
【図５】本発明の第３の実施形態の辞書検索装置の構成図である。
【図６】第３の実施形態の処理の流れを示すフローチャートである。
【図７】本発明の第４の実施形態の辞書検索装置の構成図である。
【図８】第４の実施形態の処理の流れを示すフローチャートである。
【図９】第１の実施形態の辞書検索装置をパソコン等のコンピュータ上で実施する場合の構成図である。
【符号の説明】
１０１，３０１，５０１，７０１ 入力装置
１０２，３０２，５０２，７０２ 辞書
１０３，３０３，５０４，７０４ 検索語リスト
１０４，３０４，５０５，７０５ 処理装置
１０５，３０５，５０６，７０６ 出力装置
５０３，７０３ 可能後続語リスト
２０１〜２１１，４０１〜４１３，６０１〜６１１，８０１〜８１６ ステップ
９０１ 入力装置
９０２，９０３，９０４ 記憶装置
９０５ 出力装置
９０６ 記録媒体
９０７ データ処理装置[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a dictionary search method and apparatus.
[0002]
[Prior art]
Morphological analyzers that divide natural language into morphemes are widely used in natural language processing systems such as Japanese Kana-Kanji conversion devices, information retrieval devices, machine translation systems, and speech recognition devices.
[0003]
In morphological analysis of languages such as Japanese and Chinese that do not have a separator such as a space between words, it is not easy to determine which character a word starts. It is necessary to list all that are possible. Even in languages such as English where there is a space between words, in the case of speech recognition, it is not clear how words are separated, so it is necessary to list all possible words.
[0004]
To get all the words that may be included in an input sentence of length n, search the dictionary in order, starting with the first character and having a length of 1 and then a length of 2, then the second character There is a method of searching in order of a word having a length of 1 and a word having a length of 2 starting from. This method can also obtain all the words, but in this case, n (n + 1) / 2 dictionary searches are required, which is not efficient.
[0005]
As a high-speed dictionary construction method, a trie structure (for example, “Iwanami Course Software Science 15 Natural Language Processing”) is known. However, each character requires processing to follow a tree structure. There was a problem that the search efficiency was not so good.
[0006]
[Problems to be solved by the invention]
Conventionally, a trie structure known as a fast dictionary construction method stores words in a tree structure that branches for each character. Even in a dictionary search using this structure, all the words that may be included in the input sentence can be obtained by n searches. However, since it is necessary to process the tree structure for each character, There was a problem that the search efficiency was not so good.
[0007]
An object of the present invention is to provide a dictionary search method and apparatus capable of efficient search, and a recording medium on which a dictionary search program is recorded.
[0010]
The first dictionary search device of the present invention describes, for each registered word in the dictionary, a pointer to a word that completely matches the head part of the word and is shorter than that word, and that each word can be a subsequent word. By giving a list of possible words in advance , simply searching for the longest matching word, all the words that match the beginning of the input sentence and a list of words that may start from the second letter are stored in a single dictionary It can be obtained by searching.
[0011]
The second dictionary search device of the present invention is such that the first dictionary search device further searches the input sentence while shifting the input sentence by one character (excluding the first character). Thereby, when the input sentence length is n, all the words that may be included in the input sentence are obtained by dictionary search n times or less. Moreover, since a single search is performed within a narrow range, the efficiency is high.
[0012]
DETAILED DESCRIPTION OF THE INVENTION
Next, embodiments of the present invention will be described with reference to the drawings.
[0013]
FIG. 1 is a block diagram of the dictionary search apparatus according to the first embodiment of the present invention.
[0014]
The dictionary search apparatus according to the present embodiment includes an input device 101 for inputting a sentence, and the longest of words registered in each registered word that completely match the first partial character string of the word and shorter than the word. A processing unit 104 that searches the dictionary 102 in which a pointer to a word is written, a search word list 103, and a word that completely matches the head part of the input sentence from the dictionary 102, and stores the searched word in the search word list 103 And an output device 105 that outputs (displays or prints) the contents of the search term list 103.
[0015]
FIG. 2 is a flowchart showing the processing contents of the processing device 104. First, in step 201, a sentence is input from the input device 101. Next, in step 202, a word that is equal to or smaller than the input sentence (before the input sentence) is searched from the dictionary 102. This search can be performed by a binary search or the like. In step 203, it is determined whether or not the searched word completely matches the head portion of the input sentence. If there is a complete match, the word is stored in the search word list 103 at step 208. If it does not completely match, the pointer described in the dictionary 102 is traced in step 204, and it is determined in step 205 whether or not it completely matches. If there is a perfect match, go to step 208. If there is no exact match, step 204 searches for the next pointer word. If there is no pointer in step 206, there is no complete word match, and “no corresponding word” is output to the output device 105 in step 207. After step 208, in step 209, if a pointer is written in the exact word, follow the pointer, and in step 210, search for the word obtained by tracing the exact word and the pointer of the word in order. Store in the word list 103. In the final step 211, the words in the search word list 103 are output to the output device 105.
[0016]
Step 208 may be combined with step 210.
[0017]
Next, the operation of the dictionary search device will be described taking as an example the case where the dictionary search device of the present embodiment is used for searching Japanese and searching for “Katsuru Matsuri”. It is assumed that the dictionary 102 has the words in Table 1. The description in parentheses is for explanation of the operation, and is not related to the operation of the dictionary search device.
[0018]
[Table 1]

[0019]
“Kuruma shrimp” has a pointer to “car”, “car” has a pointer to “car”, and “de” and “den-taku” have “de” Pointer to is described.
[0020]
There are two types of “de”, the consecutive form of the particle “de” and the auxiliary verb “da”. In the case of such an isomorphic word, only one entry is provided in the dictionary. It is clear that it is easy to expand to a plurality of words after the dictionary search is completed.
[0021]
First, “until it comes” is input in step 201, and “until it comes” is searched in step 202. Since the comparison in the order of the dictionaries is (“Katsumamatsu” <“De”) and (“Kuruuma shrimp” <“Katsuma shrimp”), “3: Kumamatsu shrimp” is obtained. Next, in Step 203, “Katsumamatsu” and “Kuruuma Ebi” are compared, and “Kuruuma Ebi” does not completely match the head of “Kuruuma Ebisu”. Get. In step 205, “car until doll” is compared with “car”, and “car” completely matches the head of “car doll”, so “2: car” is stored in the search word list 103 in step 208. . In step 209, the pointer “2: car” is traced to obtain “1: car”, and “1: car” is stored in the search word list 103 in step 210. Since there is no description in the pointer “1: come”, the process proceeds to step 211 and “2: car” and “1: come” in the search word list 103 are output.
[0022]
FIG. 3 is a block diagram of the dictionary search apparatus according to the second embodiment of the present invention.
[0023]
The dictionary search apparatus according to the present embodiment includes an input device 301 for inputting a sentence, and the longest of words registered in each registered word that completely match the first partial character string of the word and shorter than the word. The dictionary 302 in which the pointer to the word is described, the search word list 303, and the word that completely matches the head part of the input sentence are searched from the dictionary 302, the searched word is stored in the search word list 303, and then input The processing unit 304 performs the same processing for each sentence shifted by one character at the beginning of the sentence, and the output unit 305 outputs (displays or prints) the contents of the search word list 303.
[0024]
FIG. 4 is a flowchart showing the processing contents of the processing device 304. Steps 401 to 410 and 413 are the same as steps 201 to 210 and 211 in FIG. In the present embodiment, after step 410, in step 411, the input sentence is shifted by one character, that is, the process after step 402 is repeated for the sentence from which the first character is deleted until there is no input sentence.
[0025]
Next, the operation of the dictionary search apparatus will be described taking as an example the case where the dictionary search apparatus of the second embodiment is similarly used for searching Japanese and a search for “Katsuru Matsuri” is performed. As the dictionary 302, the same dictionary 102 as in the first embodiment is used.
[0026]
First, “Matsuru” is input, and “Matsuru” is searched in Step 402. Thereafter, the same processing as in the first embodiment is performed to obtain two words “1: car” and “2: car”, and these two words are stored in the search word list 303. In step 411, the input sentence “Katsuru Matsu” is shifted by one character, and the dictionary 302 is searched for “Rutama Matsu”. “Rutamamatsu” is searched for a dictionary, but no word candidate is obtained. Next, “until” is subjected to a dictionary search, and one word “up to 3:” is obtained and stored in the search word list 303. Next, “dematsu” is searched for a dictionary. In this case, the search in step 402 yields “5: deci”, but does not completely match the beginning of the input sentence, so a short word is traced in step 404 to obtain “4: de”, and this word is the beginning. Since it completely matches the part, one word “4: de” is output. Therefore, one word “4: de” is stored in the search word list 303. Next, “Matsu” is subjected to a dictionary search, and one word “7: Matsu” is obtained and stored in the search word list 303. Next, “tsu” is subjected to a dictionary search, but no word candidate is obtained.
[0027]
As a result, the words in Table 2 are obtained in the search word list 303, and all the words that may be included in the “until the time” are obtained.
[0028]
[Table 2]

[0029]
FIG. 5 is a block diagram of the dictionary search apparatus according to the third embodiment of the present invention.
[0030]
The dictionary search apparatus according to the present embodiment includes an input device 501 for inputting a sentence, and the longest of words registered in each registered word that are completely identical to the first partial character string of the word and shorter than the word. A dictionary 502 in which a pointer to a word, a possible subsequent word (FL) that is a word starting with the second character of the word, a possible subsequent word list 503, a search word list 504, an input sentence Is searched from the dictionary 502, the searched word is stored in the search word list 504, and the possible subsequent words described in the dictionary 502 of the completely matched word are stored in the possible subsequent word list 503. And an output device 506 that outputs (displays or prints) the contents of the search word list 504 and the possible subsequent word list 503.
[0031]
FIG. 6 is a flowchart showing the processing contents of the processing device 505. The processing in steps 601 to 607, 609, and 610 is the same as that in steps 201 to 207, 209, and 210 in FIG. In this embodiment, if there is a perfect match in step 603, the possible successor words of the exact match word described in the dictionary 502 are stored in the possible successor word list 503 in step 608. In the final step 611, all the words stored in the possible subsequent word list 503 and the search word list 504 are output.
[0032]
Note that the order of steps 601 and 602 may be reversed, and step 608 may be after step 610.
[0033]
Next, the operation of the dictionary search apparatus will be described by taking, as an example, the case where the dictionary search apparatus according to the present embodiment is used for searching Japanese in the same manner, and “Katsuru Matsuri” is searched from all words in the dictionary 502. To do. It is assumed that the dictionary 502 has the words in Table 3. The description in parentheses is for explanation of the operation, and is not related to the operation of the dictionary search device.
[0034]
[Table 3]

[0035]
As possible subsequent words of “Kuru”, “9: Rumun” and “10: Rumoi” are described. This indicates that there is a possibility that these two words are words that start from the second letter of “Kuru”. As a possible successor of “car”, only “9: Rum” is described. This indicates that there is a possibility that only “Ruman” is a word starting from the second letter of “Kuruma”. In the case of “Kuruma Ebi”, since there is no word starting from the second character, that is, “Ruma Ebi” in the dictionary 502, “None” is described in the possible subsequent word column. Similarly, the possible subsequent words of “to” include the words “4: de” to “6: dentaku”, and other words can start from the second letter (de) of “to” It shows that there is no sex.
[0036]
First, in step 601, “Matsu Matsuri” is input. In Step 602, “3: Caramel prawn” is obtained by the same processing as Step 202 of the first embodiment, and in Steps 603 to 607, the processing similar to Steps 203 to 207 of the first first embodiment is performed. Get 2: Car. In step 608, the possible subsequent word “9: Rumun” described in “2: Car” is stored in the possible subsequent word list 503. In steps 609 and 610, two words “2: car” and “1: car” are stored in the search word list 504 in the same process as in steps 209 and 210 of the first embodiment. In step 611, two words “2: car” and “1: car” are output to the output device 506 as search terms and “9: run” as possible successors.
[0037]
FIG. 7 is a block diagram of the dictionary search apparatus according to the fourth embodiment of the present invention.
[0038]
The dictionary search apparatus according to the present embodiment includes an input device 701 for inputting a sentence, and the longest of words registered in each registered word that completely match the first partial character string of the word and shorter than the word. A dictionary 702 in which a pointer to a word, a possible subsequent word (FL) of the word is described, a possible subsequent word list 703, a search word list 704, and a word that completely matches the head portion of the input sentence are stored in the dictionary 702. , The searched word is stored in the search word list 704, and the possible subsequent words of the completely matched word described in the dictionary 702 are stored in the possible subsequent word list 703. Thereafter, the input sentence is shifted by one character. In other words, the processing device 705 performs the same processing for the sentence from which the first character is sequentially removed, and the output device 706 outputs (displays or prints) the contents of the search word list 704 and the possible subsequent word list 703. .
[0039]
FIG. 8 is a flowchart showing the processing contents of the processing apparatus 705 of this embodiment. In FIG. 8, the processing of steps 801, 803 to 808, 810 to 812, and 816 is the same as that of steps 601, 602 to 607, 608 to 610, and 611 in FIG. In step 802, the search range of the dictionary 702 is initialized to “all words in the dictionary”. If there is no search word in step 809, the search range of the dictionary 702 is set to “all words in the dictionary” in step 813. Steps 814 and 815 are the same as steps 411 and 412 in FIG.
[0040]
Note that the order of steps 801 and 802 may be switched.
[0041]
Next, similarly, the operation of the dictionary search apparatus will be described taking as an example the case where the dictionary search apparatus according to the present embodiment is used for Japanese search and “Katsuru Matsuri” is searched. As the dictionary 702, the same dictionary 502 as that of the third embodiment is used.
[0042]
First, in step 801, “Fill until coming” is input, and in step 802, the search range is initialized to “all words in the dictionary”, that is, (1 to 10). In step 803, “Matsuru until” is searched from the search range. By searching, the same processing as in the above embodiment is performed to obtain two words “1: car” and “2: car” and a list of possible subsequent words (9 to 9). In step 810, (9-9) is stored in the possible subsequent word list 703. In step 812, two words “1: car” and “2: car” are stored in the search word list 704.
[0043]
Next, in step 814, the input sentence is shifted by one character to give "Rutama Matsu". In Step 803, “Rutama Matsu” is searched from the range (9 to 9). In this case, since “Ruman” does not completely match the head part of “Rumatsu Matsu”, it is found that a word candidate cannot be obtained in a narrower search range than the entire dictionary. Since there is no search word, the search range is set to “all words in dictionary” in step 813.
[0044]
Next, “Matsumatsu” is searched for a dictionary, and “all words in the dictionary” are searched. As a result, one word “up to 8:” is obtained and stored in the search word list 704. Next, search for “dematsu”. Similarly, a search is made from the range of “4: de” to “6: detataku”, and one word “4: de” is searched and stored in the search word list 704.
[0045]
Next, “Matsu” is subjected to a dictionary search, and a search is performed from all possible succeeding words (1 to 10) “4: de”, and one word “7: Matsu” is obtained and stored in the search word list 704. The
[0046]
Since the possible successor of “7: matsu” is described as “none”, it is immediately determined in step 803 that there is no word starting with “tsu”, and no word candidate is obtained.
[0047]
As a result, the search result list of Table 2 is obtained in the same manner as in the second embodiment, and all of the words that may be included in the “until the car” are obtained.
[0048]
FIG. 9 is a configuration diagram when the dictionary search apparatus of the first embodiment is implemented by a computer such as a personal computer.
[0049]
The input device 901 corresponds to the input device 101 and is a keyboard or the like. The storage devices 902 and 903 correspond to the dictionary 102 and the search word list 103, respectively. The storage device 904 is a hard disk. The output device 905 corresponds to the output device 105, and is a printer, a display, or the like. A recording medium 906 is a recording medium such as a floppy disk, a CD-ROM, or a magneto-optical disk in which the processing of the processing device 104 (FIG. 2) is recorded as a dictionary search program. The data processing device 907 is a CPU that reads a dictionary search program from the recording medium 906 and executes it.
[0050]
Similarly, the dictionary search apparatus of the second, third, and fourth embodiments can be implemented on a computer such as a personal computer.
[0051]
【The invention's effect】
As described above, the present invention has the following effects.
[0052]
In the invention of claim 1 , since the range of the possibility of the subsequent word is automatically narrowed down when searching for the word starting from each character, a more efficient dictionary search can be realized by the dictionary search after the second character. According to the invention of claim 2 , higher-speed morphological analysis can be realized.
[Brief description of the drawings]
FIG. 1 is a configuration diagram of a dictionary search apparatus according to a first embodiment of this invention.
FIG. 2 is a flowchart showing a flow of processing of the first embodiment.
FIG. 3 is a configuration diagram of a dictionary search apparatus according to a second embodiment of this invention.
FIG. 4 is a flowchart showing a processing flow of the second embodiment.
FIG. 5 is a configuration diagram of a dictionary search apparatus according to a third embodiment of the present invention.
FIG. 6 is a flowchart illustrating a processing flow of the third embodiment.
FIG. 7 is a block diagram of a dictionary search apparatus according to a fourth embodiment of the present invention.
FIG. 8 is a flowchart showing the flow of processing of the fourth embodiment.
FIG. 9 is a configuration diagram when the dictionary search apparatus according to the first embodiment is implemented on a computer such as a personal computer.
[Explanation of symbols]
101, 301, 501, 701 Input device 102, 302, 502, 702 Dictionary 103, 303, 504, 704 Search word list 104, 304, 505, 705 Processing device 105, 305, 506, 706 Output device 503, 703 Possible subsequent Word list 201-211, 401-413, 601-611, 801-816 Step 901 Input device 902, 903, 904 Storage device 905 Output device 906 Recording medium 907 Data processing device

Claims (5)

A dictionary search method performed by a dictionary search device having an input device, a processing device, and an output device,
Inputting a sentence from the input device to the processing device ;
The processing device , for each registered word, completely matches the first partial character string of the word and has a pointer to the longest word among words shorter than the word and the second and subsequent characters of the word Searching for a word that is equal to or smaller than the input sentence from a dictionary that describes possible subsequent words that are in
The processor determines whether a search term exactly matches the beginning of the input sentence;
If the processing unit does not match exactly, stepping the pointer in order until an exact match is found;
The processing unit storing in the possible successor list a possible successor word of the exact match word described in the dictionary;
If the processing device has a pointer written to a completely matched word, the step of following the pointer of the word in order;
The processing device stores in the search word list a word that is completely matched and a word obtained by sequentially tracing the pointer of the word;
A dictionary search method , comprising: the processing device outputting the search word list and the possible subsequent word list to the output device . A dictionary search method performed by a dictionary search device having an input device, a processing device, and an output device,
The processing device inputting a sentence from the input device to the processing device ;
The processing device, for each registered word, completely matches the first partial character string of the word and has a pointer to the longest word among words shorter than the word and the second and subsequent characters of the word Initializing the search range of the dictionary in which possible subsequent words that are words in are written to all words in the dictionary;
The processing device searches the dictionary for a word in the search range that is equal to or smaller than the input sentence, and determines whether the search word completely matches the head part of the input sentence. If not, follow the pointer in order until an exact match is found, store the possible success words of the exact match described in the dictionary in the possible success word list, and write the pointer to the exact match If it is, the word pointer is followed in order, and the exact word and the word obtained by following the word pointer are stored in the search word list. If no exact word is found, the dictionary is searched. Setting the range to all words;
The processing device, the first character of the input sentence, two characters, for each sentence excluding ..., and repeating the process step of setting a search or found search range of said,
A dictionary search method , comprising: the processing device outputting the search word list and the possible subsequent word list to the output device . Each registered word is a word that has a pointer to the longest word out of words that are exactly the same as the first partial character string of the word and shorter than the word, and that starts with the second and subsequent characters of the word. A dictionary with some possible successors,
Search term list,
A list of possible successors, and
An input device for inputting a sentence;
A word that is equal to or smaller than the input sentence is searched from the dictionary, and it is determined whether or not the search word completely matches the head part of the input sentence. The pointers are traced in order, and the possible successor words described in the dictionary of the completely matched words are stored in the possible successor word list. If the pointers are described in the completely matched words, the pointers of the words are sequentially A processing device for storing in the search word list the words that have been traced, and the words obtained by tracing the pointers of the words in order,
A dictionary search device having an output device for outputting the search word list and the possible subsequent word list. Each registered word is a word that has a pointer to the longest word out of words that are exactly the same as the first partial character string of the word and shorter than the word, and that starts with the second and subsequent characters of the word. A dictionary with some possible successors,
Search term list,
A list of possible successors, and
An input device for inputting a sentence;
Initialize the search range of the dictionary to all words in the dictionary, search for words that are equal to the input sentence or smaller than the input sentence, and determine whether the search word completely matches the head part of the input sentence, If there is no exact match, the pointer is sequentially traced until a completely matched word is found, the possible successor words of the exact match word described in the dictionary are stored in the possible successor word list, and the exact match word is pointed to Is stored in the search word list by following the pointers of the words in order, and the exact words and the words obtained by following the pointers of the words in order. A processing device that sets the search range of the dictionary to all words and repeats the processing from the search to the setting of the search range for each sentence except the first character, two characters,. ,
A dictionary search device having an output device for outputting the search word list and the possible subsequent word list. A computer-readable recording medium on which a dictionary search program for executing the function of the dictionary search device according to claim 3 or 4 by a computer is recorded.

Images