(57)【要約】【課題】多数の見出し語を収録する大規模辞書の搭載と高速な単語検出とを両立させる。【解決手段】単語抽出装置は、文字数が所定数以下の見出し語を収録する見出し語辞書ｄ1〜ｄKと、文字数が所定数を超える見出し語を収録する見出し語辞書ｄK+と、テキストファイルに含まれる着目点の文字、またはテキストファイルに含まれる、着目点の文字を末尾とし、文字数が所定数以下である着目対象の文字列が、見出し語辞書ｄ1〜ｄKに収録されているか否かを判定する検出部５と、テキストファイルに含まれる、着目点の文字を含み、文字数が所定数よりも大きい文字列が、第２の見出し語辞書に収録されているか否かを判定するＤＦＡ部４とを備える。見出し語辞書ｄ1〜ｄKと検出部５とはプロセサによって構成され、見出し語辞書ｄK+はＤＲＡＭによって構成され、ＤＦＡ部４はＦＰＧＡによって構成される。【選択図】  図５
2017084042.tif 000002
【特許請求の範囲】
【請求項１】
テキストファイルの中から、辞書に見出し語として収録されている単語を検出する単語抽出装置において、
文字数が所定数以下の見出し語を、見出し語の文字数ごとに収録する第１の見出し語辞書と、
文字数が前記所定数を超える見出し語を収録する第２の見出し語辞書と、
前記テキストファイルに含まれる着目点の文字、または前記テキストファイルに含まれる、前記着目点の文字を末尾とし、文字数が前記所定数以下である着目対象の文字列が、前記第１の見出し語辞書に収録されているか否かを判定する第１の検出手段と、
前記テキストファイルに含まれる、前記着目点の文字を含み、文字数が前記所定数よりも大きい着目対象の文字列が、前記第２の見出し語辞書に収録されているか否かをＤＦＡにより判定する第２の検出手段とを備え、
前記第１の見出し語辞書と前記第１の検出手段とは、プロセサによって構成され、
前記第２の見出し語辞書は、ＤＲＡＭによって構成され、
前記第２の検出手段は、ＦＰＧＡによって構成されることを特徴とする単語抽出装置。
【請求項２】
請求項１記載の単語抽出装置において、
前記第１の見出し語辞書は、見出し語の文字数ごとに設けられ、見出し語のハッシュ関数を計算したときにこのハッシュ関数に基づいて特定される格納領域に当該見出し語を収録し、
前記第１の検出手段は、前記着目点の文字から計算したハッシュ関数により前記第１の見出し語辞書を検索し、この着目点の文字が前記第１の見出し語辞書に収録されているか否かを判定する共に、文字数が１より大で前記所定数以下である前記着目対象の文字列から計算したハッシュ関数により前記第１の見出し語辞書を検索し、この着目対象の文字列が前記第１の見出し語辞書に収録されているか否かを判定することを特徴とする単語抽出装置。
【請求項３】
請求項１記載の単語抽出装置において、
前記第１の見出し語辞書は、
文字数が１の見出し語またはこの見出し語に対応する値を、見出し語の文字コードに基づいて特定される格納領域に収録する辞書と、
文字数が１を超える見出し語の文字数ごとに設けられ、見出し語のハッシュ関数を計算したときにこのハッシュ関数に基づいて特定される格納領域に当該見出し語を収録する辞書とから構成され、
前記第１の検出手段は、前記着目点の文字の文字コードにより前記第１の見出し語辞書を検索し、この着目点の文字が前記第１の見出し語辞書に収録されているか否かを判定する共に、文字数が１より大で前記所定数以下である前記着目対象の文字列から計算したハッシュ関数により前記第１の見出し語辞書を検索し、この着目対象の文字列が前記第１の見出し語辞書に収録されているか否かを判定することを特徴とする単語抽出装置。
【請求項４】
請求項１乃至３のいずれか１項に記載の単語抽出装置において、
さらに、文字数が前記所定数よりも大きい前記着目対象の文字列から前記所定数分の文字数の先頭文字列を取り出し、この先頭文字列から計算したハッシュ関数に基づいて特定される前記第２の見出し語辞書の格納領域に格納されている、文字数が前記所定数よりも大きい全ての見出し語を前記第２の検出手段に送出する送出機能手段を備え、
前記第２の見出し語辞書は、文字数が前記所定数よりも大きい見出し語の前記所定数分の先頭文字列からハッシュ関数を計算したときにこのハッシュ関数に基づいて特定される格納領域に当該見出し語を収録し、
前記第２の検出手段は、前記送出機能手段から送出された見出し語に基づいて、文字数が前記所定数よりも大きい前記着目対象の文字列が、前記第２の見出し語辞書に収録されているか否かをＤＦＡにより判定することを特徴とする単語抽出装置。
【請求項５】
請求項４記載の単語抽出装置において、
前記第２の検出手段は、
前記送出機能手段から送出された見出し語を格納する転送レートバッファと、
この転送レートバッファに格納されている各見出し語からそれぞれ前記所定数分の文字数の先頭文字列を削除する第１の部分文字抽出手段と、
文字列を格納するためのキューと、
前記第１の部分文字抽出手段が先頭文字列を削除した見出し語を前記キューに格納する第１の登録手段と、
前記キューから取り出した文字列の先頭文字を除去した部分文字列を出力する第２の部分文字抽出手段と、
前記キューから取り出した文字列の先頭文字を出力する先頭文字抽出手段と、
この先頭文字抽出手段が取り出した文字と前記着目点の文字とを比較し、前記先頭文字抽出手段が取り出した文字と前記着目点の文字とが一致し、かつ前記キューから取り出した文字列に前記先頭文字よりも後の文字がない場合に、前記着目対象の文字列が前記第２の見出し語辞書に収録されていると判定する比較手段と、
前記先頭文字抽出手段が取り出した文字と前記着目点の文字とが一致し、かつ前記キューから取り出した文字列に前記先頭文字よりも後の文字がある場合に、前記第２の部分文字抽出手段から出力された文字列を前記キューに登録する第２の登録手段とから構成されることを特徴とする単語抽出装置。
【請求項６】
請求項５記載の単語抽出装置において、
前記キューと前記第２の部分文字抽出手段と前記先頭文字抽出手段と前記比較手段と前記第２の登録手段とは、それぞれ複数設けられることを特徴とする単語抽出装置。
【請求項７】
テキストファイルの中から、辞書に見出し語として収録されている単語を検出する単語抽出方法において、
文字数が所定数以下の見出し語を、見出し語の文字数ごとに収録する第１の見出し語辞書を参照し、前記テキストファイルに含まれる着目点の文字、または前記テキストファイルに含まれる、前記着目点の文字を末尾とし、文字数が前記所定数以下である着目対象の文字列が、前記第１の見出し語辞書に収録されているか否かを判定する第１の検出ステップと、
文字数が前記所定数を超える見出し語を収録する第２の見出し語辞書を参照し、前記テキストファイルに含まれる、前記着目点の文字を含み、文字数が前記所定数よりも大きい着目対象の文字列が、前記第２の見出し語辞書に収録されているか否かをＤＦＡにより判定する第２の検出ステップとを含み、
前記第１の見出し語辞書は、プロセサによって構成され、
前記第２の見出し語辞書は、ＤＲＡＭによって構成され、
前記第１の検出ステップは、前記プロセサによって実行され、
前記第２の検出ステップは、ＦＰＧＡによって実行されることを特徴とする単語抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的文字列により記された言語表現（テキストファイル）の中から、辞書に見出し語（キーワード）として収録されている単語を検出する技術に係り、特に日本語等の、単語による分かち書き表記のないテキストファイルに好適な単語抽出装置および方法に関するものである。
【背景技術】
【０００２】
単語抽出とは、テキストファイルの中から、辞書に見出し語として収録されている単語（キーワード）を検出する処理である。
従来、このような単語抽出は、汎用のプロセッサ上でソフトウエアによって実行されていた。また、ＦＰＧＡ（field-programmable gate array）等により専用のハードウエア処理加速器を使うことも行われている（非特許文献１参照）。また、ハッシュ関数値を使って見出し語を辞書に格納する高速化手法と組み合わせて、ハードウエアアクセラレーションを実現する技術が提案されている（非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Yusuke Sekihara et al.，“A study of a real-time keyword matching process targeting Twitter data”，International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies（HEART），2015
【非特許文献２】Kanak Agarwal et al.，“A high-speed and large-scale dictionary matching engine for Information Extraction systems”，Application-Specific Systems，Architectures and Processors（ASAP），2013
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の単語抽出では、テキストファイル内の単語が、予め用意した辞書内に収録されているかどうかを判定しようとする場合、次の（１）、（２）のステップを実行することになる。
（１）テキストファイルを先頭から走査して検索対象とする単語候補を特定する。
（２）上記の単語候補について辞書内にあるか検索／判定する。
【０００５】
また、上記の（２）のステップで検索する辞書が大規模である場合には、辞書の見出し語を、あらかじめ、ハッシュ関数値による補助見出しで読み出せるように格納しておき、単語候補のハッシュ関数値によって、上記の格納記憶を読み出すことによって、検索の手間を小さくすることができる。
【０００６】
ただし、ハッシュ関数値は、異なる文字列に対して同じ値を与えてしまうことがあるので、ハッシュ関数値を補助見出しとして利用した場合、以下の（Ａ）、（Ｂ）のような問題があった。
（Ａ）複数の見出し語が読み出されることがある。
（Ｂ）ハッシュ関数値の計算に与えた引数である文字列（＝単語候補）とは異なる文字列が格納されている場合がある。
【０００７】
そこで、ハッシュ関数による補助見出しを用いる場合には、上記の（２）のステップは次の（２−１）〜（２−３）のような処理となる。
（２−１）単語候補のハッシュ関数値を計算する。
（２−２）上記ハッシュ関数値により、辞書に格納されている該当する見出し語を全て読み出す。
（２−３）辞書から読み出した複数の見出し語と、テキストファイルから抽出した単語候補との文字列一致を検査する。
【０００８】
英文等の、単語による分かち書き表記のあるテキストファイルに対してであれば、単語と単語のあいだに空白があることを、単語の特定に利用できるため、上記の（１）のステップが簡単化され、事実上の処理は不要となる。
さらに、英文等の場合、（２）のステップで検索する対象となる単語候補も、テキストファイルの特定の文字位置、すなわち着目点に対してただ１つとなる。
【０００９】
このように、英文等のテキストファイルでは、着目点に対して検索対象の単語候補が１つに定まるため、辞書内の検索において、見出し語に対する補助見出しとして機能するハッシュ関数値を計算する手数も着目点に対して１度の計算のみで十分であり、計算の手間を少なくすることが可能であった。
【００１０】
一方、日本語等の、単語単位での分かち書き表記のないテキストファイルの場合、（１）のステップで導かれる単語候補はただ１つとはかぎらず、複数あることに注意しなければならない。一般には、テキストファイル内のある位置（着目点）の１つの文字を最後の文字とする、開始点の異なる単語が単語候補となる。すなわち、１つの着目点に対して、単語の構成文字数として想定する範囲内の全ての長さの部分文字列を単語候補としなければならない。
【００１１】
単語の構成文字数の最大値をＭとすれば、Ｍ個の単語候補が有り得るということである。すなわち、日本語等の、単語による分かち書き表記のないテキストファイルについて、上記と同様のハッシュ関数による手法を用いようとすると、上記の（１）のステップで導かれる単語候補がＭ個あるため、単語候補が１つしかない場合と比較して、（２）のステップの手間が概ねＭ倍になる。また、単語候補がＭ個になることにより、単語候補が、（２−２）のステップで読み出された見出し語のどれとも一致しないことも増えるため、処理の手間がさらに増加する。
【００１２】
以上のような問題があるため、和文等の、単語による分かち書き表記のないテキストファイルに対しては、従来、決定性有限オートマトン（ＤＦＡ：Deterministic Finite Automaton）、非決定性有限オートマトン（ＮＦＡ：Non-deterministic Finite Automaton）を用いる方法が採用されていた（非特許文献１参照）。
しかしながら、決定性／非決定性の有限オートマトンを用いる方法は、辞書に収録する見出し語ごとに、１組みのオートマトンの内部状態を保持しなければならない。
【００１３】
オートマトンおよびその内部状態を、高速な論理回路を格納することが可能なＦＰＧＡなどによって用意する場合には、十分な処理速度を提供することができる。しかし、見出し語数の大きい辞書検索に対して、決定性／非決定性の有限オートマトンを用いる方法を採用しようとすると、辞書に収録する見出し語数の増大に伴って必要とするＦＰＧＡの容量も大きくなり、やがて搭載することができなくなるため、概ね１万語を超える見出し語に対しては、十分な処理速度を提供することが不可能であった。
【００１４】
本発明は、上記課題を解決するためになされたもので、多数の見出し語を収録する大規模辞書の搭載と高速な単語検出とを両立させることができる単語抽出装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明は、テキストファイルの中から、辞書に見出し語として収録されている単語を検出する単語抽出装置において、文字数が所定数以下の見出し語を、見出し語の文字数ごとに収録する第１の見出し語辞書と、文字数が前記所定数を超える見出し語を収録する第２の見出し語辞書と、前記テキストファイルに含まれる着目点の文字、または前記テキストファイルに含まれる、前記着目点の文字を末尾とし、文字数が前記所定数以下である着目対象の文字列が、前記第１の見出し語辞書に収録されているか否かを判定する第１の検出手段と、前記テキストファイルに含まれる、前記着目点の文字を含み、文字数が前記所定数よりも大きい着目対象の文字列が、前記第２の見出し語辞書に収録されているか否かをＤＦＡにより判定する第２の検出手段とを備え、前記第１の見出し語辞書と前記第１の検出手段とは、プロセサによって構成され、前記第２の見出し語辞書は、ＤＲＡＭによって構成され、前記第２の検出手段は、ＦＰＧＡによって構成されることを特徴とするものである。
【００１６】
また、本発明の単語抽出装置の１構成例において、前記第１の見出し語辞書は、見出し語の文字数ごとに設けられ、見出し語のハッシュ関数を計算したときにこのハッシュ関数に基づいて特定される格納領域に当該見出し語を収録し、前記第１の検出手段は、前記着目点の文字から計算したハッシュ関数により前記第１の見出し語辞書を検索し、この着目点の文字が前記第１の見出し語辞書に収録されているか否かを判定する共に、文字数が１より大で前記所定数以下である前記着目対象の文字列から計算したハッシュ関数により前記第１の見出し語辞書を検索し、この着目対象の文字列が前記第１の見出し語辞書に収録されているか否かを判定することを特徴とするものである。
また、本発明の単語抽出装置の１構成例において、前記第１の見出し語辞書は、文字数が１の見出し語またはこの見出し語に対応する値を、見出し語の文字コードに基づいて特定される格納領域に収録する辞書と、文字数が１を超える見出し語の文字数ごとに設けられ、見出し語のハッシュ関数を計算したときにこのハッシュ関数に基づいて特定される格納領域に当該見出し語を収録する辞書とから構成され、前記第１の検出手段は、前記着目点の文字の文字コードにより前記第１の見出し語辞書を検索し、この着目点の文字が前記第１の見出し語辞書に収録されているか否かを判定する共に、文字数が１より大で前記所定数以下である前記着目対象の文字列から計算したハッシュ関数により前記第１の見出し語辞書を検索し、この着目対象の文字列が前記第１の見出し語辞書に収録されているか否かを判定することを特徴とするものである。
【００１７】
また、本発明の単語抽出装置の１構成例は、さらに、文字数が前記所定数よりも大きい前記着目対象の文字列から前記所定数分の文字数の先頭文字列を取り出し、この先頭文字列から計算したハッシュ関数に基づいて特定される前記第２の見出し語辞書の格納領域に格納されている、文字数が前記所定数よりも大きい全ての見出し語を前記第２の検出手段に送出する送出機能手段を備え、前記第２の見出し語辞書は、文字数が前記所定数よりも大きい見出し語の前記所定数分の先頭文字列からハッシュ関数を計算したときにこのハッシュ関数に基づいて特定される格納領域に当該見出し語を収録し、前記第２の検出手段は、前記送出機能手段から送出された見出し語に基づいて、文字数が前記所定数よりも大きい前記着目対象の文字列が、前記第２の見出し語辞書に収録されているか否かをＤＦＡにより判定することを特徴とするものである。
【００１８】
また、本発明の単語抽出装置の１構成例において、前記第２の検出手段は、前記送出機能手段から送出された見出し語を格納する転送レートバッファと、この転送レートバッファに格納されている各見出し語からそれぞれ前記所定数分の文字数の先頭文字列を削除する第１の部分文字抽出手段と、文字列を格納するためのキューと、前記第１の部分文字抽出手段が先頭文字列を削除した見出し語を前記キューに格納する第１の登録手段と、前記キューから取り出した文字列の先頭文字を除去した部分文字列を出力する第２の部分文字抽出手段と、前記キューから取り出した文字列の先頭文字を出力する先頭文字抽出手段と、この先頭文字抽出手段が取り出した文字と前記着目点の文字とを比較し、前記先頭文字抽出手段が取り出した文字と前記着目点の文字とが一致し、かつ前記キューから取り出した文字列に前記先頭文字よりも後の文字がない場合に、前記着目対象の文字列が前記第２の見出し語辞書に収録されていると判定する比較手段と、前記先頭文字抽出手段が取り出した文字と前記着目点の文字とが一致し、かつ前記キューから取り出した文字列に前記先頭文字よりも後の文字がある場合に、前記第２の部分文字抽出手段から出力された文字列を前記キューに登録する第２の登録手段とから構成されることを特徴とするものである。
また、本発明の単語抽出装置の１構成例において、前記キューと前記第２の部分文字抽出手段と前記先頭文字抽出手段と前記比較手段と前記第２の登録手段とは、それぞれ複数設けられることを特徴とするものである。
【００１９】
また、本発明の単語抽出方法は、文字数が所定数以下の見出し語を、見出し語の文字数ごとに収録する第１の見出し語辞書を参照し、前記テキストファイルに含まれる着目点の文字、または前記テキストファイルに含まれる、前記着目点の文字を末尾とし、文字数が前記所定数以下である着目対象の文字列が、前記第１の見出し語辞書に収録されているか否かを判定する第１の検出ステップと、文字数が前記所定数を超える見出し語を収録する第２の見出し語辞書を参照し、前記テキストファイルに含まれる、前記着目点の文字を含み、文字数が前記所定数よりも大きい着目対象の文字列が、前記第２の見出し語辞書に収録されているか否かをＤＦＡにより判定する第２の検出ステップとを含み、前記第１の見出し語辞書は、プロセサによって構成され、前記第２の見出し語辞書は、ＤＲＡＭによって構成され、前記第１の検出ステップは、前記プロセサによって実行され、前記第２の検出ステップは、ＦＰＧＡによって実行されることを特徴とするものである。
【発明の効果】
【００２０】
本発明によれば、分かち書きの無い日本語表記等のテキストファイルに対する単語の検出であっても、事前に定めた所定数までの検査と、所定数を超えた末尾までの検査に分けて、大規模な第２の見出し語辞書をＤＲＡＭに搭載し、所定数までの検査をプロセサで行い、所定数を超えた末尾までの検査をＦＰＧＡで行うことにより、多数の見出し語を収録する大規模辞書の搭載と高速な単語検出とを両立させることができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態において辞書に見出し語を格納する構造を説明する図でる。
【図２】本発明の実施の形態において辞書に見出し語を格納する構造を説明する図でる。
【図３】本発明の実施の形態において辞書に見出し語を格納する手順を説明するフローチャートである。
【図４】本発明の実施の形態において辞書に見出し語を格納する手順を説明するフローチャートである。
【図５】本発明の実施の形態に係る単語抽出装置の構成を示すブロック図である。
【図６】本発明の実施の形態に係る単語抽出装置の構成を示すブロック図である。
【図７】本発明の実施の形態に係る単語抽出装置の単語抽出動作を説明するフローチャートである。
【図８】本発明の実施の形態に係る単語抽出装置のＤＦＡ部と制御部の動作を説明するフローチャートである。
【図９】本発明の実施の形態に係る単語抽出装置を実装する装置の構成を示すブロック図である。
【図１０】本発明の実施の形態に係る単語抽出装置を図９に示した装置に実装する場合に各構成要素が実現する機能を説明する図である。
【図１１】本発明の実施の形態に係る単語抽出装置の他の構成を示すブロック図である。
【図１２】本発明の実施の形態に係る単語抽出装置の他の構成の動作を説明するフローチャートである。
【図１３】本発明の実施の形態に係る１文字見出し語辞書の他の構造を説明する図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について図面を参照して説明する。本実施の形態では、和文等の、単語による分かち書き表記のないテキストファイルを処理対象とし、テキストファイルを構成する文字単位で処理を進めることを前提とする。
【００２３】
まず、辞書に見出し語を格納する構造と格納する手順について説明する。図１、図２は辞書に見出し語を格納する構造を説明する図、図３、図４は辞書に見出し語を格納する手順を説明するフローチャートである。なお、図３と図４のＫ１同士が繋がり、Ｋ２同士が繋がっていることは言うまでもない。
【００２４】
全ての見出し語は、その見出し語を構成する文字数ｊが同じ値である語を収集したｊ文字見出し語辞書ｄjに格納される。いま、あるｊ文字で構成される単語Ａを格納する場合を例に説明する。図示しない辞書管理手段は、辞書に格納すべき見出し語Ａを取得すると（図３ステップＳ１００）、１つの見出し語についての処理回数をカウントするための変数ｔを０に初期化する（図３ステップＳ１０１）。
【００２５】
続いて、辞書管理手段は、見出し語Ａの文字数ｊ＝ｌｅｎ（Ａ）を計算する（図３ステップＳ１０２）。辞書管理手段は、文字数ｊが事前に定められた所定数Ｋ以下の場合（Ｋは２以上の整数）、見出し語Ａのハッシュ関数値ｈ０＝ｈj（Ａ）を計算し（図３ステップＳ１０３）、ｊ文字見出し語辞書ｄjのアドレスｈ０の格納領域１００を参照する（図３ステップＳ１０４）。
【００２６】
辞書管理手段は、ｊ文字見出し語辞書ｄjのアドレスｈ０の格納領域１００に未だ何も格納されていないときは、この格納領域１００のデータとして見出し語Ａを格納する（図３ステップＳ１０５）。辞書管理手段は、ｊ文字見出し語辞書ｄjのアドレスｈ０の格納領域１００に文字列が既に格納されており、この格納されている文字列が見出し語Ａと同じであったときには、特段処理を行わずに、ステップＳ１００に戻って次の見出し語の処理を行う。
【００２７】
また、辞書管理手段は、ｊ文字見出し語辞書ｄjのアドレスｈ０の格納領域１００に文字列が格納されており、この文字列が見出し語Ａでなかったときには、変数ｔを１増やす（図３ステップＳ１０６）。そして、辞書管理手段は、変数ｔが所定の上限回数Ｇ以下の場合には（Ｇは２以上の整数）、ｊ文字見出し語辞書ｄjのアドレスｈ０のリンクフィールド１０１に格納されている値ｈ［ｔ］（ここではｔ＝１なので、ｈ［ｔ］＝ｈ１）を取得するか、このリンクフィールド１０１に値が格納されていないときには、所定の方法により、アドレスｈ０のハッシュ関数値ｈ１＝ｎｅｘｔ＿ｈａｓｈj（ｈ０）を計算する（図３ステップＳ１０７）。このハッシュ関数値ｈ１＝ｎｅｘｔ＿ｈａｓｈj（ｈ０）を計算する方法としては、非特許文献２に開示された方法を用いることができる。
【００２８】
辞書管理手段は、取得または計算した値ｈ１を基に、ｊ文字見出し語辞書ｄjのアドレスｈ１の格納領域１００を参照し（図３ステップＳ１０８）、この格納領域１００に未だ何も格納されていないときは、この格納領域１００のデータとして見出し語Ａを格納する（図３ステップＳ１０９）。そして、辞書管理手段は、見出し語Ａを格納できた場合には、ｊ文字見出し語辞書ｄjのアドレスｈ０のリンクフィールド１０１に、リンク情報としてアドレスｈ１を格納する（図３ステップＳ１１０）。
【００２９】
辞書管理手段は、ｊ文字見出し語辞書ｄjのアドレスｈ１の格納領域１００に文字列が既に格納されており、この格納されている文字列が見出し語Ａと同じであったときには、特段処理を行わずに、ステップＳ１００に戻って次の見出し語の処理を行う。
【００３０】
また、辞書管理手段は、ｊ文字見出し語辞書ｄjのアドレスｈ１の格納領域１００に文字列が格納されており、この文字列が見出し語Ａでなかったときには、変数ｔを１増やし（ステップＳ１０６）、変数ｔが所定の上限回数Ｇ以下の場合には、ｊ文字見出し語辞書ｄjのアドレスｈ１のリンクフィールド１０１に格納されている値ｈ［ｔ］（ここではｔ＝２なので、ｈ［ｔ］＝ｈ２）を取得するか、このリンクフィールド１０１に値が格納されていないときには、アドレスｈ１のハッシュ関数値ｈ２＝ｎｅｘｔ＿ｈａｓｈj（ｈ１）を計算する（ステップＳ１０７）。
【００３１】
辞書管理手段は、取得または計算した値ｈ２を基に、ｊ文字見出し語辞書ｄjのアドレスｈ２の格納領域１００を参照し（ステップＳ１０８）、この格納領域１００に未だ何も格納されていないときは、この格納領域１００のデータとして見出し語Ａを格納する（ステップＳ１０９）。そして、辞書管理手段は、見出し語Ａを格納できた場合には、ｊ文字見出し語辞書ｄjのアドレスｈ１のリンクフィールド１０１に、リンク情報としてアドレスｈ２を格納する（ステップＳ１１０）。
【００３２】
こうして、未収録の見出し語Ａをｊ文字見出し語辞書ｄjに格納できるまで、ステップＳ１０６〜Ｓ１１０の処理が繰り返し実行される。辞書管理手段は、変数ｔが所定の上限回数Ｇを超えても、見出し語Ａをｊ文字見出し語辞書ｄjに格納できなかった場合には、見出し語Ａの処理を打ち切り、ユーザに対して格納の失敗を通知する（図３ステップＳ１１１）。
【００３３】
本実施の形態では、辞書に格納する見出し語の文字数によってそれぞれ異なる格納方法を採る。上記で説明したとおり、見出し語の文字数ｊが事前に定められた所定数Ｋ以下のものは、それぞれの見出し語の文字数ｊに対応する専用のｊ文字見出し語辞書ｄjに、全て同じ方法で格納する。
【００３４】
次に、見出し語の文字数ｊが所定数Ｋより大きい場合について説明する。辞書管理手段は、見出し語Ａの文字数ｊが所定数Ｋより大きい場合、変数ｔを０に初期化し（図４ステップＳ１１２）、見出し語Ａの先頭Ｋ文字分の部分文字列Ｂ＝ｌｅｆｔ（Ａ，Ｋ）を取得する（図４ステップＳ１１３）。ｌｅｆｔ（Ａ，Ｋ）は、文字列Ａの左側からＫ文字取得する関数を意味する。
【００３５】
続いて、辞書管理手段は、文字列Ｂのハッシュ関数値ｈ０＝ｈK（Ｂ）を計算し（図４ステップＳ１１４）、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０の格納領域１０２を参照する（図４ステップＳ１１５）。辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０の格納領域１０２に未だ何も格納されていないときは、この格納領域１０２のデータとして文字列Ｂを格納し、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０のポインタフィールド１０４に事前に格納されているアドレスｒ［ｔ］（ここではｔ＝０なので、ｒ［ｔ］＝ｒ０）によって特定される格納領域１０５に、見出し語Ａを格納する（図４ステップＳ１１６）。ｒ［ｔ］は、文字列Ｂと同じ先頭文字列を有し、かつ文字数ｊが所定数Ｋより大きい見出し語を格納するための格納領域１０５を示すアドレス値である。
【００３６】
また、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０の格納領域１０２に文字列が既に格納されており、この文字列が文字列Ｂと同じであったときには、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０のポインタフィールド１０４に事前に格納されているアドレスｒ０によって特定される格納領域１０５に、見出し語Ａを格納する（図４ステップＳ１１７）。
【００３７】
なお、辞書管理手段は、ステップＳ１１６，Ｓ１１７において、ｒ０がまだ用意されていない場合には、アドレスｒ０に対応する格納領域１０５を新たに確保した後に、この格納領域１０５に文字列Ａを格納すると共に、そのアドレスｒ０を超Ｋ文字見出し語辞書ｄK+のアドレスｈ０のポインタフィールド１０４に格納する。
【００３８】
ただし、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｒ０によって特定される格納領域１０５に文字列が既に格納されており、この文字列が見出し語Ａと同じであったときには、特段処理を行わずに、ステップＳ１００に戻って次の見出し語の処理を行う。
【００３９】
また、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０の格納領域１０２に文字列が格納されており、この文字列が文字列Ｂでなかったときには、変数ｔを１増やす（図４ステップＳ１１８）。そして、辞書管理手段は、変数ｔが所定の上限回数Ｇ以下の場合には、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０のリンクフィールド１０３に格納されている値ｈ［ｔ］（ここではｔ＝１なので、ｈ［ｔ］＝ｈ１）を取得するか、このリンクフィールド１０３に値が格納されていないときには、所定の方法により、アドレスｈ０のハッシュ関数値ｈ１＝ｎｅｘｔ＿ｈａｓｈK（ｈ０）を計算する（図４ステップＳ１１９）。上記と同様に、ハッシュ関数値ｈ１＝ｎｅｘｔ＿ｈａｓｈK（ｈ０）を計算する方法としては、非特許文献２に開示された方法を用いることができる。
【００４０】
辞書管理手段は、取得または計算した値ｈ１を基に、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１の格納領域１０２を参照し（図４ステップＳ１２０）、この格納領域１０２に未だ何も格納されていないときは、この格納領域１０２のデータとして文字列Ｂを格納し、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１のポインタフィールド１０４に事前に格納されているアドレスｒ［ｔ］（ここではｔ＝１なので、ｒ［ｔ］＝ｒ１）によって特定される格納領域１０５に、見出し語Ａを格納する（図４ステップＳ１２１）。そして、辞書管理手段は、見出し語Ａを格納できた場合には、超Ｋ文字見出し語辞書ｄK+のアドレスｈ０のリンクフィールド１０３に、リンク情報としてアドレスｈ１を格納する（図４ステップＳ１２２）。
【００４１】
また、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１の格納領域１０２に文字列が既に格納されており、この文字列が文字列Ｂと同じであったときには、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１のポインタフィールド１０４に事前に格納されているアドレスｒ１によって特定される格納領域１０５に、見出し語Ａを格納する（図４ステップＳ１２３）。
【００４２】
辞書管理手段は、ステップＳ１２１，Ｓ１２３において、ｒ１がまだ用意されていない場合には、アドレスｒ１に対応する格納領域１０５を新たに確保した後に、この格納領域１０５に文字列Ａを格納すると共に、そのアドレスｒ１を超Ｋ文字見出し語辞書ｄK+のアドレスｈ１のポインタフィールド１０４に格納する。
【００４３】
ただし、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｒ１によって特定される格納領域１０５に文字列が既に格納されており、この文字列が見出し語Ａと同じであったときには、特段処理を行わずに、ステップＳ１００に戻って次の見出し語の処理を行う。
【００４４】
また、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１の格納領域１０２に文字列が格納されており、この文字列が文字列Ｂでなかったときには、変数ｔを１増やし（ステップＳ１１８）、変数ｔが所定の上限回数Ｇ以下の場合には、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１のリンクフィールド１０３に格納されている値ｈ［ｔ］（ここではｔ＝２なので、ｈ［ｔ］＝ｈ２）を取得するか、このリンクフィールド１０３に値が格納されていないときには、アドレスｈ１のハッシュ関数値ｈ２＝ｎｅｘｔ＿ｈａｓｈK（ｈ１）を計算する（ステップＳ１１９）。
【００４５】
辞書管理手段は、取得または計算した値ｈ２を基に、超Ｋ文字見出し語辞書ｄK+のアドレスｈ２の格納領域１０２を参照し（ステップＳ１２０）、この格納領域１０２に未だ何も格納されていないときは、この格納領域１０２のデータとして文字列Ｂを格納し、超Ｋ文字見出し語辞書ｄK+のアドレスｈ２のポインタフィールド１０４に事前に格納されているアドレスｒ［ｔ］（ここではｔ＝２なので、ｒ［ｔ］＝ｒ２）によって特定される格納領域１０５に、見出し語Ａを格納する（ステップＳ１２１）。そして、辞書管理手段は、見出し語Ａを格納できた場合には、超Ｋ文字見出し語辞書ｄK+のアドレスｈ１のリンクフィールド１０３に、リンク情報としてアドレスｈ２を格納する（ステップＳ１２２）。
【００４６】
また、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｈ２の格納領域１０２に文字列が格納されており、この文字列が文字列Ｂと同じであったときには、超Ｋ文字見出し語辞書ｄK+のアドレスｈ２のポインタフィールド１０４に事前に格納されているアドレスｒ２によって特定される格納領域１０５に、見出し語Ａを格納する（ステップＳ１２３）。
【００４７】
辞書管理手段は、ステップＳ１２１，Ｓ１２３において、ｒ２がまだ用意されていない場合には、アドレスｒ２に対応する格納領域１０５を新たに確保した後に、この格納領域１０５に文字列Ａを格納すると共に、そのアドレスｒ２を超Ｋ文字見出し語辞書ｄK+のアドレスｈ２のポインタフィールド１０４に格納する。
【００４８】
ただし、辞書管理手段は、超Ｋ文字見出し語辞書ｄK+のアドレスｒ２によって特定される格納領域１０５に文字列が既に格納されており、この文字列が見出し語Ａと同じであったときには、特段処理を行わずに、ステップＳ１００に戻って次の見出し語の処理を行う。
【００４９】
こうして、未収録の見出し語Ａを超Ｋ文字見出し語辞書ｄK+に格納できるまで、ステップＳ１１８〜Ｓ１２３の処理が繰り返し実行される。辞書管理手段は、変数ｔが所定の上限回数Ｇを超えても、見出し語Ａを超Ｋ文字見出し語辞書ｄK+に格納できなかった場合には、見出し語Ａの処理を打ち切り、ユーザに対して格納の失敗を通知する（図４ステップＳ１２４）。
【００５０】
以上のような図３、図４の処理を、処理対象の見出し語が無くなるまで、見出し語ごとに実行する。これにより、全ての見出し語を辞書に格納することができる。
なお、図１に示したｊ文字見出し語辞書ｄjの構造は、見出し語の文字数ｊごとに用意され、図２に示した超Ｋ文字見出し語辞書ｄK+の構造は、見出し語の文字数が所定数Ｋより大きい見出し語を全て格納するために１つ用意される。図２に示した超Ｋ文字見出し語辞書ｄK+の構造の一部を、図１に示したｊ文字見出し語辞書ｄjの構造によって共用するようにしてもよい。
【００５１】
次に、テキストファイル内に、辞書に収録されている単語が出現するかどうかを検出する方法について、概要を説明する。
いま、テキストファイル中の現在の着目点の１文字を単語候補とし、この文字からハッシュ関数値を計算し、このハッシュ関数値により、辞書に格納されている該当する見出し語を読み出し、着目点の文字と辞書に格納されている見出し語とを比較することで、着目点の文字が辞書に収録されているかどうかを判定する。同様に、着目点の文字を末尾とし、文字数が所定数Ｋ以下である着目対象の文字列を単語候補とし、この文字列からハッシュ関数値を計算し、このハッシュ関数値により、辞書に格納されている該当する見出し語を読み出し、着目対象の文字列と辞書に格納されている見出し語とを比較することで、着目対象の文字列が辞書に収録されているかどうかを判定する。
【００５２】
それとともに、着目点の文字を末尾とし、文字数が所定数Ｋである文字列から計算したハッシュ関数値と同じアドレスのポインタフィールドに格納されている、より長い文字数の収録候補があることを示すポインタに基づいて、着目点の文字を末尾とする文字数がＫである先頭文字列を有し、かつ文字数が所定数Ｋより大きい全ての見出し語を例えばＤＭＡ転送により高速に辞書から読み出してＤＦＡ部に送出し、先頭文字列よりも後の文字について、逐次的に、かつ必要数並列処理により、着目点の文字と一致するかどうかを比較する。
【００５３】
ＤＦＡ部における逐次的な処理では、常にテキストファイルの現在の着目点の文字とキューから取り出した文字列の先頭文字とを比較する。現在の着目点の文字とキューから取り出した文字列の先頭文字とが一致していて、かつその文字がキューから取り出した文字列の最終文字であれば、この文字を末尾とする、文字数が所定数Ｋよりも大きい文字列が辞書に収録されていると判定する。
【００５４】
また、現在の着目点の文字とキューから取り出した文字列の先頭文字とが一致しているが、その文字がキューから取り出した文字列の最終文字でない場合、キューから取り出した文字列から先頭文字を１文字削除し、先頭文字を削除した文字列を改めてキューに登録する。
【００５５】
なお、現在の着目点の文字とキューから取り出した文字列の先頭文字とを比較した結果、文字が一致していなければ、キューから取り出した文字列を再度キューに登録することはせずに破棄する。
【００５６】
図５、図６は本実施の形態の単語抽出装置の構成を示すブロック図、図７は単語抽出装置の単語抽出動作を説明するフローチャートである。なお、図５〜図７の例では、テキストファイルに、例えば「明日の天気は晴れ」という文字列が含まれており、現在の着目点の１文字はこの文字列中の「れ」であるとする。この着目点の文字をＣ0とする。また、着目点よりも１文字前の文字をＣ-1（上記の文字列の「晴」の字）、２文字前の文字をＣ-2（「は」の字）、３文字前の文字をＣ-3（「気」の字）、４文字前の文字をＣ-4（「天」の字）、５文字前の文字をＣ-5（「の」の字）、６文字前の文字をＣ-6（「日」の字）、７文字前の文字をＣ-7（「明」の字）とする。
【００５７】
図５に示すように、単語抽出装置は、現在の着目点の文字と、着目点の文字を末尾とし、文字数が所定数Ｋ以下である文字列とを格納する部分文字列格納部１と、部分文字列格納部１に格納された文字と文字列のそれぞれについてハッシュ関数を計算するハッシュ生成部２と、辞書を格納する辞書格納部３と、テキストファイル中の、文字数が所定数Ｋより大きい文字列について辞書に収録されている見出し語との文字列一致検査のためのＤＦＡ部４（第２の検出手段）と、着目点の文字または文字列が辞書に収録されていることをユーザに通知するための検出部５（第１の検出手段）と、単語抽出装置全体を制御する制御部６とから構成される。
辞書格納部３は、前述のｊ文字見出し語辞書ｄj（図５のｄ1〜ｄK）と、前述の超Ｋ文字見出し語辞書ｄK+と、送出機能部３０とを有する。
【００５８】
図６に示すように、ＤＦＡ部４は、送出機能部３０から送出された見出し語を格納する転送レートバッファ４０と、転送レートバッファ４０に格納されている各見出し語からそれぞれ所定数Ｋ分の文字数の先頭文字列を削除する部分文字抽出部４１と、文字列を格納するためのキュー（queue）４２と、部分文字抽出部４１が先頭文字列を削除した見出し語をキュー４２に格納する登録部４３と、キュー４２から取り出した文字列の先頭文字を除去した部分文字列を出力する部分文字抽出部４４と、キューから取り出した文字列の先頭文字を出力する先頭文字抽出部４５と、先頭文字抽出部４５が取り出した文字と着目点の文字とを比較する比較部４６と、先頭文字抽出部４５が取り出した文字と着目点の文字とが一致し、かつキュー４２から取り出した文字列に前記先頭文字よりも後の文字がある場合に、部分文字抽出部４４から出力された文字列をキュー４２に登録する登録部４７とから構成される。
【００５９】
以下、図７に基づいて単語抽出装置の動作を説明する。テキストファイル中の着目点の１文字Ｃ0を取得すると（図７ステップＳ２００）、文字Ｃ0を単語候補として、この単語候補が１文字見出し語辞書ｄ1に見出し語として収録されているか否かの検査（図７ステップＳ２０１，Ｓ２０４）と、文字Ｃ0を末尾として含むｊ文字（ただし、１＜ｊ≦Ｋ）の文字列を単語候補として、この単語候補がｊ文字見出し語辞書ｄjに見出し語として収録されているか否かの検査（図７ステップＳ２０２，Ｓ２０５）とが開始され、併せて、文字Ｃ0の１文字から始まるキュー登録があるか否かの検査（図７ステップＳ２０３）が、ＤＦＡ部４で開始される。
【００６０】
部分文字列格納部１は、現在の着目点の文字Ｃ0を例えば、ｊ文字ＦＩＦＯ（first in，first out）として保持することによって、文字Ｃ0（単語候補）と、文字Ｃ0を末尾として含むｊ文字（ただし、１＜ｊ≦Ｋ）の文字列Ｓj（単語候補）とを保持している。
ハッシュ生成部２は、文字Ｓ1＝Ｃ0についてハッシュ関数ｈ1（Ｓ1）を計算する（図７ステップＳ２０１）。
【００６１】
１文字見出し語辞書ｄ1は、見出し語のハッシュ関数を計算したときにハッシュ関数がｈとなる、文字数が１の見出し語を予め収録している。
検出部５は、文字Ｓ1＝Ｃ0から計算されたハッシュ関数ｈ1（Ｓ1）により１文字見出し語辞書ｄ1を検索した結果、１文字見出し語辞書ｄ1の、ハッシュ関数ｈ1（Ｓ1）と同じ値のアドレスで特定される格納領域に文字Ｓ1＝Ｃ0が収録されている場合、文字Ｓ1＝Ｃ0が辞書に収録されていることをユーザに対して通知する（図７ステップＳ２０４）。
【００６２】
また、ハッシュ生成部２は、文字Ｃ0を末尾として含む、ｊ文字の各文字列Ｓj（ただし、１＜ｊ≦Ｋ）について、それぞれハッシュ関数ｈj（Ｓj）を計算する（図７ステップＳ２０２）。これらのハッシュ関数ｈj（Ｓj）の計算方法は互いに同じものである必要はない。
【００６３】
ｊ文字見出し語辞書ｄj（ただし、１＜ｊ≦Ｋ）は、見出し語のハッシュ関数を計算したときにハッシュ関数が同じｈとなる、文字数がｊの見出し語を予め収録している。このｊ文字見出し語辞書ｄjは、前述のとおり、該当する見出し語が複数存在する場合には、これらの見出し語をリンクによって関係付けることにより、ｊ文字の文字列Ｓj（単語候補）から計算されたハッシュ関数ｈj（Ｓj）を検索キーとして検索したときに、ハッシュ関数ｈj（Ｓj）で特定されるｊ文字の全ての見出し語を検索できるようになっている。
【００６４】
検出部５は、ｊ文字の各文字列Ｓjから計算されたハッシュ関数ｈj（Ｓj）によりｊ文字見出し語辞書ｄjを検索した結果、ｊ文字見出し語辞書ｄjの、ハッシュ関数ｈj（Ｓj）と同じ値のアドレスで特定される格納領域に文字列Ｓjが収録されている場合、文字列Ｓjが辞書に収録されていることをユーザに対して通知する（図７ステップＳ２０５）。検出部５は、このような処理をｊ文字（ただし、１＜ｊ≦Ｋ）の文字列Ｓj毎に行う。
【００６５】
超Ｋ文字見出し語辞書ｄK+は、文字数が所定数Ｋよりも大きい見出し語のみを予め収録している。超Ｋ文字見出し語辞書ｄK+は、文字数が所定数Ｋよりも大きい文字列（単語候補）の先頭Ｋ文字分の部分文字列から計算されたハッシュ関数ｈKを検索キーとして検索したときに、ハッシュ関数ｈKで特定されるＫ文字の補助見出し語を先頭文字列として含む、文字数が所定数Ｋよりも大きい全ての見出し語を検索できるようになっている。超Ｋ文字見出し語辞書ｄK+は、前述のとおり、見出し語をポインタとリンクによって関連付けることにより、ハッシュ関数ｈKによる検索ができるようになっている。
【００６６】
ハッシュ生成部２は、文字Ｃ0を末尾として含む、文字数が所定数Ｋよりも大きい文字列（単語候補）の先頭Ｋ文字分の部分文字列についてハッシュ関数ｈKを計算する（図７ステップＳ２０６）。
【００６７】
辞書格納部３の送出機能部３０は、文字数が所定数Ｋよりも大きい文字列（単語候補）の先頭Ｋ文字分の部分文字列から計算されたハッシュ関数ｈKにより超Ｋ文字見出し語辞書ｄK+を検索し、ハッシュ関数ｈKで特定されるＫ文字の補助見出し語ＳKを先頭文字列として含む、文字数が所定数Ｋよりも大きい全ての見出し語を超Ｋ文字見出し語辞書ｄK+から取り出してＤＦＡ部４へ送出する（図７ステップＳ２０７）。
【００６８】
ＤＦＡ部４は、辞書格納部３の送出機能部３０から取得した、Ｋ文字までの一致が確認された見出し語のリストに対して、Ｋ文字以降の文字の一致を追跡する機能を持つ。その詳しい動作について図６を用いて説明する。
【００６９】
ＤＦＡ部４全体としては、キュー４２に格納された語の全てに対して、その先頭文字が現在の入力文字（着目点の文字）と一致しているかどうかを調べ、先頭文字が入力文字と一致していない語をキュー４２から削除するという機能を実行している（図７ステップＳ２０３）。以下、図６と図８を用いてＤＦＡ部４の説明を続ける。図８はＤＦＡ部４と制御部６の動作の詳細を説明するフローチャートである。
【００７０】
まず、現在の入力文字Ｃ0の１つ前の文字Ｃ-1を末尾とするＫ文字の文字列を先頭文字列として含む、文字数が所定数Ｋよりも大きい見出し語、すなわち辞書格納部３の送出機能部３０から取得した、Ｋ文字までの一致が確認された見出し語のリストは、ＤＦＡ部４の転送レートバッファ４０に格納されている。なお、この送出機能部３０からの送出処理および転送レートバッファ４０への格納処理は、入力文字が現在の入力文字Ｃ0の１つ前の文字Ｃ-1であったときに行われた処理である。
【００７１】
ＤＦＡ部４の部分文字抽出部４１は、制御部６による制御に従って、転送レートバッファ４０に格納されている各見出し語からそれぞれＫ文字の先頭文字列を削除する（図８ステップＳ３００）。
ＤＦＡ部４の登録部４３は、制御部６による制御に従って、部分文字抽出部４１が先頭文字列を削除した見出し語をキュー４２に格納する（図８ステップＳ３０１）。これにより、キュー４２には、その先頭文字が現在の入力文字（着目点の文字）と一致しているか検査される見出し語由来の文字列が格納されることになる。
【００７２】
ＤＦＡ部４の先頭文字抽出部４５と部分文字抽出部４４とは、キュー４２から文字列を１つ共有して取り出す（図８ステップＳ３０２）。
部分文字抽出部４４は、キュー４２から取り出した文字列の先頭文字を除去した部分文字列を登録部４７に与える（図８ステップＳ３０３）。
【００７３】
先頭文字抽出部４５は、キュー４２から取り出した文字列の先頭文字を比較部４６に与える（図８ステップＳ３０４）。
比較部４６は、先頭文字抽出部４５が取り出した文字と現在の入力文字Ｃ0との比較を行い、結果を制御部６に通知する（図８ステップＳ３０５）。
【００７４】
制御部６は、比較部４６からの通知に基づき、部分文字抽出部４４から登録部４７に与えられた文字列を登録部４７が再びキュー４２に登録するかどうかを制御する。具体的には、制御部６は、先頭文字抽出部４５が取り出した文字と現在の入力文字Ｃ0とが一致した場合（図８ステップＳ３０６においてＹＥＳ）、ステップＳ３０２でキュー４２から取り出した文字列に、先頭文字抽出部４５が取り出した先頭文字よりも後の文字があるかどうかを調べる（図８ステップＳ３０７）。
【００７５】
キュー４２から取り出した文字列に、先頭文字よりも後の残りの文字がない場合（ステップＳ３０７においてＮＯ）、制御部６は、検出部５に対して見出し語の検出を通知する（図８ステップＳ３０８）。この通知に応じて、検出部５は、文字数が所定数Ｋよりも大きい文字列（文字Ｃ-1を末尾とするＫ文字の文字列の後に文字Ｃ0が続く（Ｋ＋１）文字の文字列）が辞書に収録されていることをユーザに対して通知する。
【００７６】
また、制御部６は、キュー４２から取り出した文字列に残りの文字がある場合（ステップＳ３０７においてＹＥＳ）、登録部４７に対して、部分文字抽出部４４から入力された部分文字列をキュー４２に登録するよう指示する。こうして、キュー４２から取り出した文字列の先頭文字が現在の入力文字Ｃ0と一致し、かつキュー４２から取り出した文字列に先頭文字よりも後の文字がある場合、先頭文字よりも後の残りの部分がキュー４２に再び登録される（図８ステップＳ３０９）。
【００７７】
制御部６は、キュー４２から取り出した文字列の先頭文字が現在の入力文字Ｃ0と一致しない場合（図８ステップＳ３０６においてＮＯ）、特段処理を行わずに、ステップＳ３１０に進む。
【００７８】
ステップＳ３１０では、制御部６は、キュー４２に未処理の文字列が格納されているかどうかを判定する。キュー４２に未処理の文字列が格納されている場合には（ステップＳ３１０においてＹＥＳ）、ステップＳ３０２に戻る。こうして、キュー４２に含まれる全ての文字列に対してステップＳ３０２〜Ｓ３１０の処理が実行される。なお、ここで言う未処理の文字列とは、現在の入力文字Ｃ0を対象とするＤＦＡ部４の動作でステップＳ３０２の処理が開始される前にキュー４２に格納されていた文字列のうち、ステップＳ３０２〜Ｓ３１０の処理がなされていない文字列のことであり、現在の入力文字Ｃ0を対象とするＤＦＡ部４の動作でステップＳ３０９の処理によりキュー４２に登録された文字列は、未処理の文字列には含まれない。
【００７９】
制御部６は、ＤＦＡ部４のキュー４２に未処理の文字列がなくなり、ＤＦＡ部４の処理が終わると、図７における待ち合わせに制御を移行させる。前述のとおり、辞書格納部３の送出機能部３０からは、現在の入力文字（注目点の文字）Ｃ0を末尾とするＫ文字の文字列を先頭文字列として含む、文字数が所定数Ｋよりも大きい見出し語のリストがＤＦＡ部４に送出される。ＤＦＡ部４の転送レートバッファ４０には、この送出機能部３０から送出された見出し語が格納される（図７ステップＳ２０８）。
【００８０】
こうした機能により、ＤＦＡ部４全体としては、現在の入力文字Ｃ0の１つ前の文字Ｃ-1を末尾とするＫ文字の文字列を先頭文字列として含む、文字数が所定数Ｋよりも大きい見出し語から先頭文字列を削除した部分文字列をキュー４２に格納しておき、これらの文字列とキュー４２に既に格納されている語の全てについて、その先頭文字が現在の入力文字Ｃ0と一致しているか調べ、一致している文字列部分だけを残し、キュー４２の登録内容を常に更新するという機能を達成している。
【００８１】
なお、ＤＦＡ部４の内部のキュー４２と先頭文字抽出部４５と比較部４６と登録部４７と部分文字抽出部４４とをそれぞれ複数用意しておき、ステップＳ３０２〜Ｓ３１０の処理を各キュー４２に登録されている文字列に対して同時に並列実行することによって、ステップＳ３０２〜Ｓ３１０の処理回数を１回、すなわち繰り返し無しで完了させることができ、用意できる資源量に応じて、所望の性能を得ることができる。この場合、キュー４２と先頭文字抽出部４５と比較部４６と登録部４７と部分文字抽出部４４のそれぞれの個数を、文字列数の上限より大きい数にしておけばよい。
【００８２】
以上で、図７の処理が終了し、テキストファイル中の次の着目点の１文字（文字Ｃ0の１つ後の文字）について図７の処理を開始する。
【００８３】
本実施の形態の単語抽出装置を実装する装置のブロック図を図９に示す。この単語抽出装置を実装する装置は、コンピュータ（プロセサ１０）とＦＰＧＡ１１とが搭載された装置である。入出力装置１２は、見出し語およびテキストファイルの入力と、検出部５の結果の出力を行う。入出力装置１２による出力方法としては、検出部５からの通知結果を画面に表示したり、検出部５からの通知結果の情報を外部に送出したりする方法がある。ローカルメモリ１３は、プロセサ１０のプログラムとプロセサ１０の処理の途中結果を格納する。
【００８４】
プロセサ１０（ＣＰＵ：Central Processing Unit）は、ローカルメモリ１３に格納されたプログラムに従って処理を実行し、バス１５に接続されている他の装置の制御手順を提供し、一部の処理も自ら行う。ＤＲＡＭ（Dynamic Random Access Memory）１４は、見出し語を収録する辞書の記憶装置として機能する。ＦＰＧＡ１１は、ＤＦＡ４の機能を実現する。
【００８５】
図５に示した本実施の形態の単語抽出装置を図９に示した装置に実装する場合に各構成要素が実現する機能を図１０を用いて説明する。
前記の所定数Ｋをたかだか２（あるいは３）とすると、部分文字列格納部１と、ハッシュ生成部２と、超Ｋ文字見出し語辞書ｄK+を除く辞書格納部３と、検出部５と、制御部６とは、プロセサ１０によるソフトウエア処理によって実現することができる。辞書格納部３のｊ文字見出し語辞書ｄj（図１０のｄ1〜ｄK）は、プロセサ１０内部のメモリに格納される。
【００８６】
超Ｋ文字見出し語辞書ｄK+については、Ｋの値が小さいときには大規模となるため、専用のＤＲＡＭ１４に格納する。
前記のとおり、ＤＦＡ４については、ＦＰＧＡ１１によって実現できる。なお、プロセサ１０およびローカルメモリ１３については、個別の部品を使用する方法の他に、ＦＰＧＡ１１に搭載する方法もある。
【００８７】
また、前述の辞書管理手段は、プロセサ１０と、ローカルメモリ１３に格納されたプログラムによって実現してよいし、図９に示した装置の外部に設けられる他のコンピュータ等の装置によって実現してもよい。
【００８８】
本実施の形態における辞書格納部３の１文字見出し語辞書ｄ1については、ハッシュ関数値を用いずに、文字コードそのものをアドレスとして使用することも可能である。この場合の単語抽出装置の構成を図１１に示す。また、図１１の単語抽出装置の動作を図１２に示す。
【００８９】
１文字見出し語辞書ｄ1は、文字数が１の見出し語のみを予め収録しており、現在の入力文字（着目点の文字）Ｃ0の文字コードを検索キーとして検索できるようになっている。
検出部５は、１文字見出し語辞書ｄ1に現在の入力文字Ｃ0が収録されている場合、文字Ｃ0が辞書に収録されていることをユーザに対して通知する（図１２ステップＳ２０４ａ）。
【００９０】
なお、文字コードの一致は、文字、すなわち見出し語の一致であるため、１文字のみで構成されている見出し語そのものを１文字見出し語辞書ｄ1に登録しなくてもよい。すなわち、１文字の見出し語を１文字見出し語辞書ｄ1に登録する場合には、当該見出し語の文字コード（アドレス）に対応する１文字見出し語辞書ｄ1の格納領域に例えば値１を格納し、１文字見出し語辞書ｄ1に登録されていない１文字の見出し語については、この見出し語の文字コード（アドレス）に対応する１文字見出し語辞書ｄ1の格納領域に例えば値０を格納しておけばよい。この場合の１文字見出し語辞書ｄ1の構造の例を図１３に示す。図１３の例では、文字コードｍ０，ｍ２の格納領域に値１が格納され、文字コードｍ１の格納領域に値０が格納されている。
【００９１】
これにより、検出部５は、現在の入力文字の文字コードをアドレスとして１文字見出し語辞書ｄ1を参照したときに、このアドレスで特定される１文字見出し語辞書ｄ1の格納領域に値１が格納されている場合には、入力文字が１文字見出し語辞書ｄ1に収録されていると判定し、アドレスで特定される１文字見出し語辞書ｄ1の格納領域に値０が格納されている場合には、入力文字が１文字見出し語辞書ｄ1に収録されていないと判定することができる。
【００９２】
以上説明したように、本実施の形態では、分かち書きの無い日本語表記等のテキストファイルに対する単語の検出であっても、大規模辞書の先頭の事前に定めた所定文字数Ｋまでの検査と、所定文字数Ｋを超えた末尾までの検査に分けることによって、所定文字数Ｋまでの検査をプロセサ１０で行い、所定文字数Ｋを超えた末尾までの検査をＦＰＧＡ１１で行い、大規模辞書（超Ｋ文字見出し語辞書ｄK+）をＤＲＡＭ１４で保有するという実装を行うことが可能となる。
【００９３】
ＦＰＧＡ１１内では、十分な数、たとえば、１０００程度のＤＦＡを並列して動作させることが可能である。そこで、ＤＲＡＭ１４のＤＭＡ転送能力が大きいことを利用して、所定文字数Ｋを超えた末尾までの検査についてはプロセサ１０を介さずにＦＰＧＡ１１で行うことが可能となり、負荷の偏りを軽減することができ、高速性が得られる。
【００９４】
また、ＦＰＧＡ１１内に搭載できるＤＦＡの数は、一般的な辞書の語数に対しては十分ではないが、大規模辞書をＤＲＡＭ１４で保有することにより、十分な規模、たとえば約百万語といった見出し語の搭載も可能となる。
また、本実施の形態では、辞書を構築する際に、ユーザが所定文字数Ｋの値を設定することができるので、単語抽出装置の性能の調整が可能となり、多数の見出し語を収録する大規模辞書の搭載と高速な単語検出が両立可能となる。
【産業上の利用可能性】
【００９５】
本発明は、テキストファイルの中から単語を抽出する技術に適用することができる。
【符号の説明】
【００９６】
１…部分文字列格納部、２…ハッシュ生成部、３…辞書格納部、４…ＤＦＡ部、５…検出部、６…制御部、３０…送出機能部、４０…転送レートバッファ、４１，４４…部分文字抽出部、４２…キュー、４３，４７…登録部、４５…先頭文字抽出部、４６…比較部、ｄj…ｊ文字見出し語辞書、ｄK+…超Ｋ文字見出し語辞書。
【図１】
2017084042.tif 000003
【図２】
2017084042.tif 000004
【図３】
2017084042.tif 000005
【図４】
2017084042.tif 000006
【図５】
2017084042.tif 000007
【図６】
2017084042.tif 000008
【図７】
2017084042.tif 000009
【図８】
2017084042.tif 000010
【図９】
2017084042.tif 000011
【図１０】
2017084042.tif 000012
【図１１】
2017084042.tif 000013
【図１２】
2017084042.tif 000014
【図１３】
2017084042.tif 000015