JP3628565B2

JP3628565B2 - 辞書検索方法、装置、および辞書検索プログラムを記録した記録媒体

Info

Publication number: JP3628565B2
Application number: JP30413099A
Authority: JP
Inventors: 義博松尾
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 1999-10-26
Filing date: 1999-10-26
Publication date: 2005-03-16
Anticipated expiration: 2019-10-26
Also published as: JP2001125907A

Description

【０００１】
【発明の属する技術分野】
本発明は辞書検索方法および装置に関する。
【０００２】
【従来の技術】
自然言語を形態素に分割する形態素解析装置は日本語の仮名漢字変換装置や、情報検索装置、機械翻訳システム、音声認識装置などの自然言語処理システムに広く用いられる。
【０００３】
日本語や中国語のように単語間に空白などの区切り記号がない言語の形態素解析では、語がどの文字から始まっているかが容易には判定できないため、入力文の部分文字列のうち単語の可能性があるものをすべて列挙することが必要である。また、英語など語間に空白がある言語でも、音声認識の場合には語間の区切りが明らかでないため、やはり語の可能性があるものすべてを列挙する必要がある。
【０００４】
長さｎの入力文中に含まれる可能性のあるすべての語を得るために、１文字めから始まる長さ１の語、長さ２の語、と順に辞書を検索し、次に２文字めから始まる長さ１の語、長さ２の語、と順に検索する方法がある。この方法でもすべての語が得られるが、この場合、ｎ（ｎ＋１）／２回の辞書検索が必要となり、効率的ではなかった。
【０００５】
また、高速な辞書構成方法としてはトライ構造（例えば「岩波講座ソフトウエア科学１５自然言語処理」）が知られているが、１文字ごとに木構造をたどる処理が必要なため、それぞれの回の検索の効率があまりよくないという問題があった。
【０００６】
【発明が解決しようとする課題】
従来、高速な辞書構成方法として知られているトライ構造では、文字ごとに分岐する木構造で単語を格納する。この構造を用いた辞書検索でも、ｎ回の検索で入力文に含まれている可能性のある単語をすべて得られるが、１文字ごとに木構造をたどる処理が必要なため、それぞれの回の検索の効率があまりよくないという問題があった。
【０００７】
本発明の目的は、効率的な検索が可能な辞書検索方法、装置、および辞書検索プログラムを記録した記録媒体を提供することにある。
【００１０】
本発明の第１の辞書検索装置は、辞書の各登録語に、その語の先頭部分と完全一致し、かつその語より短い語へのポインタを記載し、さらに、各語に後続語の可能性のある語のリストをあらかじめ与えることにより、最長一致する語を検索するだけで、入力文の先頭部分と一致するすべての語と２文字目から始まる可能性のある語のリストを一度の辞書検索で得られるようにしたものである。
【００１１】
本発明の第２の辞書検索装置は、第１の辞書検索装置にさらに、入力文を１文字ずらしながら（先頭の１文字を除きながら）検索するようにしたものである。これにより、入力文長がｎの場合、ｎ回以下の辞書検索で、入力文に含まれている可能性のある単語が全て得られる。また、１回の検索を狭い範囲で行うので効率がよい。
【００１２】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１３】
図１は本発明の第１の実施形態の辞書検索装置の構成図である。
【００１４】
本実施形態の辞書検索装置は、文を入力するための入力装置１０１と、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタが記載されている辞書１０２と、検索語リスト１０３と、入力文の先頭部分と完全一致する語を辞書１０２から検索し、検索した語を検索語リスト１０３に記憶する処理装置１０４と、検索語リスト１０３の内容を出力（表示または印字）する出力装置１０５で構成されている。
【００１５】
図２は処理装置１０４の処理内容を示すフローチャートである。まず、ステップ２０１に、入力装置１０１から文を入力する。次に、ステップ２０２に、辞書１０２から入力文と等しいか、入力文より小さい（入力文より前にある）語を検索する。この検索は二分探索などにより行うことができる。ステップ２０３に、検索された語が入力文の先頭部分と完全に一致するかどうか判定する。完全一致するならば、ステップ２０８でその語を検索語リスト１０３に記憶する。完全一致しなければ、ステップ２０４で辞書１０２に記載されたポインタをたどり、ステップ２０５で完全一致するかどうか判定する。完全一致すれば、ステップ２０８に行く。完全一致しなければ、ステップ２０４で、次のポインタの語を探索する。ステップ２０６で、ポインタがなければ、完全一致する語がないことになり、ステップ２０７で、「該当語なし」を出力装置１０５に出力する。ステップ２０８の後、ステップ２０９で、完全一致した語にポインタが記載されていれば、ポインタをたどり、ステップ２１０に、完全一致した語と、その語のポインタを順にたどって得られた語を検索語リスト１０３に記憶する。最後のステップ２１１で、検索語リスト１０３の語を出力装置１０５に出力する。
【００１６】
なお、ステップ２０８はステップ２１０と一緒にしてもよい。
【００１７】
次に、本実施形態の辞書検索装置を日本語の検索に用いた場合で、「くるまでまつ」を検索する場合を例にとって本辞書検索装置の動作を説明する。辞書１０２には表１の語があったものとする。なお、括弧内の記述は動作の説明のために記載したもので、辞書検索装置の動作には関係がない。
【００１８】
【表１】

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

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

【００３５】
「くる」の可能後続語としては、「９：るまん」と「１０：るもい」が記載されている。これは「くる」の２文字目から始まる語としてはこの２語の可能性があることを示している。「くるま」の可能後続語としては、「９：るまん」のみが記載されている。これは「くるま」の２文字目から始まる語としては「るまん」のみが可能性があることを示している。「くるまえび」の場合には、２文字目から始まる、すなわち「るまえび」で始まる語が辞書５０２に存在していないため、可能後続語欄には“なし”と記載されている。同様に、「まで」の可能後続語には「４：で」から「６：でんたく」の語が記載されており、その他の語が「まで」の２文字目（で）から始まる可能性がないことを示している。
【００３６】
まず、ステップ６０１で「くるまでまつ」が入力される。ステップ６０２で第１の実施形態のステップ２０２と同様の処理で「３：くるまえび」を得、ステップ６０３〜６０７で第１の第１の実施形態のステップ２０３〜２０７と同様の処理で、「２：くるま」を得る。ステップ６０８では「２：くるま」に記載されている可能後続語「９：るまん」を可能後続語リスト５０３に格納する。ステップ６０９，６１０では第１の実施形態のステップ２０９，２１０と同様の処理で、検索語リスト５０４に「２：くるま」と「１：くる」の２語を格納する。ステップ６１１では、検索語として「２：くるま」と「１：くる」の２語を、可能後続語として「９：るまん」を出力装置５０６に出力する。
【００３７】
図７は本発明の第４の実施形態の辞書検索装置の構成図である。
【００３８】
本実施形態の辞書検索装置は、文を入力するための入力装置７０１と、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の可能後続語（ＦＬ）が記載されている辞書７０２と、可能後続語リスト７０３と、検索語リスト７０４と、入力文の先頭部分と完全一致する語を辞書７０２から検索し、検索した語を検索語リスト７０４に記憶し、また完全一致した語の、辞書７０２に記載されている可能後続語を可能後続語リスト７０３に記憶し、以後入力文を１文字ずらし、すなわち先頭の１文字を順次除いた文について同様の処理を行う処理装置７０５と、検索語リスト７０４と可能後続語リスト７０３の内容を出力（表示または印字）する出力装置７０６で構成されている。
【００３９】
図８は本実施形態の処理装置７０５の処理内容を示すフローチャートである。図８中、ステップ８０１、８０３〜８０８、８１０〜８１２、８１６の処理は図６中のステップ６０１、６０２〜６０７、６０８〜６１０、６１１と同じである。ステップ８０２では辞書７０２の検索範囲を「辞書中の全語」に初期化する。ステップ８０９で検索語が無かった場合、ステップ８１３で辞書７０２の検索範囲を「辞書中の全語」に設定する。ステップ８１４，８１５の処理は図４中のステップ４１１，４１２と同じである。
【００４０】
なお、ステップ８０１と８０２の順序が入れ替っていてもよい。
【００４１】
次に、同様に、本実施形態の辞書検索装置を日本語の検索に用いた場合で、「くるまでまつ」を検索した場合を例にとって本辞書検索装置の動作を説明する。辞書７０２として第３の実施形態と同じ辞書５０２を用いる。
【００４２】
まず、ステップ８０１で「くるまでまつ」が入力され、ステップ８０２で検索範囲は「辞書中の全語」、すなわち（１〜１０）と初期化される。ステップ８０３で「くるまでまつ」が検索範囲の中から検索される。検索によって前記実施形態と同様の処理をして「１：くる」と「２：くるま」の２語と可能後続語リスト（９〜９）が得られる。ステップ８１０で（９〜９）を可能後続語リスト７０３に格納する。ステップ８１２で「１：くる」と「２：くるま」の２語を検索語リスト７０４に格納する。
【００４３】
次に、ステップ８１４で入力文を１文字ずらし、「るまでまつ」を与える。ステップ８０３では、「るまでまつ」を範囲（９〜９）から検索する。この場合、「るまん」は「るまでまつ」の先頭部分と完全一致しないので、語の候補が得られないことが、辞書全体から検索するよりも狭い検索範囲で判明する。検索語がなかったのでステップ８１３で検索範囲を「辞書中の全語」に設定する。
【００４４】
次に、「までまつ」を辞書検索にかけ、「辞書中の全語」から検索する。その結果「８：まで」の１語が得られ、検索語リスト７０４に格納される。次に、「でまつ」を検索する。同様に、「４：で」から「６：でんたく」の範囲から検索し、「４：で」の１語が検索され検索語リスト７０４に格納される。
【００４５】
次に、「まつ」を辞書検索にかけ、「４：で」の可能後続語（１〜１０）のすべてから検索し、「７：まつ」の１語が得られ、検索語リスト７０４に格納される。
【００４６】
「７：まつ」の可能後続語は“なし”と記載されているため、ステップ８０３で「つ」から始まる語は存在しないことを即座に判定し、語の候補は得られない。
【００４７】
結果として、第２の実施形態と同様に表２の検索結果リストが得られ、「くるまでまつ」に含まれる可能性のある語がすべて得られている。
【００４８】
図９は第１の実施形態の辞書検索装置をパソコン等のコンピュータで実施する場合の構成図である。
【００４９】
入力装置９０１は入力装置１０１に対応し、キーボード等である。記憶装置９０２，９０３はそれぞれ辞書１０２、検索語リスト１０３に相当する。記憶装置９０４はハードディスクである。出力装置９０５は出力装置１０５に相当し、プリンタ、ディスプレイ等である。記録媒体９０６は処理装置１０４の処理（図２）を辞書検索プログラムとして記録した、フロッピィ・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク等の記録媒体である。データ処理装置９０７は記録媒体９０６から辞書検索プログラムを読み込んで、これを実行するＣＰＵである。
【００５０】
なお、第２、第３、第４の実施形態の辞書検索装置も同様に、パソコン等のコンピュータ上で実施することができる。
【００５１】
【発明の効果】
以上説明したように、本発明によれば、下記のような効果がある。
【００５２】
請求項１の発明では、各文字から始まる語の検索の際に自動的に後続語の可能性の範囲が絞られるため、２文字目以降の辞書検索でより効率的な辞書検索が実現できる。請求項２の発明によって、さらに高速な形態素解析が実現できる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態の辞書検索装置の構成図である。
【図２】第１の実施形態の処理の流れを示すフローチャートである。
【図３】本発明の第２の実施形態の辞書検索装置の構成図である。
【図４】第２の実施形態の処理の流れを示すフローチャートである。
【図５】本発明の第３の実施形態の辞書検索装置の構成図である。
【図６】第３の実施形態の処理の流れを示すフローチャートである。
【図７】本発明の第４の実施形態の辞書検索装置の構成図である。
【図８】第４の実施形態の処理の流れを示すフローチャートである。
【図９】第１の実施形態の辞書検索装置をパソコン等のコンピュータ上で実施する場合の構成図である。
【符号の説明】
１０１，３０１，５０１，７０１入力装置
１０２，３０２，５０２，７０２辞書
１０３，３０３，５０４，７０４検索語リスト
１０４，３０４，５０５，７０５処理装置
１０５，３０５，５０６，７０６出力装置
５０３，７０３可能後続語リスト
２０１〜２１１，４０１〜４１３，６０１〜６１１，８０１〜８１６ステップ
９０１入力装置
９０２，９０３，９０４記憶装置
９０５出力装置
９０６記録媒体
９０７データ処理装置

Claims

入力装置と処理装置と出力装置を有する辞書検索装置で行なわれる辞書検索方法であって、
前記入力装置から前記処理装置に文を入力するステップと、
前記処理装置が、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の２文字目以降を先頭に持つ語である可能後続語が記載されている辞書から前記入力文と等しいか、前記入力文より小さい語を検索するステップと、
前記処理装置が、検索語が前記入力文の先頭部分と完全一致するかどうか判定するステップと、
前記処理装置が、完全一致していなければ、完全一致する語が見つかるまでポインタを順にたどるステップと、
前記処理装置が、完全一致した語の、前記辞書に記載されている可能後続語を可能後続語リストに記憶するステップと、
前記処理装置が、完全一致した語にポインタが記載されていれば、その語のポインタを順にたどるステップと、
前記処理装置が、完全一致した語と、その語のポインタを順にたどって得られた語を検索語リストに記憶するステップと、
前記処理装置が、前記検索語リストと前記可能後続語リストを前記出力装置に出力するステップを有する辞書検索方法。
入力装置と処理装置と出力装置を有する辞書検索装置で行なわれる辞書検索方法であって、
前記処理装置が、前記入力装置から前記処理装置に文を入力するステップと、
前記処理装置が、各登録語に、該語の先頭部分文字列と完全一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の２文字目以降を先頭に持つ語である可能後続語が記載されている辞書の検索範囲を辞書中の全語に初期化するステップと、
前記処理装置が、前記辞書から前記検索範囲の、前記入力文と等しいか、前記入力文より小さい語を検索し、検索語が前記入力文の先頭部分と完全一致するかどうか判定し、完全一致していなければ、完全一致する語が見つかるまでポインタを順にたどり、完全一致した語の、前記辞書に記載されている可能後続語を可能後続語リストに記憶し、完全一致した語にポインタが記載されていれば、その語のポインタを順にたどり、完全一致した語と、その語のポインタを順にたどって得られた語を検索語リストに記憶し、完全一致した語が見つからなければ辞書の検索範囲を全語に設定するステップと、
前記処理装置が、前記入力文の先頭の１文字，２文字，・・・を除いた各文について、前記の検索から検索範囲を設定するステップの処理を繰り返すステップと、
前記処理装置が、前記検索語リストと前記可能後続語リストを前記出力装置に出力するステップを有する辞書検索方法。
各登録語に、該語の先頭部分文字列と完全に一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の２文字目以降を先頭に持つ語である可能後続語が記載されている辞書と、
検索語リストと、
可能後続語リストと、
文を入力する入力装置と、
前記辞書から前記入力文と等しいか、前記入力文より小さい語を検索し、検索語が前記入力文の先頭部分と完全一致するかどうか判定し、完全一致しなければ、完全一致する語が見つかるまで順にポインタをたどり、完全一致した語の前記辞書に記載されている可能後続語を前記可能後続語リストに記憶し、完全一致した語にポインタが記載されていれば、その語のポインタを順にたどり、完全一致した語と、その語のポインタを順にたどって得られた語を前記検索語リストに記憶する処理装置と、
前記検索語リストおよび前記可能後続語リストを出力する出力装置を有する辞書検索装置。
各登録語に、該語の先頭部分文字列と完全に一致し、かつ該語よりも短かい語のうち、最長の語へのポインタと、該語の２文字目以降を先頭に持つ語である可能後続語が記載されている辞書と、
検索語リストと、
可能後続語リストと、
文を入力する入力装置と、
前記辞書の検索範囲を辞書中の全語に初期化し、前記入力文と等しいか、前記入力文より小さい語を検索し、検索語が前記入力文の先頭部分と完全一致するかどうか判定し、完全一致しなければ、完全一致する語が見つかるまで順にポインタをたどり、完全一致した語の、前記辞書に記載されている可能後続語を前記可能後続語リストに記憶し、完全一致した語にポインタが記載されていれば、その語のポインタを順にたどり、完全一致した語と、その語のポインタを順にたどって得られた語を前記検索語リストに記憶し、完全一致した語が見つからなければ辞書の検索範囲を全語に設定し、前記入力文の先頭の１文字，２文字，・・・を除いた各文について、前記の検索から前記検索範囲の設定までの処理を繰り返す処理装置と、
前記検索語リストおよび前記可能後続語リストを出力する出力装置を有する辞書検索装置。
請求項３または４に記載の辞書検索装置の機能をコンピュータで実行するための辞書検索プログラムを記録した、コンピュータ読取り可能な記録媒体。