複数の文字列それぞれを1または複数のトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データであり、前記木構造データのノードには末端ノードまでの長さの最大値および最小値が関連づけられている木構造データを記憶するインデックスメモリと、検索する文字列を1または複数のトークンの列に変換するトークナイザと、前記トークナイザにより変換されたトークンの列を走査しながら前記インデックスメモリに記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索することにより、前記検索する文字列が前記複数の文字列の中に存在するかどうかを検出する検索部と、を有し、前記検索部は、ノードの子ノードの中から、末端ノードまでの長さの最大値および最小値の範囲内に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを検出する検索装置。前記インデックスメモリが記憶する木構造データを構成するノードには、ノードの表すトークンの文字列の長さが関連づけられており、前記検索部は、ノードの子ノードの中から、次に走査するトークンの文字列の長さが関連付けられている子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを検出する請求項1に記載の検索装置。前記インデックスメモリが記憶する木構造データを構成するノードには、末端ノードまでの長さのリストが関連づけられており、前記検索部は、ノードの子ノードの中から、子ノードに関連づけられているリスト中に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを検出する請求項1または2に記載の検索装置。前記トークナイザは、前記検索する文字列中の区切り文字により前記検索する文字列を区切りトークンの列に変換する請求項1から3のいずれかに記載の検索装置。前記トークナイザは、前記検索する文字列を、定められた単語の有無にしたがって単語の列に区切ってトークンの列に変換する請求項1から4のいずれかに記載の検索装置。前記トークナイザは、前記検索する文字列中の1文字を1トークンとする請求項1または2に記載の検索装置。複数の文字列それぞれを1または複数のトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データであり、前記木構造データのノードには末端ノードまでの長さの最大値および最小値が関連づけられている木構造データを記憶部に記憶している計算機に、検索する文字列を1または複数のトークンの列に変換させ、変換されたトークンの列を走査しながら前記インデックスメモリに記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索することにより、前記検索する文字列が前記複数の文字列の中に存在するかどうかを検出させるためのプログラムであり、ノードの子ノードの中から、末端ノードまでの長さの最大値および最小値の範囲内に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを前記計算機に検出させるプログラム。複数の文字列それぞれを1または複数のトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データであり、前記木構造データのノードには末端ノードまでの長さの最大値および最小値が関連づけられている木構造データを記憶部に記憶している計算機の動作方法であり、前記計算機が、検索する文字列を1または複数のトークンの列に変換し、変換されたトークンの列を走査しながら前記インデックスメモリに記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索することにより、前記検索する文字列が前記複数の文字列の中に存在するかどうかを検出し、ノードの子ノードの中から、末端ノードまでの長さの最大値および最小値の範囲内に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを含む、計算機の動作方法。B木などを用いる従来の技術においては、登録された文字列を絞り込むことが行なわれることにより、検索の効率化が図られている。しかしながら、絞り込まれた範囲内において、文字列を順次比較する必要がある。このため、文字列が登録されていないことを確認するためには、絞り込まれた範囲内の全ての文字列を比較することになる。したがって、文字列が登録されていることを検出することは少ない手間で行なえるものの、登録されていないことを検出するには、手間が掛かることになる。本発明の目的の一つとして、与えられた文字列が、登録されていることの検出および登録されていないことの検出を、少ない手間により行なう検索装置などを提供する。そこで、本発明の一実施形態として、複数の文字列それぞれを1または複数のトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データであり、前記木構造データのノードには末端ノードまでの長さの最大値および最小値が関連づけられている木構造データを記憶するインデックスメモリと、検索する文字列を1または複数のトークンの列に変換するトークナイザと、前記トークナイザにより変換されたトークンの列を走査しながら前記インデックスメモリに記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索することにより、前記検索する文字列が前記複数の文字列の中に存在するかどうかを検出する検索部と、を有し、前記検索部は、ノードの子ノードの中から、末端ノードまでの長さの最大値および最小値の範囲内に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを検出する検索装置を提供する。より具体的には、検索部は、トークン列保持部と、トークン個数保持部と、トークン番号保持部と、ノード情報保持部とを備え、トークン列保持部は、前記トークナイザが変換したトークンの列の情報を保持し、トークン個数保持部は、未走査のトークンの個数を保持し、トークン番号保持部は、走査中のトークンの前記トークンの列における番号を保持し、ノード情報保持部は、現在到達しているノードの情報を保持し、現在到達しているノードの子ノードの中に、末端ノードまでの長さの最大値および最小値の範囲内にトークン個数保持部が保持している数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを検出する。また、本発明の一実施形態として、複数の文字列それぞれを1または複数のトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データであり、前記木構造データのノードには末端ノードまでの長さの最大値および最小値が関連づけられている木構造データを記憶部に記憶している計算機に、検索する文字列を1または複数のトークンの列に変換させ、変換されたトークンの列を走査しながら前記インデックスメモリに記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索することにより、前記検索する文字列が前記複数の文字列の中に存在するかどうかを検出させるためのプログラムであり、ノードの子ノードの中から、末端ノードまでの長さの最大値および最小値の範囲内に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを検出させるプログラムを提供する。また、本発明の一実施形態として、複数の文字列それぞれを1または複数のトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データであり、前記木構造データのノードには末端ノードまでの長さの最大値および最小値が関連づけられている木構造データを記憶部に記憶している計算機の動作方法であり、前記計算機が、検索する文字列を1または複数のトークンの列に変換し、変換されたトークンの列を走査しながら前記インデックスメモリに記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索することにより、前記検索する文字列が前記複数の文字列の中に存在するかどうかを検出し、ノードの子ノードの中から、末端ノードまでの長さの最大値および最小値の範囲内に未走査のトークンの数を含む子ノードが存在しなければ、前記検索する文字列が前記複数の文字列の中に存在しないことを含む、計算機の動作方法を提供する。本発明により、与えられた文字列が登録された文字列かどうかの検索の早期の段階において、与えられた文字列が登録されていないことが検出され、与えられた文字列が、登録されていることの検出および登録されていないことの検出を、従来よりも少ない手間により行なうことが可能となる。以下、本発明を実施するための形態を実施形態として説明する。なお、本発明は、以下の実施形態に限定されることはなく、種々の変形を加えて実施することが可能である。実施形態1図1は、本発明の一実施形態に係る検索装置の機能ブロック図を示す。検索装置100は、インデックスメモリ101と、トークナイザ102と、検索部103とを有する。インデックスメモリインデックスメモリ101は、1または複数の木構造データを記憶する。インデックスメモリ101が記憶する1または複数の木構造データが表す木構造は次の2つの条件を満たす。条件1複数の文字列それぞれを1または複数のトークンの列に変換して、共通するトークンの列を開始端より併合することにより、構成されている。条件2木構造のノードには、末端ノードまでの長さの最大値および最小値が関連付けられている。木構造に関する定義本実施形態において、木構造とは、数学的に定義されるグラフ構造であり、そのグラフ構造はイ1または複数のノードを有し、ロ始点と終点とをノードして持つエッジによって始点のノードと終点のノードとを接続し、ハ単連結であり、かつ、ニループを構成するエッジが存在しないことを特徴とする。木構造を表すデータを木構造データと定義する。木構造データは、ノードとエッジとを表すデータ構造により表すことができる。このようなデータ構造としては、例えば後に図3を用いて説明されるデータ構造がある。帰納的に、1木構造を定義しつつ同時に2根ノードと、3末端ノードと、4根ノードから末端ノードまでの長さの最大値および最小値とを定義すると次のようになる。定義111つのノードは木構造である。2、3そのノードは、その木構造の根ノードでありかつ末端ノードである。4この木構造において、根ノードから末端ノードまでの長さの最大値および最小値はともに1である。定義211または複数の木構造T1、...、Tnがある場合、木構造T1、...、Tnのいずれのノードでもない新たなノードpと木構造T1、...、Tnのそれぞれの根ノードとを、ノードpを始点としそれぞれの根ノードを終点とするn本のエッジそれぞれにより接続した構造は、新たな木構造である。2この新たな木構造の根ノードはノードpであり、3この新たな木構造の末端ノードは、木構造T1、...、Tnのそれぞれの末端ノードであり、4この新たな木構造の根ノードから末端ノードまでの長さの最大値は、{T1の根ノードから末端ノードまでの長さの最大値、...、Tnの根ノードから末端ノードまでの長さの最大値}の最大値に1を加えた値であり、この新たな木構造の根ノードから末端ノードまでの長さの最小値は、{T1の根ノードから末端ノードまでの長さの最小値、...、Tnの根ノードから末端ノードまでの長さの最小値}の最小値に1を加えた値である。木構造の任意のノードqから、ノードqを始点としノードr1を終点とするエッジe1があり、ノードr1を始点としノードr2を終点とするエッジe2があり、...、ノードrn-1を始点としノードrnを終点とするエッジenがあるとき、ノードの列q、r1、r2、...、rn-1、rnをノードqを始点とする経路と定義し、ノードqからノードrnまでの長さをnと定義する。トークンの列に関する定義図2は、文字列を1または複数のトークンの列に変換することを説明するための図である。トークンとは文字または文字の並びである単語を表すデータ構造をいう。文字列を1または複数のトークンの列に変換するとは、文字列を、その構成要素である文字または単語を表すデータ構造の並びに変換することをいう。文字列をトークンの列に変換することは、字句解析LexicalAnalysisと称されることもある。図2は、一例として、文字列TYHKBMBNKYMをトークンの列に変換する際に、空白を表す文字を単語間の区切りとして扱うことにより、単語TY、HK、BMB、NKYMそれぞれに対応する4つのトークンの並びに区切られることを示している。図2のa、bそれぞれは、変換される文字列をトークンの列に変換した場合のトークンの並びを表すデータ構造の例を示している。図2のaは、5つの要素スロットからなる配列が用意され、スロット201には、文字列TYへのポインタTYが格納されたメモリのアドレス、スロット202には、文字列HKへのポインタ、スロット203には、文字列BMBへのポインタ、スロット204には、文字列NKYMへのポインタが格納され、スロット205には、トークンの列の終わりであることを示す値例えば、NULLが格納されている状態を示す。なお、5つのスロットからなる配列の代わりに、5つのリストが直列に連結されたデータ構造などを用いてもよい。図2のbは、図2のaと同様に、5つのスロットからなる配列が用意されていることを示しているが、各スロットは、文字列TYHKBMBNKYMが格納されているメモリの領域210の中のアドレスと、トークンが表す文字列の長さとを格納している。すなわち、スロット211には、領域210のTYの開始文字であるTが格納されているアドレスと、TYの文字数である2とが格納され、スロット212には、領域210のHKの開始文字であるHが格納されているアドレスと、HKの文字数である2とが格納され、スロット213には、領域210の、BMBの開始文字である開始文字であるBが格納されているアドレスと、BMBの文字数である3とが格納され、スロット214には、領域210のNKYMの開始文字であるNが格納されているアドレスと、NKYMの文字数である4とが格納されている。また、スロット215には、トークンの列の終わりである値と、例えば0とが格納されている。文字列をトークンの列に変換する場合には、図2に示したように、空白やその他の記号を表す文字により文字列を区切り、単語としてのトークンの列に変化することができる。また、空白やその他の記号を表す文字が含まれない場合や空白やその他の記号を表す文字を区切りとしない場合には、あらかじめ定められた単語を、文字列の始め文字列の1文字目から順に取得してトークンのデータ構造としてもよい。例えば、あらかじめ定められた単語がTY、HKである場合には、文字列HKTYはHKとTYとに対応するトークンの列に変換することができる。また、文字列TYKTJMHKは、KTJMがあらかじめ定められている単語ではないが、前後のTY、HKはあらかじめ定められた単語であるので、あらかじめ定められた単語の有無により、TY、KTJM、HKという単語のトークンの列に変換することができる。また、文字列を構成する1文字それぞれを1つのトークンに対応させて、トークンの列に変換することも可能である。例えば、文字列TYHKは、T、Y、H、Kという文字のトークンの列に変換することができる。一般に、文字コードによっては全ての1文字が等しいバイト数で構成されるとは限らない。そこで、全ての1文字が等しいバイト数で構成されない文字コードを用いる場合などには、このように1文字を1トークンとして、文字列をトークンの列に変換することもできる。なお、トークンの列において、1番目のトークンをトークン列の開始端という。例えば、図2の例においては、TYに対応するトークンがトークン列の開始端となる。トークンの列の併合により構成される木構造に関する定義上述の条件1における、共通するトークンの列を開始端より併合するとは、次の処理をいう。第1のトークンの列A1A2...AnB1B2...Bmと第2のトークンの列A1A2...AnC1C2...Ckとが与えられた場合、この2つトークンの列は、開始端A1よりn個のトークンの部分列A1A2...Anが共通している。そこで、A1からAnのそれぞれのトークンに対応するノードを順に直列にエッジで接続し、A1に対応するノードを根ノードとし、Anに対応するノードを末端ノードとする木構造を作る。次に、Anに対応するノードの子ノードを、B1に対応するノードとC1に対応するノードとし、B1からBmそれぞれのトークンに対応するノードを順に直列にエッジで接続し、また、C1からCkのそれぞれに対応するノードを順に直列にエッジで接続することをいう。なお、2つのトークンの列において、共通するトークンの列が開始端より存在しない場合には、2つの異なる木構造が構成される。例えば、DEFとGEFのように、開始端のトークンであるDとGとが異なる場合には、トークンD、トークンEおよびトークンFそれぞれに対応するノードを順に直列にエッジで接続した木構造と、トークンG、トークンEおよびトークンFそれぞれに対応するノードを順に直列にエッジで接続した木構造とが構成される。なお、文字列の先頭には、文字数0の空文字列が存在するとして、先頭の空文字列をトークンとすれば、共通するトークンの列が開始端より存在しない場合でも、1つの木構造を生成することができ、このような場合でも本発明の一実施形態は適用可能である。部分木に関する定義なお、以下では、トークンの列D1D2...Dnについて、D1からDnそれぞれに対応するノードを順に直列にエッジで接続して得られる木構造を、トークンの列D1D2...Dnに対応する木構造ということにする。また、木構造の根ノードを開始点として、エッジの始点から終点を順に辿って得られる経路を木構造の部分木ということにする。例えば、トークンの列E1E2E3E4E5に対応する木構造の部分木として、E1、E1E2、E1E2E3やE1E2E3E4に対応する木構造を挙げることができる。また、すでに、共通するトークンの列を開始端より併合して構成された木構造がすでに存在する場合において、新たなトークンの列を追加するとは、その新たなトークンの列の開始端からの部分列に対応する木構造が、すでに存在する木構造のいずれかの木構造の部分木となれば、部分列以外のトークンの列に対応する木構造の根ノードを、その部分木の最後のノードの子ノードとする。もし、新たなトークンの列の開始側の部分に対応する木構造が、すでに存在する木構造のどの部分木ともならない場合には、その新たなトークンの列に対応する木構造を追加する。ノードとエッジとを表すデータ構造の例本実施形態においては、条件2として述べたように、木構造を構成するノードそれぞれには、そのノードを根ノードとする木構造の末端ノードまでの長さの最大値および最小値が関連付けられている。そこで、インデックスメモリ101が記憶する木構造データは、例えば、図3に示すデータ構造により、ノードとそのノードを始点とするエッジとを表して記憶される。図3において、1つのデータ構造には4つのスロット301-304が含まれ、第1スロット301には、トークンが表す文字または文字列が格納される。第2スロットには、そのノードを根ノードとする木構造の末端ノードまでの長さの最大値が格納される。第3スロットには、そのノードを根ノードとする木構造の末端ノードまでの長さの最小値が格納される。第4スロット304には、子ノードの情報が格納され、これによりエッジが表される。なお、第1スロット301には、トークンが表す文字または文字列そのものが格納される必要はなく、トークンが表す文字または文字列へのポインタなど、トークンが表す文字または文字列を表すための情報が格納されていればよい。スロット304に格納される子ノードの情報とは、子ノードを表すデータ構造を参照するために必要な情報である。例えば、子ノードに対応するデータ構造が格納されているメモリのアドレスである。1つのノードの子ノードが複数存在すれば、複数のメモリのアドレスが第4スロット304に格納される。また、末端ノードを表すデータ構造においては、子ノードの情報は格納されないこととなる。トークンの列に対応する木構造の例図4は、複数のトークンの列と、その複数のトークンの列から共通するトークンの列を開始端より併合して構成される木構造との例を示す。図4のaに示すように、第1のトークンの列として、ABCD、第2のトークンの列としてABDEC、第3のトークンの列として、ACEBEF、第4のトークンの列として、ACEBGHが与えられたとする。これらのトークンの列から、共通するトークンの列を開始端より併合して構成される木構造は、図4のbに示すように、各ノードに対応するデータ構造401-414を用いて構成される。例えばデータ構造401は、トークンAのノードに対応する。トークンAは複数のトークンの列の全ての開始端に現れるので、データ構造401に対応するノードの末端ノードまでの長さの最大値は、ACEBEFおよびACEBGHのトークンの個数である6となり、最小値は、ABCDのトークンの個数である4となる。データ構造401に対応するノードの子ノードとして、データ構造402に対応するノードとデータ構造408に対応するノードとがある。前者は、トークンBに対応し、後者はトークンCに対応する。このため、データ構造401の第4のスロットの値として、データ構造402とデータ構造408とのそれぞれが格納されているアドレスと、アドレスの列の終わりを示す値NULLとが格納されている。データ構造402には、BDECとBCDとに対応して、データ構造402に対応するノードを根ノードとする木構造の末端ノードまでの最大値および最小値として、4および3が格納され、子ノードを表す情報として、CDというトークンの列に対応する木構造の根ノードに対応するデータ構造403とDECというノード列に対応する木構造の根ノードに対応するデータ構造405とのそれぞれが格納されているアドレスが格納されている。以下、データ構造404-414は同様に説明される。特に、末端ノードに対応するデータ構造404、407、412、414において、それに対応するノードを根ノードとする木構造の末端ノードまでの長さの最大値と最小値とは同じになり、1である。したがって、末端ノードまでの長さの最大値と最小値とがともに1であるかどうかにより、末端ノードであるかどうかを判定できる。共通するトークンの列を開始端より併合する処理のフローチャートの例共通するトークンの列を開始端より併合してトークンに対応するノードを用いて構成された木構造の構成方法については、一般的に述べたが、それをフローチャートで具体的に示した例が、図5である。ステップS501の処理として、変数LとMとの初期化を行なう。すなわち、変数Lに、併合するべきトークンの列のトークンの個数を代入し、変数Mに、1を代入する。図5のフローチャートにおいては、トークンの列を走査し、開始端より順にトークンの文字列を取得し、木構造の根ノードから順にノードの文字列と比較を行なう。このとき、変数Lは、未走査のトークンの数を表し、変数Mは、開始端より何番目のトークンを現在注目しているかを表す。ステップS502の処理として、配列Nの初期化を行なう。配列Nは、木構造の根ノードを始点とする経路の情報を格納する。そこで、Mが1であるステップS502においては、配列NのM番目の要素N[M]に、木構造の根ノードに対応するデータ構造であって、開始端のトークンの文字列を第1のスロットに格納しているデータ構造のアドレスを代入する。なお、そのような木構造の根ノードに対応するデータ構造が存在しない場合には、N[M]にはNULLが代入されるものとする。ステップS503として、N[M]の値がNULLであるかどうかを判断する。もし、N[M]の値がNULLであれば、共通するトークンの列が開始端より存在しない。そこで、ステップS504へ処理を移行させ、トークンの列に対応する木構造を構成して追加する。ステップS503において、N[M]の値がNULLでなければ、共通するトークンの列が開始端よりする。そこで、ステップS505に処理を移行させ、N[M]の表すノードの最大値及び最小値の調整を行なう。すなわち、Lの値が、N[M]の表すノードの末端ノードまでの長さの最大値を超えていれば、Lを、N[M]の表すノードの最大値として格納する。また、Lの値が、N[M]の表すノードの末端ノードまでの長さの最小値を下回っていれば、Lを、N[M]の表すノードの最小値として格納する。ステップS506の処理として、トークンを一つ処理したので、Lの値を1減少させ、次のトークンを処理するために、Mの値を1増加させる。ステップS507の処理として、Lの値が0と等しいかどうかを判定する。もし、Lの値が0に等しければ、トークンの列の全てのトークンに対応するノードが木構造に存在したので、処理を終了する。Lの値が0に等しくなければ、ステップS508へ処理を移行する。ステップS508の処理として、N[M-1]の表すノードの子ノードのうち、M番目のトークンの文字列を持つノードのアドレスを変数N[M]に代入する。ステップS509の処理として、N[M]の値がNULLであるかどうかを判定する。もし、N[M]の値がNULLであれば、ステップS510へ処理を移行させ、M番目以後のトークンの列に対応する木構造を生成し、その根ノードを、N[M-1]の子ノードとして追加する。ステップS509の処理において、N[M]の値がNULLでなければ、M番目のトークンとN[M]に対応するノードとの処理のために、ステップS505へ戻る。インデックスメモリ101は、複数の文字列が与えられた場合、それぞれの文字列について、例えば図5のフローチャートを実行して得られる木構造データを記憶する。インデックスメモリ101に、複数の文字列が与えられ、条件1と条件2とを満たす木構造に対応する木構造データが記憶されているときには、新たな文字列が、複数の文字列の中に存在するかどうかは、次のようにして検出することができる。すなわち、新たな文字列をトークンの列に変換し、図5のフローチャートを実行した場合に、ステップS507において、変数Lの値が0となったときに、N[M]が末端ノードであるかどうかにより検出することができる。そこで、以下では、複数の文字列が与えられ、条件1と条件2とを満たす木構造に対応する木構造データが記憶されている場合に、新たな文字列が、複数の文字列の中に存在するかどうかを検出する処理についてより詳細に説明する。また、新たな文字列のことを、検索する文字列という。トークナイザトークナイザ102は、検索する文字列を1または複数のトークンの列に変換する。変換されたトークンの列は、検索装置100のメモリに格納され、例えば格納されたメモリのアドレスが、検索部103に伝達される。検索部検索部103は、トークナイザ102により検索する文字列から変換されたトークンの列を走査し、インデックスメモリ101に記憶されている木構造データのノードの子ノードを選択して根ノードを始点とする経路を検索する。すなわち、検索部103は、トークナイザ102により検索する文字列から変換されたトークンの列を開始端から順に走査し、走査中のトークンの情報を取得する。そして、取得されたトークンの情報を用いて、インデックスメモリ101に記憶されている木構造データの表す木構造の走査中のノードの子ノードの中からノードを選択する。これを、子ノードを選択するという。子ノードを選択するときには、選択される子ノードの末端ノードまでの長さの最大値以下かつ最小値以上の範囲に、未走査のトークンの数を含むように選択する。もし、未走査のトークンの数が、どの子ノードの末端ノードまでの長さの最大値を超えていたり、あるいは、どの子ノードの末端ノードまでの長さの最小値を下回っていたりすれば、検索する文字列のトークンの個数が、複数の文字列のどの文字列のトークンの個数と同じにならないので、検索する文字列は、複数の文字列のどの文字列とも異なることが直ちに検出できる。そこで、検索部103は、図6に示すように、トークン列保持部602と、トークン個数保持部603と、トークン番号保持部604と、ノード情報保持部605とを有していてもよい。トークン列保持部602は、トークナイザが、検索する文字列を変換したトークンの列を保持する。例えば、図2のaや図2のbに示す配列のアドレスを、レジスタなどを用いて記憶する。トークン個数保持部603は、トークナイザが、検索する文字列を変換したトークンの列のトークンの個数を保持する。例えば、トークンの個数を、レジスタなどを用いて記憶する。トークン番号保持部604は、トークンの列の中で、現在走査しているトークンの番号を保持する。例えば、トークンの番号を、レジスタなどを用いて記憶する。ノード情報保持部605は、木構造データの現在走査しているノードに対応するデータ構造に関する情報を記憶する。例えば、ノードに対応するデータ構造のアドレスを、レジスタなどを用いて記憶する。図7は、検索部103の処理の流れを説明するフローチャートである。変数Lは未走査のトークンの数を保持する変数である。変数Mは、何番目のトークンを走査しているかを表す変数である。そこで、ステップS701として、変数Lにトークナイザから伝達されたトークンの列のトークンの個数を代入する。また、変数Mに1を代入する。なお、変数Lは、トークン個数保持部603に対応し、変数Mは、トークン番号保持部604に対応する。ステップS702の処理として、1番目のトークンの文字列を持ち、変数Lの値が、かつ、末端ノードまでの長さの最大値と最小値との範囲内となる根ノードの情報を変数Nに代入する。変数Nは、ノード情報保持部605に対応する。ステップS703の処理として、Nの値がNULLかどうかを判定する。Nの値がNULLであれば、1番目のトークンの文字列を持ち、かつ、末端ノードまでの長さの最大値と最小値との範囲内となる根ノードが存在しないことであるので、検索する文字列は登録されていない。すなわち、複数の文字列の中に検索する文字列は存在しない。したがって、ステップS704処理を移行し、文字列は登録されていないと判断する。ステップS703においてNの値がNULLでなければ、ステップS705へ処理を移行し、トークンを1つ走査したので、未走査のトークンの数を格納する変数Lの値を1減少させ、次のトークンを走査するために、変数Mの値を1増加させる。ステップS706の処理として、変数Lの値が0に等しいかどうかを判定する。もし変数Lの値が0に等しければ、トークンの列の全てのトークンを走査したので、ステップS707へ処理を移行させる。ステップS707の処理として、変数Nが末端ノードを表すかどうかを判定する。もし、Nが末端ノードでなければ、ステップS708へ処理を移行させ、文字列は登録されていないと判断する。ステップS707において、Nが末端ノードであると判定されれば、ステップS709へ処理を移行させ、文字列は登録されていると判断する。ステップS706において、Lが0と等しくないと判定されれば、ステップS710へ処理を移行し、変数Nの表すノードの子ノードのうち、M番目のトークンの文字列を持ち、かつ、変数Lの値が、末端ノードまでの長さの最大値と最小値との範囲内となるノードの情報を代入する。ステップS711の処理として、変数Nの値がNULLであるかどうかを判定する。変数Nの値がNULLであれば、M番目のトークンに対応するノードが存在しないこととなる。したがって、ステップS712に処理を移行させ、文字列は登録されていないと判断する。ステップS711において、変数のNの値がNULLでないと判定されれば、ステップS705へ戻る。なお、本実施形態に係る検索装置は、計算機にプログラムを実行させることにより実現することができる。すなわち、インデックスメモリ101を計算機のメモリや二次記憶として実現し、トークナイザ102と検索部103とをそれぞれ実現するモジュールとして有するプログラムを計算機のCPUに実行させることにより実現できる。トークナイザ102を実現するモジュールは、例えば、検索する文字列が格納されたメモリのアドレスから文字列を読出して、メモリ中の領域にトークンの列を表すデータ構造を構成し、その領域のアドレスを、検索部103を実現するモジュールに伝達する。検索部103を実現するモジュールは、トークン列保持部602、トークン個数保持部603、トークン番号保持部604、ノード情報保持部605に対応するレジスタなどを操作し、トークンの列に変換された文字列が、インデックスメモリ101に記憶された木構造に対応する文字列の中に存在するかどうかなどを検出する。なお、検索装置は、LSIなどを組み合わせて、ハードウェアのみによって実現することもできる。実施例図8は、図5と図7とのフローチャートの処理の例を示す。図8のaに示すように、登録される文字列がMRMAINETCOLTDとMRMAINETSYSTEMCOLTDとであれば、図5のフローチャートの処理により、図8のbに示す木構造が生成される。したがって、インデックスメモリ101には、図8のbに示す木構造を表す木構造データが記憶される。検索する文字列が、MRMAINETであれば、トークナイザ102により、図8のcに示すデータ構造によって表されるトークンの列が生成される。このトークンの列が、検索部103に伝達されると、ステップS702において、Nの値がNULLとなる。なぜならば、ノード1は、1番目のトークンの文字列であるMRを有するが、トークンの列のトークンの個数が2であり、2はノード1から末端ノードまでの長さの最大値4と最小値3との範囲に含まれないので、ステップS703においてS704へ分岐し、文字列は登録されていないと判断される。実際、図8のaには、MRMAINETと一致する文字列は含まれていない。したがって、MAINETに対応するトークンを走査するまでもなく、MRMAINETが登録されていないと判断できる。検索文字列が、MRMAINETCOLTDであれば、トークナイザ102により、図8のdに示すデータ構造によって表されるトークンの列が生成される。このトークンの列が、検索部103に伝達されると、変数L、M、Nの値は図8のeに示されるように遷移する。すなわち、ステップS701における変数L、M、Nの値は行21に示されるものとなる。ただし、Nの値は初期化前であり、NULLとした。ステップS702が実行されると、変数L、M、Nの値は、行22に示すように、Nの値がノード1を表すようになる。ステップS705が終了すると、変数L、M、Nの値は、行23に示すようになる。ステップS706が実行され、ステップS710が実行されると、変数L、M、Nの値は、行24に示すようになる。ステップS711において、Nの値はNULLではないので、ステップS705に処理が戻り、変数L、M、Nの値は行25に示すようになる。ステップS706、S710の処理により、変数L、M、Nの値は、行26に示すようになり、ステップS711においてNの値はNULLではないので、ステップS705へ処理が戻り、変数L、M、Nの値は行27に示すようになる。ステップS706において、変数Lの値が0になっているので、ステップS707へ分岐し、ノード3は末端ノードなので、ステップS709に分岐する。したがって、ステップS709において、文字列は登録されていると判断される。実際、図8aには、第2の文字列にMRMAINETCOLTDが存在する。このように、登録されている文字列を検索する場合であっても、トークンの列と一致しないノードを走査することがない。応用例本実施形態に係る検索装置は、例えば振込の宛名人が取引先として登録されているかどうかを検出し、また、振込の宛名人が取引先であれば、その口座番号などを取得するために用いることができる。すなわち、あらかじめ、取引先の口座の名義人の名前を表す文字列それぞれをトークンの列に変換し、共通するトークンの列を開始端より併合して構成される木構造データをインデックスメモリ101に記憶する。このとき、木構造データには末端ノードまでの長さの最大値および最小値を関連づけておく。そして、振込の宛名人の名前が入力された場合、その名前を表す文字列をトークナイザ102に伝達し、トークンの列に変換し、検索部103により名前を表す文字列が、取引先の口座の名義人の名前の文字列の中に存在するかを検出する。例えば図7のフローチャートのS708、S712の処理が実行される場合には、振込の宛名人が取引先として登録されていないとする。また、末端ノードに、取引先の口座番号など関連付けておくことにより、ステップS709の処理が実行される場合に、変数Nの表すノードに関連付けられた口座番号などを取得することにより、取引先の口座番号などを取得することができ、振込の処理などを行なうことができる。実施形態2本発明の実施形態2として、図3に示したデータ構造の変形例を図9に示す。図9のaにおいて、データ構造は、6つのスロットを有し、スロット901、904、905、906は、図3におけるスロット301、302、303、304にそれぞれ対応する。図9においては、スロット902、903が示されている。スロット902には、スロット901に記憶される文字列の先頭の文字列が格納される。また、スロット903には、その文字列の長さが格納される。例えば、スロット901にMTUが格納される場合には、スロット902、スロット903にはそれぞれ、M、3が格納される。図9のbは、aに示すデータ構造を用いて、図8のaに示す文字列に対応する木構造データを示す。このようなデータ構造を用いる場合には、図7のフローチャートのステップS702とステップS710において、まず、トークンの文字列の先頭の文字が、スロット902に格納されている文字と同じであり、かつ、トークンの文字列の長さが、スロット903に格納されている値と同じノードのアドレスを得るようにする。もし、トークンの文字列の先頭の文字が、スロット902に格納されている文字と同じであり、かつ、トークンの文字列の長さが、スロット903に格納されている値と同じノードが根ノードあるいは子ノードとして存在しなければ、トークンの文字列とスロット901の文字列とを比較するまでもなく、検索する文字列が、複数の文字列の中に存在しないことを検出することができる。また、ノードに、末端ノードまでの長さの最大値および最小値を関連付けるのではなく、末端ノードまでの長さのリストを関連付けておいてもよい。この場合には、未走査のトークンの数が、子ノードに関連付けられているリストになければ、検索する文字列が、複数の文字列の中に存在しないことを検出することができる。