(57)【特許請求の範囲】
【請求項１】
w種類の記号からなる記号列が識別符号に対応付けて格納されるデータ構造を記憶する記憶部、
検索の対象となる記号列が当該データ構造における開始ノードから開始するように格納されているか否かを調べ、格納されている場合は、当該記号列に対応付けられた識別符号を検索結果とする検索部
を備える記号列検索装置であって、
当該データ構造には、
当該w種類の記号に対する遷移行列が格納されるノード配列であって、位置iの遷移行列は、当該ノード配列のi番目の要素からi+w-1番目の要素までの区間（以下、n[i]，…，n[i+w-1]という。）によって表現され、ノード配列と、
当該データ構造に格納される記号列に含まれる部分記号列が格納される記号配列であって、位置j、長さkの部分記号列は、当該記号配列のj番目の要素からj+k-1番目の要素までの区間（以下、m[i]，…，m[i+w-1]という。）によって表現される記号配列と、
ノードの列であって、当該ノードの列に含まれるノードのそれぞれは、
（ａ）当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれか一方が、区別可能に格納される当該遷移行列参照領域、
（ｂ）当該記号配列中における部分記号列の位置および長さ、もしくは、識別符号のいずれか一方が、区別可能に格納される当該部分記号列参照領域
を有するノードの列と、
が格納され、当該遷移行列の要素は、それぞれ、当該ノードの列に含まれるノードのいずれかに対応付けられ、
当該データ構造に或る記号列s1，s2，…，sNが、或る識別符号に対応付けられて、当該ノードの列に含まれるp番目のノードから開始するように格納されるとき、
（１）当該p番目のノードの部分記号列参照領域に、当該記号配列中における部分記号列の位置jおよび長さkが格納されており、かつ、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，sNと一致する場合、当該p番目のノードの遷移行列参照領域に当該或る識別符号が格納されており、
（２）当該p番目のノードの部分記号列参照領域に当該記号配列中における部分記号列の位置jおよび長さkが格納されており、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，skと一致し、当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納されている場合、当該データ構造には、記号列sk+2，…，sNが当該或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されており、
（３）当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納される場合、当該データ構造には、記号列s2，…，sNが当該或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されており、
（４）当該データ構造に長さ０の記号列が、当該或る識別符号に対応付けられて、r番目のノードから開始するように格納される場合、当該r番目のノードの遷移行列参照領域、もしくは、部分記号列参照領域に、当該或る識別符号が格納されており、
当該データ構造において、当該ノードの列に含まれるノードのいずれか１つが、開始ノードとされる
ことを特徴とする記号列検索装置。
【請求項２】
請求項１に記載の記号列検索装置であって、
当該遷移行列参照領域は、整数値により、当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれかを格納し、当該整数値中の所定のビットが立っているか否かにより、当該ノード配列中における遷移行列の位置と識別符号とのいずれを格納しているかを区別する
ことを特徴とする記号列検索装置。
【請求項３】
請求項１に記載の記号列検索装置であって、
当該部分記号列参照領域は、
整数値により当該記号配列中における部分記号列の長さを格納し、
整数値により、当該記号配列中における部分記号列の位置、もしくは、識別符号のいずれかを格納し、当該整数値中の所定のビットが立っているか否かにより、当該ノード配列中における部分記号列の位置と識別符号とのいずれを格納しているかを区別する
ことを特徴とする記号列検索装置。
【請求項４】
請求項１から３のいずれか１項に記載の記号列検索装置であって、
当該データ構造は、文字列に一意に対応付けられたビット列を所定のビット数ごとに区切ったビット列の列を格納し、
当該所定のビット数ごとに区切ったビット列を当該所定の種類の記号とする
ことを特徴とする記号列検索装置。
【請求項５】
請求項１から３のいずれか１項に記載の記号列検索装置であって、
当該データ構造は、文字列を格納し、
当該所定の種類の記号は、当該文字列が含む文字である
ことを特徴とする記号列検索装置。
【請求項６】
請求項１から５のいずれか１項に記載の記号列検索装置であって、
当該ノードの列は、当該データ構造において当該ノード配列とは異なる領域に格納され、
当該ノード配列の各要素には、当該ノードの列に含まれるノードのインデックスが格納され、
当該ノード配列の各要素は、当該ノードの列に含まれる「当該要素に格納されるインデックス」番目のノードが対応付けられる
ことを特徴とする記号列検索装置。
【請求項７】
請求項１から５のいずれか１項に記載の記号列検索装置であって、
当該ノード配列の各要素には、当該要素に対応付けられるノードが格納される
ことを特徴とする記号列検索装置。
【請求項８】
請求項１から７のいずれか１項に記載の検索装置であって、
前記記憶部に記憶されるデータ構造に格納されているか否かを調べる記号列の入力を受け付ける検索記号列入力受付部
をさらに備え、
前記検索部は、前記入力を受け付けられた記号列が当該データ構造における開始ノードから開始するように格納されているか否かを調べ、格納されている場合は、当該記号列のそれぞれに対応付けられた識別符号を検索結果とし、
当該データ構造に或る記号列s1，s2，…，sNが或る識別符号に対応付けてp番目のノードから開始するように格納されているときに、当該或る識別符号を検索結果とするものであり、
（１）当該p番目のノードの部分記号列参照領域に、当該記号配列中における部分記号列の位置jおよび長さkが格納されており、かつ、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，sNと一致する場合、当該p番目のノードの遷移行列参照領域に或る識別符号が格納されていれば、当該或る識別符号を検索結果とし、
（２）当該p番目のノードの部分記号列参照領域に当該記号配列中における部分記号列の位置jおよび長さkが格納されており、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，skと一致し、当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納されている場合、当該データ構造は、記号列sk+2，…，sNが或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されていれば、当該或る識別符号を検索結果とし、
（３）当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納される場合、当該データ構造には、記号列s2，…，sNが或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されていれば、当該或る識別符号を検索結果とし、
（４）当該データ構造に長さ０の記号列が、当該或る識別符号に対応付けられて、r番目のノードから開始するように格納される場合、当該r番目のノードの遷移行列参照領域、もしくは、部分記号列参照領域に、或る識別符号が格納されていれば、当該或る識別符号を検索結果とする
ことを特徴とする記号列検索装置。
【請求項９】
w種類の記号からなる記号列が識別符号に対応付けて格納されるデータ構造を記憶する記憶部、検索記号列入力受付部、検索部を備える記号列検索装置において実行される記号列検索方法であって、
当該データ構造には、
当該w種類の記号に対する遷移行列が格納されるノード配列であって、位置iの遷移行列は、当該ノード配列のi番目の要素からi+w-1番目の要素までの区間（以下、n[i]，…，n[i+w-1]という。）によって表現され、ノード配列と、
当該データ構造に格納される記号列に含まれる部分記号列が格納される記号配列であって、位置j、長さkの部分記号列は、当該記号配列のj番目の要素からj+k-1番目の要素までの区間（以下、m[i]，…，m[i+w-1]という。）によって表現される記号配列と、
ノードの列であって、当該ノードの列に含まれるノードのそれぞれは、
（ａ）当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれか一方が、区別可能に格納される当該遷移行列参照領域、
（ｂ）当該記号配列中における部分記号列の位置および長さ、もしくは、識別符号のいずれか一方が、区別可能に格納される当該部分記号列参照領域
を有するノードの列と、
が格納され、当該遷移行列の要素は、それぞれ、当該ノードの列に含まれるノードのいずれかに対応付けられ、
当該データ構造に或る記号列s1，s2，…，sNが、或る識別符号に対応付けられて、当該ノードの列に含まれるp番目のノードから開始するように格納されるとき、
（１）当該p番目のノードの部分記号列参照領域に、当該記号配列中における部分記号列の位置jおよび長さkが格納されており、かつ、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，sNと一致する場合、当該p番目のノードの遷移行列参照領域に当該或る識別符号が格納されており、
（２）当該p番目のノードの部分記号列参照領域に当該記号配列中における部分記号列の位置jおよび長さkが格納されており、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，skと一致し、当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納されている場合、当該データ構造には、記号列sk+2，…，sNが当該或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されており、
（３）当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納される場合、当該データ構造には、記号列s2，…，sNが当該或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されており、
（４）当該データ構造に長さ０の記号列が、当該或る識別符号に対応付けられて、r番目のノードから開始するように格納される場合、当該r番目のノードの遷移行列参照領域、もしくは、部分記号列参照領域に、当該或る識別符号が格納されており、
当該データ構造において、当該ノードの列に含まれるノードのいずれか１つが、開始ノードとされ、
前記検索記号列入力受付部が、前記記憶部に記憶されるデータ構造に格納されているか否かを調べる記号列の入力を受け付ける検索記号列入力受付工程と、
前記検索部が、前記入力を受け付けられた記号列が当該データ構造における開始ノードから開始するように格納されているか否かを調べ、格納されている場合は、当該記号列のそれぞれに対応付けられた識別符号を検索結果とする検索工程と、
を備え、
前記検索工程では、
当該データ構造に或る記号列s1，s2，…，sNが或る識別符号に対応付けてp番目のノードから開始するように格納されているときに、当該或る識別符号を検索結果とするものであり、
（１）当該p番目のノードの部分記号列参照領域に、当該記号配列中における部分記号列の位置jおよび長さkが格納されており、かつ、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，sNと一致する場合、当該p番目のノードの遷移行列参照領域に或る識別符号が格納されていれば、当該或る識別符号を検索結果とし、
（２）当該p番目のノードの部分記号列参照領域に当該記号配列中における部分記号列の位置jおよび長さkが格納されており、当該記号配列中における部分記号列の位置jおよび長さkにより表現される部分記号列mj，…，mj+k-1がs1，…，skと一致し、当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納されている場合、当該データ構造は、記号列sk+2，…，sNが或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されていれば、当該或る識別符号を検索結果とし、
（３）当該p番目のノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置qが格納される場合、当該データ構造には、記号列s2，…，sNが或る識別符号に対応付けられて「遷移行列n[q]，…，n[q+w-1]の記号sk+1に対応する要素に対応付けられるノード」から開始するように格納されていれば、当該或る識別符号を検索結果とし、
（４）当該データ構造に長さ０の記号列が、当該或る識別符号に対応付けられて、r番目のノードから開始するように格納される場合、当該r番目のノードの遷移行列参照領域、もしくは、部分記号列参照領域に、或る識別符号が格納されていれば、当該或る識別符号を検索結果とする
ことを特徴とする記号列検索方法。
【請求項１０】
コンピュータを請求項１から８のいずれか１項に記載の記号列検索装置の各部として機能させるプログラムを記録したことを特徴とするコンピュータ読取可能な情報記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、記号列をデータ構造に効率良く格納し、当該データ構造から記号列を検索し、当該データ構造へ記号列を追加して格納するのに好適な、データ構造、記号列検索装置、記号列格納装置、記号列検索方法、記号列格納方法、ならびに、プログラムに関する。
【０００２】
【従来の技術】
従来から、記号列（文字の並び等）が辞書に登録されているか否かを高速に判断するため、辞書をトライ（trie）構造のデータ構造とする手法が提案されている。
【０００３】
言語処理では、共通接頭辞検索（Common Prefix Search）を用いることが多いが、トライ構造は、この共通接頭辞検索を高速に実行できるような索引構造である。
【０００４】
記号列に含まれる記号の種類がw種類であるとするとき、このようなトライ構造を単純に構成すると2w分木となり、データ構造のサイズのオーダーはO(2w/w)となってしまう。
【０００５】
そこで従来から、最小接頭辞トライ（Minimal Prefix Trie）というデータ構造が提案されている。これは、トライ構造の開始ノードから終端ノードまでに至る経路の中で、分岐が発生しない連続する２つ以上のノードをまとめあげて、これらにより表現される記号列を部分記号列として別途記憶することにより、データ構造のサイズを小さくしようとするものである。
【０００６】
各ノードをノード配列に格納し、部分記号列を当該記号の配列（記号配列）にて表現した場合、最小接頭辞トライ構造では、各ノードには、以下の４種類の情報を格納する必要がある。
・部分記号列が記号配列内に記憶される位置
・当該部分記号列の長さ
・開始ノードからそのノードに至るまでの記号列が当該最小接頭辞トライに格納（登録）された記号列である場合、当該記号列に割り当てられる識別符号
・当該ノードからの遷移先を表現する行列（配列）のノード配列中における位置
【０００７】
【発明が解決しようとする課題】
しかしながら、高速な検索というトライ構造の利点は残したまま、従来の最小接頭辞トライよりもさらにデータ構造のサイズを小さくしたい、という要望は大きい。
【０００８】
本発明は、記号列をデータ構造に効率良く格納し、当該データ構造から記号列を検索し、当該データ構造へ記号列を追加して格納するのに好適な、データ構造、記号列検索装置、記号列格納装置、記号列検索方法、記号列格納方法、ならびに、これらを実現するためのプログラムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記目的を達成するため、本発明の第１の観点に係るデータ構造は、所定の種類の記号からなる記号列を複数格納し、以下のように構成する。
【００１０】
すなわち、当該データ構造は、当該記号列のそれぞれに識別符号を対応付けて格納する。
【００１１】
さらに、当該データ構造は、複数のノードを格納するノード配列と、部分記号列を格納する記号配列と、を有する。
【００１２】
そして、当該複数のノードのそれぞれは、遷移行列参照領域と、部分記号列参照領域と、を有し、
（ａ）当該遷移行列参照領域は、当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれかを格納し、
（ｂ）当該部分記号列参照領域は、当該記号配列中における部分記号列の位置および長さ、もしくは、識別符号のいずれかを格納する。
【００１３】
また、当該データ構造は、当該複数のノードのいずれか１つを開始ノードとする。
【００１４】
さらに、或る記号列が、或る識別符号に対応付けて当該データ構造に格納される場合、
（１）現在ノードとしてまず開始ノードを採用し、現在記号列としてまず或る記号列を採用し、
（２）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列と一致する場合、当該現在ノードの遷移行列参照領域に或る識別符号が格納され、
（３）現在記号列の長さが０である場合、当該現在ノードの遷移行列参照領域もしくは部分記号列参照領域に或る識別符号が格納され、
（４）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列の先頭と一致する場合、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列として採用し、
（５）当該現在ノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置が格納される場合、当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として、それぞれ採用する
ことにより各ノードに格納される情報が定義される。
【００１５】
本データ構造により、各ノードの利用効率を向上し、トライ構造を表現するデータ構造のサイズを小さくすることができる。なお、本データ構造を「ミニマル（Minimal）トライ」と呼ぶ。
【００１６】
また、本発明のデータ構造において、当該遷移行列参照領域は、整数値により、当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれかを格納し、当該整数値中の所定のビットが立っているか否かにより、当該ノード配列中における遷移行列の位置と識別符号とのいずれを格納しているかを区別するように構成することができる。
【００１７】
これは、遷移行列参照領域を、遷移行列の位置と識別符号とのいずれかを格納するために共用するための好適実施態様の一つである。
【００１８】
また、本発明のデータ構造において、当該部分記号列参照領域は、整数値により当該記号配列中における部分記号列の長さを格納し、整数値により、当該記号配列中における部分記号列の位置、もしくは、識別符号のいずれかを格納し、当該整数値中の所定のビットが立っているか否かにより、当該ノード配列中における部分記号列の位置と識別符号とのいずれを格納しているかを区別するように構成することができる。
【００１９】
これは、部分記号列参照領域を、部分記号列の位置と識別符号とのいずれかを格納するために共用するための好適実施態様の一つである。
【００２０】
また、本発明のデータ構造において、当該データ構造は、文字列に一意に対応付けられたビット列を所定のビット数ごとに区切ったビット列の列を格納し、当該所定のビット数ごとに区切ったビット列を当該所定の種類の記号とするように構成することができる。
【００２１】
これにより、いわゆるマルチビット（Multi Bit）トライを本発明のデータ構造にて実現することができる。一般に、格納される記号列の各記号のビット幅は一定で、２ビット以上であるため、１ビットごとに木構造を作る必要はない。そこで、当該記号のビット幅ごとに木構造を構成することができる。
【００２２】
また、本発明のデータ構造において、当該データ構造は、文字列を格納し、当該所定の種類の記号は、当該文字列が含む文字であるように構成することができる。
【００２３】
一般に、トライ構造においては、文字列を格納することが多い。本発明は、このような場合に好適な実施形態の一つである。
【００２４】
本発明の他の観点に係る記号列検索装置は、記憶部と、検索記号列入力受付部と、検索部と、を備え、以下のように構成する。
【００２５】
すなわち、記憶部は、記号列を格納するデータ構造を記憶する。
【００２６】
一方、検索記号列入力受付部は、記憶部に記憶されるデータ構造に格納されているか否かを調べる記号列の入力を受け付ける。
【００２７】
さらに、検索部は、入力を受け付けられた記号列が当該データ構造に格納されているか否かを調べ、格納されている場合は、当該記号列のそれぞれに対応付けられた識別符号を検索結果とする。
【００２８】
ここで、当該データ構造は、上記の発明に係るデータ構造である。
【００２９】
一方、検索部は、
（１）現在ノードとしてまず開始ノードを採用し、現在記号列としてまず入力を受け付けられた記号列を採用し、
（２）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列と一致する場合、当該現在ノードの遷移行列参照領域に格納された識別符号を検索結果とし、
（３）現在記号列の長さが０である場合、当該現在ノードの遷移行列参照領域もしくは部分記号列参照領域に格納された識別符号を検索結果とし、
（４）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列の先頭と一致する場合、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列として採用し、
（５）当該現在ノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置が格納される場合、当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として、それぞれ採用し、
（６）そうでない場合、入力を受け付けられた記号列は格納されていない旨を検索結果とする。
【００３０】
本発明により、上記データ構造に所望の記号列が格納（登録）されているか否かを調べることができ、格納されている場合には、当該記号列に割り当てられた識別符号を取得することができる。
【００３１】
本発明の他の観点に係る記号列格納装置は、記憶部と、追加記号列入力受付部と、追加部と、を備え、以下のように構成する。
【００３２】
すなわち、記憶部は、記号列を格納するデータ構造を記憶する。
【００３３】
一方、追加記号列入力受付部は、当該データ構造に追加すべき記号列の入力を受け付ける。
【００３４】
さらに、追加部は、入力を受け付けられた記号列を、当該データ構造に追加して格納する。
【００３５】
ここで、当該データ構造は、当該記号列のそれぞれに識別符号を対応付けて格納する。
【００３６】
また、当該データ構造は、複数のノードを格納するノード配列と、部分記号列を格納する記号配列と、を有し、
【００３７】
さらに、当該複数のノードのそれぞれは、遷移行列参照領域と、部分記号列参照領域と、を有し、
（ａ）当該遷移行列参照領域は、当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれかを格納し、
（ｂ）当該部分記号列参照領域は、当該記号配列中における部分記号列の位置および長さ、もしくは、識別符号のいずれかを格納する。
【００３８】
そして、当該データ構造は、当該複数のノードのいずれか１つを開始ノードとする。
【００３９】
また、追加部は、或る記号列を、或る識別符号に対応付けて当該データ構造に追加して格納する場合、
（１）現在ノードとしてまず開始ノードを採用し、現在記号列としてまず或る記号列を採用し、
（２）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列と一致する場合、当該現在ノードの遷移行列参照領域に或る識別符号が格納され、
（３）現在記号列の長さが０である場合、当該現在ノードの遷移行列参照領域もしくは部分記号列参照領域に或る識別符号が格納され、
（４）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列の先頭と一致する場合、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列として採用し、
（５）当該現在ノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置が格納される場合、当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として、それぞれ採用する
ことにより各ノードに格納される情報が定義されるように、追加して格納する。
【００４０】
本発明の他の観点に係る記号列検索方法は、検索記号列入力受付工程と、検索工程と、を備え、以下のように構成する。
【００４１】
すなわち、検索記号列入力受付工程では、記号列を格納するデータ構造に格納されているか否かを調べる記号列の入力を受け付ける。
【００４２】
一方、検索工程では、入力を受け付けられた記号列が当該データ構造に格納されているか否かを調べ、格納されている場合は、当該記号列のそれぞれに対応付けられた識別符号を検索結果とする。
【００４３】
ここで、当該データ構造は、上記の発明に係るデータ構造である。
【００４４】
一方、検索工程では、
（１）現在ノードとしてまず開始ノードを採用し、現在記号列としてまず入力を受け付けられた記号列を採用し、
（２）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列と一致する場合、当該現在ノードの遷移行列参照領域に格納された識別符号を検索結果とし、
（３）現在記号列の長さが０である場合、当該現在ノードの遷移行列参照領域もしくは部分記号列参照領域に格納された識別符号を検索結果とし、
（４）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列の先頭と一致する場合、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列として採用し、
（５）当該現在ノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置が格納される場合、当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として、それぞれ採用し、
（６）そうでない場合、入力を受け付けられた記号列は格納されていない旨を検索結果とする。
【００４５】
本発明の他の観点に係る記号列格納方法は、追加記号列入力受付工程と、追加工程と、を備え、以下のように構成する。
【００４６】
すなわち、追加記号列入力受付工程では、記号列を格納するデータ構造に追加すべき記号列の入力を受け付ける。
【００４７】
一方、追加工程では、入力を受け付けられた記号列を、当該データ構造に追加して格納する。
【００４８】
ここで、当該データ構造は、当該記号列のそれぞれに識別符号を対応付けて格納する。
【００４９】
また、当該データ構造は、複数のノードを格納するノード配列と、部分記号列を格納する記号配列と、を有する。
【００５０】
さらに、当該複数のノードのそれぞれは、遷移行列参照領域と、部分記号列参照領域と、を有し、
（ａ）当該遷移行列参照領域は、当該ノード配列中における遷移行列の位置、もしくは、識別符号のいずれかを格納し、
（ｂ）当該部分記号列参照領域は、当該記号配列中における部分記号列の位置および長さ、もしくは、識別符号のいずれかを格納する。
【００５１】
そして、当該データ構造は、当該複数のノードのいずれか１つを開始ノードとする。
【００５２】
また、追加工程では、或る記号列を、或る識別符号に対応付けて当該データ構造に追加して格納する場合、
（１）現在ノードとしてまず開始ノードを採用し、現在記号列としてまず或る記号列を採用し、
（２）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列と一致する場合、当該現在ノードの遷移行列参照領域に或る識別符号が格納され、
（３）現在記号列の長さが０である場合、当該現在ノードの遷移行列参照領域もしくは部分記号列参照領域に或る識別符号が格納され、
（４）当該現在ノードの部分記号列参照領域に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列の先頭と一致する場合、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列として採用し、
（５）当該現在ノードの遷移行列参照領域に当該ノード配列中における遷移行列の位置が格納される場合、当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として、それぞれ採用する
ことにより各ノードに格納される情報が定義されるように、追加して格納する。
【００５３】
本発明の他の観点に係るプログラムは、コンピュータを、上記の記号列検索装置、もしくは、記号列格納装置として機能させ、あるいは、コンピュータに、上記の記号列検索方法、もしくは、記号列格納方法を実行させるように構成する。
【００５４】
当該プログラムは、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＦＤ（Flexible Disk）などの各種の記録媒体に記録することができるほか、インターネットなどのコンピュータ通信網を介して配布することができる。
【００５５】
【発明の実施の形態】
以下、添付図面を参照して、本発明の実施の形態について説明する。
【００５６】
（情報処理装置の概要構成）
図１は、本発明のデータ構造が記録された記録媒体を処理して、記号列検索装置ならびに記号列格納装置として機能しうる典型的な情報処理装置の概要構成を示す模式図である。以下、図１を参照して説明する。
【００５７】
情報処理装置１０１は、ＣＰＵ（Central Processing Unit；中央処理ユニット）１０２によって制御される。情報処理装置１０１に電源を投入すると、ＣＰＵ１０２は、ＲＯＭ（Read Only Memory；読出専用メモリ）１０３に記憶されたＩＰＬ（Initial Program Loader；初期プログラムローダ）を実行する。
【００５８】
ＩＰＬは、ハードディスク１０４、ＦＤ（Flexible Disk；フレキシブルディスク）ドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭ（Compact Disk ROM）ドライブ１１１に装着されたＣＤ−ＲＯＭなどの記録媒体に記憶されたＯＳ（Operating System；オペレーティング・システム）プログラムを読み出して実行するプログラムである。
【００５９】
ＯＳを起動した後、ＣＰＵ１０２は、キーボード１０５やマウス１０６などにより入力されたユーザの指示にしたがって、あるいは、ハードディスクなどにあらかじめ記述された設定ファイルの内容にしたがって、ハードディスクなどに記憶されたアプリケーションプログラムを実行する。
【００６０】
当該アプリケーションプログラムを実行することにより、情報処理装置１０１は、記号列検索装置ならびに記号列格納装置として機能することとなる。ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなど記憶媒体に、本発明のミニマルトライデータ構造が記録されることになる。なお、情報処理装置１０１が記号列格納装置として機能する場合には、当該記憶媒体は書き込みが可能である必要があるため、ＣＤ−ＲＯＭを利用することはできない。
【００６１】
ＣＰＵ１０２は、これらのプログラムの実行の際に、ＲＡＭ（Random Access Memory）１０７を一時的な作業用記憶領域として用いる。このほか、一時的な作業用記憶領域として、ＣＰＵ１０２内に設けられたレジスタやキャッシュ（図示せず）が使われる。
【００６２】
プログラムの実行に伴い、ユーザに結果を報告したり、途中経過を見せるため、ＣＰＵ１０２は、液晶ディスプレイやＣＲＴ（Cathode Ray Tube）などの表示装置１０８に当該情報を表示することができる。マウス１０６による指示操作では、マウス１０６を移動することにより、画面に表示されたカーソルが移動し、マウス１０６をクリックすることにより、カーソルが指すメニュー項目を選択することができる。
【００６３】
情報処理装置１０１は、ＮＩＣ（Network Interface Card）やモデムなどのインターフェース１０９を介してインターネットなどのコンピュータ通信網と通信を行うことができる。インターフェース１０９を介して受信した文書データを処理の対象としたり、処理した結果をインターフェース１０９を介して送信したり、インターフェース１０９を介して受信したプログラムを実行したり、などができる。
【００６４】
（ミニマルトライのデータ構造）
図２は、本発明の実施形態に係るミニマルトライのデータ構造の概念的な概要構成を示す模式図である。以下、本図を参照して説明する。
【００６５】
ミニマルトライ２０１は、記号列のそれぞれに識別符号を対応付けて格納する。このために、ミニマルトライ２０１には、複数のノードの番号を格納するノード配列２０２と、部分記号列を格納する記号配列２０３と、が用意されている。
【００６６】
なお、識別符号と記号列との対応関係であるが、「記号列が異なれば識別符号も異なる（互いに重複しない）」ようにしてもよいし、「同じ識別符号が異なる記号列に対応付けられる場合がある」ようにしてもよい。これは、当該ミニマルトライをどのような分野に応用するかによって、適宜変更することができる。
【００６７】
本実施形態では、ノード配列２０２は、「ノードそのものの情報の配列」を格納するわけではなく、「各ノードからの遷移先ノードの番号を記憶する配列」である。したがって、本実施形態では、ノード配列２０２全体をnと表記し、そのi番目の要素をn[i]と表記すると、各要素n[i]には、ノードの番号が格納される。このノード配列２０２中の「所定の幅の区間」を用いて、遷移行列を表現する。ただし、実施形態によっては、[課題を解決するための手段]でも述べた通り、「ノード配列２０２が複数のノード３０１を格納する」、すなわち、ノード配列２０２をノード３０１の配列とすることも可能である。
【００６８】
「遷移行列」とは、「次の記号のそれぞれに対応付けられる遷移先ノードの列」の意である。記号列に含まれうる記号の種類がw種である場合には、各遷移行列のサイズはwとなる。遷移先ノードは、当該ノードの番号によって指定することができるため、ノード配列２０２中の幅wの区間（上記の「所定の幅の区間」に相当する。）を用いれば、「遷移行列」を表現することができる。
【００６９】
したがって、ノード配列２０２中の遷移行列の先頭要素の位置（インデックス）が指定されれば、遷移行列を確定することができる。たとえば、先頭要素の位置がiである場合、遷移行列は、ノード配列２０２の要素n[i]〜n[i+w-1]の要素の列（上記の「所定の幅の区間」に相当する。）が当該遷移行列に相当する。
【００７０】
記号配列２０３には、部分記号列が格納される。部分記号列を指定するには、記号配列２０３中での部分記号列の開始位置（インデックス）と、当該部分記号列の長さとが指定されればよい。
【００７１】
したがって、各ノードに格納されるべき情報は、ひとまず以下の通りとなる。
・ノード配列２０２中における遷移行列の位置
・記号配列２０３中における部分記号列の位置
・記号配列２０３中における部分記号列の長さ
【００７２】
ここで、従来の最小接頭辞トライの場合に、ノードに格納されるべき情報と比較すると、「開始ノードからそのノードに至るまでの記号列が当該データ構造に格納（登録）された記号列である場合、当該記号列に割り当てられる識別符号」がないことがわかる。この識別符号の情報を、上記の情報と合わせて、うまく格納するのが、本実施形態の特徴の一つである。
【００７３】
図３は、各ノードの概念的な概要構成を示す模式図である。以下、本図を参照して説明する。各ノード３０１には、遷移行列参照領域３０２と、部分記号列参照領域３０３と、が用意されている。
【００７４】
遷移行列参照領域３０２には、当該ノード配列２０２中における遷移行列の位置、もしくは、識別符号のいずれかが格納される。遷移行列の位置と識別符号は、いずれも整数値で表現するのがもっとも単純である。そこで、当該整数値の所定のビットが立っているか否かにより、いずれが格納されているかを区別する。
【００７５】
たとえば、最上位ビットが立っているか否か、すなわち、通常の整数値表現で考えた場合、当該整数値が負であれば、それは「識別符号に−１を乗じた値」であり、当該整数値が正であれば、それは「遷移行列の位置」である、などのように区別することができる。なおこの場合、遷移行列の位置の数値は１から開始される（１−オリジン）こととすると便利である。整数値０を「登録されていない」「ＮＵＬＬ」に対応付けることができるからである。
【００７６】
なお、この場合、識別符号を負の数のみとしてもよい。この場合は、当該整数値が負であれば、それは識別符号そのものである。
【００７７】
このほか、最下位ビットが立っているか否かによって区別することもできる。通常の整数値表現で考えた場合、当該整数値が奇数であれば、それは「識別符号×２−１」であり、当該整数値が偶数であれば、それは「遷移行列の位置×２」である、などのように区別することができる。この場合も同様に、遷移行列の位置は１−オリジンとすると便利である。
【００７８】
なお、この場合、識別符号を奇数のみとしてもよい。この場合は、当該整数値が奇数であれば、それは識別符号そのものである。
【００７９】
部分記号列参照領域３０３には、当該記号配列２０３中における部分記号列の位置および長さ、もしくは、識別符号のいずれかが格納される。
【００８０】
部分記号列参照領域３０３には、整数値により当該記号配列中における部分記号列の長さを格納するのが最も自然であり、部分記号列の位置と識別符号は、いずれも整数値で表現するのが最も単純である。
【００８１】
そこで、上記の遷移行列参照領域３０２における部分記号列の位置と識別符号の区別にも、上記の場合と同様に、当該整数値の所定のビットが立っているか否かを用いることができる。
【００８２】
従来の最小接頭辞トライでは、識別符号を格納するための領域を別途各ノードに用意していたが、本実施形態では、その必要がない。このため、従来の最小接頭辞トライに比べ、本実施形態のミニマルトライ２０１では、データ構造のサイズを小さくできる。
【００８３】
なお、以下の説明では、理解を容易にするため、これらの整数値表現において、上記の正負の差異を用いて、識別符号か否かを区別する態様を採用して説明する。
【００８４】
以下、「『部分記号列の位置および長さ』と『識別符号』のいずれか一方」が、部分記号列参照領域３０３に格納される状況を、適宜以下のように表現することとする。
・「部分記号列の位置もしくは識別符号のいずれか一方」を表す整数値が０である場合、「部分記号列参照領域３０３に０が格納されている」。これは、部分記号列参照領域３０３に「値が格納されていない」「ＮＵＬＬ値が格納されている」に相当する。
・「部分記号列の位置もしくは識別符号のいずれか一方」を表す整数値が正である場合、「部分記号列参照領域３０３に正の値が格納されている」。この場合、当該部分記号列参照領域３０３は、部分記号列の位置および長さを格納していることになる。
・「部分記号列の位置もしくは識別符号のいずれか一方」を表す整数値が負である場合、「部分記号列参照領域３０３に負の値が格納されている」。この場合、当該部分記号列参照領域３０３は、識別符号を（正負の符号を反転して）格納していることになる。
【００８５】
また、「『遷移行列の位置』と『識別符号』のいずれか一方」が、遷移行列参照領域３０２に格納される状況を、適宜以下のように表現することとする。
・「『遷移行列の位置』と『識別符号』のいずれか一方」を表す整数値が０である場合、「遷移行列参照領域３０２に０が格納されている」。これは、遷移行列参照領域３０２に「値が格納されていない」「ＮＵＬＬ値が格納されている」に相当する。
・「『遷移行列の位置』と『識別符号』のいずれか一方」を表す整数値が正である場合、「遷移行列参照領域３０２に正の値が格納されている」。この場合、当該遷移行列参照領域３０２は、遷移行列の位置を格納していることになる。
・「『遷移行列の位置』と『識別符号』のいずれか一方」を表す整数値が負である場合、「遷移行列参照領域３０２に負の値が格納されている」。この場合、当該遷移行列参照領域３０２は、識別符号を（正負の符号を反転して）格納していることになる。
【００８６】
また、図３では、各ノード３０１に、遷移行列参照領域３０２と、部分記号列参照領域３０３と、が用意されている形態を示してあるが、遷移行列参照領域３０２の配列と、部分記号列参照領域３０３の配列と、を用意しておき、配列中のインデックスによりノードを表現する手法を採用してもよい。
【００８７】
なお、注記しておくが、本実施形態では、ノード配列２０２は、「各ノード３０１の配列」ではない。ノード配列２０２とは別途確保された領域に、各ノード３０１の内容が記憶される。ただし、実施形態によっては、[課題を解決するための手段]でも述べた通り、「ノード配列２０２が複数のノード３０１を格納する」、すなわち、ノード配列２０２をノード３０１の配列とすることも可能である。
【００８８】
さて、本実施形態において、ミニマルトライ２０１は、以下のような条件を満たす必要がある。なお、記号列をデータ構造に格納して、以下のような条件を満たすようなミニマルトライ２０１を構成するための手法については、後述する。
【００８９】
まず、ミニマルトライ２０１は、当該複数のノードのいずれか１つを開始ノードとする。これはトライ構造の「根」に相当するものであり、ミニマルトライに或る記号列が登録されているか否かを検索するときには、この開始ノードから検索を開始する。
【００９０】
或る記号列が、或る識別符号に対応付けてミニマルトライ２０１に格納される／されない場合を考える。当該ミニマルトライ２０１の構造を理解するには、「現在ノード」と「現在記号列」というものを考えて、そのデータ構造がミニマルトライ２０１の条件を満たしているか否かを判定するのがよい。
【００９１】
ひとまず、現在ノードとしてまず当該開始ノードを採用し、現在記号列としてまず或る記号列を採用して、以下の条件を順次調べる。
【００９２】
（イ）  現在ノードの当該部分記号列参照領域３０３に当該記号配列２０３中における部分記号列の位置および長さが格納され（部分記号列参照領域３０３に格納される整数値が正であり）、かつ、当該部分記号列が現在記号列と一致する場合、当該現在ノードの遷移行列参照領域３０２に当該或る識別符号が（正負を反転した整数値として）格納されることになる。
【００９３】
（ロ）  現在記号列の長さが０である場合、当該現在ノードの遷移行列参照領域３０２もしくは部分記号列参照領域３０３（のいずれかに負の値が格納されているのであれば、そのいずれか）に当該或る識別符号が格納されていることになる。本実施形態では、部分記号列参照領域３０３には０が格納され、遷移行列参照領域３０２に負の値が格納され、当該負の値が当該或る識別符号を表現することとなる。
【００９４】
（ハ）  当該部分記号列参照領域３０３に当該記号配列２０３中における部分記号列の位置および長さが格納され（部分記号列参照領域３０３に格納される整数値が正であり）、かつ、当該部分記号列が現在記号列の先頭と一致する場合、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列として採用して、これらの条件を再度調べ直す。
【００９５】
（ニ）  当該遷移行列参照領域３０２に当該ノード配列２０２中における遷移行列の位置が格納される（遷移行列参照領域３０２に格納される整数値が正である）場合、当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として、それぞれ採用して、これらの条件を再度調べ直す。
【００９６】
（ホ）  上記の（イ）〜（ニ）のいずれにも該当しない場合（遷移行列参照領域３０２に０が格納され、かつ、部分記号列参照領域３０３に０が格納されている場合）、当該或る記号列は、ミニマルトライ２０１には格納されていないことになる。
【００９７】
このような条件を満たすようにミニマルトライ２０１を構成してあるため、当該ミニマルトライ２０１に、或る記号列が格納されているか否かを調べ、格納されている場合に、当該記号列に割り当てられた識別符号を取得するための記号列検索は、以下のように構成することができる。
【００９８】
（記号列の検索）
図４は、本発明の実施形態に係る記号列検索装置の概要構成を示す模式図である。図５は、当該記号列検索装置により実行される記号列検索方法の処理の手順の流れを示すフローチャートである。以下、これらの図を参照して説明する。
【００９９】
記号列検索装置４０１は、記憶部４０２と、検索記号列入力受付部４０３と、検索部４０４と、を備える。
【０１００】
ここで、記憶部４０２は、記号列を格納するミニマルトライ２０１をあらかじめ記憶する。
【０１０１】
さて、記号列検索装置４０１が、記号列検索方法を開始すると、まず、検索記号列入力受付部４０３は、記憶部４０２に記憶されるミニマルトライ２０１に格納されているか否かを調べる記号列の入力を受け付ける（ステップＳ５０１）。
【０１０２】
ついで、検索部４０４は、入力を受け付けられた記号列が当該ミニマルトライ２０１に格納されているか否かを調べ、格納されている場合は、当該記号列のそれぞれに対応付けられた識別符号を検索結果とする（ステップＳ５０２以降）。
【０１０３】
以下、検索部４０４による検索処理の詳細について述べる。
【０１０４】
あらかじめ、情報処理装置１０１のＲＡＭ１０７内に用意された「現在ノード」を格納するための領域と、「現在記号列」を格納するための領域と、のそれぞれに、ミニマルトライ２０１の開始ノードと、入力を受け付けられた検索したい記号列と、を代入する（ステップＳ５０２）。
【０１０５】
ついで、現在記号列の長さが０か否かを調べる（ステップＳ５２１）。これが０である場合、現在ノードの部分記号列参照領域３０３から識別符号を取得して、これを検索結果として返し（ステップＳ５２２）、本処理を終了する。
【０１０６】
なお、上記のように、部分記号列参照領域３０３には、部分記号列を参照する情報が、遷移行列参照領域３０２には、遷移行列を参照する情報が、それぞれ格納されるほか、いずれにも、識別符号ならびにＮＵＬＬ値が格納されうる。ステップＳ５２２における「識別符号を取得して検索結果として返す」とは、理解を容易にするために、「『識別符号』もしくは『ＮＵＬＬ値』のいずれかを取得し、『識別符号』が取得された場合はこれを返し、『ＮＵＬＬ値』された場合は当該記号列が格納されていない旨を報告する」旨を略記したものである。以下、同様の省略記法を適宜使用する。
【０１０７】
ついで、当該現在ノードの部分記号列参照領域３０３に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列と一致するか否かを調べ（ステップＳ５０３）、一致する場合（ステップＳ５０３；Ｙｅｓ）、当該現在ノードの遷移行列参照領域３０２に格納された識別符号を検索結果として（ステップＳ５０４）、本処理を終了する。
【０１０８】
一方、一致しない場合（ステップＳ５０３；Ｎｏ）、当該現在ノードの部分記号列参照領域３０３に当該記号配列中における部分記号列の位置および長さが格納され、かつ、当該部分記号列が現在記号列の先頭と一致するか否かを調べ（ステップＳ５０７）、そうでない場合（ステップＳ５０７；Ｎｏ）、入力を受け付けられた記号列は格納されていない旨を検索結果として（ステップＳ５１２）、本処理を終了する。
【０１０９】
一方、そうである場合（ステップＳ５０７；Ｙｅｓ）、当該現在記号列の先頭から当該部分記号列を除去した記号列を新たに現在記号列とする（ステップＳ５０８）。
【０１１０】
そして、当該ノード配列２０２中における遷移行列の位置が格納されているか否かを調べ（ステップＳ５０９）、格納されていない場合（ステップＳ５０９；Ｎｏ）、現在記号列の長さが０であるか否かを調べ（ステップＳ５０５）、０でない場合（ステップＳ５０５；Ｎｏ）、入力を受け付けられた記号列は格納されていない旨を検索結果として（ステップＳ５２３）、本処理を終了する。
【０１１１】
一方、０である場合（ステップＳ５０５；Ｙｅｓ）、当該現在ノードの遷移行列参照領域３０２もしくは部分記号列参照領域３０３に格納された識別符号を検索結果として（ステップＳ５０６）、本処理を終了する。
【０１１２】
一方、遷移行列が格納されている場合（ステップＳ５０９；Ｙｅｓ）当該遷移行列において当該部分記号列の先頭の記号に対応付けられたノードを新たに現在ノードとして（ステップＳ５１０）、当該現在記号列から先頭の記号を除去した記号列を新たに現在記号列として（ステップＳ５１１）、ステップＳ５２１に戻る。
【０１１３】
このように、ミニマルトライ２０１のデータ構造に即して、記号列の検索の処理が実行されることになる。
【０１１４】
（記号列の格納）
以下では、ミニマルトライ２０１のデータ構造に、順次記号列を格納していく手法の詳細について説明する。図６は、本発明の実施形態に係る記号列格納装置の概要構成を示す模式図である。図７は、当該記号列格納装置により実行される記号列格納方法の処理の手順の流れを示すフローチャートである。以下、これらの図を参照して説明する。
【０１１５】
記号列格納装置６０１は、記憶部６０２と、追加記号列入力受付部６０３と、追加部６０４と、を備える。
【０１１６】
ここで、記憶部６０２は、記号列を格納するミニマルトライ２０１を記憶するためのもので、記憶部６０２にミニマルトライ２０１が構成される。
【０１１７】
記号列格納方法においては、まず、追加記号列入力受付部６０３は、ミニマルトライ２０１に追加すべき記号列の入力を受け付ける（ステップＳ７０１）。
【０１１８】
ついで、追加部６０４は、入力を受け付けられた記号列を、当該データ構造に、上記ミニマルトライ２０１の条件を満たすように追加して格納する（ステップＳ７０２）。
【０１１９】
そして、追加すべき記号列がなくなるまで（ステップＳ７０３）、ステップＳ７０１〜ステップＳ７０３の処理を繰り返す。
【０１２０】
図８は、ステップＳ７０２における追加処理の手順の流れを示すフローチャートである。以下、当該追加処理の詳細について説明する。
【０１２１】
本追加処理においても、「現在ノード」と「現在記号列」を格納するための領域をＲＡＭ１０７にあらかじめ用意しておく。
【０１２２】
まず、ミニマルトライ２０１の開始ノードを現在ノードに、格納させたい記号列を現在記号列に、それぞれ代入する（ステップＳ８０１）。
【０１２３】
ついで、現在記号列の長さが０であるか否かを調べ（ステップＳ８０２）、０でない間（ステップＳ８０１；Ｎｏ）、以下のステップＳ８０３〜Ｓ８１５の処理を繰り返す。
【０１２４】
まず、現在ノードの部分記号列参照領域３０３に格納されている整数値を調べる（ステップＳ８０３）。当該整数値が０である場合（ステップＳ８０３；＝０）、図９に示す処理Ａを実行して（ステップＳ８０４）、ステップＳ８０２に戻る。
【０１２５】
一方、当該整数値が負の場合（ステップＳ８０３；負）、図１０に示す処理Ｂを実行して（ステップＳ８０５）、ステップＳ８０２に戻る。
【０１２６】
一方、当該整数値が正の場合（ステップＳ８０３；正）、当該整数値によって参照される部分記号列を取得し（ステップＳ８０６）、当該部分記号列の長さと現在文字列の長さを比較する（ステップＳ８０７）。
【０１２７】
長さが等しい場合（ステップＳ８０７；等しい）、当該部分記号列と、現在文字列とを比較する（ステップＳ８０８）。両者が一致する場合（ステップＳ８０８；一致）図１１に示す処理Ｃを実行する（ステップＳ８０９）。
【０１２８】
一方、両者が一致しない場合（ステップＳ８０８；不一致）、図１２に示す処理Ｄを実行する（ステップＳ８１０）。
【０１２９】
そして、ステップＳ８０９、Ｓ８１０の後に、現在文字列から先頭文字を除去し（ステップＳ８１１）、現在ノードの遷移行列と当該先頭文字とから次のノードを取得して（ステップＳ８１２）、現在ノードを次のノードに設定し（ステップＳ８１３）、ステップＳ８０２に戻る。
【０１３０】
一方、長さが等しくない場合（ステップＳ８０７；等しくない）、現在文字列の先頭部分が、当該部分記号列と一致するか否かを調べ（ステップＳ８１４）、一致する場合（ステップＳ８１４；一致）、図１３に示す処理Ｅを実行する（ステップＳ８１５）。
【０１３１】
一方、一致しない場合（ステップＳ８１４；不一致）、図１２に示す処理Ｄを実行する（ステップＳ８１６）。
【０１３２】
ステップＳ８１５、Ｓ８１６の後は、ステップＳ８０２に戻る。
【０１３３】
一方、現在記号列の長さが０になったら（ステップＳ８０２；Ｙｅｓ）、現在ノードの部分記号列参照領域３０３の値を調べる（ステップＳ８２１）。当該整数値が負の場合（ステップＳ８２１；負）、これが格納すべき記号列に対応する識別符号に相当するので、本処理を終了する。
【０１３４】
一方、当該整数値が正の場合（ステップＳ８２１；正）、格納すべき記号列に対応する識別符号の値の負の値にして、部分記号列参照領域３０３に格納し（ステップＳ８２２）、それまで部分記号列参照領域３０３により参照されていた部分記号列の先頭記号を遷移行列により表現し（ステップＳ８２３）、遷移先ノードの部分記号列参照領域に識別符号を格納し（ステップＳ８３１）、退避しておいた遷移先を新しいノードに設定して（ステップＳ８３２）、本処理を終了する。
【０１３５】
一方、当該整数値が０の場合（ステップＳ８２１；＝０）、格納すべき記号列に対応する識別符号の値を負の値にして、部分記号列参照領域３０３に格納し（ステップＳ８２４）、本処理を終了する。
【０１３６】
以下、処理Ａの詳細について述べる。処理Ａが開始されると、まず、遷移行列参照領域３０２の値を調べる（ステップＳ９０１）。値が正である場合（ステップＳ９０１；正）、現在記号列から先頭記号を除去し（ステップＳ９０２）、当該先頭記号と当該遷移行列とから次のノードを取得し（ステップＳ９０３）、現在ノードを次のノードに設定して（ステップＳ９０４）、処理Ａからリターンする。
【０１３７】
一方、値が負である場合（ステップＳ９０１；負）、遷移行列参照領域３０２の値を、部分記号列参照領域３０３にコピーし（ステップＳ９０５）、新しい遷移行列を確保して（ステップＳ９０６）、遷移行列参照領域３０２に当該新しい遷移行列の位置を格納し（ステップＳ９０７）、ステップＳ９０２に進む。
【０１３８】
一方、値が０である場合（ステップＳ９０１；＝０）、現在記号列を文字配列に格納し（ステップＳ９０９）、当該文字配列内の位置と、現在記号列の長さを部分記号列参照領域３０３に格納し（ステップＳ９１０）、遷移行列参照領域３０２に識別符号を負の値にして格納し（ステップＳ９１１）、記号列格納処理を終了する。
【０１３９】
以下、処理Ｂの詳細について述べる。処理Ｂが開始されると、まず、遷移行列参照領域３０２の値を調べる（ステップＳ１００１）。値が正である場合（ステップＳ１００１；正）、現在記号列から先頭記号を除去し（ステップＳ１００２）、当該先頭記号と当該遷移行列から次のノードを取得し（ステップＳ１００３）、現在ノードを次のノードに設定して（ステップＳ１００４）、処理Ｂからリターンする。
【０１４０】
一方、それ以外である場合（ステップＳ１００１；その他）、新しい遷移行列を確保して（ステップＳ１００５）、遷移行列参照領域３０２に当該新しい遷移行列の位置を格納し（ステップＳ１００６）、ステップＳ１００２に進む。
【０１４１】
以下、処理Ｃの詳細について述べる。処理Ｃが開始されると、まず、遷移行列参照領域３０２の値を調べる（ステップＳ１１０１）。値が負である場合（ステップＳ１１０１；負）、ここに当該登録対象の識別符号が格納されていることになるので、記号列格納処理を終了する。
【０１４２】
一方、０である場合（ステップＳ１１０１；＝０）、遷移行列参照領域３０２に当該識別符号を負の値にして格納し（ステップＳ１１０２）、記号列格納処理を終了する。
【０１４３】
一方、正である場合（ステップＳ１１０１；正）、部分記号列から末尾記号を除去し（ステップＳ１１０３）、新しい遷移行列を確保し（ステップＳ１１０４）、除去した記号で遷移して（ステップＳ１１０５）、遷移先のノードの部分記号列格納領域に識別符号を負の値にして格納し（ステップＳ１１０６）、記号列格納処理を終了する。
【０１４４】
以下、処理Ｄの詳細について述べる。まず、不一致となった部分の前後で部分記号列を分割する（ステップＳ１２０１）。次に、現在ノードの部分記号列参照領域３０３が当該分割された前半を参照するように、部分記号列参照領域３０３を更新する（ステップＳ１２０２）。
【０１４５】
そして、当該分割された後半の先頭記号と遷移行列参照領域３０２を見て、遷移先ノードがあるか否かを調べる（ステップＳ１２０３）。
【０１４６】
遷移先ノードがある場合（ステップＳ１２０３；ある）、現在ノードの遷移行列参照領域３０２の値を退避し（ステップＳ１２０４）、新しい遷移行列を確保し（ステップＳ１２０５）、当該新しい遷移行列の位置を遷移先ノードの遷移行列参照領域３０２に格納し（ステップＳ１２０６）、部分記号列の不一致部分の先頭記号を用いて現在ノードから遷移して現在ノードを更新する（ステップＳ１２０７）。
【０１４７】
さらに、現在ノードの部分記号列参照領域３０３が、部分記号列の不一致部分より後ろを参照するように、部分記号列参照領域３０３を更新する（ステップＳ１２０８）。また、退避した遷移行列参照領域３０２の位置を、現在ノードの遷移行列参照領域３０２に格納し（ステップＳ１２０９）、ステップＳ１２０７の遷移の遷移元のノードへ戻り（ステップＳ１２１０）、ステップＳ１２１６へ進む。
【０１４８】
一方、遷移先ノードがない場合（ステップＳ１２０３；ない）、新しい遷移行列を確保して（ステップＳ１２１１）、その位置を遷移行列参照領域３０２に格納し（ステップＳ１２１２）、当該分割した後半の先頭記号を用いて、現在ノードから遷移して現在ノードを更新する（ステップＳ１２１３）。
【０１４９】
さらに、現在ノードの部分記号列参照領域３０３が当該分割された後半を参照するように、部分記号列参照領域３０３を更新し（ステップＳ１２１４）、ステップＳ１２１３の遷移の遷移元のノードへ戻り（ステップＳ１２１５）、ステップＳ１２１６へ進む。
【０１５０】
そして、現在ノードから、現在記号列の不一致部分の先頭記号を用いて遷移して現在ノードを更新する（ステップＳ１２１６）、さらに、現在ノードの部分記号列参照領域３０３が現在記号列の不一致部分より後ろを参照するように、部分記号列参照領域３０３を更新し（ステップＳ１２１７）、遷移行列参照領域３０２に、識別符号を格納して（ステップＳ１２１８）、記号列格納処理を終了する。
【０１５１】
以下、処理Ｅの詳細について述べる。まず、遷移行列参照領域３０２の値を調べ（ステップＳ１３０１）、これが負でない場合（ステップＳ１３０１；正）、ステップＳ１３０８に進む。
【０１５２】
これが負である場合（ステップＳ１３０１；負）、部分記号列参照領域３０３により参照される部分記号列の末尾記号を除去し（ステップＳ１３０２）、当該負の値を退避し（ステップＳ１３０３）、新しい遷移行列を確保して（ステップＳ１３０４）、その位置を遷移行列参照領域３０２に格納し（ステップＳ１３０５）、当該除去した末尾記号を用いて遷移を行い（ステップＳ１３０６）、遷移後のノードの部分記号列参照領域３０３に、退避した負の値を格納する（ステップＳ１３０７）。
【０１５３】
そして、部分記号列を当該現在記号列の先頭から除去し（ステップＳ１３０８）、さらに当該現在記号列の先頭記号を除去し（ステップＳ１３０９）、当該先頭記号により、遷移を行って（ステップＳ１３１０）、リターンする。
【０１５４】
また、遷移行列参照領域３０２の値が０である場合（ステップＳ１３０１；＝０）、新規遷移先を確保してから（ステップＳ１３２０）、ステップＳ１３０８に進む。
【０１５５】
なお、ステップＳ１３０２は、１ビットだけ残っている場合の処理であり、２ビット以上残っている場合は実行する必要はない。
【０１５６】
このようにして、記号列を順次ミニマルトライ２０１に格納していくことにより、上記のミニマルトライ２０１が満たすべき条件を満たしたまま、ミニマルトライ２０１に新しい記号列を格納することができる。
【０１５７】
（記号の種類）
本発明においては、記号列に含まれる所定の種類の記号は、文字そのものを利用してもよいし、文字列を所定ビット数ごとに区切ったビット列を利用してもよい。所定のビット数ごとに区切ったビット列を利用する手法は、従来からも、マルチビットトライにおいても利用されている。一般に、文字列は所定のビット数単位で構成されるため、１ビットごとにノードを用意するのではなく、所定のビット数ごとにノードを用意してトライ構造を構成することができる。
【０１５８】
【発明の効果】
以上説明したように、本発明によれば、記号列をミニマルトライに効率良く格納し、ミニマルトライから記号列を検索し、ミニマルトライへ記号列を追加して格納するのに好適な、ミニマルトライ、記号列検索装置、記号列格納装置、記号列検索方法、記号列格納方法、ならびに、これらを実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【図１】  本発明のデータ構造を処理する典型的な情報処理装置の概要構成を示す模式図である。
【図２】  ミニマルトライのデータ構造の概念的な概要構成を示す模式図である。
【図３】  各ノードの概念的な概要構成を示す模式図である。
【図４】  記号列検索装置の概要構成を示す模式図である。
【図５】  記号列検索方法の処理の手順の流れを示すフローチャートである。
【図６】  記号列格納装置の概要構成を示す模式図である。
【図７】  記号列格納方法の処理の手順の流れを示すフローチャートである。
【図８】  記号列格納方法の手順の流れを示すフローチャートである。
【図９】  記号列格納方法の手順の流れを示すフローチャートである。
【図１０】  記号列格納方法の手順の流れを示すフローチャートである。
【図１１】  記号列格納方法の手順の流れを示すフローチャートである。
【図１２】  記号列格納方法の手順の流れを示すフローチャートである。
【図１３】  記号列格納方法の手順の流れを示すフローチャートである。
【符号の説明】
１０１  情報処理装置
１０２  ＣＰＵ
１０３  ＲＯＭ
１０４  ＨＤ
１０５  キーボード
１０６  マウス
１０７  ＲＡＭ
１０８  表示装置
１０９  インターフェース
１１０  ＦＤドライブ
１１１  ＣＤ−ＲＯＭドライブ
２０１  ミニマルトライ
２０２  ノード配列
２０３  記号配列
３０１  ノード
３０２  遷移行列参照領域
３０３  部分記号列参照領域
４０１  記号列検索装置
４０２  記憶部
４０３  検索記号列入力受付部
４０４  検索部
６０１  記号列格納装置
６０２  記憶部
６０３  追加記号列入力受付部
６０４  追加部
【図１】
0003761451.tif 000002
【図２】
0003761451.tif 000003
【図３】
0003761451.tif 000004
【図４】
0003761451.tif 000005
【図５】
0003761451.tif 000006
【図６】
0003761451.tif 000007
【図７】
0003761451.tif 000008
【図８】
0003761451.tif 000009
【図９】
0003761451.tif 000010
【図１０】
0003761451.tif 000011
【図１１】
0003761451.tif 000012
【図１２】
0003761451.tif 000013
【図１３】
0003761451.tif 000014