(57)【要約】【課題】  僅かなメモリ空間だけを必要とし、前記空間を簡単にトラバースでき、且つ簡単な手法で改変できる電子化データアレイを得る。    【解決手段】  本発明は、データ辞書のようなデータ集合の配置を表した有向ツリーの電子化データアレイに関係し、各データ入力はツリーノードと関連付けられる。このアレイは、メモリに保存されるテーブル値からなり、当該値は第１の全体的な順序関係に基づき順序付けられた前記ツリーのノードランクを示している。また、前記保存値に関連付けられた各アドレスは、第２の全体的な順序関係に基づき順序付けられた前記ツリーのノードランクを示している。本発明はさらに、前記有向ツリーの符号化方法と、前記集合のデータ入力を符号化する方法と、前記集合のデータ入力を示すインデックスを復号化する方法にも適用される。
2005525625.tif 000002
【特許請求の範囲】
【請求項１】
辞書データのようなデータ集合の編成を表した有向ツリーからなり、各々のデータは前記ツリーの固有ノードと関連付けられている電子化データアレイにおいて、
テーブル値を保存したメモリを備え、
前記値は、第１の全体的な順序関係に基づき順序付けられた前記ツリーのノードランクを示すと共に、
前記値が保存されるアドレスは、第２の全体的な順序関係に基づき順序付けられた前記ツリーのノードランクを示すものであることを特徴とする電子化データアレイ。
【請求項２】
前記第１の全体的な順序関係は、ノードをその子孫に関連して順序付ける子孫の順序関係と、一つのおよび同一のノードからの各子ノードを順序付ける長子の順序関係とを組み合わせたものであることを特徴とする請求項１記載の電子化データアレイ。
【請求項３】
第２のノードが第１のノードの子孫であるか、或いは第１のノードが第１の子の子孫または第１の子と同化し、第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第１の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも下位にあることを特徴とする請求項２記載の電子化データアレイ。
【請求項４】
第２のノードが第１のノードの子孫であるか、或いは第１のノードが第１の子の子孫または第１の子と同化し、第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第１の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも上位にあることを特徴とする請求項２記載の電子化データアレイ。
【請求項５】
前記第２の全体的な順序関係は、前記子孫の順序関係と前記長子の順序関係とを逆にした順序関係を組み合わせたものであることを特徴とする請求項２〜４のいずれか一つに記載の電子化データアレイ。
【請求項６】
第１のノードが第２のノードからの子孫であるか、或いは第１のノードが第１の子の子孫または第１の子と同化し、第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第２の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも下位にあることを特徴とする請求項５記載の電子化データアレイ。
【請求項７】
第１のノードが第２のノードからの子孫であるか、或いは第１のノードが第１の子の子孫または第１の子と同化し、第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第２の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも上位にあることを特徴とする請求項５記載の電子化データアレイ。
【請求項８】
前記データは、アルファベット順を持った一続きのアルファベットキャラクタであり、前記ツリーの各アークは少なくとも一つのデータ入力と関連付けられており、一つのノードから２つの子の間における長子の順序関係が、前記ノードとその２つの子との間の各アークと関連付けられたキャラクタ間における前記アルファベット順の関係によって与えられるものであることを特徴とする請求項２〜７のいずれか一つに記載の電子化データアレイ。
【請求項９】
辞書のようなデータ集合のアレイを表した有向ツリーの符号化方法であって、前記集合の各データ入力がそれぞれ前記ツリーの固有ノードと関連付けられているものにおいて、
第１のインデックスと第２のインデックスが前記ツリーの各ノードにそれぞれ与えられ、
前記第１のインデックスは、前記ツリーの各ノードを順序付ける第１の全体的な順序関係に基づいたノードランクを示しており、
前記第２のインデックスは、第２の全体的な順序関係に基づいたノードランクを示しており、
前記第１の全体的な順序関係が、ノードをその子孫に関連して順序付ける子孫の順序関係と、一つのノードからの子の各ノードを順序付ける長子の順序関係とを組み合わせ、
前記第２の全体的な順序関係が、前記子孫の順序関係と前記長子の順序関係とを逆にした順序関係を組み合わたことを特徴とする符号化方法。
【請求項１０】
ツリーの任意のノードに対し、ノードから生じるサブツリーのサイズを提供するために、計算ステージの再帰呼出しを行なうことを特徴とする請求項９記載の符号化方法。
【請求項１１】
親ノードと呼ばれる同一ノードからの第１の子と第２の子に関し、前記子が前記長子の順序関係に基づき順序付けられた子のリストに近接すると、前記計算ステージは、第１の子の第１インデックスと、第１の子から生じるサブツリーのサイズから開始して、第２の子の第１インデックスを決定すると共に、第１の子の第２インデックスと、第２の子から生じるサブツリーのサイズから開始して、第２の子の第２インデックスを決定することを特徴とする請求項１０記載の符号化方法。
【請求項１２】
前記計算ステージは、前記親ノードの第１インデックスと、前記リストの最後となるように分類された子の第２インデックスから開始する前記親ノードの第２インデックスとから、前記リストの最初となるように分類された子の第１インデックスを決定することを特徴とする請求項１１記載の符号化方法。
【請求項１３】
前記計算ステージは、前記親ノードの子から生じるサブツリーのサイズの合計から開始して、前記親ノードから生じるサブツリーのサイズを決定することを特徴とする請求項１０〜１２のいずれか一つに記載の符号化方法。
【請求項１４】
与えられたノードに対して、第１のポインタ種が前記子孫の順序関係に基づき子ノードを提供すると共に、第２のポインタ種がそれ以外の子ノードのリストを提供するようなポインタにより、ツリーの第１データアレイ上で動作することを特徴とする請求項９〜１３のいずれか一つに記載の符号化方法。
【請求項１５】
前記ツリーの各ノードにおける前記第１インデックスを示す値を、前記ツリーの各ノードにおける前記第２インデックスを示すアドレスに配列するテーブルを提供することを特徴とする請求項９〜１３のいずれか一つに記載の符号化方法。
【請求項１６】
前記ツリーの各ノードにおける前記第２インデックスを示す値を、前記ツリーの各ノードにおける前記第１インデックスを示すアドレスに配列するテーブルを提供することを特徴とする請求項９〜１３のいずれか一つに記載の符号化方法。
【請求項１７】
データ集合に属する入力したデータ入力を符号化する方法であって、前記データはアルファベット順で提供された一続きのアルファベットキャラクタからなり、それぞれのデータ入力が前記ツリーの固有ノードと、キャラクタに関連付けられた前記ツリーの各アークとに関連付けられているものにおいて、
前記ツリーは、請求項１〜８のいずれか一つに記載の電子化データアレイによって表されており、
前記ツリーは、根から開始してパスに沿ってノードからノードへとトラバースされると共に、前記データ入力はキャラクタ毎に分析され、
前記パスの瞬間的なノードに続くノードが瞬間的なノードの子から選択され、この選択が一連の比較ステージによって実行され、それぞれの比較ステージでは、前記データ入力における瞬間的なキャラクタと、瞬間的なノードをその子の一つにリンクするアークに関連付けられたキャラクタとを比較し、
前記入力データが完全に分析された時にだけ前記トラバースが中断されると共に、
前記データ入力の符号化された値としてインデックスを提供し、このインデックスは、前記パスの最後のノードを示す前記電子化データアレイからなるテーブルのアドレスの関数であることを特徴とする符号化方法。
【請求項１８】
前記インデックスは前記パスの最後のノードを示すアドレスに等しいことを特徴とする請求項１７記載の符号化方法。
【請求項１９】
前記インデックスは前記パスの最後のノードを示すアドレスで、前記テーブルに保存された値に等しいことを特徴とする請求項１７記載の符号化方法。
【請求項２０】
前記瞬間的なノードの連続する子は、前記電子化データアレイのテーブルにそれらのそれぞれを示したアドレスに基づき決定され、瞬間的な子自身を示すアドレスと、この瞬間的な子から生じるサブツリーのサイズとから開始して、瞬間的な子に続く子を示すアドレスを得ることを特徴とする請求項１７〜１９のいずれか一つに記載の符号化方法。
【請求項２１】
瞬間的な子を示すアドレスで前記テーブルに保存される値と、先行する子を示すアドレスで前記テーブルに保存される値とから開始して、瞬間的な子から生じるサブツリーのサイズを得ることを特徴とする請求項２０記載の符号化方法。
【請求項２２】
辞書データのような有向ツリーとして配列されたデータ集合に属するデータ入力を示すインデックスを復号化する方法であって、前記データはアルファベット順で提供された一続きのアルファベットキャラクタからなり、それぞれのデータ入力が前記ツリーの固有ノードと、キャラクタに関連付けられた前記ツリーの各アークとに関連付けられているものにおいて、
前記ツリーは、請求項１〜８のいずれか一つに記載の電子化データアレイによって表されており、
前記ツリーは、根から開始してパスに沿ってトラバースされ、
前記パスの瞬間的なノードに続くノードが瞬間的なノードの子から選択され、この選択が一連の比較ステージによって実行され、それぞれの比較ステージでは、前記インデックスと、前記電子化データアレイにて前記子の一つを示すインデックスとを比較し、
復号化された値として、前記パスを構成するアークと関連付けられたキャラクタチェインを提供することを特徴とする復号化方法。
【請求項２３】
前記子の一つを示すインデックスは、前記電子化データアレイのテーブルのアドレスであることを特徴とする請求項２２記載の復号化方法。
【請求項２４】
前記子の一つを示すインデックスは、前記電子化データアレイのテーブルに保存される値であることを特徴とする請求項２２記載の復号化方法。
【請求項２５】
前記瞬間的なノードの連続する子は、前記電子化データアレイのテーブルにそれらのそれぞれを示したアドレスに基づき決定され、瞬間的な子を示すアドレスと、この瞬間的な子から生じるサブツリーのサイズとから、瞬間的な子に続く子を示すアドレスを得ることを特徴とする請求項２２〜２４のいずれか一つに記載の復号化方法。
【請求項２６】
瞬間的な子を示すアドレスで前記テーブルに保存される値と、先行する子を示すアドレスで前記テーブルに保存される値とから、瞬間的な子から生じるサブツリーのサイズを得ることを特徴とする請求項２５記載の復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、とりわけ辞書のようなデータ集合の編成を示す有向ツリーの電子化データアレイに関する。また本発明は、前記電子化されたデータアレイに前記有向ツリーを符号化する方法に関する。また本発明は、前記データ集合に属するデータエントリを、前記電子化されたデータアレイのインデックスに符号化する方法に関する。さらに本発明は、前記電子化されたデータアレイのインデックスを基準として、対応する前記データを取り出すことが可能な復号化方法に関する。
【背景技術】
【０００２】
技術状況を論じる前に、これから先に用いる幾つかの用語を定義する。
【０００３】
有向グラフ（以下、単に「グラフ」という）は、ペアＧ＝（Ｓ，Ａ）を示すもので、Ｓは頂点（以下、これも「ノード（節）」という）の集合，Ａは「アーク（弧）集合」と呼ばれるＳ×Ｓ個のサブ集合である。
【０００４】
グラフ内のパス（経路）は、（ｓl-1，ｓl）がi=1…nに対するアークとなるような、順序付けられた頂点の連続（ｓ0，ｓ1，…ｓ）である。ここで、ｓn＝ｓ0（但し、ｎ≧１）であれば、このパスは「回路」若しくは「サイクル」と呼ばれる。仮にあるグラフにおける２つの任意のノードが、１つのパスによってリンクされている場合、そのグラフは「関連された」ものと呼ばれる。
【０００５】
ツリー（木）は、非回路の関連されたグラフとして定義される。これは、２つの任意の頂点が、唯一のパスによってリンクされるものとしても示される。木は特別な頂点Ｒを備えており、この特別な頂点Ｒと異なるあらゆる頂点ｓが、パスによって頂点Ｒの後ろにリンクされるようになっている。こうした特別な頂点Ｒは、ツリーの「根（ルート）」と呼ばれる。
【０００６】
特定の頂点Ｓに対し、頂点Ｓから頂点ｓdへの間にパスが存在するようなツリーのあらゆる頂点ｓdが、頂点Ｓの子孫（descendant）となる。逆に特定の頂点ｓに対し、頂点Ｓａから特定の頂点ｓへの間にパスが存在するようなツリーのあらゆる頂点Ｓａが、頂点ｓの祖先（ancestor）となる。頂点Ｓにつながる「頂点の子（offspring）」は、（Ｓ，ｓf）∈Ａのような頂点ｓの子孫ｓfである。ツリーのあらゆる頂点ｓにとって、ｓのサブツリーはｓの全ての子孫を含んだ根ｓのツリーである。
【０００７】
最後に、「葉（リーフ）」とは子孫の存在しない全てのツリー頂点である。
【０００８】
多くのデータ処理方法が、特に情報のクラス化，圧縮若しくは保存の手順において、枝分かれした木構造のデータアレイを用いている。
【０００９】
考慮中のアプリケーションについて言えば、データは文字，連続する音素，波形，或いは輝度／クロミナンスパターンなどの繋がり（鎖）でもよい。
【００１０】
一般的に先入観がなければ、以下に説明するデータは、初歩的な構成要素やキャラクタ（例えば、文字，表意文字，数字，英数字記号）の繋がりによって構成されるであろう。こうした利用可能なキャラクタの集合は、一つのアルファベットを構成する。ここでは、前記アルファベットが「アルファベット順」と呼ばれる完全な順序関係を持っていると仮定する。
【００１１】
「サーチエンジン」，「辞書検索」，「電話帳検索」などのような多くのアプリケーションでは、特にオンラインのアクセスに際して、実際の動作状態に厳しい制約を伴いながら、非常に大容量のデータを保存し、アクセス可能にしなければならない。
【００１２】
大掛りな計算能力を必要とせずに、全データを素早くアクセスできるようにしなければならない。さらには、アクセス時間を減らすために、中央メモリに大きなデータ容量を持ち続けなければならない。このメモリのサイズが極度に肥大化するのを防ぐのに、事前にデータを頻繁に圧縮する必要がある。好ましくは、解凍を行なう必要なしに、データをアクセスできるようにすべきであって、これによりアクセス時間がさらに低下するであろう。
【００１３】
上述のアプリケーションに関して言えば、データが非対称的に処理されてもよい。データの圧縮段階は、比較的長時間で複雑な処理を含んでもよいため、逆にデータアクセス時の検索段階は簡素で且つ高速でなければならない。従ってデータは、固定の圧縮されたフォームでメモリに保存されてもよく、データの更新はそのデータがオンラインで逆戻りする前に行なわれる。
【００１４】
データ編成した幾何学構造は、その一つが上記定義されたツリーでもあるが、圧縮を行うのにとりわけ都合がよい。この幾何学構造は、特に辞書若しくは電話帳に存在する。ワード（語）の共通な認識において、辞書は「入力」とも呼ばれるデータファイルであって、各々のデータは一連のアルファベットキャラクタからなり、このアルファベットキャラクタの繋がりはツリー幾何学構造で編成される。
【００１５】
実際の電子化されたデータアレイで、全ての辞書データはインデックスと関連付けられている。辞書内のキャラクタ（若しくはワード）の繋がりを検索することは、それに対応するワードのインデックスを確認することを意味する。従って、頭文字を表記するよりもデータ処理に適合した一続きのインデックスにより、テキストが表現されてもよい。
【００１６】
従来技術において、様々な種類の表現やアレイ（配列）が、とりわけZiv-Lempel圧縮を利用した二分テーブルの形式や、ハッシュテーブルの形式や、構文的（レクシカル）ツリーの形式で提案されている。
【００１７】
完全アクセスの場合には、上記様々な種類の表現が同等のパフォーマンスを提供する。ここでいう「完全アクセス」とは、エラーや変更を無視して、解析すべきワードに一致する辞書内の正確なつながりのキャラクタを検索するためのアクセスモードのことである。
【００１８】
構文的ツリーの形式によるデータアレイは、一連のキャラクタの分析（例えば、構文解析）を想定している。図１は、次の辞書Δ（Δ＝{"abolish"，"abolition"，"appeal"，"attorney"，"bar"，"barrister"，"bench"，"case"，"court"，"crime"}）に対する構文的ツリーの例を示している。
【００１９】
この構文的ツリーでは、辞書の各ワードにおけるキャラクタに対して、前記アークが関連付けられることに留意されたい。より具体的には、それぞれのツリーアークにタグが関連付けられており、それぞれのタグは、タグとして機能するキャラクタと適合する。構文的ツリーは、辞書内の一つのワードに骨格が一致する全てのパスの接合からなる。パスの「骨格（スケルトン）」は、このパスの構成要素となるアークタグのキャラクタの繋がりである。辞書のワードは、辞書「入力」とも呼ばれる。
【００２０】
さらに、構文的ツリーの各リーフは白抜き円で示されているのに対し、それ以外の頂点は塗潰し円で示されていることに留意されたい。このツリーの根は、「Ｒ」として示されている。
【００２１】
ここでのツリーは、インデックス化されているものと見なす。すなわち、一つのインデックスは各々の頂点と関連付けられている。構文的ツリーにおける一つの基本的な動作は、与えられたワードに基づき、これに対応する辞書入力のインデックスに対して検索を行なうことにある。この動作は、連続するキャラクタによりタグ付けられたアークに沿って、ツリーのトラバース（移動処理）が必要となる。
【００２２】
より具体的には、検索アルゴリズムは、辞書入力の値［associated-index(s)］が存在するならば、この辞書入力の値としてインデックスを戻し、さもなければデフォルトでは識別できないコード｛unknown-word-index｝を戻す"AnalyzeWord"関数を実行する。以後、前記値はＣ言語の擬似コードにて、次のように表現される。
【００２３】
【表１】
2005525625.tif 000003
【００２４】
上記"s = corresponding-descendant(s)"なる命令によるトラバースは、構文的ツリーの電子化されたデータアレイが利用可能であることを前提としている。
【００２５】
一般に、電子化されたツリーのデータアレイは、簡単にそのツリーをトラバースし、利用して変更することが必要とされる。
【００２６】
初期に知られた電子化データアレイでは、メモリに記憶され、（ｓi，ｓj）∈Ａのときにｍij＝１となる隣接テーブル（adjacency Table）Ｍ＝（ｍij）（但し、i=0,…,n ；j=0,…,n）によって、ツリーが表現される。
【００２７】
また、最近の電子化データアレイでは、連続するポインタとしてツリーが示されている。図２Ａに示す第１に知られた変形例では、各々のノードが値（若しくはインデックス）と、その子ノードを指し示すポインタのテーブルとにより表現される。テーブルのサイズは、あるツリーのノードが保有することができる子の最大数（k）に一致する（この場合のツリーを、「k-ツリー」という）。図２Ａに示す変形例は、３−ツリーを示している。
【００２８】
ポインタのテーブルによって子ノードを符号化すると、多くの数の子ノードを持った少ない数のノードと、僅かな数の子ノードしか持たないその他多くの数のノードとを、ツリーが保有した時点で既に、多くのメモリ空間を必要とする欠点を引き起こす。第２に知られたアレイの変形例では、与えられたノードに対し、「年長の子」と呼ばれる子ノードの一つに向けて指し示すポインタと、「年長の子」からその兄弟の繋がったリストに向けてのポインタとを利用することで、この困難さが改善される。図２Ｂは、こうした第２の変形例としての５−ツリー表現を示している。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
ポインタはツリーの幾何学的構造を素早く改変させることができる反面、相対的にかなり大きなメモリを必要とする。さらに、ノード間での子孫の検出は迅速でない。こうした検出は、２つのノードをリンクするパスを解明するものと考えられるので、ポインタによる表現の範囲内では、かなりの電子化リソースが必要となる。ツリーの過渡的な閉鎖（closing）を保存することで、演算処理量を相当に減らすことができ、この場合はノードがそれぞれの子孫を指し示すであろう。しかし、後者の選択では比較的多くのメモリ空間を占有する。
【００３０】
本発明の目的は、僅かなメモリ空間だけを必要とし、しかも前記空間を簡単にトラバースでき、且つ簡単な手法で改変できる電子化データアレイを生成することにある。
【課題を解決するための手段】
【００３１】
上記目的は、辞書データのようなデータ集合の編成を表した木からなり、各々のデータが前記ツリーの固有ノードと関連付けられ、メモリに保存された値からなるテーブルを備えており、前記値は、第１の全体的な順序関係に基づき順序付けられた前記ツリーのノードランクを示すと共に、前記値が保存されるアドレスが、第２の全体的な順序関係に基づき順序付けられた前記ツリーのノードランクを示す電子化データアレイによって達成される。
【００３２】
好ましくは、前記第１の全体的な順序関係は、ノードをその子孫に関連して順序付ける子孫の順序関係と、与えられたノードからの各子ノードを順序付ける長子の順序関係とを組み合わせたものからなる。
【００３３】
本発明の第１実施例では、第２のノードが第１のノードの子孫であるか、さもなければ第１のノードが第１の子の子孫または第１の子と同化し、且つ第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第１の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも下位にある。
【００３４】
本発明の第２実施例では、第２のノードが第１のノードの子孫であるか、さもなければ第１のノードが第１の子の子孫または第１の子と同化し、且つ第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第１の全体的な順序関係に基づき、リーの第１のノードがツリーの第２のノードよりも上位にある。
【００３５】
好ましくは、前記第２の全体的な順序関係は、前記子孫の順序関係と前記長子の順序関係とを逆にした順序関係を組み合わせたものからなる。
【００３６】
本発明の第１変形例では、第１のノードが第２のノードからの子孫であるか、或いは第１のノードが第１の子の子孫または第１の子と同化し、第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第２の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも下位にある。
【００３７】
本発明の第２変形例では、第１のノードが第２のノードからの子孫であるか、或いは第１のノードが第１の子の子孫または第１の子と同化し、第２のノードが第２の子の子孫または第２の子と同化し、これらの第１の子と第２の子を、第１のノードおよび第２のノードに共通の祖先が有すると共に、前記長子の順序関係に基づき前記第１の子が前記第２の子よりも下位にあれば、前記第２の全体的な順序関係に基づき、ツリーの第１のノードがツリーの第２のノードよりも上位にある。
【００３８】
仮に、前記データがアルファベット順をなす一続きのアルファベットキャラクタであり、前記ツリーの各アークが少なくとも一つのデータ入力のキャラクタと関連付けられれば、前記ノードとその２つの子との間の各アークと関連付けられたキャラクタ間における前記アルファベット順の関係によって、同一ノードから２つの子の間における長子の順序関係を決定してもよい。
【００３９】
本発明はさらに、辞書のようなデータ集合のアレイを表した有向ツリーがあって、前記集合の各データ入力がそれぞれ前記ツリーの固有ノードと関連付けられており、第１のインデックスと第２のインデックスが前記ツリーの各ノードにそれぞれ与えられ、前記第１のインデックスは、前記ツリーの各ノードを順序付ける第１の全体的な順序関係に基づいたノードランクを示しており、前記第２のインデックスは、第２の全体的な順序関係に基づいたノードランクを示しており、前記第１の全体的な順序関係が、ノードをその子孫に関連して順序付ける子孫の順序関係と、同一ノードからの各子ノードを順序付ける長子の順序関係とを組み合わせてなり、前記第２の全体的な順序関係が、前記子孫の順序関係と前記長子の順序関係とを逆にした順序関係を組み合わせてなる有向ツリーの符号化方法に関する。
【００４０】
好ましくは、当該符号化方法は、あらゆる任意のツリーノードに対して、前記ノードから生じるサブツリーのサイズを明らかにする計算ステージの再帰の呼出しを含んでいる。
【００４１】
親ノードと呼ばれる同一ノードからの第１の子と第２の子に関し、前記子が前記長子の順序関係に基づき順序付けられた子のリストに近接すると、前記計算ステージは、第１の子の第１インデックスと、第１の子から生じるサブツリーのサイズを基にして、第２の子の第１インデックスを決定すると共に、第１の子の第２インデックスと、第２の子から生じるサブツリーのサイズを基にして、第２の子の第２インデックスを決定する。
【００４２】
前記計算ステージは、前記親ノードの第１インデックスと、前記リストの最後となるように分類された子の第２インデックスを基にした前記親ノードの第２インデックスとから、前記リストの最初となるように分類された子の第１インデックスを決定する。
【００４３】
さらにこの計算ステージは、前記親ノードの子から生じるサブツリーのサイズの合計に基づき、前記親ノードから生じるサブツリーのサイズを決定する
好ましくは、与えられたノードに対して、第１のポインタ種が前記子孫の順序関係に基づき子ノードを提供すると共に、第２のポインタ種がそれ以外の子ノードのリストを提供するようなポインタを利用して、前記符号化方法が前記ツリーの第１データアレイ上で動作する。
【００４４】
また本発明は、辞書データのような有向ツリーに基づき編成されたデータ集合に属するデータ入力に関し、前記データはアルファベット順で提供された一続きのアルファベットキャラクタからなり、それぞれのデータ入力が前記ツリーの与えられたノードと、キャラクタに関連付けられた前記ツリーの各アークに関連付けられているものにおいて、前記ツリーが上述の電子化データアレイによって表され、前記ツリーは、根から開始してパスに沿ってノードからノードへと横断されると共に、前記データ入力はキャラクタ毎に分析され、前記パスの瞬間的なノードに続くノードが前記瞬間的なノードの子のなかから選択され、この選択が一連の比較ステージによって実行され、それぞれの比較ステージでは、入力した前記データ入力における瞬間的なキャラクタと、瞬間的なノードをその子の一つにリンクするアークに関連付けられたキャラクタとを比較し、前記入力データが完全に分析された後にのみ前記トラバースが中断されると共に、前記データ入力の符号化された値をインデックスの形態で取得し、このインデックスが、前記パスの最後のノードを表わす前記電子化データアレイのテーブルのアドレスに関係するデータ入力の符号化方法によって定義される。
【００４５】
さらに本発明は、辞書データのような有向ツリーに配列されたデータ集合に属するデータ入力を示すインデックスに関し、それぞれのデータ入力が前記ツリーの固有ノードと、キャラクタに関連付けられた前記ツリーの各アークとに関連付けられているものにおいて、前記ツリーが上述の電子化データアレイによって表され、前記ツリーが根から開始してパスに沿ってトラバースされ、前記パスの瞬間的なノードに続くノードが瞬間的なノードの子のなかから選択され、この選択が一連の比較ステージによって実行され、それぞれの比較ステージでは、前記インデックスと、前記電子化データアレイにて前記子の一つを示すインデックスとを比較し、前記パスを構成するアークと関連付けられたキャラクタチェインを提供するインデックスの復号化方法により定義される。
【００４６】
上述した本発明の特徴は、他の特徴と共に、以下に示す幾つかの実施例において、添付図面と関連付けて説明される。
【発明を実施するための最良の形態】
【００４７】
本発明の基本的な概念は、ノード間の依存関係を翻訳する全体的な順序関係に基づいて、新規なツリーによる電子化データアレイを生成することにある。
【００４８】
ノードの相互依存関係は、ツリーの各ノード群に影響を及ぼす部分的な順序付け関係を引き起こす。例えば、２つのツリーノードｓ1，ｓ2に対し、ｓ1＞ｓ2であると仮定して、ｓ2がｓ1の子孫であれば、順序付けの関係が必ず存在する。しかし、このツリーの全てのノードが、このような手法で比較されるとは限らないので（例えば、同一ノードからの子のように）、当該順序付けは単に部分的なものでしかない。
【００４９】
一つのノードから子をどのように順序付けるのかがわかっている場合には、ツリーの各ノードに関係して全体的な順序関係を構築してもよい。同一ノードの子を位置付け（ランク）するための順序付けは、便宜的に「長子」の順序付けと呼ぶものとする。アークタグがアルファベットキャラクタを含んでいる構文的ツリーについて言えば、もしアーク（Ｓ，ｓ1）と関連付けられたタグのキャラクタが、アーク（Ｓ，ｓ2）と関連付けられたタグのキャラクタに先行して位置するならば、一つのノードＳからの２つの子ｓ1，ｓ2が、ｓ1＞ｓ2なる関係を満足すべきことを認めてもよい。そうでなければ、参照ラベルタグにおけるアルファベット順序が、同一ノードからの各子ノード上で、「長子」の順序付けを生じさせる。
【００５０】
部分的な子孫の順序関係（以下、これを数１のようにあらわす）と、「長子」の順序関係（以下、これを数２のようにあらわす）とを組み合わせると、全てのノード群に対する全体的な順序関係を実現できる。
【００５１】
【数１】
2005525625.tif 000004
【００５２】
【数２】
2005525625.tif 000005
【００５３】
この組み合わせを、次のような別の方法で実現してもよい。
【００５４】
−前置（prefix）順序関係（便宜的に数４によって示される。）：
【００５５】
【数３】
2005525625.tif 000006
【００５６】
【数４】
2005525625.tif 000007
【００５７】
但し、ａ’とｂ’は、ａがａ’の子孫であり、またはａ’と同化し、ｂがｂ’の子孫であり、またはｂ’と同化するような、ａとｂの共通の祖先の子孫である。
【００５８】
数３を言い換えれば、もしｂがａの子孫であるか、さもなければａ’がｂ’の年長の兄であるならば、前置順序の観点でノードａがノードｂよりも下位にある。
【００５９】
−逆前置（inverse prefix）順序関係（便宜的に数６によって示される。）：
【００６０】
【数５】
2005525625.tif 000008
【００６１】
【数６】
2005525625.tif 000009
【００６２】
−逆後置（inverse postfix）順序関係（便宜的に数８によって示される。）：
【００６３】
【数７】
2005525625.tif 000010
【００６４】
【数８】
2005525625.tif 000011
【００６５】
数７を言い換えれば、もしａがｂの子孫であるか、ａ’がｂ’の年長の兄であるならば、後置順序の観点でノードａがノードｂよりも下位にある。
【００６６】
−逆後置（inverse postfix）順序関係（便宜的に数１０によって示される。）：
【００６７】
【数９】
2005525625.tif 000012
【００６８】
【数１０】
2005525625.tif 000013
【００６９】
２つの任意のツリーノードがお互いに子孫であるか、或いは共通の祖先の子孫であるため、上述の順序関係は全体的な順序関係を示すものとなる。したがって、上記数４（または数６）、および数８（または数１０）の順序関係は、ツリーが持つノードＳ全体の順序付けを完全に可能にする。すなわち、［0，n］におけるＳの「ランキング（順位付け）」関数は、上記のそれぞれの順序関係と関連付けることができる。
【００７０】
例えば、Prefix(s1)Rank＜Prefix(s2)Rankのとき且つその時に限り、次の数１１となるようなものが、PrefixRank：Ｓ→［0，n］である。
【００７１】
【数１１】
2005525625.tif 000014
【００７２】
Postfix(s1)Rank＜Postfix(s2)Rankのとき且つその時に限り、次の数１２となるようなものが、PostfixRank：Ｓ→［0，n］である。
【００７３】
【数１２】
2005525625.tif 000015
【００７４】
PrefixRank（前置ランク）およびPostfixRank（後置ランク）は、順序付けられた群のモルフィズム（写像）である。「ランキング」関数であるInversePrefixRank（逆前置ランク）およびInversePostfixRank（逆後置ランク）も、順序関係を用いて、同様の手法で定義することができる。
【００７５】
InversePrefix(s1)Rank＜InversePrefix(s2)Rankのとき、且つその時に限り、次の数１３となるようなものが、InversePrefixRank：Ｓ→［0，n］である。
【００７６】
【数１３】
2005525625.tif 000016
【００７７】
InversePostfix(s1)Rank＜InversePostfix(s2)Rankのとき、且つその時に限り、次の数１４となるようなものが、InversePostfixRank：Ｓ→［0，n］である。
【００７８】
【数１４】
2005525625.tif 000017
【００７９】
第１実施態様において、次の数１５で定義される［0，n］に対する［0，n］の双射（bijection）が、電子化されたデータアレイを構築するのに用いられる（ここで、oは写像の合成を表わす）。
【００８０】
【数１５】
2005525625.tif 000018
【００８１】
双射Ｔ−１は、この第１実施態様の変形に利用される。
【００８２】
同様の手法で、本発明の別な各実施態様では、InversePostfixRank o Prefix-1Rank，PostfixRank o InversePrefix-1Rank，またはInversePostfixRank o InversePrefix-1Rankの合成を基にした双射を利用してもよく、さらにこれらの実施形態の変形で、各々の双射の逆を利用してもよい。
【００８３】
単純化するために、本発明の議論では双射ＴおよびＴ−１の利用を制限するが、これは他の双射でも等しく適用できるものと理解されたい。
【００８４】
前記双射Ｔは、メモリ内に保存される第１のテーブル値の形態で電子的に表現してもよく、ノードの後置ランク（PostfixRank）は、このノードの前置ランク（PrefixRank）を示すアドレスに保存される。
【００８５】
同様に、前記双射Ｔ−１は、メモリ内に保存される第２のテーブル値の形態で電子的に表現してもよく、ノードの前置ランクは、このノードの前置ランクを示すアドレスに保存される。
【００８６】
一つの例では、これらの双射の重要性と利用をより明確にするであろう。
【００８７】
図３は、各ノードが（太字と下線で示される）前置ランクと、（イタリック体で示される）後置ランクによってインデックス化されたツリーを表している。例えば構文的ツリーの場合に、ラベルタグのアルファベット順序により引き起こされる「長子」の順序関係は、便宜的に左から右に増加して示される。この手法では、各々のノードｓが、一つの対（Prefix（s）rank，Postfix（s）Rank）で関連付けられる。好ましくは、図３Ｂに示す双射Ｔまたは図３Ｃに示す双射Ｔ−１によって、これらのペアがテーブルに保存される。
図３Ｂでは、後置ランクの値が、対応する前置ランクの値により指示されたアドレスに記憶される。その逆に、前置ランクの値は、対応する後置ランクの値により指示されたアドレスに記憶される。
【００８８】
本発明によるツリー状電子化データアレイの第１の利点は、従来のポインタによる表記が２倍のメモリ空間を必要とするのに対して、（ｎ＋１）ツリーのサイズのメモリ空間だけを占有することにある。
【００８９】
また、このツリー状電子化データアレイの本質的な第２の利点は、２つのノード間の依存（従属）関係を、非常に簡単な手法にできることにある。例えば、ノードｓ２がノードｓ１に依存するか否かを決めるのに、一方でｓ１の前置ランクPrefix（s1）rankと、ｓ２の前置ランクPrefix（s2）rankとを比較し、他方でｓ１の後置ランクPostfix（s2）Rankと、ｓ２の後置ランクPostfix（s2）Rankとを比較すれば、それ以外に必要なものはない。つまり、Prefix(s2)Rank＞Prefix(s1)RankおよびPostfix(s2)Rank＜Postfix(s1)Rankのとき、且つその時に限り、ノードｓ２がノードｓ１に依存する。
【００９０】
従って、図３Ａに関し、ペア（PrefixRank，PostfixRank）＝（５，１）で表現されるノードは、ペア（PrefixRank，PostfixRank）＝（１，５）で表現されるノードには依存するが、ペア（PrefixRank，PostfixRank）＝（22，21）で表現されるノードには依存しない。
【００９１】
同様の手法で図３Ｂのテーブルを利用すると、与えられたノードの子孫あるいは祖先が簡単に決定される。例えば、ノード（８，12）の子孫リストを決定するためには、アドレス８から開始して、アドレスを増加する方向にテーブルを分析し、後置ランク12よりも小さい値の保存データ（この場合は、６，10，11，７，８，９）の中を検索すれば十分である。これらの値は、該ノードの子孫の後置ランクを意味するものとなる。また、ノード（８，12）の祖先リストを確定するには、アドレス８から開始して、アドレスを減少する方向にテーブルを分析し、後置ランク12よりも大きい値の保存データ（ここでは、19，22）の中を検索すれば十分であろう。これらの値は、当該ノードの祖先の後置ランクを意味するものとなる。
【００９２】
図３Ｃのテーブルは、二重の手続きに利用される。前述の例に戻ると、アドレス12から開始して、アドレスを減少する方向にテーブルを分析し、前置ランク８よりも高い値の保存データ（この場合は、14，10，13，12，11，９）の中を検索するだけで、子孫のリストを決定してもよい。これらの値は、該ノードの子孫の前置ランクを意味するものとなる。また、ノード（８，12）の祖先リストを確定するには、アドレス12から開始して、アドレスを増加する方向にテーブルを分析し、前置ランク８に満たない値の保存データ（ここでは、７，０）の中を検索すれば十分であろう。これらの値は、当該ノードの祖先の前置ランクを意味するものとなる。
【００９３】
本発明の電子化データアレイにより提供された第３の利点とは、例えば構文的ツリーを利用して、キャラクタ（ワード）の繋がりを分析する際に、根から葉に向けて、さもなければ葉から根に向けて、ツリーを簡単にトラバース（移動処理）できることにある。このトラバースは、例えばノード自身のインデックスからキャラクタの繋がりを生成する際に実行される。
【００９４】
根から葉に向けてのトラバースは、与えられたノードの子を決定するためのノウハウを推定する。ここで示すように、図３Ｂまたは図３Ｃのテーブルは、前記子の検索を簡単に可能にする。
【００９５】
ナビゲーションアルゴリズムが、ノード（12，８）の子を検索していると推定される一方で、図３Ｂに示すテーブルが考慮される。アドレス８から開始して、アドレスが増加する方向にテーブルが分析される。上述した同様の手法で、12に満たないテーブルデータが検索される。12に満たないデータエントリｘを保持すると、ｘに満たない次のデータは考えに入れない。言い換えるならば、ｘよりも大きな（但し、初期値12よりは小さい）データエントリｘ’が見つかるまで、テーブルはさらに分析されることになる。この手続きは、テーブルの終点まで繰り返される。従って本例では、最初の値６に出会うと、この値が12より小さいということで保持され（＜12）、その後、値10も６より大きく12より小さいということで保持される（６＜10＜12）。後に続く値７，８，９は保持されないが、その理由はこれらが12より小さいものの、他方では最後に保持された値10を越えないからである。次の値11は、10より大きく12より小さいということで保持されるが（10＜11＜12）、それ以降の各値は12よりも大きいということで保持されない。
【００９６】
図３Ｃのテーブルは、二重のアプローチに用いられる。前述の例を利用すると、アドレス12から開始して、アドレスが減少する方向にテーブルが分析される。上述の手法で、８より大きい前置ランクを備えた保存データが検索される。８よりも大きなデータエントリｘに出会うと、それに続くｘより大きなデータは無視されることになる。言い換えるならば、ｘに満たない（但し、初期値８よりも大きい）データエントリｙが見つかるまで、テーブルはさらに分析される。この手続きは、テーブルの開始点に到達するまで繰り返される。従って本例では、最初の値14に出会うと、この値が８より大きいということで保持され（＞８）、その後、値10も８より大きく14より小さいということで保持される（８＜10＜14）。後に続く値11，12，13は、８よりも大きいものの無視されるが、その理由はこれらが最後に保持された値10を上回るからである。次の値９は、８より大きく10より小さいということで保持されるが（８＜９＜10）、それ以降の各値は８よりも小さいということで保持されない。
【００９７】
与えられたノードの子を決定するこうした方法は、小さなツリーに対してのみ適応する。以下に示すが、大きなツリーに関しては、前記子の前置／後置ランクが直接的な手法でより高速に算出できる。
【００９８】
双射ＴおよびＴ−１に基づいて構築されたテーブルに代わって、InversePostfixRanko Prefix-1Rank，PostfixRank o InversePrefix-1Rank，またはInversePostfixRank o InversePrefix-1Rankの双射を基にして、さらにはこれらの双射の逆を基にして、テーブルが構築されるならば、場合によっては分析の方向を変更したり、および／または不等式の方向を変更したりするのと引換えにではあるが、与えられたノードの子を同様の手法で決定することが可能になる。
【００９９】
同様に、葉から根へのツリーのトラバースは、与えられたノードの父親を決定できることが前提である。ここではナビゲーションアルゴリズムが、ノード（12，８）の父親を検索することが想定され、最初に図３Ｂのテーブルが考慮されるようになる。アドレス８から開始して、アドレスが減少する方向にテーブルが分析される。12よりも大きい最初のデータエントリに出会うと、このデータエントリは適用可能なノードの父親の後置インデックスを提供する（ここでは19となる）。
【０１００】
勿論、図３Ｃにおいて二重の手続きが実行される。本例では、アドレス12から開始して、アドレスが減少する方向にテーブルが分析される。８よりも小さい最初のデータエントリに出会うと、このデータエントリは適切なノードの父親の前置インデックスを提供する（ここでは７となる）。
【０１０１】
「ツリー符号化」という動作であって、任意のツリーを電子化されたデータアレイに変換するために、ノードのインデックス化を最初に行なわなければならない。本発明における電子化データアレイの形態にツリーを符号化するためには、前置ランク（PrefixRank）および後置ランク（PostfixRank）の各関数（あるいは、上述した他の関数でもよい）によって、各ノードをインデックス化する必要がある。ここでは一般論を失わずに、上記２つの関数に制限して、本発明におけるインデックス化の方法を説明することにする。
【０１０２】
当該インデックス化の方法は、図２Ｂに示す手法のポインタを利用した従来の電子化データアレイ上で動作する。従来のデータアレイは、辞書入力のファイルから開始して、既知の手法で入手される。縦方向のポインタの繋がりは、各辞書入力の入力関係に対応している。一つのノードにおける兄弟の横方向の繋がりは、ラベルタグを分類することにより受け継がれるような、「長子」の順序に基づき行なわれる。
【０１０３】
根自身の前置ランクは０に初期化されると共に、ツリーはその後、この根から年長の子からのポインタに沿って葉に達するまで（従来モードによれば、最も左側にあるもの）、トラバースされる。この葉の後置ランクは０に初期化される。
【０１０４】
図４に示すように、ツリーのノードＳが、増加する「長子」の順序に配列された子Ｓ0，Ｓ1，…Ｓpを有する（すなわち、子は横方向の繋がりに順序付けられる）ものと仮定する。次の関係が続いて起こる。
【０１０５】
【数１６】
2005525625.tif 000019
【０１０６】
但し、Γ(s)は、sから生じたサブツリーのサイズである。前置ランクおよび後置ランクによるインデックス化は、与えられた頂点ｓに対し、ツリーから生じたサブツリーのサイズΓ(s)を戻す関数を再帰呼出しすることで、そのツリーの根から一方向に実行される。この関数は、Ｃ言語の擬似コードにて、次のように記載される。
【０１０７】
【表２】
2005525625.tif 000020
【０１０８】
上記プログラムにおいて、SubTreeSize 変数は、現在の瞬間的な子（offspring）ノード(s)から生じたサブツリーのサイズであり、OffspringSubTreesSize関数は、既に分析された子ノードから生じたサブツリーのサイズの累積値である。
【０１０９】
EncodingTree 関数は、図３Ｂに示す種類のインデックステーブルの形態に、電子化データアレイを直接生成すると共に、メモリ内に保存される。この電子化データアレイが一度生成されれば、初期のポインタアレイはもはや必要なくなり、除外されることとなる。
【０１１０】
以下、議論を単純化するために、構文的ツリーとして体系化された辞書を取り上げると、各々の辞書のデータ入力はツリーの一つの葉に一致する。上述のように、ツリーと同じサイズを有するテーブルの形態をなす電子化データアレイは、本発明の符号化方法によって実現できる。
【０１１１】
この電子化データアレイは、好ましくは与えられたキャラクタの繋がりに基づいて、それに一致する辞書入力を検索するのに利用されるであろう。インデックスは、葉自身の前置ランク（あるいは、葉自身の逆前置ランクが選択されることもある）のような従来の手法で取得される。根から葉に向けてツリーをトラバースするために、本発明における第１の方法をインデックス検索が利用する。
【０１１２】
逆に電子化データアレイは、好ましくは辞書入力のインデックスに基づき、それに一致するキャラクタの繋がり（チェイン）を生成するのに利用される。根から葉に向けてツリーをトラバースするために、本発明における第２の方法を、このキャラクタチェインの生成が利用する。
【０１１３】
最初に、キャラクタチェインＣに対するインデックス検索の場合を考えることにする。ツリーは、タグが連続するＣのキャラクタを保有するアークに沿って、根からトラバースされる。
【０１１４】
好ましくは、根から葉に向けてツリーをトラバースする本発明による第１の方法は、次の手法で動作する。ノードＳの第１の子ｓ０に達すると、次のように初期化される。
【０１１５】
【数１７】
2005525625.tif 000021
【０１１６】
また、第１の子ｓ０から生じるサイズΓ(s0)は、次のようにして計算される。
【０１１７】
【数１８】
2005525625.tif 000022
【０１１８】
但し、LastPostfix は、サブツリーのトラバースが中断された最後の子の後置ランク（言い換えれば、トラバース中に最後に切り取られたサブツリーにおける、根の後置ランク）である。例えば、根にリンクするアークと、図３Ａにおける後置ランク５のノードが、検索するキャラクタを持たないという理由で、当該ノードが保持されなかった場合は、ｌこのノードから生じるサブツリーはトラバースされず、LastPostfix＝５になるであろう。その後、後置ランクが19であるノード、上手く行けば後置ランクが12であるノードに至るまで、トラバースが継続する。このノード（後置ランク19のノードＳの最初の子ｓ２）から生じるサブツリーのサイズは、事実上７である。
【０１１９】
次に、ノードＳの連続するそれぞれの子ｓｉの前置ランクが、次の再帰関係を利用して決定される。
【０１２０】
【数１９】
2005525625.tif 000023
【０１２１】
それぞれの分析された子ｓｉに対して、キャラクタチェインＣにおける進行中のキャラクタ（Character in Progress）ｃが、ノードＳを子ｓｉに連結するアークのタグにより提示されたキャラクタと等しいか否かのテストが行なわれる。もし等しくなければ、次の子ｓｉ＋１と分析を続け、以下同様に進行中のキャラクタが見つかるか、ノードＳの全ての子が分析されるまで、テストが行なわれる。
【０１２２】
与えられたノードＳに到達した時点では、そのノードＳにどの程度の数の子がいるのか予め判らない。この目的を達成するために、好ましくは前記ノードＳから生じたサブツリーのサイズΓ(Ｓ)が、保存されるべきである。次に、子ｓｉを連続的に検討したときに、OffspringSubTreesSize変数は次のように更新されることとなる。
【０１２３】
【数２０】
2005525625.tif 000024
【０１２４】
さらには、OffspringSubTreesSize ＝ Γ(Ｓ)−１のときに、ノードＳにおける全ての子ｓｉが分析されたことを理解するであろう。
【０１２５】
進行中のキャラクタが見つからずに、全ての子が分析された場合、（キャラクタチェインＣの一部を含んでいるかもしれないが、）キャラクタチェインＣは完全には辞書入力に一致しないものとなる。もし、進行中のキャラクタが子ｓｉの一つに見つかったら、Ｓ＝ｓｉとし、次のキャラクタで検索サイクルが再び開始する。この手続きは、ツリーの葉に到達するまで繰り返される。検索されたインデックスは、この葉の前置ランクである。好ましくは、例えば図１の"bar"と"barrister"のような、前置がお互いに共通するワードを検索できるようにするために、それぞれのワードの終わりに、例えばスペース(空白)のキャラクタのような、ワード終了を示すマーカーを加えてもよい。この場合は、ツリーの全ての葉が、ワード終了のマーカーを保有する。
【０１２６】
本手法では、キャラクタの繋がりすなわちAnalyzeWordに基づいて、移動処理（トラバース）の終わりに到達した葉の前置ランクを戻すTreeTraversal 関数を定義してもよい。この関数は、本発明における電子化データアレイを利用する。そのＣ言語の擬似コードは、次のように記載される。
【０１２７】
【表３】
2005525625.tif 000025
【０１２８】
逆に、インデックスＩ（ツリー葉の前置ランクに等しいものと仮定する）から始まる辞書入力に一致して、キャラクタチェインの生成を望むならば、本発明における第２のトラバース方法が利用されるであろう。前記第２の方法は、検索されたインデックスＩに対して子ノードの前置ランクを比較することで、当該子ノードの選択が、それ以降決定されるような第１の方法とは異なる。より詳しくは、Prefix(si+1)Rank＞１なる関係が確認されれば、子ノードｓｉがすぐに選択される。したがって、分析された各ノードの前置ランク値を増加させることで、インデックスＩに近づいてゆく。
【０１２９】
第２の方法では、それぞれのサブツリーのサイズΓ(sｉ)から開始して、与えられたノードＳの子の前置ランクを同一に相互計算する。さらに、与えられたノードＳの子sｉの分析を止める基準は、ノードＳから生じるサイズΓ(Ｓ)と、既に分析された子のサイズΓ(sｉ)の合計に基づいている。
【０１３０】
ここでは、PrefixGuide なるインデックスから開始し、一致するキャラクタチェインを戻す GenerateWord関数を定義してもよい。この GenerateWord 関数も、本発明のツリーにおける電子化データアレイを利用する。そのＣ言語の擬似コードは、次のように記載される。
【０１３１】
【表４】
2005525625.tif 000026
【図面の簡単な説明】
【０１３２】
【図１】構文的ツリーの一例を示す図である。
【図２Ａ】第１のポインタを用いたツリーによる電子化されたデータアレイの図である。
【図２Ｂ】第２のポインタを用いたツリーによる電子化されたデータアレイの図である。
【図３Ａ】本発明の第１実施例におけるツリーの符号化方法をあらわした図である。
【図３Ｂ】図３Ａのツリーによる電子化されたデータアレイの第１変形例を示す図である。
【図３Ｃ】図３Ａのツリーによる電子化されたデータアレイの第２変形例を示す図である。
【図４】前置ランクおよび後置ランクによりインデックス化される前のツリー部分を示す図である。
【図１】
2005525625.tif 000027
【図２Ａ】
2005525625.tif 000028
【図２Ｂ】
2005525625.tif 000029
【図３Ａ】
2005525625.tif 000030
【図３Ｂ】
2005525625.tif 000031
【図３Ｃ】
2005525625.tif 000032
【図４】
2005525625.tif 000033
【国際調査報告】
2005525625.tif 000034
2005525625.tif 000035
2005525625.tif 000036
2005525625.tif 000037
2005525625.tif 000038
2005525625.tif 000039