(57)【特許請求の範囲】
【請求項１】
原文内の文字列の範囲を決定する決定部と、
前記決定部により決定された範囲内に含まれるトークンを、トークン毎に正規化し、正規化した前記トークンを連結して連結トークン文字列を作成し、該連結トークン文字列が規定長に達している場合、前記連結トークン文字列を前記規定長で打ち切り、前記打ち切りトークン文字列のハッシュ値を算出し、算出した前記ハッシュ値に対応付けられた用語を、ハッシュ値と用語とが対応付けられて事前に登録されている記憶部から、１つまたは複数取得する検索部と、
を有する言語処理装置。
【請求項２】
請求項１に記載の言語処理装置において、
前記検索部は、文の区切り文字としても使用される規定文字が原文にある場合、正規化の前、または後に、前記規定文字の前方にあるトークンの順序を、トークン単位もしくは文字単位で逆順にし、該逆順のトークン文字列を連結して連結トークン文字列を作成する言語処理装置。
【請求項３】
請求項１または２に記載の言語処理装置において、さらに、
用語を登録するためのデータに記述された登録用語の文字列を取得し、該登録用語文字列内に含まれるトークンを、トークン毎に正規化し、正規化した前記トークンを連結して連結トークン文字列を作成し、該連結トークン文字列が前記規定長に達している場合、前記連結トークン文字列を前記規定長で打ち切り、前記打ち切りトークン文字列のハッシュ値を算出し、算出した前記ハッシュ値と、前記登録用語文字列とを対応付けて前記記憶部に登録する登録部を有する言語処理装置。
【請求項４】
コンピュータに、
原文内の文字列の範囲を決定させ、
決定された範囲内に含まれるトークンを、トークン毎に正規化させ、
正規化された前記トークンを連結して連結トークン文字列を作成させ、
前記連結トークン文字列が規定長に達している場合、前記連結トークン文字列を前記規定長で打ち切らせ、
前記打ち切りトークン文字列のハッシュ値を算出させ、
算出された前記ハッシュ値に対応付けられた用語を、ハッシュ値と用語とが対応付けられて事前に登録されている記憶部から、１つまたは複数取得させる
ためのプログラム。
【請求項５】
コンピュータが、
原文内の文字列の範囲を決定し、
決定した範囲内に含まれるトークンを、トークン毎に正規化し、
正規化した前記トークンを連結して連結トークン文字列を作成し、
前記連結トークン文字列が規定長に達している場合、前記連結トークン文字列を前記規定長で打ち切り、
前記打ち切りトークン文字列のハッシュ値を算出し、
算出した前記ハッシュ値に対応付けられた用語を、ハッシュ値と用語とが対応付けられて事前に登録されている記憶部から、１つまたは複数取得する
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、用語を格納したデータの構造および用語の検索方法に関する。
【背景技術】
【０００２】
情報検索システムやかな漢字変換システム、機械翻訳システムを代表とする多くの自然言語処理システムは、英語や日本語など、処理の対象となる言語の個々の単語の情報をあらかじめ機械可読辞書に格納しておき、処理対象となる自然言語文に対して機械可読辞書を用いた高速な辞書検索を行って、入力文の単語情報を解析する処理部を備えていることが多い。この辞書検索は通常形態素解析と呼ばれる処理で実行される。
【０００３】
日英翻訳システムでは、原文が日本語であるため、日本語の用語が登録された機械可読辞書を用いた日本語形態素解析システムを具備する。一方、英日翻訳システムでは、原文が英語であるため、英語の用語が登録された機械可読辞書を用いた英語形態素解析システムを具備する。
【０００４】
関連技術として、以下の文献が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０４−１０１２７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明が解決しようとする課題は、辞書検索の高速化を図ることが可能な技術を提供することである。
【課題を解決するための手段】
【０００７】
実施形態の言語処理装置は、決定部と、検索部とを有する。決定部は、原文内の文字列の範囲を決定する。検索部は、決定部により決定された範囲内に含まれるトークンを、トークン毎に正規化し、正規化したトークンを連結して連結トークン文字列を作成し、連結トークン文字列が規定長に達している場合、連結トークン文字列を規定長で打ち切り、打ち切りトークン文字列のハッシュ値を算出し、算出したハッシュ値に対応付けられた用語を、ハッシュ値と用語とが対応付けられて事前に登録されている記憶部から、１つまたは複数取得する。
【図面の簡単な説明】
【０００８】
【図１】原文の一例を示すとともに、辞書検索用のスパンの一例を示す図である。
【図２】原文と、辞書に登録されている見出しとの対応例を示す図である。
【図３】原文および辞書見出しを正規化し、ハッシュ値を算出して検索する処理の一例を説明する図である。
【図４】辞書見出しと、その見出しを正規化した結果との対応例を示す図である。
【図５】ピリオドやコロンを含む原文の一例を示す図である。
【図６】ピリオドが辞書見出し語の一部かどうかを判定するための処理を行う際に必要となるスパンのバリエーション例を示す図である。
【図７】実施形態の英語形態素解析システムの構成例を示す図である。
【図８】ｆｌａｔ辞書の一例を示す図である。
【図９】第１の課題を解消するための検索インデクス作成部の動作例を示す図である。
【図１０】第１の課題を解消するためのスパン決定部の動作例を示す図である。
【図１１】第１の課題を解消するための辞書検索部の動作例を示す図である。
【図１２】本実施形態のｆｌａｔ辞書を例示する図であり、辞書見出し、正規化文字列、打ち切り正規化文字列の一例を示す図である。
【図１３】本実施形態を適用した場合のハッシュ検索処理数の低減例を示す図である。
【図１４】第２の課題を解消するための検索インデクス作成部の動作例を示す図である。
【図１５】第２の課題を解消するためのスパン決定部の動作例を示す図である。
【図１６】第２の課題を解消するための辞書検索部の動作例を示す図である。
【図１７】ピリオドを含んだ原文を例示し、その原文についてのスパンのバリエーションを示した図である。
【図１８】図１７で示す原文に関するｆｌａｔ辞書の見出し、正規化文字列、逆順打ち切り正規化文字列を例示した図である。
【図１９】図１７で示す原文に対し、本実施形態を適用した場合のハッシュ検索処理数の低減例を示す図である。
【発明を実施するための形態】
【０００９】
本実施形態の説明に入る前に、まずは前提となる技術について説明する。
【００１０】
（前提技術）
＜辞書検索技術について＞
辞書検索技術・アルゴリズムは計算機工学の基本技術の１つであり、辞書検索技術やアルゴリズムについては各種の方式がある。多くの検索方式は、そこで用いられる木状のデータ構造の名前で呼ばれる。たとえば、ハッシュ検索、平衡木、Ｂ木、パトリシア木、サフィックス木、トライ木・トライ検索、ダブルアレイなどである。
【００１１】
これらの辞書検索方式は、検索速度や検索に必要なデータ構造（インデクス）の量、そのインデクスの作成速度、検索の仕方（部分一致検索ができるか否か等）にそれぞれ優劣があり、辞書検索が利用されるシーンやシステムで要求される仕様に応じて使い分けられている。
【００１２】
＜システム辞書、ユーザ辞書＞
機械翻訳システムでは、形態素解析に用いる機械可読辞書として、システムがあらかじめ備えているシステム辞書と、ユーザが後から作成するユーザ辞書との両方を備える場合が多い。たとえば日本語形態素解析では、システム辞書は「机」「動く」いった日常的に用いられる単語を含んだ基本辞書と、例えば「形態素解析」といった特定の分野で用いられる専門用語を格納した専門用語辞書とから構成される場合が多い。基本辞書はどのような文書の翻訳でも用いられるが、専門用語辞書は翻訳する文書の分野に応じてユーザが選択できるようになっている。
【００１３】
システム辞書の登録用語数は数十〜数百万語である場合が多く、高速な検索が必要とされる。しかしながら、システム辞書は機械翻訳システムのベンダが提供するものであり、ユーザがそこに登録されている用語を追加したり削除したりすることは想定されていない。よって、後から用語の追加・削除が行われることがないため、以下の事柄が実現可能となる。
（１）システム辞書のデータ構造および検索方式は軽量化および高速化を図ることができる。
（２）機械可読辞書の構築、つまり辞書検索用のインデクスの作成はベンダが一度だけ行えばよい。したがって、インデクス作成の遅い辞書検索方式であっても作成されたインデクスによる辞書検索速度が速い方が好ましい。
（３）計算機システム上でシステム辞書ファイルをアクセスするときはreadonly モードで十分である。これにより、排他制御の省略・システムの簡素化および検索の高速化を図ることができる。
【００１４】
一方、ユーザ辞書はユーザが後から用語を登録・削除して利用するものであり、システム辞書と要求仕様が異なってくる。具体的には
（１）ユーザ辞書でも近年は登録数が数十万規模になる場合もあり、１つの用語を追加、削除するために辞書全体のインデクスを作り直すことは現実的でない。そこで、部分的にインデクスを作り直すことができる辞書検索方式が必要となる。
（２）ユーザ辞書に対しては読み出しと書き込みの双方があるため、ファイルアクセスにはreadとwriteの両方が存在する。複数のユーザや翻訳プロセスが同一のユーザ辞書をアクセスする場合、必要に応じて排他制御が必要となる。
【００１５】
＜ユーザ辞書でのハッシュ検索の優位性＞
上述のように、ユーザ辞書の検索においては、部分的にインデクスを作り直すことができる辞書検索方式が必要となる。ダブルアレイ等の辞書検索方式は、部分的にインデクスを作り直すことが困難である。またパトリシア木やトライ木・トライ検索などでは、辞書登録数をｎとすると、検索インデクスはｎ＾２以上のサイズとなる。検索の高速化のため検索インデクスは通常メモリ上に保持される場合が多い。近年は辞書語数が数百万語になる場合も稀でない。したがって検索インデクスが巨大だと検索に巨大なメモリ量が必要となる。
【００１６】
このような事情、およびそのロジックが単純であることから、ユーザ辞書検索ではハッシュ検索を用いることが多い。
【００１７】
＜ハッシュ検索を用いた英語形態素解析用の辞書検索＞
ここで、ハッシュ検索を用いた英語形態素解析用の辞書検索について述べる。英語形態素解析に求められる機能には以下のものがある。
（１）辞書検索
英語形態素解析の基本機能である。英語の場合、基本的に単語間にはスペースやハイフン等の記号が存在する。一方"computer science" といった複数の単語からなる辞書見出しも存在する。このような事情から、英語の文章に対して原文のいろいろな範囲（スパン）について、その部分が辞書見出し語を構成していないか確認するために辞書引きを行う必要がある。
【００１８】
以降、本実施形態では、ハイフン、カンマ等の記号、スペースでセパレートされた文字列をトークンと呼ぶことにする。また、連続する任意のトークン列をスパンと呼ぶ。
【００１９】
図１にその例を示す。この例では原文"The computer science-based algorithm on partial lattice" に対して、辞書検索に必要となるスパンのバリエーションが矢印で示されている。図１において、トークンは、"computer"、science"、"based"、"algorithm"、"on"、"partial"、"lattice"である。これらトークンは、それぞれ辞書に登録されていることが多いが、"computer science", "science-based", "science-based algorithm" といったスパンも、それぞれ１つの意味を成すため、１つの辞書見出しとなって辞書に登録されている可能性がある。このことから、これらのスパンで辞書検索を行う必要がある。尚、「見出し」や「辞書見出し」とは、辞書に登録される用語（文字列）のことを指し、１つのトークンのみならず、複数のトークンにより構成される場合もある。
【００２０】
また、"Times flies like an arrow." といった英語の故事成語なども、その全体で１つの辞書登録用語のように検索できることが好ましい。したがって、検索用語の長さあるいはトークン数については、あまり上限をもたせないことが望ましい。
【００２１】
（２）多様な辞書登録
例えば近年の特許出願に関する文書などでは、化学式や塩基配列、ＤＮＡシーケンス文字列、記号列など極めて長い文字列が１つの専門用語として扱われるケースが多く、よって、極めて長い文字列をそのまま辞書登録されるケースが増している。このような用語についても、ユーザ辞書登録および検索できることが望ましい。また、これらの記号列にはハイフンやコロン、ピリオドなど従来辞書見出し語の構成文字として使われていない文字が含まれる場合がある。特にピリオド記号については、後述する文分割処理の障害となるため、従来の辞書検索システムでは各種制限が存在する場合が多い。しかしどのような文字列も登録・検索できることが辞書検索の理想である。
【００２２】
（３）柔軟な辞書検索
英語では辞書見出しと原文の表記とが異なる場合がある。主要なものは、大文字小文字の違いや、活用語尾のゆれ(inflection)である。つまり、小文字でつづられる一般単語でも文頭に位置する場合には、先頭字が大文字になる(capitalize される）という表記の揺れである。その他、"ATTENTION", "NO WARRANTY" のようにすべての文字がcapitalize される場合もある。このほかにも、スペースとハイフンのゆれ、スペースの有無といった表記のゆれが存在する。図２にこの例を示す。図２は、原文と辞書見出しとの対応を示す図である。このようなゆれに対しても、辞書検索でカバーできることが望ましい。さらには、辞書検索においてカバーする表記のゆれの範囲を指定できることが望ましい。ハッシュ検索はこのようなフレキシブルな検索に好適である。
【００２３】
図３に例を示す。具体的には、ある辞書見出しを辞書登録する際に、表記を正規化してからハッシュ値（インデクス）を算出し、このハッシュ値に対応付けて辞書見出しの用語を登録する（図３の左列参照）。検索の際も、ユーザから得られる原文を正規化してからハッシュ値を算出し、ハッシュ値が一致する見出し用語を検索する（図３の右列参照）。ハッシュ値と辞書見出しとの関係が１：Ｎ（Ｎは複数）である場合、この検索の際には、ハッシュ検索により検索対象がＮ個に絞られ、このＮ個分について、パターンマッチング等の検索処理が行われる。
【００２４】
尚、正規化処理にはステミングといった技術が用いられる。図４にステミング処理後の結果を例示する。このようにして見出し用語が登録された辞書インデクス（ハッシュテーブル）を用いて辞書検索を行うときは、検索キーとなる原文文字列に対しても正規化を行い、ハッシュ値を算出してから辞書検索を行う（図３の右列参照）。この正規化により、表記がゆれても同じ検索キーを得ることができるため、表記のゆれによらない辞書検索が可能になる。
【００２５】
（４）文分割機能
機械翻訳等のシステムでは、原文書全体を処理（翻訳）する際に、原文書に含まれる文章を個々の文に分割して、それを単位として処理（翻訳）を行うことが一般的である。英語の場合、通常ピリオドおよびセミコロンが文のセパレータとなっており、ピリオドないしセミコロンの位置で原文を分割することにより、個々の文が得られる。しかし、図５に示すように、末尾にピリオドがつく略語（例えば企業や会社を示す「Corp.」）等、多くの例外も存在する。また上述したように、ユーザ辞書に登録可能な見出しを制限しない場合、"book.  A " のような辞書登録、つまりスペースが後続するピリオドですら見出し用語の一部である場合がありうる。したがって、正確な文分割、あるいは文末位置の判定には辞書検索を行うことが必要となる。
【００２６】
（課題）
＜第１の課題＞
以上解説したように、英語形態素解析において英語原文に対して辞書検索を行う場合、原文のあらゆるスパンに対して、そのスパンが辞書見出しを構成するか調べるために辞書検索を行うことが必要となる。この検索処理は、原文中のトークン数をｎとした場合、辞書検索回数がｎ！となり、長い文に対しては大変多くのハッシュ辞書検索回数が必要となる。これは、形態素解析処理の速度低下を招く。登録可能な単語長や見出し語トークン数を制約することにより辞書検索回数を減らすことが可能となるが、これは上述した多様な辞書登録に対する障害となる。
【００２７】
本実施形態の態様では、辞書見出しをハッシュテーブルに登録する際に、ハッシュキーとなる文字列として、トークン毎にステミングを行って得られた文字列（正規化文字列）をそのまま用いるのでなく、予め規定された文字列長を超す部分を削除した文字列（打ち切り正規化文字列）を用いる。また検索の際にも同様に、トークン毎にステミングを行った文字列（正規化文字列）をそのまま用いるのでなく、上記文字列長を超す部分を削除した文字列（打ち切り正規化文字列）を用いる。
【００２８】
＜第２の課題＞
また上述したように、文分割をする際には、原文に含まれるピリオドやセミコロンが辞書見出し語の一部でないかどうかを判定する必要がある。図６に例を示す。この例では、"rrr" の後ろのピリオドが辞書見出し語の一部かどうかを判定するために必要となる辞書検索のバリエーションや検索数、スパン長を矢印で示している。見出し語長に制約を設けない場合、スパンの開始位置のバリエーションとしてはピリオド位置から文頭にまで遡る必要がある。また、スパンの終了位置のバリエーションもピリオド位置から文末にまで達する必要がある。したがって、ハッシュを用いた辞書検索回数が極端に増えてしまい、形態素解析処理の速度低下を招くという問題がある。
【００２９】
本実施形態の態様では、文末位置を判定するのに必要となる辞書検索回数の増大を防ぐため、上述の正規化文字列の打ち切り処理を、ピリオド位置から前方に向かうトークン列に対して行う。また、そこで用いるトークン列を逆順にする。これにより、ハッシュによる辞書検索回数を減らし、形態素解析の高速化を図ることが可能となる。
【００３０】
（実施形態の態様）
上述した課題を解決するシステムの構成例を図７に示す。本実施形態では、英文の原文を取得して日本語訳を出力する翻訳システムに組み込まれた形態素解析システムを一例として示しているが、翻訳システムに限定されない。また本実施形態は、辞書登録の際は登録用データ内（後述のｆｌａｔ辞書）の英文用語に対しての処理について説明し、検索の際は英語原文に対しての処理について説明するが、処理対象の言語は英語に限定されず、その他の自然言語や、プログラミングや数式等の人工言語、形式言語にも適用させてもよい。
【００３１】
また以下の説明では、辞書へ用語を登録する動作、辞書から用語を検索する動作の２つの異なる（非同期な）動作があることに留意する。
【００３２】
英語形態素解析システム１００（言語処理装置）は、文書情報管理部１０、形態素解析部２０、検索インデクス作成部３０（登録部）を有する。形態素解析部２０は、さらに文分割処理部２１、スパン決定部２２（決定部）、辞書検索部２３（検索部）を有し、辞書検索部２３は、さらに文字列正規化部２４、ハッシュ値計算部２５、ハッシュテーブル２７、形態素解析辞書２６から構成されている。
【００３３】
尚、英語形態素解析システム１００は、プロセッサ、メモリ、ハードディスクドライブ等の二次記憶装置、キーボードやマウスの入力装置、モニター等の出力装置を有する従前のコンピュータであるものとする。また図７に示される各ユニットは、１つのコンピュータ筺体で提供されてもよく、使用頻度や使用者数に応じて複数のコンピュータにより構成され、提供されてもよい。また、図７に示される各ユニットは、二次記憶装置に予め導入されているプログラムがメモリにロードされ、ロードされたプログラムがプロセッサにより演算実行されることで実現される。
【００３４】
まずここで、辞書の検索時に動作するユニットについて説明する。文書情報管理部１０は、原文書（電子化された文書）全体の文書情報を取得して管理し、形態素解析部２０による文分割結果を格納する。文書情報管理部１０は、原文書がＨＴＭＬ、ＸＭＬ文書の場合は原文書に含まれるタグの情報や章・節の構造情報等を一元管理する。これにはＤＯＭ（ドキュメントオブジェクトモデル）と呼ばれる技術を用いることができる。
【００３５】
形態素解析部２０は、文書情報管理部１０で管理された原文書情報を参照してその一部あるいは全体の文分割処理および形態素解析を行い、形態素解析結果をファイルや出力装置、または次の工程として実行されるモジュールや関数等の処理部に出力する。形態素解析結果は、通常１つの文ごとの品詞列ないし品詞ラティスとして出力される。
【００３６】
文分割処理部２１は、スパン決定部２２および辞書検索部２３をコントロールして原文の文分割を行う。
【００３７】
スパン決定部２２は、原文に対してスパンのバリエーションを作成して、各スパンに対して辞書検索を行う（本実施形態のバリエーション例については後述）。
【００３８】
文字列正規化部２４は、ステミング等の技術によって表記のゆれを吸収することにより、同じ用語については表記によらず同一の文字列を生成する。ステミングは、公知技術を採用することができるが、本実施形態では、さらに、ステミングされたトークンを連結し、連結トークン文字列が規定長に達している場合は、文字列先頭から規定長で打ち切る処理（規定長を超えた文字列を削除する処理）を行う。また文字列正規化部２４は、処理対象にピリオドが含まれている場合などには、トークンを逆順にして連結する処理を行う。これらの処理の詳細については後述する。
【００３９】
ハッシュ値計算部２５は、文字列正規化部２４により正規化された文字列のハッシュ値を計算する。ハッシュ値の計算に用いるハッシュ関数については公知の技術を用いることができる。
【００４０】
ハッシュテーブル２７は、ハッシュ値から形態素解析辞書２６中の用語エントリを取得するときに用いられるものであり、通常、単方向リンクリストとして実装される。形態素解析辞書２６は、ｆｌａｔ辞書（後述）の個々の用語の情報を機械可読用に構成したものである。尚、ハッシュテーブル２７や形態素解析辞書２６は、メモリや二次記憶装置（これらを記憶部とする）に記憶されている。
【００４１】
次に、辞書登録時に主として動作するユニットである検索インデクス作成部３０について説明する。検索インデクス作成部３０は、検索処理（形態素解析処理）の実行に先立って、オフラインでｆｌａｔ辞書を解析してハッシュ値を算出し、ハッシュ検索用のハッシュテーブル２７と形態素解析辞書２６とを作成する。ｆｌａｔ辞書とは、辞書検索インデクスの作成の源となるテキストファイルである。図８に例を示す。本実施形態のｆｌａｔ辞書は、見出し用語、および当該見出し語の品詞、単語の活用形の情報である変化形、訳語情報等を含む情報である。検索インデクス作成部３０は、このｆｌａｔ辞書の見出し用語を正規化し、正規化後の文字列のハッシュ値を算出してハッシュテーブル２７に登録するとともに、ｆｌａｔ辞書内で定義されている見出し用語、品詞、変化形、訳語を１行ずつ形態素解析辞書２６に登録する。また検索インデクス作成部３０は、登録するハッシュテーブル２７内のハッシュ値が、登録する形態素解析辞書２６内の見出し文字列へのリンクとなるように定義付けをする。
【００４２】
検索インデクス作成部３０は、正規化を行う際に、文字列正規化部２４と同様の処理を行う。すなわち、検索インデクス作成部３０は、見出し用語が複数のトークンによって構成されている場合は、ステミングされたトークンを連結し、連結トークン文字列が規定長に達している場合は、文字列先頭から規定長で打ち切る処理を行う。また検索インデクス作成部３０は、処理対象の辞書見出しにピリオドが含まれている場合などには、トークンを逆順にして連結する処理を行う。この処理の詳細については後述する。また検索インデクス作成部３０は、検索時に算出されるハッシュ値と値を一致させるため、ハッシュ値計算部２５と同様のハッシュ算出処理を行う。
【００４３】
この他、形態素解析部２０は、各スパンの辞書検索結果は統合して最終的な形態素解析結果を出力する。また原文の表記のゆれに応じた活用情報を形態素解析結果に付与する。たとえば原文での表記が"books"であり、正規化後の文字列が"book"となって辞書検索できた場合、形態素解析結果に含まれる見出し用語（"book"）の情報に、複数形であるという情報を付与する。
【００４４】
＜第１の課題に向けた態様＞
このように構成された英語形態素解析システム１００において、上述の第１の課題であるハッシュ辞書検索回数の増大を防ぐ態様について述べる。本実施形態では、辞書見出しをハッシュテーブル２７に登録する際に、ハッシュキーとなる文字列として、トークン毎にステミングを行って得られた文字列をそのまま用いるのでなく、予め規定された文字列長を超す部分を削除した文字列を用いる。以下、図９〜図１３を利用して説明する。
【００４５】
まず、形態素解析処理に先立って行われる辞書登録時の動作について説明する。検索インデクス作成部３０は、図９に示すアルゴリズムに従ってハッシュテーブル２７および形態素解析辞書２６を構築する。
【００４６】
検索インデクス作成部３０は、ｆｌａｔ辞書中の辞書エントリ（見出し用語）ごとに、Ｓ１０２〜Ｓ１１０の処理を行う（Ｓ１０１）。
【００４７】
検索インデクス作成部３０は、品詞情報、訳語情報などの用語情報を形態素解析辞書２６に登録する（Ｓ１０２）。検索インデクス作成部３０は、辞書エントリに記述された活用情報に基づき表記のゆれ（動詞や形容詞の活用形、名詞の複数形や所有格など）を生成する（Ｓ１０３）。
【００４８】
検索インデクス作成部３０は、上記表記ゆれ毎に、以下の処理を行う。すなわち、検索インデクス作成部３０は、辞書エントリが複数のトークンにより構成されている場合は、トークンに分割し（Ｓ１０５）、トークン毎にステミングを行う（Ｓ１０６）。検索インデクス作成部３０は、ステミングされたトークン文字列を連結して連結トークン文字列を作成する（Ｓ１０７）。検索インデクス作成部３０は、連結トークン文字列が規定文字列長に達している場合は、連結した文字列の先頭から規定文字列長で打ち切る（Ｓ１０８）。検索インデクス作成部３０は、打ち切った残りの文字列（打ち切りトークン文字列、打ち切り正規化文字列）についてのハッシュ値を計算する（Ｓ１０９）。
【００４９】
検索インデクス作成部３０は、ハッシュ値から形態素解析辞書２６の用語登録位置へのリンクをハッシュテーブル２７に登録する（Ｓ１１０）。
【００５０】
続いて、辞書検索時（形態素解析処理）の動作について説明する。形態素解析処理の実行においては、原文が与えられると、スパン決定部２２は、図１０に示すアルゴリズムに従って原文の各スパンを生成する。図１０の動作について説明する。スパン決定部２２は、まず原文のトークン数をカウントする（Ｓ２０１）。ここでは、カウント数をｎとする。
【００５１】
スパン決定部２２は、変数ｓが１（文の先頭のトークン）からｎに至るまで、および変数ｅが（ｓ＋１）からｎに至るまで、ｆｏｒループ（ネスト構成）を実行する（Ｓ２０２、Ｓ２０３）。
【００５２】
スパン決定部２２は、変数ｓから変数ｅまでのトークン列を１つのスパンとする（Ｓ２０４）。このスパンに対して辞書検索が行われる（Ｓ２０５）。尚、Ｓ２０５の処理は辞書検索部２３の処理であり、詳細は後述する。
【００５３】
ステップＳ２０５の辞書検索処理で、合致する見出しが検索された場合（Ｓ２０６、Ｙ）、その辞書検索結果を出力し（Ｓ２０７）、処理はＳ２０８に進む。合致する見出しが検索されなかった場合（Ｓ２０６、Ｎ）、もしくはＳ２０７の処理が行われた後、スパン決定部２２は、打ち切り正規化文字列が規定長を超えているかを判定する（Ｓ２０８）。規定長を超えている場合（Ｓ２０８、Ｙ）、スパン決定部２２は、内側のループ（変数ｅのループ）を終了させ、変数ｓをインクリメントさせて、再度Ｓ２０３からの処理を実行する（Ｓ２０９）。一方、規定長以下の場合（Ｓ２０８、Ｎ）、スパン決定部２２は、変数ｅの値をインクリメントさせて、再度Ｓ２０４からの処理を実行する。
【００５４】
上記Ｓ２０１〜Ｓ２０９の動作により、図１に示すような順番でスパンが生成される。辞書検索部２３は、スパン決定部２２から与えられた原文の文字列スパンに対して、図１１に示すアルゴリズムに従って辞書検索（上記Ｓ２０５の処理）を行う。
【００５５】
辞書検索部２３は、スパンに含まれる文字列（スパン文字列）をトークンに分割する（Ｓ３０１）。辞書検索部２３は、トークン毎にステミングを行い（Ｓ３０２）、ステミングされたトークン文字列を連結する（Ｓ３０３）。辞書検索部２３は、連結したトークン文字列を、文字列先頭から規定文字列長で打ち切る（Ｓ３０４）。辞書検索部２３は、打ち切り正規化文字列のハッシュ値を計算し（Ｓ３０５）、計算したハッシュ値、およびハッシュテーブル２７に基づき、形態素解析辞書２６の用語登録位置へのリンクを取得する（Ｓ３０６）。
【００５６】
辞書検索部２３は、取得したリンクから形態素解析辞書２６に登録された用語情報（１つまたは複数（Ｎ））を取得し（Ｓ３０７）、用語情報ごとに、以下の処理を実施する（Ｓ３０８）。辞書検索部２３は、形態素解析辞書２６の各エントリに記述された活用情報の基づき、表記のゆれ（動詞や形容詞の活用形、名詞の複数形や所有格など）を生成する（Ｓ３０９）。辞書検索部２３は、スパン文字列、および原文の後続する文字列が、表記のゆれのいずれかに一致するかを判定する（Ｓ３１０）。一致しない場合（Ｓ３１０、一致しなかった）、辞書検索部２３による検索処理は終了し、一致する場合（Ｓ３１０、一致した）、辞書検索部２３は、一致したゆれの表記の活用情報に応じて辞書検索結果に活用情報を付与し（Ｓ３１１）、辞書検索結果を出力する（Ｓ３１２）。このときの出力先は、機能呼び出し元のスパン決定部２２であるとするが、ファイルや出力装置に出力されてもよい。
【００５７】
上記各動作ついて、具体例を図１２および図１３に示しつつ説明する。
【００５８】
図１２は、図９に示す検索インデクス作成部３０の動作を説明するものであり、図１２の第１列の見出し用語を登録する場合の例である。今、ｆｌａｔ辞書に図１２の第１列に示すような見出し用語があった場合、検索インデクス作成部３０は、各見出しについて、トークン毎に正規化して連結し（第２列参照）、最終的に第３列に示す打ち切り正規化文字列を生成する。打ち切りの規定長は、この例では１４としている。この打ち切り正規化文字列に対して、検索インデクス作成部３０はハッシュ値を計算し、その値に基づいてハッシュテーブル２７から形態素解析辞書２６へのリンクを生成する。尚、打ち切り正規化文字列の作成に至るまでの処理は、文字列正規化部２４が行ってもよく、またハッシュ値の計算は、ハッシュ値計算部２５が行ってもよい。
【００５９】
図１３は、図１２の見出し用語が登録された形態素解析辞書２６およびハッシュテーブル２７を用いて、スパン決定部２２および辞書検索部２３が、与えられた原文についての辞書検索を行う様を図示したものである。スパン決定部２２は、図１０に示すように、
（１）スパン末尾を伸ばす（１トークン後ろにずらす）。
（２）スパン末尾が文末に達したら、スパン先頭位置を１トークン後ろにずらす。
という順番でスパンの各バリエーションを生成する。
【００６０】
生成された各スパンに対し、辞書検索部２３は辞書引きを行うが、打ち切り正規化文字列が規定値に達した場合、以降のスパン末尾の拡張とそれに対する辞書検索を省略することができる。なぜなら、それより長い見出し用語が形態素解析辞書２６に存在する場合、以降、そのハッシュキーは、図１２に示した登録時の"conputscienceb"と同じとなるからである。
【００６１】
図１３の例では、"computer"、"computer science"の順に検索が行われ、"computer science-based"のスパンに対する文字列検索の際に、打ち切り正規化文字列"conputscienceb"のハッシュ値が算出される。このハッシュ値にリンク付けされた見出しは、図１２に示すように
computer science-based
computer science-based algorithm
computer science-based algorithm course
computer science-based theory
の４つであり、この４つの見出しがハッシュ値に紐づいた見出しであるとして検索される。そのうち、原文と一致するのは
computer science-based
computer science-based algorithm
である。したがって、この２つが辞書検索結果として出力される。
【００６２】
図１３に示すように、これ以降のスパン
"computer science-based algorithm" 
"computer science-based algorithm on " 
"computer science-based algorithm on partial"
"computer science-based algorithm on partial lattice"
に対しての、ハッシュ値に基づく辞書検索は不要になる。次のステップである"science"に対する辞書検索も同様に、打ち切り正規化文字列が規定値に達した場合は、以降のスパン末尾の拡張とそれに対する辞書検索を省略することができる。
【００６３】
本実施形態を適用しない場合、検索漏れの観点から、長文のトークン文字列の全てのスパンのバリエーションについて、トークンを正規化し、連結して文字列を生成してハッシュ値を算出し、ハッシュ値にリンクされた見出しを検索する、という動作となる。
【００６４】
一方、本実施形態を適用させることで、打ち切り正規化文字列に達するまでの分のみ、上記トークン正規化、文字列連結、ハッシュ値算出、ハッシュ値を基に検索する処理を行えばよい。打ち切り正規化文字列以上のスパンについては、上述のように高々数件〜数十件の中から検索するだけで済む。本実施形態のように、打ち切り正規化文字列を用いてハッシュ値を用いた検索を打ち切ることで、ハッシュ値を用いた検索処理の回数を低減させることができる。その代償としては、全スパンのバリエーションに対しハッシュ検索を行う場合よりも、ハッシュ検索結果の件数が増える場合もあるが、この検索結果のうちからマッチング等により抽出する手法の方が、検索の高速化を図ることができる。以上、本実施形態を適用させることで、第１の課題は解消される。
【００６５】
＜第２の課題に向けた態様＞
次に、上記第２の課題である、文末位置を判定するのに必要な辞書検索回数の増大を防ぐ態様について述べる。本実施形態では、先に述べた正規化文字列の打ち切り処理をピリオド位置から前方のトークン列に対して行う。また、そこで用いるトークン列を逆順にする。以下、図１４〜図１９を用いて説明する。
【００６６】
まず、形態素解析処理（検索処理）に先立って、検索インデクス作成部３０は、図１４に示すアルゴリズムに従ってハッシュテーブル２７および形態素解析辞書２６を構築する。この処理は、見出し中にピリオドが含まれる用語について実施される。
【００６７】
検索インデクス作成部３０は、ｆｌａｔ辞書中のピリオドを見出し用語に含む辞書エントリについて、以下に記す処理を行う（Ｓ４０１）。
【００６８】
検索インデクス作成部３０は、品詞情報、訳語情報などの用語情報を形態素解析辞書２６に登録する（Ｓ４０２）。検索インデクス作成部３０は、辞書エントリに記述された活用情報に基づき表記のゆれ（動詞や形容詞の活用形、名詞の複数形や所有格など）を生成する（Ｓ４０３）。
【００６９】
検索インデクス作成部３０は、上記表記ゆれ毎に、以下に記す処理を行う。すなわち、検索インデクス作成部３０は、辞書エントリが複数のトークンにより構成されている場合は、トークンに分割し（Ｓ４０５）、ピリオドよりも後ろのトークンを削除し（Ｓ４０６）、トークン毎にステミングを行う（Ｓ４０７）。検索インデクス作成部３０は、トークン単位で順序を逆順にし（Ｓ４０８）、逆順にしたトークン文字列を連結する（Ｓ４０９）。Ｓ４０７、Ｓ４０８は逆転してもよい。検索インデクス作成部３０は、トークン文字列先頭から、規定文字列長で打ち切り、逆順打ち切り正規化文字列を作成する（規定文字列長を超えた文字は削除）（Ｓ４１０）。検索インデクス作成部３０は、逆順打ち切り正規化文字列のハッシュ値を計算する（Ｓ４１１）。
【００７０】
検索インデクス作成部３０は、ハッシュ値から形態素解析辞書２６の用語登録位置へのリンクをハッシュテーブル２７に登録する（Ｓ４１２）。
【００７１】
検索時の動作ついて説明する。検索時、文末判定処理の実行の際、原文が与えられるとスパン決定部２２は、図１５に示すアルゴリズムに従って原文のピリオド位置の周辺のスパンを生成する。図１５の動作について説明する。スパン決定部２２は、この処理で、ピリオドが文切りを意味するピリオドであるか否かも合わせて判定することができる。
【００７２】
スパン決定部２２は、まず原文の中のピリオド位置を探す（Ｓ５０１）。このピリオドの位置をｎとする。次いで、スパン決定部２２は、変数ｓが（ｎ−１）から１に至るまで、Ｓ５０３〜Ｓ５０８の処理を繰り返し実行する（Ｓ５０２）。尚、Ｓ５０２において、値（ｎ−１）は、ピリオド文字の１つ前（直前）のトークンを意味し、値１は、文の先頭のトークンを意味する。
【００７３】
スパン決定部２２は、変数ｓから（ｎ−１）までのトークン列を１つのスパンとし（Ｓ５０３）、このスパンに対して、辞書検索が行われる（Ｓ５０４）。尚、ステップＳ５０４の処理は辞書検索部２３の処理であり、詳細は後述する。
【００７４】
ステップＳ５０４の辞書検索処理で、合致する見出しが検索された場合（Ｓ５０５、Ｙ）、当該ピリオドは、辞書内に登録されている用語で用いられている文字であるため、スパン決定部２２は、文の区切りを意味するピリオドとしては扱わず、よって文切りを行わない（Ｓ５０６）。処理は、その後Ｓ５０７に進む。一方、合致する見出しが検索されなかった場合（Ｓ５０５、Ｎ）、もしくはＳ５０６の処理が行われた後、スパン決定部２２は、逆順打ち切り正規化文字列が規定長を超えているかを判定する（Ｓ５０８）。規定長を超えている場合（Ｓ５０８、Ｙ）、スパン決定部２２は、当該ピリオドが辞書内に登録されている用語で用いられた文字では無いため、当該ピリオドで文切りを行い、処理を終了させる（Ｓ５０８）。また逆順打ち切り正規化文字列が規定長を超えていない場合（Ｓ５０７、Ｎ）、スパン決定部２２は、変数ｓの値をデクリメントしてＳ５０３からの処理を再度実行する。
【００７５】
辞書検索部２３は、スパン決定部２２から与えられた原文のピリオド位置の周辺のスパンに対して、図１６に示すアルゴリズムに従って辞書検索（上記Ｓ５０４の処理）を行う。
【００７６】
辞書検索部２３は、ピリオドで終わるスパン中の文字列（スパン文字列）をトークンに分割する（Ｓ６０１）。辞書検索部２３は、トークン毎にステミングを行い（Ｓ６０２）、ステミングしたトークンを逆順にして（Ｓ６０３）、逆順後のトークンを連結する（Ｓ６０４）。尚、ステップＳ６０２、Ｓ６０３の順序は逆転してもよいが、図１４のＳ４０７、Ｓ４０８と同じ順となるようにする。
【００７７】
辞書検索部２３は、文字列先頭からの規定文字列長で打ち切る（逆打ち切り正規化文字列）（Ｓ６０５）。辞書検索部２３は、逆打ち切り正規化文字列のハッシュ値を計算し（Ｓ６０６）、計算したハッシュ値、およびハッシュテーブル２７に基づき、形態素解析辞書２６の用語登録位置へのリンクを取得する（Ｓ６０７）。
【００７８】
辞書検索部２３は、取得したリンクから形態素解析辞書２６に登録された用語情報（１つまたは複数（Ｎ））を取得し（Ｓ６０８）、用語情報ごとに、以下の処理を実施する（Ｓ６０９）。辞書検索部２３は、形態素解析辞書２６の各エントリに記述された活用情報の基づき、表記のゆれ（動詞や形容詞の活用形、名詞の複数形や所有格など）を生成する（Ｓ６１０）。辞書検索部２３は、スパン文字列が上記表記のゆれのいずれかに一致するかを判定する（Ｓ６１１）。一致しない場合（Ｓ６１１、一致しなかった）、辞書検索部２３による検索処理は終了し、一致する場合（Ｓ６１１、一致した）、辞書検索部２３は、原文のピリオド以降の文字列が、上記表記のゆれのピリオド以降の部分と一致するかを判定する（Ｓ６１２）。一致しない場合（Ｓ６１２、一致しなかった）、辞書検索部２３による検索処理は終了し、一致する場合（Ｓ６１２、一致した）、辞書検索結果を出力する（Ｓ６１３）。このときの出力先は、機能呼び出し元のスパン決定部２２であるものとするが、ファイルや出力装置に出力されてもよい。
【００７９】
以下、図１７、図１８、図１９を用いて、上記動作の詳細な説明を行う。
【００８０】
図１７は、１つのピリオドを含むある原文に対して、そのピリオドを含む全スパンのバリエーションを示している。理論的には、これらの各々が辞書登録語である可能性があるため、全てのバリエーションごとに、辞書検索を行う必要がある。
【００８１】
図１８は図１４に示す検索インデクス作成部３０の動作を説明するものであり、図１８の第１列を登録する場合の例である。ｆｌａｔ辞書に図１８の第１列に含まれるようなピリオドを含む見出しが存在する場合、検索インデクス作成部３０は、ピリオド位置から前方のトークン列に対して、トークンの正規化、連結を行い（第２列参照）、逆順にして第３列に示すような逆順打ち切り正規化文字列を作成する。この例では打ち切り規定長は１２になっている。作成された逆順打ち切り正規化文字列に対してハッシュ値が計算され、算出されたハッシュ値がハッシュテーブル２７に登録され、見出し用語を含んだｆｌａｔ辞書内の定義情報が、形態素解析辞書２６にハッシュ値と対応付けられて登録される。
【００８２】
図１９は、図１８の見出し用語が登録された形態素解析辞書２６およびハッシュテーブル２７を用いて、原文の分割位置の判定を行う様を図示したものである。
【００８３】
スパン決定部２２は、図１５に示すように、原文中にピリオドがあれば、その位置から前方に向かってスパンを作成し、処理の対象となるトークン列の範囲を決定する。そして、辞書検索部２３は、その各々について辞書検索を行う。辞書検索ロジックは、生成された各スパンに対して辞書引きを行うが、逆打ち切り正規化文字列が規定値に達した場合、以降のスパン拡張とそれに対するハッシュによる辞書検索を省略することができる。
【００８４】
図１９の例では、スパン"G." に対する辞書検索で辞書見出し"G. Thompson" が検索される（図１８も参照）。またスパン"analysis method by G." に対する辞書検索で辞書見出し"analysis method by G. Thompson"と"molecular analysis method by G." が検索される。この時点で逆順打ち切り正規化文字列は規定値に達しているので、スパン"molecular analysis method by G." や"optical molecular analysis method by G."に対してハッシュによる辞書検索を行う必要はない。
【００８５】
文分割が目的であれば、ピリオド位置で１つでも辞書単語が検索されたならば、その位置のピリオドは単語の一部であり文分割すべきでないと判断して処理を終了することができる。原文中にピリオドが複数ある場合は、各ピリオドについて上述した手法を適用すればよい。
【００８６】
このような態様により、図６に比して、はるかに少ない辞書検索回数で文分割を行うことができる。上記「第１の課題に向けた態様」でも説明したように、逆順打ち切り正規化文字列を用いることで、ハッシュ値による検索を打ち切り、その代わりに複数ヒットした見出しの中からマッチングするものを抽出する方が、ハッシュ値による検索を全スパンに対して行うよりも、検索が高速となる。
【００８７】
尚、本例では、正規化されたトークンの単位で逆順にしている。すなわち、"g"、"b"、"method"、"anal"の順で逆順打ち切り正規化文字列が生成されるとしたが、１文字単位で逆順にしてもよい。この場合、生成される打ち切り文字列は、"gbdohtemsyla"となる。当然、登録時に１文字単位で逆順にした場合、検索時においても、登録したハッシュ値と一致させるために１文字単位で逆順にする必要がある。
【００８８】
以上、この実施形態で説明した態様により、用語検索の高速化を図ることができる。
【００８９】
なお、本発明の実施形態を説明したが、当該実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。この新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９０】
１０  文書情報管理部、２０  形態素解析部、２１  文分割処理部、２２  スパン決定部、２３  辞書検索部、２４  文字列正規化部、２５  ハッシュ値計算部、２６  形態素解析辞書、２７  ハッシュテーブル、３０  検索インデクス作成部、１００  英語形態素解析システム（言語処理装置）。
【図１】
0005380566.tif 000002
【図２】
0005380566.tif 000003
【図３】
0005380566.tif 000004
【図４】
0005380566.tif 000005
【図５】
0005380566.tif 000006
【図６】
0005380566.tif 000007
【図７】
0005380566.tif 000008
【図８】
0005380566.tif 000009
【図９】
0005380566.tif 000010
【図１０】
0005380566.tif 000011
【図１１】
0005380566.tif 000012
【図１２】
0005380566.tif 000013
【図１３】
0005380566.tif 000014
【図１４】
0005380566.tif 000015
【図１５】
0005380566.tif 000016
【図１６】
0005380566.tif 000017
【図１７】
0005380566.tif 000018
【図１８】
0005380566.tif 000019
【図１９】
0005380566.tif 000020