(57)【要約】【目的】  精度が高いというコスト最小法を用いた形態素解析装置の利点を残したままで、メモリ容量の使用量が小さい、日本語形態素解析装置を提供する。【解決手段】  辞書検索モジュール１０４、形態素列同士の接続可能性を判断する接続可能性判定モジュール１０７、接続コスト計算モジュール１０９を備えた日本語形態素解析装置において、更に、前接連結処理優先不要形態素列削除モジュール２１１を設け、辞書検索と同時に前接連結処理を行う単語を選択し、不要となった形態素列を逐次削除することにより形態素解析を行う。【選択図】  図２６
2008217817.tif 000002
【特許請求の範囲】
【請求項１】
辞書検索手段、形態素列同士の接続可能性を判断する接続可能性判定手段、接続コスト計算手段を備えた日本語形態素解析装置において、更に、前接連結処理制御手段、前接連結処理優先不要形態素列削除手段を設け、辞書検索と同時に前接連結処理を行う単語を選択し、不要となった形態素列を逐次削除することにより形態素解析を行うことを特徴とする日本語形態素解析装置。
【請求項２】
請求項１記載の日本語形態素解析装置において、更に、形態素枝刈り手段、形態素枝刈り制御手段を備え、同一文字位置から始まる形態素のうちコストの大きい形態素を枝刈りしてＣＹＫ表から削除すると共に、枝刈りされた形態素を必要に応じてＣＹＫ表に戻すようにしたことを特徴とする日本語形態素解析装置。
【請求項３】
請求項２記載の日本語形態素解析装置において、前記形態素枝刈り制御手段は、同じ文字位置で優先順位が最大の単語について、ＣＹＫ表で連結可能な後続形態素を見出すことができない場合に、枝刈りした形態素の中から後接形態素を探索し、連結可能な形態素が見つかった場合に、その形態素を枝刈りされていない単語としてＣＹＫ表に戻すことを特徴とする日本語形態素解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、日本語形態素解析装置に関するものである。
【背景技術】
【０００２】
従来、日本語を形態素解析する装置としては、コスト最小法（文献：田中穂積著「自然言語解析の基礎」、頁１４３〜１５３；産業図書株式会社、平成元年１１月２７日初版発行）を用いたものが、最も精度が高い装置として用いられている。図５１は、コスト最小法を用いた日本語形態素解析装置の構成の例である。１は形態素解析を行う日本語仮名漢字混じり文を入力する入力モジュール、２はＣＹＫ表を作成するＣＹＫ表作成モジュール、３はＣＹＫ表におけるＣＹＫ表の形態素列に形態素の接続コストを設定するコスト設定モジュール、４はコスト最小となる形態素列を選択するコスト最小解選択モジュール、５は文頭から文末までに相当する形態素列形態素列を出力する出力モジュール、６は入力文の各文字位置で最左部分語を検索してＣＹＫ表に書き込む辞書検索モジュール、７は形態素の表記、読み、品詞、左側接続属性、右側接続属性等を格納する形態素辞書、８は形態素列同士の接続可能を判定する接続可能性判定モジュール、９は前接する形態素の右側接続属性と後接する形態素の左側接続属性とが接続可能な組み合わせかどうか記録した接続表、１０は接続可能な形態素同士の接続コストを計算する接続コスト計算モジュール、１１は接続コスト計算に用いる接続コスト表である。
【０００３】
ここで、各種用語の定義を行っておく。
【０００４】
（最左部分語）：左端の文字が元の文字列の左端になっているような部分文字列。
【０００５】
例：「畜産物価格安定法」の最左部分語は、「蓄」、「畜産」、「畜産物」、「畜産物価」、「畜産物価格」、「畜産物価格安」、「畜産物価格安定」、「畜産物価格安定法」となる。
【０００６】
（ＣＹＫ表）：（入力文の文字数＋２）個の行と列をもつテーブルで、Ｉ行Ｊ列目には入力文のＪ文字目からＩ文字目までを表記としてもつ単語、又はこれらを連結した単語列が格納される。Ｉ行Ｊ列目の要素の集合をＴ（Ｉ，Ｊ）と表す。入力文全体の形態素解析結果となる単語列は、Ｔ（入力文の文字数＋２、１）に格納される（”＋２”は文頭と文末に解析上必要な文字を一文字ずつ追加するためである）。
【０００７】
（単語）：単語は、表記、読み、品詞、左側接続属性、右側接続属性、その他の文法情報といった属性をもつノードとする。これらのうちの１つでも内容が異なれば、別の単語とみなす。「形態素」と同義とする。
【０００８】
（単語列）：本明細書においては、各単語に後接する単語は、必ず１つであるため、各単語は、文頭からその単語までの単語列と、後接する単語の連結処理を、単語列の末尾の単語と、後接単語との連結処理と記述する場合がある。例えば、Ｔ（Ｉ，Ｊ）＊Ｔ（Ｊ−１，１）の場合、Ｔ（Ｉ，Ｊ）に含まれる単語と、Ｔ（Ｊ−１，Ｋ）（Ｋは最後の単語の開始位置）に含まれる単語の連結処理となる。
【０００９】
（連結）：ＣＹＫ表において、２つの単語列を結合する処理。結合した単語列は、識別子のついたリスト構造となる。例えば、「＃＾／文頭／（読みなし）」と「畜産／名／チクサン」を結合した構造は、［１］：［＃＾／文頭／（読みなし）、畜産／名／チクサン］となる。これに更に「物／名／ブツ」を結合した構造は、［２］：［［１］、物／名／ブツ］となる。
【００１０】
（統合）：ＣＹＫ表の欄に登録する際、単語列の最後の単語が同じ単語列は、最後の単語を共有するリスト構造にまとめる。例えば、［［１］、は／助詞／ワ］と［［２］、は／助詞／ワ］とは、［（［１］；［２］）、は／助詞／ワ］というリスト構造になる。
【００１１】
（Ｔ（Ｉ，Ｊ）＊Ｔ（Ｋ，Ｌ））：ＣＹＫ表のＴ（Ｉ，Ｊ）に含まれる単語列とＴ（Ｋ，Ｌ）に含まれる単語列の全ての組み合わせについて、連結して良いかどうかのチェックを行い、連結可能である２つの単語の組み合わせを連結した連結した集合を表す。
【００１２】
（ｘ＊ｙ）：ＣＹＫ表のＴ（Ｉ，Ｊ）に含まれる単語列ｘとＴ（Ｋ，Ｌ）に含まれる単語列ｙについて、連結して良いかどうかのチェックを行い、連結可能である２つの単語を連結した結果を表す。
【００１３】
（前接、後接）：２つの隣接した単語について、前側の単語を前接単語と呼び、後ろ側の単語を後接単語と呼ぶ。また、前側の単語は後ろ側の単語に前接する、後ろ側の単語は前側の単語に後接するという。
【００１４】
（文頭文字・文末文字）：ＣＹＫ表を用いる場合、処理の都合上、入力文の文頭と文末に全角１文字分の文字を追加する（「＄＾」と「＃＄」）。本明細書においては、これらの文字をそれぞれ、「文頭文字」、「文末文字」と呼ぶ。
【００１５】
（文頭ノード・文末ノード）：文頭文字・文末文字から始まる単語は、１文字表記の単語が、それぞれ一つずつ存在するように単語辞書を構成する。本明細書では、文頭文字・文末文字１文字を表記とする単語を、それぞれ「文頭ノード」、「文末ノード」と呼ぶことにする。また、読みは、空文字列、品詞も、それぞれ、「文頭ノード」、「文末ノード」とする。
【００１６】
図５２は、ＣＹＫ表の例である。入力文は、「畜産物価格安定法」とし、１文の解析が終わった状態になっている。Ｉ行目、Ｊ列目には、表記が入力文のＪ文字目からＩ文字目までに一致する形態素列が記入される。処理の開始時には、辞書に登録されている形態素のみが表に格納され、形態素同士の連結処理によりできた［１］〜［２６］のような形態素列が随時追加されていく。［１］〜［２６］で表される形態素列を図５３に示す。以下、表のＩ行Ｊ列目の欄をＴ（Ｉ、Ｊ）と記述する。
【００１７】
図５４は、従来のコスト最小法形態素解析アルゴリズムの例を示すフローチャートである。
【００１８】
図５５は、従来の装置におけるコスト最小解の選択方法を説明した図である。図５２のＴ（入力文の文字数＋２、１）の形態素列が、形態素解析の結果となるが、これをグラフ形式で表すと図５５のようになる。各アークには、形態素の接続コスト（下線のない値）がついている。以下のようにして、各ノードに、文頭からのアークの和の最小値を付与する。まず、文頭のノードに０を付与する。値のついているノードについて、その値に入力アークについているコストを加え、コストの和（下線のついている値）をアークに付与する。出力アークすべてにコストの和が付与されたノードについては、コストの和のうち最も小さな値を付与する。このようにして、ノードにコストの和を付与する。すべてのノードについてコストの和が設定されたら、文末からノードに付与されている値と同じコストの和の値が付与されているアークを辿り、そのパス上にある形態素を取り出すことによりコスト最小解を得ることができる。ノードの値に等しい値を持つアークは１つとは限らないため、コスト最小解は一意に決まるとは限らない。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
しかし、従来の形態素解析装置では、図５２のＣＹＫ表を生成してからコスト最小解を決定する構成を取っているため、使用するメモリ容量が大きくなるという問題点があった。また、メモリ容量を減らすために、個々の形態素の優先度を評価することによりＣＹＫ表の列の要素を削除する方法もあるが、形態素単独では優先度が低くても、入力文の形態素列を構成する形態素である場合もあり、精度の低下をまねくという問題点があった。
【００２０】
本発明は、精度が高いというコスト最小法を用いた形態素解析装置の利点を残したままで、メモリ容量の使用量が小さい、日本語形態素解析装置を提供することを目的とする。
【課題を解決するための手段】
【００２１】
そのために、日本語形態素解析装置は、辞書検索手段、形態素列同士の接続可能性を判断する接続可能性判定手段、接続コスト計算手段を備えた日本語形態素解析装置において、更に、前接連結処理制御手段、前接連結処理優先不要形態素列削除手段を設け、辞書検索と同時に前接連結処理を行う単語を選択し、不要となった形態素列を逐次削除することにより形態素解析を行うことを特徴としている。
【００２２】
また、本発明の日本語形態素解析装置は、更に、形態素枝刈り手段、形態素枝刈り制御手段を備え、同一文字位置から始まる形態素のうちコストの大きい形態素を枝刈りしてＣＹＫ表から削除すると共に、枝刈りされた形態素を必要に応じてＣＹＫ表に戻すようにしたことを特徴としている。
【００２３】
また、本発明の日本語形態素解析装置は、前記形態素枝刈り制御手段は、同じ文字位置で優先順位が最大の単語について、ＣＹＫ表で連結可能な後続形態素を見出すことができない場合に、枝刈りした形態素の中から後接形態素を探索し、連結可能な形態素が見つかった場合に、その形態素を枝刈りされていない単語としてＣＹＫ表に戻すことを特徴としている。
【発明の効果】
【００２４】
本発明の日本語形態素解析装置によれば、辞書検索手段、形態素列同士の接続可能性を判断する接続可能性判定手段、接続コスト計算手段を備えた日本語形態素解析装置において、更に、前接連結処理制御手段、前接連結処理優先不要形態素列削除手段を設け、辞書検索と同時に前接連結処理を行う単語を選択し、不要となった形態素列を逐次削除することにより形態素解析を行う構成としたので、辞書検索後すぐに連結処理を行うため、処理のステップ数が減少し、辞書検索と連結処理の切換えのオーバーヘッドが少なくなるため処理速度が向上する。
【００２５】
また、形態素枝刈り手段、形態素枝刈り制御手段を備え、同一文字位置から始まる形態素のうちコストの大きい形態素を枝刈りしてＣＹＫ表から削除すると共に、枝仮された形態素を必要に応じてＣＹＫ表に戻す構成としたので、枝刈りの閾値を変えることにより、使用メモリ量を可変にすることができる。
【００２６】
さらに、前記形態素枝刈り制御手段は、同じ文字位置で優先順位が最大の単語について、ＣＹＫ表で連結可能な後続形態素を見出すことができない場合に、枝刈りした形態素の中から後接形態素を探索し、連結可能な形態素が見つかった場合に、その形態素を枝刈りされていない単語としてＣＹＫ表に戻す構成としたので、使用メモリ量を削減した場合の、枝刈りによる性能低下を低減できる。
【発明を実施するための最良の形態】
【００２７】
（第１の実施の形態）
図１は、第１の実施の形態における装置構成図である。１０１は形態素解析を行う日本語仮名漢字混じり文を入力する入力モジュール、１０２は同じ文字位置から始まる形態素の後接連結処理をまとめて行う後接連結処理優先ＣＹＫ表生成モジュール、１０３は形態素列を出力する出力モジュール、１０４は入力文の各文字位置で最左部分語を検索してＣＹＫ表に書き込む辞書検索モジュール、１０５は形態素の表記、読み、品詞、左側接続属性、右側接続属性等を格納する形態素辞書、１０６は後接連結処理が行えるように必要な辞書検索をまとめておこなう辞書検索制御モジュール、１０７は形態素列同士の接続可能性を判定する接続可能性判定モジュール、１０８は前接形態素列の右側の属性と後接形態素の左側の属性とが接続可能な組み合わせかどうか記録した接続表、１０９は接続可能な形態素列同士の接続コストを計算する接続コスト計算モジュール、１１０は接続コスト計算に用いる接続コスト表、１１１はＣＹＫ表において入力文全体の形態素列を生成する上で不要となった形態素列を削除する連結処理優先不要形態素列削除モジュールである。
【００２８】
第１の実施の形態で用いるＣＹＫ表は、図２のデータ構造で実装する。辞書から検索された形態素は、図２のような入力文での形態素の先頭の文字位置毎に双方向リストで結合する。各リストは、文字毎に用意された変数ｔ［Ｊ］（Ｊは形態素の先頭文字位置）から参照する。双方向リストでは、形態素の末尾の文字位置に関係なく１つの双方向リストに登録する。また、各文字位置毎に、その文字位置から始まる形態素のうち、最も表記が長い形態素の表記長をＭＡＸ＿ＬＥＮ［Ｊ］に記録する（Ｊは先頭文字位置）。
【００２９】
図３は図２中の双方向リストのノードの構造である。形態素列は、形態素から前接形態素へリンクを張ることにより表す。第１の実施の形態では、後述するように、前接形態素へのリンクは必ず１つ以下になり、リンクは、文頭まで一意に辿ることができる。従って、各形態素のノードは、同時に文頭からその形態素までの形態素列も表している。
【００３０】
以下、第１の実施の形態における装置の動作を説明する。まず、入力モジュール１０１に仮名漢字混じり文が入力される。入力モジュールは、文字列を連結処理優先ＣＹＫ表生成モジュール１０２に送る。
【００３１】
後接連結処理優先ＣＹＫ表生成モジュール１０２は、入力文の先頭に「＃＾」、入力文の末尾に「＃＄」を追加したうえで、図４のフローチャートに従って形態素解析を行う。
【００３２】
図４のフローチャートについて説明する。図５４に示した従来のアルゴリズムとの違いは、後続連結処理に必要な部分についてだけ辞書検索を行うこと、形態素列に形態素の接続コストの和がついていること、形態素の連結処理の際に接続可能性のチェックだけでなくコストの比較を行うこと、及び、解析途中で不要となった形態素列を削除することである。フローチャートの中で、形態素列は先頭位置と末尾位置を指定するが、第１の実施の形態では、末尾位置は無視して、先頭位置で決まる双方向リストを辿ることにより参照する。
【００３３】
ステップＳ１０１において文の文字数の設定する。ステップＳ１０２からＳ１０３，Ｓ１０２ａ、Ｓ１０２ｂは、ＣＹＫ表の初期化を行う。これは、図２の双方向リストへの参照を格納する変数ｔ［Ｊ］のポインタを初期化することに相当する。
【００３４】
ステップＳ１０４、Ｓ１０５は、１文字目の位置での辞書検索である。文頭と文末に追加した文字は特殊な文字であり、表記の長さが１の単語が１つだけが検索される。辞書検索は、辞書検索モジュール１０４を介して、形態素辞書１０５を検索する。
【００３５】
ステップＳ１０６は、次の辞書検索位置として２文字目を指定する処理である。
【００３６】
ステップＳ１０７からステップＳ１１８までの処理は、Ｉ文字目での後続形態素との連結処理である。Ｉは入力文の１文字目から、最後から２文字目までの値を順次設定する。
【００３７】
ステップＳ１０８〜Ｓ１１２までの処理は、Ｉ文字目から始まる形態素の、表記の文字数が最も多い形態素の終わりの文字位置まで辞書検索が終わっているかどうかをチェックし、辞書検索が終わっていない場合は、辞書検索を行い、辞書検索が終わった次の位置をＪに設定する処理である。この処理は、辞書検索制御モジュール１０６が行う。
【００３８】
ステップＳ１１３〜Ｓ１１６の前までの処理は、ＫとＬをパラメータとした形態素列の連結処理（繰り返し処理）である。連結処理は、接続判定モジュール１０６、接続表１０７、接続コスト計算モジュール１０８、接続コスト表１０９により行われる。
【００３９】
この方法は、（１）接続表の接続可能性を満足し、（２）統合すべき形態素列が無いか、或いは統合の対象である形態素列より接続コストが小さい場合のみ連結を許可することとする。統合が必要となった場合には、統合の対象となる形態素列（最大１つしかあり得ない）を連結する前の状態に戻してから、形態素列を追加する。従って、統合処理は行われない。連結した形態素列には、連結前の前接形態素列のコストに、２つの形態素列の接続コストを加えた値を記録する。
【００４０】
上述の通り、連結の方法は、従来のアルゴリズムよりチェックの条件が厳しくなっている。即ち、接続が可能な場合、連結してできる形態素列の先頭から末尾までの形態素の接続コストの和を計算し、既にＣＹＫ表にある、形態素列の末尾の形態素が同じ形態素列とコストを比較し、コストが小さい場合に限って、比較した形態素列をＣＹＫ表から削除し、新たにＣＹＫ表に追加する。この場合、置き換えの対象となる以前からある形態素列は、最後の形態素に対しての連結前の状態に戻される。
【００４１】
ステップＳ１１６、Ｓ１１７は、不要となった形態素列をＣＹＫ表から削除する処理である。この処理は、後接連結処理優先不要形態素列削除モジュール１１１が行う。
【００４２】
ステップＳ１１６の処理は、文字位置がＩ＋１文字目から始まる形態素は、I文字目から始まる形態素との連結処理が終了した時点で、前接形態素と連結していなければ、それ以降、前接連結処理が成功する可能性はないので、このような形態素をすべてＣＹＫ表から削除する処理である。
【００４３】
また、ステップＳ１１７の処理は、表記の先頭の位置がI文字目から始まる形態素で、後接形態素と連結が行われていない形態素は、これ以降の処理で後接連結する可能性はないため、このような形態素列をすべてＣＹＫ表から削除する処理である。後続形態素と連結処理ができているかどうかは、後続形態素数がゼロかどうかで判定できる。さらに、削除する形態素の前接形態素で、後続形態素数がゼロになってしまう形態素を、前接形態素へのリンクを辿りながら削除していく。
【００４４】
ステップＳ１１９〜Ｓ１２１の処理は、Ｔ（Ｎ、１）にコスト最小解となるただ１つの形態素列が生成されているかどうかを判定する処理である。この判定は、後接連結処理優先ＣＹＫ表作成モジュール１０２が行う。解析の正否の結果、及び、得られた形態素列は、出力モジュール１０３により出力される。
【００４５】
図４のフローチャートによる処理を、例を用いて説明する。ステップＳ１０１からステップＳ１０４の前までの初期化処理の後、ステップＳ１０４、Ｓ１０５で、文頭ノードを設定し、ステップＳ１０６で次の辞書検索位置を設定し、さらに、ステップＳ１０７〜Ｓ１１８のループを実行する。
【００４６】
図５は、Ｉ＝１として、ステップＳ１１２までの処理が終了した状態である。１文字目の単語（文頭ノード）の表記は１文字であるため、２文字目までについて、その位置以降の入力文の最左部分語を単語辞書から検索して、「畜産物」と「畜産」の２つの単語が検索されている。
【００４７】
図６は、さらに、ステップＳ１１３から、ステップＳ１１６の前までの処理が終了し、連結処理が終わった状態である。即ち、Ｉ（＝１）文字目から始まる単語の後接処理が行われ、「畜産物」、「畜産」の２つの単語から文頭ノードへリンクが張られている。この時点で、Ｉ（＝１）文字目から始まる単語（文頭ノードのみ）で後接語がないものはなく、２文字目から始まる単語（「畜産物」と「畜産」）で前接語がないものはないため、ステップＳ１１６、Ｓ１１７では、何も処理されない。
【００４８】
ステップＳ１０７ａの判定で”Ｎ”と判定されると、ステップＳ１０７ｂを介してステップＳ１０８に戻り、Ｉ＝２として処理が進む。ステップＳ１０８〜Ｓ１１２で、Ｉ（＝２）文字目から始まる単語で最も長いものは、「畜産物」であるため、Ｉ＋ＭＡＸ＿ＬＥＮ［Ｉ］（＝５）文字目まで辞書検索を行う。図７は、辞書検索が終わった状態である。
【００４９】
図７の状態から処理が進んで、ステップＳ１１３〜Ｓ１１６の前までの処理で連結処理を行った状態が図８である。ここで、単語同士の接続可能性、及び、接続コストの大きさの大小関係については、説明上、恣意的に決定した。例えば、「畜産物」と「物価」とは、接続しないとした。実際のシステムでは、このような制約が事前に作成されて用いられる。「価格」、「価」等についても、接続可能性や、接続コストの大小関係を、恣意的に決定した。
【００５０】
次に、ステップＳ１１６、Ｓ１１７の処理が適用されて、図９の状態になる。以下、同様の処理により、図２５まで処理が進む。この状態では、ステップＳ１０７ａで、Ｉ＝Ｎ−１（＝９）であるため、処理がステップＳ１１９へ移る。図２５の［２６］は、Ｔ（１０、１）（１文字目から１０文字目までの文字列に対応する単語列）になっているため、Ｔ（Ｎ、１）≠０であり、処理がステップＳ１２０へ移り、形態素解析が成功する。図２５の単語分割が解析結果となる。
【００５１】
以上説明したように、本発明の第１の実施の形態によれば、下記の効果が得られる。
【００５２】
（１）辞書検索によりＣＹＫ表に追加される形態素のうち、未処理のままＣＹＫ表に保持する形態素を少なくできるため、装置が使用するメモリ容量を減少させることができる。
【００５３】
（２）ＣＹＫ表において不要になった形態素を随時削除するため、装置が使用するメモリ容量を減少させることができる。
【００５４】
（３）辞書引きは同じ文字列から始まる形態素をまとめて検索するが、形態素を先頭の文字位置で管理するため、辞書引きした形態素をデータ構造に格納する処理が簡単になり、処理を高速にすることができる。
【００５５】
第２の実施の形態図２６は、第２の実施の形態における装置構成図である。２０１及び２０３〜２０９の構成要素は、第１の実施の形態の１０１及び１０３〜１０９と同様の構成要素である。２０２は同じ文字位置から始まる単語の前接連結処理をまとめて行うことによりＣＹＫ表を生成する前接連結処理優先ＣＹＫ表生成モジュール、２１０は前接連結処理を行う単語を選択する連結処理制御モジュール、２１１は不要になった形態素列を削除する前接連結処理優先不要形態素列削除モジュールである。
【００５６】
第２の実施の形態で用いるＣＹＫ表は、図２７のデータ構造で実装する。辞書から検索された形態素は、図２７のような入力文での形態素の末尾の文字位置毎に双方向リストで結合する。各リストは、文字毎に用意された変数ｔ'［Ｉ］（Ｉは形態素の末尾の文字位置）から参照する。また、各文字位置毎に、その文字位置から始まる形態素のうち、最も表記が長い形態素の表記長をＭＡＸ＿ＬＥＮ［Ｊ］に記録する（Ｊは先頭の文字位置）。ＭＡＸ＿ＬＥＮ［］については、第１の実施の形態と同じく、形態素の先頭文字位置で参照する。
【００５７】
以下、第２の実施の形態における装置の動作を説明する。まず、入力モジュール２０１に仮名漢字混じり文が入力される。入力モジュールは、前接連結処理優先ＣＹＫ表生成モジュール２０２に送られる。
【００５８】
前接連結処理優先ＣＹＫ表生成モジュール２０２は、第１の実施の形態と同じく、入力文の先頭に「＃＾」、入力文の末尾に「＃＄」を追加したうえで、図２８に示したフローチャートに従って処理を進める。
【００５９】
図２８のフローチャートについて説明する。第１の実施の形態のフローチャートとの違いは、第１の実施の形態においては、辞書検索を先行して行うことにより、同じ文字位置から始まるすべての形態素の後接連結処理を一度に行っていたのに対し、第２の実施の形態では、辞書検索を行うたびに同じ文字から始まる形態素の前接連結処理を一度にまとめて行うことである。
【００６０】
ステップＳ２０１では、文の文字数の設定を行う。
【００６１】
ステップＳ２０２からＳ２０４の前までの処理は、ＣＹＫ表の初期化処理である。これは、図２７の双方向リストへの参照を格納する変数ｔ［Ｉ］のポインタを初期化する。
【００６２】
ステップＳ２０４からＳ２１２の前までの処理は、辞書検索を入力文の１文字目から、最後の文字の位置まで、１文字ずつずらしながら行い、前接連結処理を行う処理である。ステップＳ２０７からＳ２１１までの処理は、辞書検索をした文字位置が２文字目以降の場合に実行する処理であり、ステップＳ２１０の処理は、辞書検索位置が２文字目以降であれば、辞書検索で取り出された形態素と、それより前にある形態素列との連結処理を行い、連結処理が失敗した形態素はＣＹＫ表から削除する処理である。
【００６３】
第２の実施の形態における連結処理（ステップＳ２０９）は、第１の実施の形態の連結処理と同様である。連結処理は、第１の実施の形態と同様に、接続判定モジュール２０６、接続表２０７、接続コスト計算モジュール２０８、接続コスト表２０９により行われる。
【００６４】
ステップ２１１の処理は、Ｊ−１文字目で終わる形態素列で後接語との連結処理が成功していないものについては、これ以降連結処理が行われる可能性がないので、ＣＹＫ表から削除し、削除する形態素の前接形態素で、後接形態素数が０になってしまう形態素もあわせて削除する処理である。
【００６５】
ステップＳ２１２からＳ２１４は、Ｔ（Ｎ、１）にコスト最小解となるただ１つの形態素列が生成さている解析かどうかを判定する処理である。この判定は、前接連結処理優先ＣＹＫ表作成モジュール２０２が行う。解析の正否の結果、及び、得られた形態素列は、出力モジュール２０３により出力される。
【００６６】
図２８のフローチャートを、例を用いて説明する。ステップＳ２０１からＳ２０４の前までで初期化処理を行う。ステップＳ２０４からＳ２１２の前までの処理において、まず、Ｊ＝１では、１文字目から始まる単語の辞書検索だけが行われ、文頭ノードが取り出される。図２８以降の、各図において、Ｊ文字目で終わる単語のリストを作る処理があるが、これは、ステップＳ２０５の処理に含まれる。Ｊ＝１では、ステップＳ２０８からＳ２１１の処理はスキップされる。次に、Ｊ＝２では、ステップＳ２０５、Ｓ２０６により、２文字目から始まる単語が取り出され、ステップＳ２０８〜Ｓ２１１の連結処理が行われ、図２９の状態になる。
【００６７】
次に、ステップＳ２０５に戻り、Ｊ＝３として処理が進むが、Ｊ（＝３）文字目から始まる単語がないため、ステップＳ２０７〜Ｓ２１１では、何も行わず、ステップＳ２０４ａ及びＳ２０４ｂを介して、ステップＳ２０５に戻り、Ｊ＝４として処理が実行される。
【００６８】
ステップＳ２０５、Ｓ２０６で、Ｊ（＝４）文字目から始まる単語が取り出される。ステップＳ２０７〜Ｓ２１１で連結処理が行われ、図３０の状態になる。ここでも、第１の実施の形態と同様に、単語同士の接続可能性、及び、接続コストの大きさの大小関係については、説明上、恣意的に決定した。ただし、設定は第１の実施の形態と同じ設定にした。
【００６９】
以下、同様の処理により、図４４まで処理が進む。ここで、ステップＳ２０４ａで、Ｊ＝Ｎ（＝１０）であるため、ステップＳ２１２の処理に移る。図４４の［２６］は、Ｔ（１０、１）（１文字目から１０文字目までの文字列に対応する単語列）になっているため、Ｔ（Ｎ、１）≠０であり、ステップＳ２１３へ移り、形態素解析が成功する。図４４の単語分割が解析結果となる。
【００７０】
第１の実施の形態と同様に、辞書検索結果、及び、接続可能性の設定によっては、図４４のように、文頭ノードから文末ノードまでが接続した結果が得られない場合には、Ｔ（Ｎ、１）＝０になり、ステップＳ２１４へ移り、解析が失敗する。
【００７１】
以上、説明したように、第２の実施の形態によれば、下記の効果が得られる。
【００７２】
（１）辞書検索によりＣＹＫ表に追加される形態素のうち、未処理のままＣＹＫ表に保持する形態素を少なくできるため、装置が使用するメモリ容量を減少させることができる。
【００７３】
（２）ＣＹＫ表において不要になった形態素を随時削除するため、装置が使用するメモリ容量を減少させることができる。
【００７４】
（３）辞書検索位置を１文字進める毎に連結チェックをすることができるため、ＣＹＫ表に追加される連結未チェックの形態素が減り、装置が使用するメモリ容量を減少させることができる。
【００７５】
第３の実施の形態図４５は、第３の実施の形態における装置構成図である。３０１〜３１１の構成要素は、第２の実施の形態における各要素と同様である。３１２は連結処理の前に、同じ文字位置から始まる形態素をコストの小さい順番にソートする形態素ソートモジュール、３１３は形態素の優先度を計算する形態素優先度計算モジュール、３１４は形態素ソートモジュール３１２がソートした形態素の集合に対して、コストの大きい形態素を枝刈りしてＣＹＫ表から削除する形態素枝刈りモジュール、３１５は枝刈りされた形態素を必要に応じてＣＹＫ表に戻す形態素枝刈り制御モジュールである。
【００７６】
以下、第３の実施の形態における装置の動作を説明する。処理の流れは、第２の実施の形態と同様であるが、以下の２点が異なる。第１に、辞書検索後に同じ文字位置から始まる形態素について、形態素優先度計算モジュール３１３により、各形態素の優先度を計算し、さらに、形態素ソートモジュール３１２が優先度の値を用いて形態素をソートする。また、形態素枝刈りモジュール３１４が、優先度の値に閾値を設ける。
【００７７】
入力文のJ文字目から始まる形態素をソートした、優先度付きの集合をＳｏｒｔ（Ｊ）、優先度が閾値を越える形態素の順序付き集合をＳｏｒｔＢｅａｍ（Ｊ）とする。Ｓｏｒｔ（Ｊ）は、第２の実施の形態における双方向リストと別の双方向リストを設け、ノードの順序を優先度の順にソートすることで実現する。ＳｏｒｔＢｅａｍ（Ｊ）は、閾値を越えるノードのうちで、優先度が最小のノードを記憶することで実現する。閾値は、例えば、Ｊ文字目から始まる形態素について、「（最大の優先度―最小の優先度）÷２」のようにして決めることができる。以下、ＳｏｒｔＢｅａｍ（Ｊ）ＣはＳｏｒｔ（Ｊ）に含まれ、かつ、ＳｏｒｔＢｅａｍ（Ｊ）に含まれない単語の優先度による順序付き集合を示す。
【００７８】
第２に連結処理の方法が異なる。この連結処理の方法を示す。連結処理は具体的には、Ｔ（Ｊ＋ＬＥＮ＿Ｙ−１，１）＝Ｔ（Ｊ＋ＬＥＮ＿Ｙ−１，１）
∪（Ｔ（Ｊ＋ＬＥＮ＿Ｙ−１，Ｊ）＊Ｔ（Ｊ−１，１））
の式を用いて行われるが、この式自体は、第２の実施の形態における図２８のステップ２０９における連結処理の式のＫの値をＬＥＮ＿Ｙに置き換えたものである。この場合の連結の方法は、次のステップにより行われる。全てのｘ∈Ｔ（Ｊ−１，１）について行う。ｘの最後の単語の表記長をＬＥＮ＿Ｘとする。また、後接単語長をＬＥＮ＿Ｙとする。
【００７９】
（１）ｘがＳｏｒｔ（Ｊ−ＬＥＮ＿Ｘ）で優先度最大の単語の場合は、先ず、∈Ｔ（Ｊ＋ＬＥＮ＿Ｙ−１，Ｊ）∩ＳｏｒｔＢｅａｍ（Ｊ）と連結処理を行う。全ての連結処理が失敗した場合には、ｙ∈Ｔ（Ｊ＋ＬＥＮ＿Ｙ−１，Ｊ）∩ＳｏｒｔＢｅａｍ（Ｊ）Ｃについて、Ｓｏｒｔ（Ｊ）の優先度の高い順に連結が成功するまで連結処理を試みる。１つの連結処理が成功したところでｙとの連結処理を中止する。連結処理が成功した場合にはｙをＳｏｒｔＢｅａｍ（Ｊ）ＣからＳｏｒｔＢｅａｍ（Ｊ）へ優先度が最も低い要素になるようにして移動する。
【００８０】
（２）ｘの最後の単語がＳｏｒｔ（Ｊ−ＬＥＮ＿Ｘ）の優先度最大の単語でない場合は、ｙ∈Ｔ（Ｊ＋ＬＥＮ＿Ｙ−１，Ｊ）∩ＳｏｒｔＢｅａｍ（Ｊ）と連結処理を行う。
【００８１】
連結処理は、基本的に、ＳｏｒｔＢｅａｍ（）に含まれる形態素列同士で行うが、前接形態素列が、ＳｏｒｔＢｅａｍ（）中で優先度最大の形態素列であるときは、まず、ＳｏｒｔＢｅａｍ（）中の形態素と連結処理を行い、連結処理が失敗した場合は、後接形態素をＳｏｒｔＢｅａｍ（）に含まれない形態素にまで広げて連結処理を行い、１つでも連結処理が成功した時点で、優先度最大の前接形態素列の処理を終了する。
【００８２】
連結処理の流れを例で説明する。説明の都合上、各形態素のＳｏｒｔＢｅａｍ（２）、ＳｏｒｔＢｅａｍ（３）、 ＳｏｒｔＢｅａｍ（４）は、図４６のようになっていると仮定する。図４７にＪ＝５として、連結処理を開始する直前の状態を示す。
【００８３】
このような条件の下で連結処理を行うと、まず、［２］に対しては、図４８のように、ＳｏｒｔＢｅａｍ（５）に含まれる要素として、［価／動／アタイ］との連結処理が行われ、接続可能性の仮定からこの連結処理は失敗する。
【００８４】
ＳｏｒｔＢｅａｍ（５）に含まれる形態素はもうないので、次に、ＳｏｒｔＢｅａｍ（５）Ｃの形態素について、優先度の大きい方から順に連結処理を行う。
【００８５】
図４９では、「価格／名／カカク」との処理が行われ、仮定からこの連結処理が成功し［８］が生成される。この時点で連結処理は終了し、第２の実施の形態と同じ不要形態素削除処理を行うことにより、図５０の状態になる。
【００８６】
以上説明したように、第３の実施の形態によれば、以下の効果が得られる。
【００８７】
（１）辞書検索した形態素を枝刈りしてＣＹＫ表から除くことにより、除いた形態素と連結されることによりＣＹＫ表に残る形態素列を減らすことができ、装置が使用するメモリ容量を減らすことができる。
【００８８】
（２）枝刈りによりＣＹＫ表から削除された形態素の中に正しい形態素列生成に不可欠なものがあった場合に、直前の形態素の条件によりＣＹＫ表に戻される可能性があるため、枝刈りによる精度低下を少なくすることができる。
【００８９】
尚、本発明は前述の実施の形態に限定されるものではなく、本発明の趣旨に基づいて種々の変形が可能である。即ち、第１の実施の形態〜第３の実施の形態は、単体の装置として構成したが、テキスト音声変換等の自然言語処理を用いた装置の一部として用いることができる。
【図面の簡単な説明】
【００９０】
【図１】第１の実施の形態における装置構成図である。
【図２】第１の実施の形態におけるＣＹＫ表のデータ構造である。
【図３】連結リストのノード構造である。
【図４】第１の実施の形態におけるＣＹＫ表作成フローチャートである。
【図５】第１の実施の形態における形態素解析の処理過程（１）である。
【図６】第１の実施の形態における形態素解析の処理過程（２）である。
【図７】第１の実施の形態における形態素解析の処理過程（３）である。
【図８】第１の実施の形態における形態素解析の処理過程（４）である。
【図９】第１の実施の形態における形態素解析の処理過程（５）である。
【図１０】第１の実施の形態における形態素解析の処理過程（６）である。
【図１１】第１の実施の形態における形態素解析の処理過程（７）である。
【図１２】第１の実施の形態における形態素解析の処理過程（８）である。
【図１３】第１の実施の形態における形態素解析の処理過程（９）である。
【図１４】第１の実施の形態における形態素解析の処理過程（１０）である。
【図１５】第１の実施の形態における形態素解析の処理過程（１１）である。
【図１６】第１の実施の形態における形態素解析の処理過程（１２）である。
【図１７】第１の実施の形態における形態素解析の処理過程（１３）である。
【図１８】第１の実施の形態における形態素解析の処理過程（１４）である。
【図１９】第１の実施の形態における形態素解析の処理過程（１５）である。
【図２０】第１の実施の形態における形態素解析の処理過程（１６）である。
【図２１】第１の実施の形態における形態素解析の処理過程（１７）である。
【図２２】第１の実施の形態における形態素解析の処理過程（１８）である。
【図２３】第１の実施の形態における形態素解析の処理過程（１９）である。
【図２４】第１の実施の形態における形態素解析の処理過程（２０）である。
【図２５】第１の実施の形態における形態素解析の処理過程（２１）である。
【図２６】第２の実施の形態における装置構成図である。
【図２７】第２の実施の形態におけるＣＹＫ表のデータ構造である。
【図２８】第２の実施の形態におけるＣＹＫ表作成フローチャートである。
【図２９】第２の実施の形態における形態素解析の処理過程（１）である。
【図３０】第２の実施の形態における形態素解析の処理過程（２）である。
【図３１】第２の実施の形態における形態素解析の処理過程（３）である。
【図３２】第２の実施の形態における形態素解析の処理過程（４）である。
【図３３】第２の実施の形態における形態素解析の処理過程（５）である。
【図３４】第２の実施の形態における形態素解析の処理過程（６）である。
【図３５】第２の実施の形態における形態素解析の処理過程（７）である。
【図３６】第２の実施の形態における形態素解析の処理過程（８）である。
【図３７】第２の実施の形態における形態素解析の処理過程（９）である。
【図３８】第２の実施の形態における形態素解析の処理過程（１０）である。
【図３９】第２の実施の形態における形態素解析の処理過程（１１）である。
【図４０】第２の実施の形態における形態素解析の処理過程（１２）である。
【図４１】第２の実施の形態における形態素解析の処理過程（１３）である。
【図４２】第２の実施の形態における形態素解析の処理過程（１４）である。
【図４３】第２の実施の形態における形態素解析の処理過程（１５）である。
【図４４】第２の実施の形態における形態素解析の処理過程（１６）である。
【図４５】第３の実施の形態における装置構成図である。
【図４６】優先度付きの集合の例である。
【図４７】第３の実施の形態における形態素解析の処理過程（１）である。
【図４８】第３の実施の形態における形態素解析の処理過程（２）である。
【図４９】第３の実施の形態における形態素解析の処理過程（３）である。
【図５０】第３の実施の形態における形態素解析の処理過程（４）である。
【図５１】従来の日本語形態素解析装置の構成の例である。
【図５２】ＣＹＫ表の例である。
【図５３】連結した単語列の例である。
【図５４】従来のコスト最小法形態素解析フローチャートである。
【図５５】コスト最小解の選択方法を示す図である。
【符号の説明】
【００９１】
１０１  入力モジュール
１０２  後接連結処理優先ＣＹＫ表生成モジュール
１０３  出力モジュール
１０４  辞書検索モジュール
１０５  形態素辞書
１０６  辞書検索制御モジュール
１０７  接続可能性判定モジュール
１０８  接続表
１０９  接続コスト計算モジュール
１１０  接続コスト表
１１１  後接連結処理優先不要形態素列削除モジュール
【図１】
2008217817.tif 000003
【図２】
2008217817.tif 000004
【図３】
2008217817.tif 000005
【図４】
2008217817.tif 000006
【図５】
2008217817.tif 000007
【図６】
2008217817.tif 000008
【図７】
2008217817.tif 000009
【図８】
2008217817.tif 000010
【図９】
2008217817.tif 000011
【図１０】
2008217817.tif 000012
【図１１】
2008217817.tif 000013
【図１２】
2008217817.tif 000014
【図１３】
2008217817.tif 000015
【図１４】
2008217817.tif 000016
【図１５】
2008217817.tif 000017
【図１６】
2008217817.tif 000018
【図１７】
2008217817.tif 000019
【図１８】
2008217817.tif 000020
【図１９】
2008217817.tif 000021
【図２０】
2008217817.tif 000022
【図２１】
2008217817.tif 000023
【図２２】
2008217817.tif 000024
【図２３】
2008217817.tif 000025
【図２４】
2008217817.tif 000026
【図２５】
2008217817.tif 000027
【図２６】
2008217817.tif 000028
【図２７】
2008217817.tif 000029
【図２８】
2008217817.tif 000030
【図２９】
2008217817.tif 000031
【図３０】
2008217817.tif 000032
【図３１】
2008217817.tif 000033
【図３２】
2008217817.tif 000034
【図３３】
2008217817.tif 000035
【図３４】
2008217817.tif 000036
【図３５】
2008217817.tif 000037
【図３６】
2008217817.tif 000038
【図３７】
2008217817.tif 000039
【図３８】
2008217817.tif 000040
【図３９】
2008217817.tif 000041
【図４０】
2008217817.tif 000042
【図４１】
2008217817.tif 000043
【図４２】
2008217817.tif 000044
【図４３】
2008217817.tif 000045
【図４４】
2008217817.tif 000046
【図４５】
2008217817.tif 000047
【図４６】
2008217817.tif 000048
【図４７】
2008217817.tif 000049
【図４８】
2008217817.tif 000050
【図４９】
2008217817.tif 000051
【図５０】
2008217817.tif 000052
【図５１】
2008217817.tif 000053
【図５２】
2008217817.tif 000054
【図５３】
2008217817.tif 000055
【図５４】
2008217817.tif 000056
【図５５】
2008217817.tif 000057