(57)【要約】【課題】  ＸＭＬ文書データの文法特性を利用して、符号化圧縮率をより向上させた文書データの符号処理方法及びプログラムを提供する。【解決手段】  要素名と属性名とに対応する符号が指定されているＸＭＬの変換シートを用いて、ＸＭＬ原文書データを符号化するために、最初に、原文書データのタグ単位で、要素名及び属性名と、該属性名に対応する値とを検出する。次に、要素名から変換シートを用いて導出された符号と、属性名の存在の有無をビットで表した符号とを組み合わせた第１の符号を構造テーブルに順に記録する。次に、存在する属性名に対応する値を出現頻度に応じて符号化した第２の符号を、第１の符号を記録した構造テーブルのエントリにリンクした、値テーブルのエントリに記録する。更に、第１のステップから第３のステップを繰り返すことによって生成された構造テーブル及び値テーブルを符号データとする。【選択図】  図２
2005215951.tif 000002
【特許請求の範囲】
【請求項１】
拡張可能なテキスト形式の構造型記述言語で記載された原文書データを符号化する文書データ符号化方法において、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートと、
要素毎の構造符号をエントリにエントリに記録する構造テーブルと、
前記構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録する値テーブルと
を用いて、前記原文書データのタグ単位順に、
要素名と、子要素又は要素値の有無と、属性名の有無と、存在する属性値又は要素値とを検出する第１のステップと、
前記要素名から前記変換シートを用いて導出された符号と、該要素名の子要素又は要素値の有無を表す符号と、前記属性名の有無を表す符号とを組み合わせた前記構造符号を、前記構造テーブルのエントリに順に記録する第２のステップと、
存在する前記属性値又は要素値に対する符号を、前記値テーブルに記録する第３のステップと
を有し、前記第１のステップから前記第３のステップを繰り返すことによって生成された前記構造テーブル及び前記値テーブルを符号データとすることを特徴とする文書データの符号化方法。
【請求項２】
出現頻度の多い前記属性値又は要素値から順に、短い符号を割り当てた割当テーブルを更に有し、
前記第３のステップにおける前記属性値又は要素値に対する符号は、前記値割当テーブルを用いて導出されたものであり、
前記値割当テーブルも前記符号データの一部とすることを特徴とする請求項１に記載の方法。
【請求項３】
前記変換シートは、前記属性値又は要素値に対応するデータ型情報を規定しており、
前記値割当テーブルは、前記データ型情報に応じて複数存在しており、
前記第３のステップにおける前記属性値又は要素値に対する符号は、前記属性値又は要素値における前記データ型情報に対応した値割当テーブルを用いて導出されたものであることを特徴とする請求項２に記載の方法。
【請求項４】
前記構造テーブルは、出現頻度の多い前記構造符号から順に、短い符号をツリー符号として割り当てており、
前記ツリー符号を、前記原文書データの要素の出現順に並べたツリーテーブルを更に有しており、
前記ツリーテーブルも前記符号データの一部とすることを特徴とする請求項１から３のいずれか１項に記載の方法。
【請求項５】
前記属性名の有無を表す符号は、前記変換シートにおける当該要素名に指定可能な属性名順に、各属性を１ビットに割り当てたビット列によって該属性の有無を指定することを特徴とする請求項１から４のいずれか１項に記載の方法。
【請求項６】
出現頻度の多い前記属性名の有無を表す符号から順に、短い符号を割り当てた属性テーブルを更に有し、
前記第３のステップは、前記属性テーブルを用いて前記属性名の有無を表す符号を導出し、
前記属性テーブルも前記符号データの一部とすることを特徴とする請求項５に記載の方法。
【請求項７】
前記変換シートには、前記属性値又は要素値に対応する選択型情報を規定することができ、
前記第３のステップにおける前記属性値又は要素値に対する符号は、選択数に応じた最小ビット数で表されたものであることを特徴とする請求項１から６のいずれか１項に記載の方法。
【請求項８】
前記変換シートには、前記属性値又は要素値が複数の群からなる群構造型情報を規定することができ、
前記第３のステップにおける前記属性値又は要素値に対する符号は、前記群単位に、先の群について符号化した後で、後の群について先の群に対する差分値のみを符号化することを特徴とする請求項１から７のいずれか１項に記載の方法。
【請求項９】
前記変換シートには、前記属性値又は要素値を複数の群として表すためにセパレータを規定することができ、
前記第３のステップにおける前記属性値又は要素値に対する符号は、前記セパレータによって群単位に区分されることを特徴とする請求項８に記載の方法。
【請求項１０】
前記変換シートには、前記属性値又は要素値に対して固定値部分を規定することができ、
前記第３のステップにおける前記属性値又は要素値に対する符号は、前記固定値部分は省略されることを特徴とする請求項１から９のいずれか１項に記載の方法。
【請求項１１】
拡張可能なテキスト形式の構造型記述言語で記載された原文書データの符号データを復号化する文書データ復号化方法において、
前記符号データは、要素毎の構造符号をエントリに記録した構造テーブルと、該構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録した値テーブルとから構成されており、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートを用いて、
前記構造テーブルから対応する構造符号を切り出す第１のステップと、
前記構造符号に対応する値テーブルのエントリを検出し、前記構造符号から、前記変換シートを用いて、要素名と、子要素又は要素値の有無と、存在する属性名とを特定する第２のステップと、
前記値テーブルの対応するエントリの値符号から、存在する属性値又は要素値を特定する第３のステップと
を有し、前記第１のステップから前記第３のステップを繰り返すことによって原文書データに復号することを特徴とする文書データの復号化方法。
【請求項１２】
前記符号データは、出現頻度の多い前記属性値又は要素値から順に、短い符号を割り当てた値割当テーブルを更に含んでおり、
前記第３のステップにおける前記属性値又は要素値は、前記値割当テーブルを用いて導出されたものであることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記変換シートは、前記属性値又は要素値に対応するデータ型情報を規定しており、
前記値割当テーブルは、前記データ型情報に応じて複数存在しており、
前記第３のステップにおける前記属性値又は要素値は、前記属性値又は要素値における前記データ型情報に対応した値割当テーブルを用いて導出されたものであることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記符号データは、前記構造テーブルを、出現頻度の多い前記構造符号から順に、短い符号をツリー符号として割り当てており、該ツリー符号を、前記原文書データの要素の出現順に並べたツリーテーブルを更に含んでいることを特徴とする請求項１１から１３のいずれか１項に記載の方法。
【請求項１５】
前記属性名の有無を表す符号は、前記変換シートにおける当該要素名に指定可能な属性名順に、各属性を１ビットに割り当てたビット列によって該属性の有無が指定されていることを特徴とする請求項１１から１４のいずれか１項に記載の方法。
【請求項１６】
前記符号テーブルは、出現頻度の多い前記属性名の有無を表す符号から順に、短い符号を割り当てた属性テーブルを更に含んでおり、
前記第３のステップは、前記属性テーブルを用いて前記属性名の有無を導出することを特徴とする請求項１５に記載の方法。
【請求項１７】
前記変換シートには、前記属性値又は要素値に対応する選択型情報を規定することができ、
前記第３のステップにおける前記属性値又は要素値に対する符号は、選択数に応じた最小ビット数で表されたものであることを特徴とする請求項１１から１６のいずれか１項に記載の方法。
【請求項１８】
前記変換シートには、前記属性値又は要素値が複数の群からなる群構造型情報を規定することができ、
前記第３のステップにおける前記属性値又は要素値の値符号は、前記群単位に、先の群について符号化した後で、後の群について先の群に対する差分値のみを符号化されたものであり、前記先の群について復号化した後で、前記後の群を復号化した値に前記差分値を加算して導出することを特徴とする請求項１１から１７のいずれか１項に記載の方法。
【請求項１９】
前記変換シートには、前記属性値又は要素値を複数の群として表すためにセパレータを規定することができ、
前記第３のステップにおける前記属性値又は要素値の値符号は、前記セパレータによって群単位に区分されることを特徴とする請求項１８に記載の方法。
【請求項２０】
前記変換シートには、前記属性値又は要素値に対して固定値部分を規定することができ、
前記第３のステップにおける前記属性値又は要素値の値符号は、前記変換シートを用いて、省略された前記固定値部分を復元して導出することを特徴とする請求項１１から１９のいずれか１項に記載の方法。
【請求項２１】
拡張可能なテキスト形式の構造型記述言語で記載された原文書データを符号化する文書データ符号化プログラムにおいて、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートと、
要素毎の構造符号をエントリにエントリに記録する構造テーブルと、
前記構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録する値テーブルと
を用いて、前記原文書データのタグ単位順に、
要素名と、子要素又は要素値の有無と、属性名の有無と、存在する属性値又は要素値とを検出する第１のステップと、
前記要素名から前記変換シートを用いて導出された符号と、該要素名の子要素又は要素値の有無を表す符号と、前記属性名の有無を表す符号とを組み合わせた前記構造符号を、前記構造テーブルのエントリに順に記録する第２のステップと、
存在する前記属性値又は要素値に対する符号を、前記値テーブルに記録する第３のステップと
して実行し、前記第１のステップから前記第３のステップを繰り返すことによって生成された前記構造テーブル及び前記値テーブルを符号データとすることを特徴とする文書データの符号化プログラム。
【請求項２２】
拡張可能なテキスト形式の構造型記述言語で記載された原文書データの符号データを復号化する文書データ復号化プログラムにおいて、
前記符号データは、要素毎の構造符号をエントリに記録した構造テーブルと、該構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録した値テーブルとから構成されており、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートを用いて、
前記構造テーブルから対応する構造符号を切り出す第１のステップと、
前記構造符号に対応する値テーブルのエントリを検出し、前記構造符号から、前記変換シートを用いて、要素名と、子要素又は要素値の有無と、存在する属性名とを特定する第２のステップと、
前記値テーブルの対応するエントリの値符号から、存在する属性値又は要素値を特定する第３のステップと
して実行し、前記第１のステップから前記第３のステップを繰り返すことによって原文書データに復号することを特徴とする文書データの復号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、拡張可能なテキスト形式の構造型記述言語で記載された原文書データを符号化又は復号化する文書データ符号化又は復号化方法及びそのプログラムに関する。
【背景技術】
【０００２】
従来、伝送すべきデータ量を削減するために、文書データを符号化及び復号化する方法がある。この方法を実現するには、送信装置及び受信装置はそれぞれ、変換テーブルを所持する必要がある。変換テーブルは、構造型記述言語と符号データとを１対１に対応付けたものである。送信装置は、変換テーブルに基づいて文書データを符号データに符号化する。一方、受信装置は、変換テーブルに基づいて符号データを文書データに復号化する。このような方法は、インターネットにおけるセキュリティの観点からも有効である。変換テーブルを有さないクライアントは、符号データを復号することができないからである。
【０００３】
具体的には、ＸＭＬ(eXtensible Markup Language)又はＳＧＭＬ(Standard Generalized Markup Language)準拠の符号化テーブルを用いて、ＸＭＬ／ＳＧＭＬ文書データの符号化を行う方法がある（例えば特許文献１及び２参照）。この方法は、ＸＭＬ／ＳＧＭＬ形式の構造型記述言語で記載された変換テーブルに、要素名、要素値、属性名及び属性値の項目に符号長及び符号を定義し、第１の要素名に対する第２の要素名が親子関係を示す符号長及び符号とを定義したものである。この変換テーブルを用いて文書データを符号化することにより、データ伝送量を削減することができる。また、復号側装置は、符号データからの元の文書データを復元させることないために、パーサも必要としない。
【０００４】
図１は、符号化サーバを含むシステム構成図である。
【０００５】
サーバ４は、ＸＭＬ形式の文書データを符号化サーバ６へ送信する。符号化サーバ６は、変換テーブルサーバ７から受信した変換テーブルを用いて、文書データを符号化する。その符号データは、クライアント５へ送信される。クライアント５は、変換テーブルサーバ７から受信した変換テーブルを用いて、文書処理を行う。図１によれば、ＸＭＬ形式の文書データを送信する既存のサーバに変更を加えることなく、符号化サーバをプロキシサーバとして利用することができる。
【０００６】
【特許文献１】特開２００２−２５９１９４号公報
【非特許文献１】小林、高木、村松、馬場、松本、井ノ上「ＸＭＬ文書汎用符号化方式「ｘｅｕｓ」、信学技報ＤＥ２００１−９、ｐｐ．６５〜７２
【非特許文献２】小林、松本、井ノ上「汎用ＸＭＬ文書符号化方式「ＸＥＵＳ」の性能評価」、ＦＩＴ（情報科学技術フォーラム）、２００３、ＬＥ００８、ｐｐ．９９〜１００
【発明の開示】
【発明が解決しようとする課題】
【０００７】
このような従来技術に対して、符号圧縮率をより向上させることが問題となってきた。従来技術は、ＸＭＬ文書データについてタグ単位に順列的に符号化をしており、ＸＭＬ文法の性質を利用したものではなかった。ＸＭＬには、１要素に同じ名称の属性は１度しか記述できないという条件、符号化対象文書の論理構造の相関、及び、符号化対象文書の各値の特性のようなものを十分に利用した符号化方法ではなかった。
【０００８】
通常のＸＭＬ文書データにおいては、論理構造部分は極めて同じ又は近似したタグが連続する場合が多いにもかかわらず、タグ単位に一連に符号化するために、結局のところ符号化されたビット列自体にも同じビット列が連続する場合が多かった。
【０００９】
従って、本発明は、ＸＭＬ文書データの文法特性を利用して、符号化圧縮率をより向上させた文書データの符号処理方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明における符号化方法は、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートと、
要素毎の構造符号をエントリにエントリに記録する構造テーブルと、
構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録する値テーブルと
を用いて、原文書データのタグ単位順に、
要素名と、子要素又は要素値の有無と、属性名の有無と、存在する属性値又は要素値とを検出する第１のステップと、
要素名から変換シートを用いて導出された符号と、該要素名の子要素又は要素値の有無を表す符号と、属性名の有無を表す符号とを組み合わせた構造符号を、構造テーブルのエントリに順に記録する第２のステップと、
存在する属性値又は要素値に対する符号を、値テーブルに記録する第３のステップと
を有し、第１のステップから第３のステップを繰り返すことによって生成された構造テーブル及び値テーブルを符号データとすることを特徴とする。
【００１１】
本発明の符号化方法における他の実施形態によれば、出現頻度の多い属性値又は要素値から順に、短い符号を割り当てた値割当テーブルを更に有し、第３のステップにおける属性値又は要素値に対する符号は、値割当テーブルを用いて導出されたものであり、値割当テーブルも符号データの一部とすることも好ましい。
【００１２】
また、本発明の符号化方法における他の実施形態によれば、変換シートは、属性値又は要素値に対応するデータ型情報を規定しており、値割当テーブルは、データ型情報に応じて複数存在しており、第３のステップにおける属性値又は要素値に対する符号は、属性値又は要素値におけるデータ型情報に対応した値割当テーブルを用いて導出されたものであることも好ましい。
【００１３】
更に、本発明の符号化方法における他の実施形態によれば、構造テーブルは、出現頻度の多い構造符号から順に、短い符号をツリー符号として割り当てており、ツリー符号を、原文書データの要素の出現順に並べたツリーテーブルを更に有しており、ツリーテーブルも符号データの一部とすることも好ましい。
【００１４】
更に、本発明の符号化方法における他の実施形態によれば、属性名の有無を表す符号は、変換シートにおける当該要素名に指定可能な属性名順に、各属性を１ビットに割り当てたビット列によって該属性の有無を指定することも好ましい。
【００１５】
更に、本発明の符号化方法における他の実施形態によれば、出現頻度の多い属性名の有無を表す符号から順に、短い符号を割り当てた属性テーブルを更に有し、第３のステップは、属性テーブルを用いて属性名の有無を表す符号を導出し、属性テーブルも符号データの一部とすることも好ましい。
【００１６】
更に、本発明の符号化方法における他の実施形態によれば、変換シートには、属性値又は要素値に対応する選択型情報を規定することができ、第３のステップにおける属性値又は要素値に対する符号は、選択数に応じた最小ビット数で表されたものであることも好ましい。
【００１７】
更に、本発明の符号化方法における他の実施形態によれば、変換シートには、属性値又は要素値が複数の群からなる群構造型情報を規定することができ、第３のステップにおける属性値又は要素値に対する符号は、群単位に、先の群について符号化した後で、後の群について先の群に対する差分値のみを符号化することも好ましい。
【００１８】
更に、本発明の符号化方法における他の実施形態によれば、変換シートには、属性値又は要素値を複数の群として表すためにセパレータを規定することができ、第３のステップにおける属性値又は要素値に対する符号は、セパレータによって群単位に区分されることも好ましい。
【００１９】
更に、本発明の符号化方法における他の実施形態によれば、変換シートには、属性値又は要素値に対して固定値部分を規定することができ、第３のステップにおける属性値又は要素値に対する符号は、固定値部分は省略されることも好ましい。
【００２０】
本発明における復号化方法は、
符号データは、要素毎の構造符号をエントリに記録した構造テーブルと、該構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録した値テーブルとから構成されており、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートを用いて、
構造テーブルから対応する構造符号を切り出す第１のステップと、
構造符号に対応する値テーブルのエントリを検出し、構造符号から、変換シートを用いて、要素名と、子要素又は要素値の有無と、存在する属性名とを特定する第２のステップと、
値テーブルの対応するエントリの値符号から、存在する属性値又は要素値を特定する第３のステップと
を有し、第１のステップから第３のステップを繰り返すことによって原文書データに復号することを特徴とする。
【００２１】
本発明の復号化方法における他の実施形態によれば、符号データは、出現頻度の多い属性値又は要素値から順に、短い符号を割り当てた値割当テーブルを更に含んでおり、第３のステップにおける属性値又は要素値は、値割当テーブルを用いて導出されたものであることも好ましい。
【００２２】
また、本発明の復号化方法における他の実施形態によれば、変換シートは、属性値又は要素値に対応するデータ型情報を規定しており、値割当テーブルは、データ型情報に応じて複数存在しており、第３のステップにおける属性値又は要素値は、属性値又は要素値におけるデータ型情報に対応した値割当テーブルを用いて導出されたものであることも好ましい。
【００２３】
更に、本発明の復号化方法における他の実施形態によれば、符号データは、構造テーブルを、出現頻度の多い構造符号から順に、短い符号をツリー符号として割り当てており、該ツリー符号を、原文書データの要素の出現順に並べたツリーテーブルを更に含んでいることも好ましい。
【００２４】
更に、本発明の復号化方法における他の実施形態によれば、属性名の有無を表す符号は、変換シートにおける当該要素名に指定可能な属性名順に、各属性を１ビットに割り当てたビット列によって該属性の有無が指定されていることも好ましい。
【００２５】
更に、本発明の復号化方法における他の実施形態によれば、符号テーブルは、出現頻度の多い属性名の有無を表す符号から順に、短い符号を割り当てた属性テーブルを更に含んでおり、第３のステップは、属性テーブルを用いて属性名の有無を導出することも好ましい。
【００２６】
更に、本発明の復号化方法における他の実施形態によれば、変換シートには、属性値又は要素値に対応する選択型情報を規定することができ、第３のステップにおける属性値又は要素値に対する符号は、選択数に応じた最小ビット数で表されたものであることも好ましい。
【００２７】
更に、本発明の復号化方法における他の実施形態によれば、変換シートには、属性値又は要素値が複数の群からなる群構造型情報を規定することができ、第３のステップにおける属性値又は要素値の値符号は、群単位に、先の群について符号化した後で、後の群について先の群に対する差分値のみを符号化されたものであり、先の群について復号化した後で、後の群を復号化した値に差分値を加算して導出することも好ましい。
【００２８】
更に、本発明の復号化方法における他の実施形態によれば、変換シートには、属性値又は要素値を複数の群として表すためにセパレータを規定することができ、第３のステップにおける属性値又は要素値の値符号は、セパレータによって群単位に区分されることも好ましい。
【００２９】
更に、本発明の復号化方法における他の実施形態によれば、変換シートには、属性値又は要素値に対して固定値部分を規定することができ、第３のステップにおける属性値又は要素値の値符号は、変換シートを用いて、省略された固定値部分を復元して導出することも好ましい。
【００３０】
本発明における符号化プログラムは、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートと、
要素毎の構造符号をエントリにエントリに記録する構造テーブルと、
構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録する値テーブルと
を用いて、原文書データのタグ単位順に、
要素名と、子要素又は要素値の有無と、属性名の有無と、存在する属性値又は要素値とを検出する第１のステップと、
要素名から変換シートを用いて導出された符号と、該要素名の子要素又は要素値の有無を表す符号と、属性名の有無を表す符号とを組み合わせた構造符号を、構造テーブルのエントリに順に記録する第２のステップと、
存在する属性値又は要素値に対する符号を、値テーブルに記録する第３のステップと
して実行し、第１のステップから第３のステップを繰り返すことによって生成された構造テーブル及び値テーブルを符号データとすることを特徴とする。
【００３１】
本発明における復号化プログラムは、
符号データは、要素毎の構造符号をエントリに記録した構造テーブルと、該構造テーブルのエントリに対応して、属性値又は要素値の符号をエントリに記録した値テーブルとから構成されており、
拡張可能なテキスト形式の構造型記述言語で記載され、要素名と、該要素名に指定可能な属性名とに対応する符号が指定されている変換シートを用いて、
構造テーブルから対応する構造符号を切り出す第１のステップと、
構造符号に対応する値テーブルのエントリを検出し、構造符号から、変換シートを用いて、要素名と、子要素又は要素値の有無と、存在する属性名とを特定する第２のステップと、
値テーブルの対応するエントリの値符号から、存在する属性値又は要素値を特定する第３のステップと
して実行し、第１のステップから第３のステップを繰り返すことによって原文書データに復号することを特徴とする。
【発明の効果】
【００３２】
本発明における文書データの符号処理方法及びプログラムによれば、符号化圧縮率をより向上させることができる。特に、文書データの論理構造部分と値部分とを混在して符号化していたものを、各々別々に符号化するために、それぞれの部分の特性に最適な符号化を実現することができる。
【００３３】
特に、論理構造の出現頻度と値の出願頻度との偏りを用いて符号化することができるため、従来の方法と比較し、およそ２０％の符号量を低減することができる。このような符号化方法は、ＸＭＬ及びＳＧＭＬ準拠の全ての文書データの符号化に適用でき、特に、地図コンテンツの座標値の羅列のように、座標値間の変化量が少なく且つ連続した同一又は近似したタグが連続するコンテンツに対して、極めて符号量の削減効果が大きい。
【００３４】
また、このように符号量を削減できることは、携帯電話機のような狭い帯域の無線リンクに接続された端末にとっては極めて有効である。このような符号化方法は、パース処理も必要としないために、携帯電話機のようなＣＰＵ能力の低い端末には極めて有効である。
【発明を実施するための最良の形態】
【００３５】
以下では、図面を用いて、本発明を実施するための最良の形態について詳述する。
【００３６】
図２は、本発明における文書データの符号処理方法である。
【００３７】
図２によれば、文書データ１２は、複数の文書データ１２０及び１２１によって拡張されている。一方、変換テーブル１１も、拡張された文書データに対応して、複数の変換テーブル１１０及び１１１のリンク情報を定義している。これにより、XML形式の文書データ１２は、変換テーブル１１を用いて符号化１０される。
【００３８】
また、図２によれば、符号データは、変換テーブル２１を用いて、直接的に文書処理３０され、ブラウザ２４に表示される。本発明によれば、符号データには、要素の論理構造も含まれる。従って、文書データに復号する必要もなく、更にパーサ２３によって論理構造を解析する必要もない。
【００３９】
図３は、文書データのサンプルである。以下では、この文書データを例にとって説明する。
【００４０】
図４は、図３の文書データに対応した種々の符号化テーブルである。
【００４１】
図４によれば、文書データの論理構造を示すために、ツリーテーブルと、構造テーブルと、属性テーブルとを有し、値を示すために値テーブルとを有する。このように、本発明の特徴は、論理構造を示す部分と、値の部分とを別々に符号化することに特徴ある。
【００４２】
ここで、ツリーテーブルと構造テーブルとをリンクさせる符号と、属性有無の符号とは、ハフマン符号で表されている。ハフマン符号とは、出現頻度が高い項目には短い符号を割当て、そうでない項目には長い符号を割り当てるという方法である。このような可変長の符号化を効率的に行なうことで、個々の情報に一定サイズの符号を割り当てる方法と比較して、効率の良いデータ圧縮が実現できる。
【００４３】
図５は、図３の文書データに対応したハフマンテーブル（値割当テーブル）である。
【００４４】
図５によれば、整数ハフマンテーブルと、文字列ハフマンテーブルと、占有ビット長テーブルとを有する。図４と同様に、これらテーブルも、ハフマン符号によって割当てられている。従って、各テーブルは出現頻度によりソートされたものであり、出現頻度の多いものから順に、短い符号が割り当てられる。値の符号には、このインデックス符号を用いる。このインデックス符号の割り当て方法にハフマン符号化のような出現頻度による可変長符号化法を用いることにより、符号量低減を実現できる。従来技術によれば、値の符号化は、符号化ルールに定義された符号により符号化していたが、本発明によれば、各データ型毎に、値の出現頻度テーブルを作成し、各値の出現頻度により動的に符号長を算出して、符号化を行う。
【００４５】
図６Ａ及び図６Ｂは、変換シートである。
【００４６】
変換シートは、文書データに依存することなく、符号化又は復号化する装置が予め保有しているものであって、要素名又は属性名と符号との対応関係を規定したものである。
【００４７】
図７は、図３の文書データにおける符号化の過程を表す説明図である。以下では、図７に基づいて、各テーブルを参照しながら説明する。
【００４８】
[T1]<svg>
->"101"
最初に"svg"について、変換シート（図６Ａ）の[x1]により符号"00"を導出する。このとき、svgの子要素は有るので"1"とし、属性は無いので"0"とする。
"svg"について、"0010"を構造テーブルに記録し（Ｆ）、その値は無いので、対応する値テーブルには記録しない。また、構造テーブルのそのエントリＦには、符号"101"が割り当てられている。この符号"101"は、ツリーテーブルに"svg"と対応させて記録する。
【００４９】
[T2]<g id="300" stroke="#1e90ff" stroke-width="1" fill="none">
->"011","100,1110,111,00,0"
"g"について、svgの子要素として、変換シート[x3]により符号"01"を導出する。このとき、gの子要素は有るので"1"とする。また、変換シート[x7]〜[x10]により、属性が４個あることが把握でき、更にそれら４個全ての属性が[T2]には含まれるので、符号"1111"とする。それぞれのビットがid,stroke,stroke-width,fillを表す。ＸＭＬ仕様上、１要素内で２度同じ属性を記述することはできず、各属性について存在するか否かのどちらかであるために、このような記載が可能となる。ここで、属性テーブルを参照すると、"1111"は、符号"01"に対応している。従って、"g"は全体で"01101"に符号化できる。"g"について、"01101"を構造テーブルに記録する（Ｄ）。ここで、この構造テーブルのそのエントリDには"011"が割り当てられている。この符号"011"は、ツリーテーブルに"g"と対応させて記録する。
【００５０】
本発明によれば、従来のように"g"要素＝"010101"、"id"要素＝"101010"というように、各要素名及び属性名に対して符号を割り当てるのではなく、"g"は、"
id, stroke, stroke-width, fill"属性の有無に４ビット割り当てることにより、その値のみを符号化すればよい。
【００５１】
"id"について、属性値"300"は、整数ハフマンテーブルによって"300"->"1110"とし、そのサイズ４ビットを占有ビット長テーブルによって符号"100"とする。
"stroke"について、属性値"#1e90ff"は、文字列ハフマンテーブルにより、符号"111"を導出する。
"stroke-width"について、属性値"1"は、整数ハフマンテーブルにより符号"00"を導出する。
"fill"について、属性値"none"は、変換シート[x11]によれば選択型であるので、符号"0"を導出する。
最後に、"g"の値符号"100,1110,111,00,0"は、対応する値テーブルのエントリＤに記録される。
【００５２】
ここで、変換シート[x11][x12]によれば、"fill"には、選択型というデータ型が指定されている。従来技術によれば、値のとりえる候補（選択肢）が限られていた場合でも、値を、数値又は文字のようなデータ型により符号化する必要があった。本発明によれば、g要素のfill属性の属性値は、noneか７文字の文字列しかないので、値がnoneの場合は符号"0"のみで済む。ASCIIだと4byte必要なところを1bitで符号化できる。
これにより、選択肢に割り当てたインデックス符号で符号化することができ、符号量低減が実現できる。
【００５３】
[T3]<polyline points="88,99 96,102 108,109"/>
->"000","11111,11110,0100,0101,0110,0111"
"polyline"について、"g"の子要素として、変換シート[x14]により符号"10"を導出する。このとき、polylineの子要素は無いので"0"とする。また、変換シート[x17]〜[x21]により、属性が５個あることが把握でき、更に、それらpointsの属性のみが[T2]に含まれているので、符号"10000"とする。それぞれのビットが"points,stroke,stroke-width,fill,stroke-dasharray"を表す。この符号"10000"から、属性テーブルを用いて符号"100"が導出される。これらのビット列の"100100"は、構造テーブル（Ａ）に記録される。構造テーブルのこのエントリＡには符号"000"が割り当てられており、その符号"000"を"polyline"と対応させてツリーテーブルに記録する。
【００５４】
"points"の値は、座標"coordinates"型であることが把握できる。従って、"=88,99 96,102 108,109"は、(88,99)(96,102)(108,109)の群からなる座標であることが把握できる。ここで、"88,99 96,102 108,109"をそのまま６つの数値群として符号化するのではなく、データ型に座標値型を用いることにより、先の座標値群からの差分値、即ち" 88,99,+8,+3,+12,+7"と変換して符号化する。整数ハフマンテーブルを用いて、最初の値"88"->"11111", "99"->"11110"と符号化できる。次に、"96,102"は、先の座標値群の差分値"+8,+3"と表され、整数ハフマンテーブルを用いて"0100,0101"と符号化できる。次に、"108,109"は、先の座標値群の差分値"+12,+7"と表され、整数ハフマンテーブルを用いて"0110,0111"と符号化できる。このような符号化は、座標間の変化量が少ないデータ（例えば地図データ）に極めて有効な符号化である。最後に、"polyline"の値符号"11111,11110,0100,0101,0110,0111"は、対応する値テーブルのエントリＡに記録される。
【００５５】
数値と数値と区切り（セパレータ）は、通常、スペース" "が記載されるが、変換シート[x17]によれば、カンマ","を定義している。値によってはそのセパレータも異なる。このような場合、従来技術のように文字列として符号化するのではなく、符号化規則としてその属性におけるセパレータを定義し、それによって値を分割して符号化することもできる。ここでは、"points"の値については、X,Y座標が","で区切られ、更にその対が" "で区切られている。このように、値の属性によって複数のセパレータを組み合わせることによって、高い符号化効率を実現することができる。
【００５６】
[T4]</g>
->"011"
"/"の論理構造符号"011"を、論理構造テーブルに記録する。
【００５７】
[T5]<g id="500" fill="#ff4500">
->"100","01,111,1,111"
"g"について、svgの子要素として、変換シート[x3]により、符号"01"を導出する。このとき、gの子要素は有るので"1"とする。また、変換シート[x7]〜[x10]により、属性が４個あることが把握でき、更に、id及びfillの属性だけが[T5]には含まれるので、符号"1001"とする。それぞれのビットが"id,stroke,stroke-width,fill"を表す。ここで、属性テーブルを参照すると、"1001"は、符号"11"に対応している。従って、"g"は全体で"01111"に符号化でき、その"01111"を構造テーブル（Ｅ）に記録する。ここで、この構造テーブルのそのエントリＥには"100"が割り当てられている。この符号"100"は、ツリーテーブルに"g"と対応させて記録する。
【００５８】
"id"について、属性値"500"は、整数ハフマンテーブルから"500"->"111"とし、そのサイズ３ビットを符号"01"とする。
"fill"について、属性値"#ff4500"について、"fill"が選択型で設定されているので、７文字"#ff4500"の場合、選択肢符号"1"の直後に、ASCII型で"#ff4500"を符号化する。このとき、"#ff4500"は、文字列ハフマンテーブルにより符号"111"が割り当てられている。
最後に、"g"の値符号"01,111,1,111"は、対応する値テーブルのエントリＥに記録される。
【００５９】
[T6]<text x="64" y="22">ABC</text>
->"001","110,01,110,110"
->"010","1000,1001,1010"
"text"について、gの子要素として、変換シート[x15]により符号"11"を導出する。このとき、textの子要素は無いので"0"とする。また、変換シート[x23]〜[x26]により、属性が４個あることが把握でき、更にx及びyの属性だけが[T6]には含まれるので、符号"1001"とする。それぞれのビットがid,stroke,stroke-width,fillを表す。ここで、属性テーブルを参照すると、"1001"は、符号"11"に対応している。従って、"text"は全体で"11011"に符号化でき、その"11011"を構造テーブル（Ｂ）に記録する。ここで、この構造テーブルのそのエントリＢには"001"が割り当てられている。この符号"001"は、ツリーテーブルに"text"と対応させて記録する。
【００６０】
"x"について、属性値"64"は、整数ハフマンテーブルにより符号"01"を導出し、そのサイズ２ビットを符号"110"とする。
"y"について、属性値"22"は、整数ハフマンテーブルにより符号"110"とし、そのサイズ３ビットを符号"110"とする。
最後に、"text"の値符号"110,01,110,110"は、対応する値テーブルのエントリＢに記録される。
【００６１】
text要素の要素値"ABC"について、このノードは要素値であるので、要素名、その子要素若しくはその要素値、又は属性も存在しない。従って、要素値"ABC"は、"NULL,0,0"に符号化でき、これを構造テーブル（Ｃ）に記録する。ここで、この構造テーブルのそのエントリ（Ｃ）には"010"が割り当てられている。この符号"010"は、ツリーテーブルに"[value]"と対応させて記録する。
【００６２】
更に、"ABC"は、文字列ハフマンテーブルから符号"1000,1001,1010"と表される。構造テーブルに対応してツリーテーブル"010"を記録する。その構造テーブル（Ｃ）に対応する値テーブルのエントリＣに符号"1000,1001,1010"を記録する。
【００６３】
</text>
->"011"
"/"の論理構造である符号"011"を、ツリーテーブルに記録する。
【００６４】
[T7]</g>
->"011"
"/"の論理構造符号"011"を、ツリーテーブルに記録する。
【００６５】
[T8]</svg>
->"011"
"/"の論理構造符号"011"を、ツリーテーブルに記録する。
【００６６】
本発明におけるその他のその他の発明の機能について説明する。
【００６７】
第１に、暗示的なセパレータについて説明する。例えば"100円"という値の場合、「数値->文字」というようにデータ型が変化した場合、"100"と"円"の間に存在するセパレータを暗示的なセパレータと定義づけている。変換シート[x11][x12]によって選択型について説明したが、例えば"100円"という値を符号化する場合、以下のような変換シートを用意することができる。
<attr name="price" explicit_separator="true" >
<value>
<number data="UI" qt="1"/>
<char data="Shift_JIS" length="implied"/>
<choice>
<list code="0">円</list>
<list code="1">ドル</list>
</choice>
</value>
</attr>
【００６８】
第２に、必ず文字列しか規定されない場合について説明する。例えば、サンプル文書に以下の記載があったとする。
<value>
http://www.kddi.com/
</value>
【００６９】
この場合、http://www.kddi.com/は、文字列以外あり得ないために、文字列ハフマンテーブルに定義することにより、極めて少ない符号に変換することができる。特に、http://と最後の"/"は、固定化されたものであるために、これらの部分の符号化も省略することができる。この場合の変換シートには、以下のような規則を記載することができる。
<value>
http://
<char data="ASCII" length="implied"/>
<value>
【００７０】
図８は、本発明における符号化処理のフローチャートである。
【００７１】
ＸＭＬの文書データが入力されたとする。
（Ｓ８０１）文書データの最初のタグから順にＳ８１２との間で、要素毎に全ての要素及び要素値について符号化する。
（Ｓ８０２）最初に、要素値か否かを判定する。
（Ｓ８０３）要素値でなければ、変換シートを用いて、当該タグの要素の符号を導出する。
（Ｓ８０４）次に、その要素に子要素又は要素値が有るか否かについて、１ビットで符号化する。
（Ｓ８０５）ＸＭＬの特性によって、変換シートによれば、その要素には属性が何個あって、その順序も予め規定されている。従って、その属性の個数のビット列を配し、その属性毎にその有無をビットで表現する。
（Ｓ８０６）Ｓ８０３〜Ｓ８０５によって得られた一連の符号列は、構造用符号として、構造テーブルに記録される。このとき、構造テーブルにおいては、出現頻度によってハフマン符号化されている。従って、出現頻度の多い構造用符号は短い符号で表され、出現頻度の少ない構造用符号は長い符号で表される。
（Ｓ８０７）構造テーブルによって指定された符号は、ツリーテーブルにその要素と共に記録される。
（Ｓ８０８）次に、その要素について属性有りか否かを判定する。属性が無ければ、次に要素の処理を行う（Ｓ８０１）。
（Ｓ８０９）属性が有る場合、文書データの最初の属性から順にＳ８１１との間で、属性毎に全ての属性について符号化する。
（Ｓ８１０）属性の存在は、既に属性ビットで把握できているので、その属性の値のみを符号化すれば足りる。ここで、占有ビット長テーブルと、整数ハフマンテーブルと、文字列ハフマンテーブルとを用いる。属性の型は、変換シートによって既に把握できているので、そのデータ型によってテーブルを選択することが可能である。また、ここでも、ハフマン符号化されているので、出現頻度の多い構造用符号は短い符号で表され、出現頻度の少ない構造用符号は長い符号で表される。
（Ｓ８１１）Ｓ８０８との間で、全ての属性について符号化するまで繰り返す。
（Ｓ８１２）Ｓ８０２において要素値であると判断されたならば、「要素名なし、子要素なし、属性なし」の符号列が、構造用符号として、構造テーブルに記録される。前述したように、構造テーブルにおいては、出現頻度によってハフマン符号化されている。
（Ｓ８１３）構造テーブルによって指定された符号は、ツリーテーブルにその要素と共に記録される。
（Ｓ８１４）要素値が、占有ビット長テーブルと、整数ハフマンテーブルと、文字列ハフマンテーブルとを用いて、符号化される。
（Ｓ８１５）要素の終了"/"を示す符号が、ツリーテーブルに記録される。
（Ｓ８１６）要素値をＳ８０１との間で、全ての要素について符号化するまで繰り返す。
（Ｓ８１７）Ｓ８０１との間で、全ての要素について符号化するまで繰り返す。
【００７２】
図９は、本発明における復号化処理のフローチャートである。
【００７３】
符号データが入力されたとする。符号データは、基本的にツリーテーブルと値テーブルとから構成される。当然に、構造テーブル、属性テーブル、占有ビット長テーブル、整数ハフマンテーブル、文字列ハフマンテーブルも必要となるが、これらテーブルは、予め符号化側と復号化側とで保持されたものであってもよい。
（Ｓ９０１）符号データの最初から順にＳ９０８との間で、要素毎に全ての要素について符号化する。
（Ｓ９０２）最初に、ツリーテーブルを参照して、要素構造の符号を切り出す。
（Ｓ９０３）構造テーブルを参照し、その符号に対応したエントリにおける、要素名、子要素有無及び属性有無のビット列を検索する。要素名のビット列は、変換シートを用いて要素名が具体的に把握できる。
（Ｓ９０４）属性有無のビット列は、属性テーブルから具体的に属性有無を示すビット列が導出される。変換シートから、その要素名に対応する属性名も把握でき、属性有無のビットにより、いずれの属性が存在するかが把握できる。
（Ｓ９０５）次に、構造テーブルのそのエントリに対応する値テーブルを参照する。これにより、存在する属性についての値のビット列を、変換シートを用いて、切り出すことができる。
（Ｓ９０６）切り出されたビット列は、占有ビット長テーブル、整数ハフマンテーブル及び文字列ハフマンテーブルによって、その値及び文字列が導出できる。
（Ｓ９０７）Ｓ９０２からの処理によって、１つの要素の構造が把握できるので、そのタグについて文書処理をする。
（Ｓ９０８）Ｓ９０１との間で、全ての要素について復号化するまで繰り返す。
【００７４】
前述した本発明の文書データの符号処理方法及びシステムの種々の実施形態によれば、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略を、当業者は容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００７５】
【図１】符号化サーバを含むシステム構成図である。
【図２】本発明における文書データの符号処理方法である。
【図３】文書データのサンプルである。
【図４】図３の文書データに対応した種々の符号化テーブルである。
【図５】図３の文書データに対応したハフマンテーブルである。
【図６Ａ】変換シートの前段部分である。
【図６Ｂ】変換シートの後段部分である。
【図７】図３の文書データにおける符号化の過程を表す説明図である。
【図８】本発明における符号化処理のフローチャートである。
【図９】本発明における復号化処理のフローチャートである。
【符号の説明】
【００７６】
１０  符号化
１１、２１、１１０、１１１、２１０、２１１  変換テーブル
１２、２２、１２０、１２１  テキスト形式の文書データ
２３  パーサ
２４  ブラウザの表示画面
３０  文書処理
４  既存のサーバ
５  クライアント
６  符号データ
７  変換テーブルサーバ
８  インターネット
【図１】
2005215951.tif 000003
【図２】
2005215951.tif 000004
【図３】
2005215951.tif 000005
【図４】
2005215951.tif 000006
【図５】
2005215951.tif 000007
【図６Ａ】
2005215951.tif 000008
【図６Ｂ】
2005215951.tif 000009
【図７】
2005215951.tif 000010
【図８】
2005215951.tif 000011
【図９】
2005215951.tif 000012