JPH04503584A - キャラクタ符号化方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 ［キャラクタ符号化方法 発明の背景 本発明はキャラクタの符号化に関するものである。

キャラクタの符号化には多くの手段が存在する。例えば、情報交換用米国基準コ ード（ＡＳＣＩυ及びマルチナショナル　キャラクタ　セット（ＭＣ３）によっ て符号の値が任意に順序付けられたキャラクタ群のキャラクタに位置にあるキャ ラクタに対して２進符号を割当てる。例えばＡＳＣＩＩはアルファベット文字（ “Ａ−Ｚ”及び“ａ−ｚ”）、数字（“Ｏ−９”）その他の記号（例えば“！” 、“＃”、“＄”、“％”又は“＆“）を含有している。各キャラクタはキャラ クタ群の位置を有し、その値はキャラクタの符号である。例えばキャラクタ“Ａ ”、“Ｂ”又は“Ｃ”は位置６５．６６及び６７に位置し、且つ夫々割当てられ た符号１０００００１．１００００１０及び１ＱＯＯＯ１ｌである。

又、ＭＣ３はＡＳＣＩＩキャラクタ群を包含すると共にいわゆる“マルチナショ ナル”キャラクタを含有する。これらマルチナショナル　キャラクタは連字（例 えば“１”）及び区別マークを有するキャラクタ（例えば“Ａ”、“ｈ”及び” を）並びに他のキャラクタ（例えば“ｉ”及び“ａ″）のような音声キャラクタ を具える。再び各キャラクタはキャラクタ群に位置し、その値はキャラクタの符 号でる。例えばキャラクタ“Ａ″。

“Ａ”及び“Ａ”は位置１９３．１９４及び１９５にあり、夫々割当てられた符 号１１０００００１．１１００００１０及び１１００００１１である。

ＡＳＣＩＩ及びＭＣ３の符号はしばしば同一キャラクタ群から２つのキャラクタ を比較するために用いる。第１のキャラクタは、その符号の値か第２のキャラク タの符号の値より大きいか、小さいか或いはこの値に等しい場合に第２のキャラ クタより太きいか、小さいか又はこれに等しくなる。例えば、ＭＣ３において、 “Ａ″は“Ａ′よりも小さい。その理由は１０００００１が１１０００００１よ りも小さいからである。

又、ＡＳＣ［ｒ及びＭＣ５の符号を用いて同一のキャラクタ群から２つ以上のキ ャラクタのストリングを比較する。第１ストリング及び第２ストリングを比較す るために、上述したキャラクタの比較を用いて第１ストリングのキャラクタ及び 第２ストリングの関連するキャラクタに適用する。この比較は、第１ストリング からのキャラクタか第２ストリングの関連するキャラクタより大きくなるか又は 小さくなるまで順次の関連するキャラクタで繰返し、この作動は“キャラクタ順 次”比較と称される。

例えば、ストリングｃａｎｏｅｓ”及び“ｃａｎｏｓ”のキャラクタ順次比較は 、“ｃａｎｏｅｓ”がＣａｎ０ｎＳ″より小さいことを示す。

その理由は“Ｃ”、“、“ｎ”及び“Ｑ”に対する符号が等しい場合でも“ｅ″ 　（０１１００１０１）に対する符号の値が“ｎ”（０１１０１１１０）に対す る符号の値より小さいからである。しかし、キャラクタ順次比較は、一旦等しく ないキャラクタが見出されると、終了する。本例ではキャラクタ“Ｓ”は永久に 比較しない。このキャラクタ順次比較は、ストリングが上段キャラクタ、下段キ ャラクタ及び音声キャラクタの組合せを有する場合には不所望な結果を生じ得る ようになる。例えば、ＭＣ３ではキャラクタ順次比較は、“ＭｃＤｏｕｇａｌ” が“λ１ｃｄｏｎａｌｄ”より小さく、且つ“Ｍｕｔｔｌｅ″が“Ｍｊｌｌｅｒ ”より小さいことを示す。上段キャラクタ、下段キャラクタ及び音声キャラクタ の組合せを含むストリングを比較するために用いる１つの方法は、以下に説明す る“３パス比較法”である。

この３パス比較法では、第１パスのステップは、１）２つのストリングのキャラ クタを全部上段キャラクタに変換し、２）任意の音声キャラクタをそのベース　 キャラクタに低減し、３）残りのキャラクタにキャラクタ順次比較を行う必要が ある。例えば“Ｍｕｌｌｅｒ”が“Ｍｉｉｌｌｅｒ”は“ＭＵＬＬＥＲ”及び“ ＭＵＤ、ＬＥＥＲ’となり、“ＭａｃＤｏｎａｌｄ”及び”Ｍａｃｄｏｎａｌｄ ”は“ＭＡＣＤＯＮＡＬＤ”及び“ＭＡＣＤＯＮＡＬＤ　”となり、”ＭａｃＤ ｏｕｇａｌ　’及び“ＭａｃＤｏｕｇａｌ”は“ＭＡＣＤＯＵＧＡＬ”及び”　 ＭＡＣＤＯＵＧＡＬ”となり、“Ｍｕｔｔｌｅ”及び“λ１ｊｉｌｌｅｒ”は“ ＭＵＴＴＬＥ”及び“ＭＬＩＬ［、ＥＲ”となる。キャラクタ順次比較が等しい 値に戻ると、この方法は第２パスに進むようになる。例えば“ＭＵＬＬＥＲ”＝ “ＭＵＬＬＥＲ”、“ＭＡＣＤＯＮＡＬＤ”＝“ＭＡＣＤＯＮＡＬＤ”及び“Ｍ ＡＣＤＯＵＧＡＬ”＝“ＭＡＣＤＯＵＧＡＬ”となる。

その他では、キャラクタ順次比較は一方が他方より大きいか又は小さくなる結果 にリターンし、比較法は終了する。例えば、“ＭＵＴＴＬＥ”　＞“ＭＵＬＬＥ Ｒ”。

第２バスのステップは、　１）２つのストリングのキャラクタを全部上段キャラ クタに変換するも音声キャラクタをそのままにし、２）ストリングをキャラクタ 順次に比較する。例えば“Ｍｕｌｌｅｒ”及び”Ｍｉｉｌｌｅｒ”は“ＭＵＬＬ ＥＲ”及び“ｙＵｔｔＥＲ”、“ＭａｃＤｏｎａｌｄ″及び“Ｍａｃｄｏｎａｌ ｄ　”は“ＭＡＣＤＮＡＬＤ”及び“ＭＡＣＤＮＡＬＤ″、“ＭａｃＤｏｕｇａ ｌ″及び“λ（ａｃＤｏｕｇａｌ”は“ＭＡＣＤＯＵＯＡＬ″及び“ＭＡＣＤＯ ＵＧＡＬ”となる。比較が、ストリングが等しいことをリターンすると、比較法 は第３パスに進行する。例えば“ＭＡＣＤＮＡＬＤ”＝“ＭＡＣＤＮＡＬＤ”及 び“ＭＡＣＤＯＵＧＡＬ”＝“ＭＡＣＤＯＵＧＡＬ”。

その他の点では、比較は１方が他方より大きいか又は小さい結果にリターンし、 比較法は終了する。例えば、“ＭＵＬＬＥＲ”〈ラクタと音声キャラクタとの混 合キャラクタに変換し、且つ２）ストリングをキャラクタ順次に比較する必要が ある。例えば、“ＭａｃＤｏｎａｌｄ　”及び“Ｍａｃｄｏｎａｌｄ″は“Ｍａ ｃＤｏｎａｌｄ　”及びＭａｃｄｏｎａｌｄ　”となり、“ＭａｃＤｏｕｇａｌ ”及びＭａｃＤｏｕｇａ１″は“ＭａｃＤｏｕｇａｌ　”及び“ＭａｃＤｏｕｇ ａｌ　”となる。比較が双方共等しい結果にリターンすると、比較法は終了する 。例えば“ＭａｃＤｏｕｇａｌ”＝“ＭａｃＤｏｕｇａｌ”。その他の点では比 較が、一方が他方より大きいか又は小さい結果にリターンすると、比較法は終了 する。

例えば、“ＭａｃＤｏｎａｌｄ　”　＞　”Ｍａｃｄｏｎａｌｄ”。

発明の概要 一般に、本発明は、キャラクタが複数の属性（例えばベース、区別及びケース　 キャラクタ）を有し、各属性が複数の値を有するキャラクタ群のキャラクタを符 号化する方法を特徴とする。この方法は、多重ディジット符号を複数の部分に分 割し、夫々の該部分に各属性を割当て、各部分に対しこの部分に割当てられた属 性の各界る値に異る数値符号を割当てるようにしたステップを具える。

好適な例では、前記各部分の長さ、即ちディジットの数が、属性の種々の異る値 の数に依存し、キャラクタから前記キャラクタ群のキャラクタに変化するように する。前記符号の全体の長さをキャラクタ群の全キャラクタに対し同一とする。

前記属性はベース属性、区別属性及びケース属性を具えるようにする。測定のベ ース属性に対する区別値の数に依存し、区別属性に割当てられた部分の長さをベ ース属性に割当てられた部分の長さよりも長くするようにする。キャラクタ符号 化方法を用いてキャラクタのストリングの各キャラクタを符号化する。前記スト リングの各キャラクタから同一の属性に相当する符号の部分を連結して各属性に 対し各キャラクタから連結された部分のセグメントを形成するようにする。前記 セグメントを連結して前記キャラクタストリングを表わす連結された符号の全体 を連結の順序に従って形成し、照合順序で第１重要度の属性に相当するセグメン トが連結総合符号の最高順序位置を有し、残りのセグメントが照合順序で降順重 要度に従って順序付けされるようにする。空キャラクタの欄を特定の属性に相当 する連結部分の２つのセグメント間に介挿し、空キャラクタの欄の長さを２つの セグメントのオーバーラツプ部から照合順序誤差が生ずるのを防止し得るように する。比較作動は、前記キャラクタ　ストリングに対する総合連結符号と優勢的 に比較して前記規定照合順序で２つのキャラクタ　ストリングの相対位置を決め るようにして行う。この比較作動によって連結セグメントの単一比較を行う。第 １及び第２属性（例えばベース及び区別属性）に対する特定の符号は、第１属性 の各位に対し第２属性の種々の値の数を計数することにより選択し、且つ、第２ 属性に割当てられた符号の部分の長さは計数値（例えばビットが属性の全部の可 能な値を表わすに充分であっても）計数値に依存して変化する。

本発明の利点は２つのキャラクタ　ストリングに対する比較作動を１ステツプで 行う点にある。他の利点は、キャラクタに対する標準符号（例えばＭＣＳ符号） の任意の順序で構成されることなく、ユーザが照合順序（即ち分類順序）を所望 のように変化させることができる点である。これがため、例えば、特定のアルフ ァベットにおいて“Ｃ”を“ｄ”の前でなく、後に位置させる必要がある場合に は、標準の符号を用いてキャラクタ（例えばＭＣＳ　）を表わすことが“ｄ”の 前に“Ｃ”が位置すると云う事実は制約ではない。又、２つの文字キャラクタ、 例えばスペイン語の“ｃｈ”及び“１１”を、照合順序を確立する上で単一キャ ラクタとして処理し得ることは他の利点である。

好適例の説明 図１は本発明キャラクタ符号システムの構成部分を示すブロック図であり、 図２は成る値を成る部分に割当てる際における一般的なステップのフローチャー トである。

本発明はテキスト　ファイル又はデータ　ベースに見出されるキャラクタのよう なキャラクタを符号化し、比較し、関連付けることにある。かかるキャラクタは 、各々が１以上の可能な値を有するベース　キャラクタ、区別マーク及びケース 　キャラクタを含む多数の可能な属性を有する。ベース属性の値は、例えば“Ａ ”、“Ｂ”又は“ＣＨとすることができる。区別属性の値は例えば曲折アクセン ト記号“＾”、低アクセント記号“１”又は波形符号記号“〜”とすることがで きる。又、ケース属性は上段、下段又はこれら上段及び下段の組合せ、例えばス ペイン語のキャラクタにおける“ＣＨ”、“ｃｈ”、“ｃｈ”及び“ｃＨ”とす ることができる。例えばキャラクタ“ｈ”はベース、その値は“Ａ”、区別、そ の値は低アクセント記号“＼”、及びケース、その値は下段を有する。キャラク タの属性に従って発生した符号の記述を以下に行う。

本発明の第１の例では、キャラクタをその属性に従って符号化する。キャラクに 対する符号は数個の部分に分割し、符号の各部分をキャラクの属性に割当てる。

以下に示す所ではキャラクタに対する符号を９ビツトの長さとすると共に３つの 可変長さ部分、即ちベース部分、区別部分及びケース部分に分割し、これら部分 をキャラクタのベース属性、区別属性及びケース属性に夫々割当てる。例えばキ ャラクタ“ａ”はベース部分、その値は００１１０　、区別部分、その値は００ ０及びケース部分、その値は０を有する。表１はキャラクタのサンプリング及び その符号を示す。

表１ キャラクタ　ベース部分　区別部分　ケース部分ａ　００１１０　０００　０ ｃ　００１１１０１　０　０ Ｃ００１１１０１０１ Ｅ　０１０　０００００　１ を　０１０　００００１　１ 倉　０１０　０００１０　１ Ｅ　０１０　０００１１　１ Ｅ　０１０　００１００　１ ｅ　０１０　０００００　−　Ｏ ｅ　０１０　００００１　０ ｅ　０１０　０００１０　０ ｅ　０１０　０００１１　０ ｅ　０１０　００１００　０ ｏ　１０００　１０００　０ ハ ｏ　１０００　１０１１　０ ｐ　１００１００００　０ ｔ　１０１１００００　０ 表１及び上述した所から明らかなように、１つの符号の各部分は長さが変化する 。例えば、　“ｔ”に対する符号のベース部分は８ビツトの長さであるが、“ｅ ”に対する符号のベース部分は単に３ビツトの長さである。その理由は、属性が 有する可能な値の数が変化するからである。例えば、“ｅ”の区別属性は可能な 多数の値を有する。これがため、“ｅ”の他の属性に割当てられる部分の長さが 短くなって区別属性に割当てられた部分に各可能な値を表わすに充分なビットを 提供し得なくなる。

更に、一つの属性に同一の値を有する任意のキャラクタはこの属性に割当てられ たその符号の部分に同一の値を有する。例えば、“Ｅ”及び“白”はそのベース 及びケース属性に同一の値を有するが、その区別属性には同一の値を有さない。

これがため、“Ｅ”及び”白”はそのベース部分に同一の値（０１０）を有する が、その区別部分には同一の値を有さない。キャラクタを符号化し、表１と同様 のテーブルを形成するために用いられるシステム及び方法を図１につき以下に説 明する。

図１に示すように、符号化システム１０は特定のキャラクタ群、例えばＭＣＳに よって供給される照合シーケンス１１と、この照合シーケンスを変更するために ユーザが供給する変更リスト１２とを具える。以下に詳述するようにテーブル発 生器１４は照合シーケンス１１及び変更リスト１２を用いて表１と同様の符号化 されたキャラクタのテーブル１６を形成する。又、この符号化キャラクタのテー ブル１６は特定のケースキャラクタ、例えばスペイン語のキャラクタと見做され る“ｃｈ”及び“ｌド及び２つのキャラクタ“ＳＳ“ど見做されるドイツ語のβ ”に対する符号を有している。

これら特定のケースキャラクタを種々の相対作動に関し以下詳細に説明する。し かし、まず最初照合シーケンス１１及び変更リスト１２について説明する。

ユーザは、各々が上述した属性の１つに対応する多数の属性クラスを変更リスト １２で規定することによりキャラクタ群の照合シーケンス１１を修正する。１つ の属性に対し１つの値を有する全てのキャラクタは１つの属性クラスに入るが、 選択された属性に対し他の値を有する全てのキャラクタは他の属性クラスに入る 。例えば“Ａ”、“、“Ａ”、“ｉ”、“Ａ”及び“當”は全て“Ａ”のベース 属性値を有すると共に１つの属性クラスに入るが、“Ｂ”及び“ｂ”は　“Ｂ” ベース属性値を有し、他の属性クラスに入る。各属性クラス内には１つ以上の属 性値が存在する。例えば、“Ａ”属性クラスは１つのベース属性値と、４つの区 別属性値と、２つのケース属性値とを有する。これらの属性値を割当てる方法を 図１の回路素子に関し、図２のフローチャートにより以下に説明する。

図２に示すステップに対しテーブル発生器１４によって変更すスト１２を読出し 、属性クラスを設定する。即ち、キャラクタ群の各キャラクタに対し、テーブル 発生器１４によってキャラクタをこれが属する任意且つ全ての属性クラスに加え 、且つこれらの属性クラスのキャラクタの数を１つ宛増大する。

図２を参照し、キャラクタ群のキャラクタの全部を一旦読出すと、テーブル発生 器１４によってキャラクタに対する符号の長さ、即ち照合シーケンス１１のキャ ラクタの数を表わすに必要な長さを計算する（ステップ１００）。例えば、５１ ２のキャラクタは９ビツトで表わすことができる。処理すべき第１の属性クラス は照合シーケンスＪ１の第１キヤラクタの第１属性クラスである。従って第１ベ ース部分の値（ｂ値）を表わす変数はｌに初期化する（ステップ１０２）。この 時点で、特定の属性のビットの。

数個の組合せを使用しないように全ての符号を設計する必要がしばしばある。例 えば“Ａ”に関し５つの区別か存在する場合には区別部分に対し３ビツトを必要 とする。３ビツトか８区別部分まで表わし得るため、３ビツトの組合せは使用し ない。

次に各属性クラス（ステップ１０４）及びこの属性クラスの各キャラクタ（ステ ップ１０６）に対し、テーブル発生器１４によってキャラクタの種々の属性に割 当てられた部分に対する値を計算する。先ず最初、テーブル発生器１４によって 種々のケース属性値を表わすに必要なビットの数を計算する（ステップ１０８） 。ステップ１０５では区別部分の値（ｄ−値）を表わす変数を各キャラクタの処 理前に０に初期化する。

属性クラスの各キャラクタに対しテーブル発生器１４によって種々のケース属性 値を表わすに必要なビットの数を計算しくステップ１０８）、且つキャラクタに 対するケース部分の値を割当てる（ステップ１１０）。

キャラクタの区別部分に対する値を割当てるために、テーブル発生器Ｉ４によっ て種々の区別属性値を表わすに必要なビットの数を計算しくステップ１１２）、 ｄ−値に等しいキャラクタに対する区別部分値を割当て（ステップ１１４）、且 つｄ−値の変数を増大させる（ステップ１１６）。例えば“Ａ”属性クラスには 区別属性に対する１つ以上の値が存在する。これがため、“Ａ”属性クラスのキ ャラクタに対する区別部分の値は、キャラクタが属性クラスに加えられる際、こ れに依存して計算される。次いで、キャラクタのベース部分に対する値を割当て るために、テーブル発生器１４は残りのビットを用いてキャラクタのベース属性 値即ちｂ−値を表わすようにしくステップ１１８）、且つこのｂ−値を増大する （ステップ１２０）。

キャラクタの種々の属性に対する部分を割当てた後、テーブル発生器１４はステ ップ１０６に戻り、属性クラスの次のキャラクタを処理する（ステップ１２２） 。属性クラスに他のキャクラクタが存在しない場合にはテーブル発生器１４はス テップ１０４に戻り、次の属性クラスを処理する（ステップ１２４）。他の属性 クラスか存在しない場合には処理は終了する（ステップ１２６）。

本発明の他の例では、符号化キャラクタのテーブル１６が一旦発生すると、１対 のキャラクタストリング２２を比較することができる。標準符号例えばＭＣ３に よって表わされるストリング２２はトランスレータ２４に供給し、これによって ストリングをテーブル１６に供給して変換されたストリング２５を発生させるよ うにする。次いで変換されたストリング２５をトランスレータ２４で連結して１ ステップ比較作動を行なうようにする。

先ず最初、各ストリングに対し、各キャラクタの符号のベース部分を互いに連結 する。例えば表１のキャラクタ群を与えて、ストリングｃｏｔｅ”および“ｃｏ ｔｅ”のベース部分を次に示すように連結する。

次に、ベース部分を次に示すように５つのビット空キャラクタパッドと連結する 。（この空キャクラクタパッドによって、種々の長さのストリングが後の例に示 されるように比較されるようにする。）。

へ ｃ　ｏ　ｔ　（ｐａｄ） ｃ　ｏ　ｔ　（ｐａｄ） 次いでベース部分および空パッドを、次に示すように互いに連結されるキャラク タの区別部分と連結する。

ｃ　ｏ　ｔ　ｅ　（ｐａｄ）ｃｏ　ｅ ｏｏｌｌ　１０１１０００１０１１０００００１０００００００１０１１０００ ００ｃ　ｏ　ｔ　ｅ　（ｐａｄ）ｃｏ　ｅ ｏｏｌ　１１０１１０００１０１１０００００１０００００００１００００００ ００先ず最初、ベース部分、空キャラクタパッドおよび区別部分をキャラクタの ケース部分と連結し、このケース部分を次に示すように互いに連結する。

上述したように、空キャラクタによって異なる長さのストリングが粗く比較され るようにする。変換ストリングを比較する際の誤りは、特に異なる長さの２つの ストリングがストリングの一方の終了点まで等しい際に属性の連結部分即ち変換 ストリングのセグメントが他の属性から発生したセグメントとオーバーラツプす る場合に発生する。かかる場合には空のキャラクタパッドによって長いストリン グのベース部分が短いストリングの区別又はケース部分と比較されるのを防止す る。例えば、次に示すように空キャラクタを用いることなく変換ストリング“？ ”および“？ａ”を比較する。

この例ではストリング？”のキャラクタ“？”の区別部分はストリングｙａ”の キャラクタ“ａ”のベース部分と一致する。これらストリングを比較した結果は “？”〉“？ａ”となり、これは意図する所とは逆となり、即ち、ストロング？ ”はストロングψａ”より小さくし、即ちこれより大きくしてはならない。かか る結果が生じるのを防止するために、空キャラクタパッドを各ストリングのベー ス部分と区別部分との間で連結する空キャラクタパッドおよびその上述した例へ の適用について以下説明を行なう。

空キャラクタパッドは全部を零で構成し、これによってパッドを、これと比較す る任意のベース部分よりも常時小さくする。

（全部が零であるベース部分は存在せず、空キャラクタパッドの零の数が過剰の 先行零となる）。これがため、異なる長さの２つのストリングが一方のストリン グの終了点に等しい場合には短いストリングの空キャラクタパッドは長いストリ ングの次のキャラクタのベース部分と一致し、これによって短いストリングが長 いストリングより長くなるのを防止する。例えば、次に示すようにストリング９ ”および“９ａ”を空キャラクタパッドと比較する。

（：６０１１１０１８０１１Ｏ品′０００冒ｏｏｏｇ：この例ではストリング９ ″に対する空キャラクタパッドをストリング♀ａ”のキャラクタ“ａ”に対する ベース部分と比較する。

変換例を完了するためには次に示すストリングを変換する。

ｃｏｔ　＝　００１１１０１１０００１０１１００００００００００１００００ ００ｃｏｐｅ＝　００１１１０１１０００１００１０００００１０００００００ １００００００００００００ｙａｔ　＝　００１１１０１００１１０１０１１０ ０００００００００００００００Ｃｏｐｅ＝　００１１１０１１０００１００１ ０００００１０００００００１００００００００１０００Ｃｏｔ　＝　００１１ １０１１０００１０１１０００００ＱＱＯＱ　Ｏ１０００１００図１に示すよう に、トランスレータ２４は上述した所と同様の変換ストリング２５を比較処理部 ２６に供給し、この比較処理部２Ｇは２つのオペランド及び長さを受けてこれら が短いか、長いか或いは等しいかの結果をリターンする。次いで分類アルゴリズ ム２８は上記結果を受けてストリング２２を順序付けるようにする。例えば上述 したように変換したストリングは次に示すように分類する。

ｌｉ：ａｔ　＝　００２１１０１００１１０１０１１００００００００００００ ００００ｃｏｐｅ＝　００１１１０１１０００１００１０００００１０００００ ００１００００００００００００ｃｏｐｅ＝　００１１１０１１０００１００１ ０００００１０００００００１００００００００１０００ｃｏｔ　＝　００１１ １０１１０００１０１１００００００００００１００００００ｃｏｔ　＝　００ １１１０１１０００１０１１００００００００００１０００１００ｃｏｔｅ＝　 ００１１１０１１０００１０１１０００００１０００００００１０００００００ ０００００本発明の他の例では“ＭＡＴＣＨＩＮＧ“、“Ｃ０ＮＴＡ　ＩＮ　ｒ ＮＧ″及び“５ＴＡＲＴ［ＮＧ　ＷＩＴｆ（″のような種々の関連操作は符号化 キャラクタのテーブル１６を用いてキャラクタのストリング及びサブストリング を比較し、且つ整合する。これらの操作は例えばキャラクタの成るストリングに 対するテキストファイル又はデータベースを探索する際に有利である。特に、こ こでは、符号化キャラクタ１６のテーブルにつき前述したように、いわゆる特定 のケースキャラクタの整合に有利である。

各関連の操作は、比較及び整合されるストリングのキャラクタに対する符号の値 に依存して真又は偽の値をリターンする。

第１ストリングが第２ストリングの任意のサブストリングと一致する場合には“ λ（ＡＴＣＨｒＮＧ”操作によって真の値をリターンする。第１ストリングが第 ２ストリング内に見出される場合には“Ｃ０ＮＴＡ　ＩＮ　ｒＮＧ“操作によっ て真の値をリターンする。第１ストリングの初期キャラクタが第２ストリングの 初期キャラクタに一致する場合には“５ＴＡＲＴＩＮＧ　ＷＩＴＨ”操作によっ て真の値をリターンする。

上述したキャラクタの関連操作の実行は容易であり、上述したキャラクタ順次比 較を用いる。即ち第１ストリングの順次の単一キャラクタを第２ストリングの関 連する単一キャラクタと比較する。しかし、“ｃｈ”、“１１”及び“β”のよ うな特定のケースキャラクタは個々に処理する必要がある。例えば、操作“５Ｔ ＡＲＴＩＮＧ　ＷＩＴＨＣ“はスペイン語の“ｃｈｉｌｅ”に対する真の値をリ ターンしない。その理由は“ｃｈ“がスペイン語では１キヤラクタであるからで ある。

特定のケースキャラクを比較するためには、“ｃｈ”のような特定のケースキャ ラクタを含む関連操作によって先ず最初符号化キャラクタのテーブル１６の１区 分にストリングの各キャラク夕を位置させる。スペイン語のキャラクタ群に対す る符号化キャラクタのテーブルは参考記事として添付する（このテーブルは、添 付されたマイクロフィッシュ参考記事のソース符号に関連するものである。従っ て部分の値はソース符号に従い、後述する理由で右から左に読出す。しかし、操 作の原理はそのままである）。例えば、添付記事に示されるスペイン語の符号化 キャラクタのテーブルを用い、操作“５ＴＡＲＴＩＮＧ　ＷＩＴＨＴ”がストリ ングの“Ｔ”を探索する場合には、これにより特定のケースの区分をチェックし てこの“Ｔ”が任意の特定のケースキャラクタの第１キヤラクタであるかどうか をみる。“Ｔ”か任意の特定のケースキャラクタの第１キヤラクタでないため、 上記操作は、これにより特定のケースキャラクタでないものを含むテーブル１６ の区分に“Ｔ″を位置させてここに見出した符号を用いる。

又、操作“５ＴＡＲＴ［ＮＧ　ＷＩＴＨＣ”がストリングの“Ｃ”を探索する場 合には、特定のケースキャラクタの区分をチェックしてこの“Ｃ“が任意の特定 のケースキャラクタの第１キヤラクタであるかどうかをみる。“Ｃ”が特定のケ ースキャラクタ″ＣＨ”の第１キヤラクタであるため、操作によってストリング の次のキャラクタが“Ｈ″であるかどうかをみる。次のキャラクタが“Ｈ”であ る場合には操作はテーブル１６の特定のケースキャラクタの区分に見出される“ ＣＨ”に対する符号を用いる。しかし、“Ｃ”の次が“Ｈ”でなかった場合には 、操作は、これによって特定のケースキャラクタでないものを含むテーブルの区 分に“Ｃ”を位置させ、ここに見出される符号を用いる。例えば、操作“５ＴＡ ＲＴ［ＮＧ　ＷＩＴＨＣ”は“ｃｈｉｌｅ”に対する偽の値をリターンすると共 に“ｃａｓａ”に対する真の値をリターンする。

ＣＦＲ３７目　１．９６（ｂ）によれば、テーブル発生器１４を実行するソース 符号は６２フレームを含むマイクロツイツチ参考記事として添付され、基準とし てここに組込まれる。使用するプログラミング語はブリス（ＶＡＸ　Ｂ１１５ｓ −３２Ｖ　４．３−８０８）、即ちデジタルイクイプメント　コーポレーション のプログラミング語であり、その詳細は、プリス　ランゲージ基準マニアルＡＡ −Ｈ２７５Ｄ−ＴＫ。

１９８７年５月としてデジタル社から出版され、市販されている。

ソース符号はＶＭＳ５．２オペレイテイング　システムによって実行されるＶＡ Ｘ　８８００コンピユータでビルス　コンパイラ４．３−８０８を用いてコンパ イルされる。ＶＡＸコンピュータのアーキテクチュアはストリングの左端ビット をバイトの最上位ビットとみなしている。これがため、ソース符号の例によって キャラクタを符号化し、これらキャラクタは右から左に向かって読出され、連結 される。次いで変換されたストリングのビットの順序リッピングと称する。本発 明において符号化及び連結の方法は説明の便宜土庄から右に実施するようにした 。

ＦＩＧＵＲＥ　１ 図２ 開始 １００　照合シーケンスのキャラクタの数を表わすに必要なビットの数を計算す る。

１０２ｂ−値＝１（ベース部分の変数）１０４　各属性クラスに対し上記計算を 行なう。

１０５　ｂ−値＝０（区別部分の変数）１０６属性クラスの各キャラクタに対し 上記計算を行なう。

１０８　種々のケース属性の値を表わすに必要なビットの数を計算する。

１１２　ｆ！々の区別属性値を表わすに必要なビットの数を計算する。

１１４　キャラクタ（ｄ−値）に対する区別部分値を割当てる。

１１６　ｄ−値を増大する。

１２０　ｂ−値を増大する。

１２２　次のキャラクタを処理するためのリターン１２４　次の属性クラスを処 理するためのリターン１２６終了 国際調査報告 ＩＩｌｌ−−ｔｍ−，１＾峠ｗａ＋＋１１’　Ｍ　ＰＣＴ／ＵＳ　９０１０５９ ４７１ｍ−歯！嚇・ｌムー嘲−、、ｉ、、ＰＣＴ／ＵＳ　９０１０５９４７国際 調査報告 ＵＳ　９００５９４７

Claims (25)

【特許請求の範囲】
1. １．キャラクタが複数の属性を有し、各属性が複数の値を有するキャラクタ群の キャラクタを符号化するに当り、多重ディジット符号を複数の部分に分割し、夫 々の該部分に各属性を割当て、各部分に対しこの部分に割当てられた属性の各異 る値に異る数値符号を割当てるようにしたことを特徴とするキャラクタ符号化方 法。
2. ２．前記各部分の長さ、即ちディジットの数が、属性の種々の異る値の数に依存 し、キャラクタから前記キャラクタ群のキャラクタに変化するようにしたことを 特徴とする請求項１又は２２に記載のキャラクタ符号化方法。
3. ３．前記符号の全体の長さをキャラクタ群の全キャラクタに対し同一としたこと を特徴とする請求項２記載のキャラクタ符号化方法。
4. ４．前記属性はベース属性、区別属性及びケース属性を具えることを特徴とする 請求項２又は２２に記載のキャラクタ符号化方法。
5. ５．前記属性はベース属性、区別属性及びケース属性を具え、且つ多数の区別値 を有するキャラクタに対し、区別属性に割当てられた部分の長さをベース属性に 割当てられた部分の長さよりも長くするようにしたことを特徴とする請求項４記 載のキャラクタ符号化方法。
6. ６．請求項１記載のステップを用いてキャラクタのストリングの各文字記号を符 号化することを特徴とする請求項１記載のキャラクタ符号化方法。
7. ７．前記ストリングの各文字記号から同一の属性に相当する符号の部分を連結し て各属性に対し各文字記号から連結された部分のセグメントを形成することを特 徴とする請求項６記載のキャラクタ符号化方法。
8. ８．前記セグメントを連結して前記字記号ストリングを表わす連結された符号の 全体を連結の順序に従って形成し、照合順序で第１重要度の属性に相当するセグ メントが連結総合符号の最高順序位置を有し、残りのセグメントが照合順序で降 順重要度に従って順序付けされるようにしたことを特徴とする請求項７記載のキ ャラクタ符号化方法。
9. ９．前記属性がベース属性、区別属性及びケース属性を具え、且つベース属性に 相当するセグメントが総合連結符号の最高順序位置を有し、区別属性に相当する セグメントが総合連結符号の中間順序位置を有し、ケース属性に相当するセグメ ントが総合連結符号の最低順序位置を有することを特徴とする請求項８記載のキ ャラクタ符号化方法。
10. １０．前記各部分の長さ、即ち、ディジットの数は属性の種々の異る値の数に依 存し、キャラクタから前記文字記号組のキャラクタに変化するようにしたことを 特徴とする請求項８記載のキャラクタ符号化方法。
11. １１．空キャラクタの欄を特定の属性に相当する連結部分の２つのセグメント間 に介挿し、空キャラクタの欄の長さを２つのセグメントのオーバーラップ部から 照合順序誤差が生ずるのを防止し得るようにしたことを特徴とする請求項１０記 載のキャラクタ符号化方法。
12. １２．前記キャラクタに対する多重ディジット符号と優勢的に比較して前記規定 照合順序で２つのキャラクタの相対位置を決めるステップを更に具えることを特 徴とする請求項１，５又は２２記載のキャラクタ符号化方法。
13. １３．前記キャラクタ　ストリングに対する総合連結符号と優勢的に比較して前 記規定照合順序で２つのキャラクタ　ストリングの相対位置を決めるステップを 更に具えることを特徴とする請求項８記載のキャラクタ符号化方法。
14. １４．前記キャラクタ　ストリングに対する総合連結符号と優勢的に比較して前 記規定照合順序で２つのキャラクタ　ストリングの相対位置を決めるステップを 更に具えることを特徴とする請求項９記載のキャラクタ符号化方法。
15. １５．前記キャラクタ組に各々が複数の値を有する第１及び第２属性を存在させ 、更に、前記第１属性の各値に対し、前記第２属性の種々の異る値の数を計数し 、第１属性に関連し第２属性の種々の異る値の計数に基づき前記第２の属性に割 当てられた部分、即ち第２部分の長さを測定し、前記第１属性の各値に対し、前 記第２部分の長さ、及び前記符号の全体の長さに基づき、第１属性に割当てられ た部分すなわち第１部分の長さを測定するようにしたことを特徴とする請求項２ 記載のキャラクタ符号化方法。
16. １６．前記符号の全長は前記文字記号組の全部のキャラクタに対し同一とし、全 部のキャラクタに対し同一とした部分の長さの和とすることを特徴すとる請求項 １５記載のキャラクタ符号化方法。
17. １７．前記属性の端異なる値に対し異る数字符号を割当てるステップは、属性の 数値順序が照合順序に相当するような値を割当てるステップとすることを特徴と する請求項２記載のキャラクタ符号化方法。
18. １８．キャラクタを表わす標準符号の順序及び特定の文字記号組に対する１組の 変更順序から照合順序を導出するステップを更に具えることを特徴とする請求項 １７記載のキャラクタ符号化方法。
19. １９．単一のベース属性は２つのキャラクタのストリングに相当し、単一の数字 符号を前記符号のベース部分に割当てて２つのキャラクタのストリングを表わす ようにしたことを特徴とする請求項４記載のキャラクタ符号化方法。
20. ２０．キャラクタを表わすために用いられる標準符号の数値順序とは異る所望の 照合順序に基づきキャラクタの２つのストリングを比較するに当り、照合符号に 対するキャラクタに関するトランスレーション　テーブルを設け、所望の照合順 序が前記照合符号の数値順序に相当するようにキャラクタに照合符号を割当て、 前記トランスレーション　テーブルを用いてキャラクタの各ストリングに対する 標準符号をトランスレーション　ストリングの各キャラクタに対する照合符号を 形成し、この照合符号を比較することを特徴とするキャラクタの２つのストリン グを比較する方法。
21. ２１．各キャラクタ　ストリングを形成するキャラクタに対する照合符号を連結 し、１方のストリングに対する連結符号と他のストリングに対する連結符号とを 比較することを特徴とする請求項２０記載のキャラクタの２つのストリングを比 較する方法。
22. ２２．前記キャラクタは複数の属性を有し、各属性は複数の値を有し、前記照合 符号は複数の部分で構成し、各部分は異る属性を割当て、各部分内で異なる数値 符号を属性の各異なる値に割当てるようにしたことを特徴とする請求項２１記載 のキャラクタの２つのストリングを比較する方法。
23. ２３．前記符号を２進数とし、最上位ビットを右側に、最下位ビットを左側に位 置させるようにしたことを特徴とする請求項１又は２０記載のキャラクタ符号化 方法。
24. ２４．前記符号を２進数とし、最上位ビットを左側に、最下位ビットを右側に位 置させるようにしたことを特徴とする請求項１又は２０記載のキャラクタ符号化 方法。
25. ２５．前記比較ステップは次のステップの１つ、即ち、第１ストリングが第２ス トリングの任意のサブストリングと整合する場合に、真の値がリターンする整合 作動と、第１ストリングが第２ストリング内に見出される際に真の値がリターン する包含作動と、第１ストリング内の初期キャラクタが第２ストリング内の初期 キャラクタと調合する場合に、真の値がリターンする開始作動とを具えることを 特徴とする請求項２３記載のキャラクタの２つのストリングを比較する方法。