JP4685348B2 - 多数の文字を扱うための効率的な照合要素構造 - Google Patents

Description

背景
発明の分野
この発明は、データベースシステム内でデータにインデックスを付け、ソートするプロセスに関する。特に、この発明は、多数の文字のソートの重みを符号化するための効率的な照合要素構造を提供するための方法および装置に関する。

関連技術
データベースシステム開発における１つの課題は、さまざまな言語のソートをサポートすることである。たとえば、データベースの中には、日本の顧客はソート方法を「日本語」に指定し、フランスの顧客はソート方法を「フランス語」に指定することができるデータベースがある。しかしながら、インターネット技術が世界的に配備される中、国際的にビジネスを拡張するため、多言語の機能をソフトウェアに持たせることが企業にとって益々重要になってきている。

データベースに記憶されるデータが急速に多言語化するにつれ、データベースのユーザは、順序付けが大半の言語に有効である単一のソートの使用に急速に興味を持つようになっている。

残念なことに、多言語のソートでは何千もの異なる文字がある可能性があり、このため、多言語のソートに関わるデータ構造が多量のメモリを消費することになる。さらに、性能を低下させることなく、これらのデータ構造を圧縮することは難しい。

多言語のソートは、通常、文字列を対応する照合要素の列に変換し、（これらの列はソートキーとしても知られる）、照合要素の列を比較してソート動作を行なうことによって実現される。この変換プロセスは、通常、各文字について対応する照合重みを含む照合重みテーブルで文字を参照することによって行なわれる。

（ユニコードコンソーシアム（Unicode Consortium）の）ユニコードテクニカルレポート第１０号（Unicode Technical Report No.10）は、１６ビットの第１の重みの値に８ビットの第２の重みの値が続き、それに続く８ビットの第３の重みの値を含む照合要素構造を特定している。第１の重みの値は文字を識別し、第２の重みの値は文字のアクセント符号を特定し、第３の重みの値は文字の大文字小文字の区別情報を特定する（関連する句読法も特定することがある）。

通常、比較機能は、まず第１の重みを比較することに注意されたい。第１の重みが整合する場合、比較機能は第２の重みを比較する。第１の重みおよび第２の重みの両方が整合すると、比較機能は第３の重みを比較する。

ユニコードテクニカルレポート第１０号によって特定される１６ビットの第１の重みの値は、６５，５３６の異なる文字しか符号化できないことに注意されたい。しかしながら、６５，５３６以上の文字を提供することが必要となってきている。これは、第１の重みの値を３２ビット（４バイト）に増やすことによって実現できる。しかしながら、第１の重みの値を１６ビットから３２ビットに増やすことには、（１）言語インデックスを構築して、３２ビットの第１の重みの値をサポートするためにより多くのメモリが必要となる、（２）言語インデックスへのアクセス時間が増加する、（３）照合要素列の記憶にさらに多くのメモリが必要となる、（４）ソートキーを比較するのにより多くのコンピュータ動作が必要となる等の多くの欠点がある。

上述のような問題なく、多数の文字を処理することのできる効率的な照合要素構造を使用するための方法および装置が必要である。

概要
この発明の一実施例は、多数の文字をサポートする照合要素の使用を容易にするシステムを提供する。このシステムは、照合要素を受取り、照合要素内の第１の重みフィールドから第１の重みの値を読取ることで作動する。第１の重みの値が確保された値のセット内にある場合、システムは、照合要素内の第２の重みフィールドおよび第３の重みフィールドの両方から第１の重みの値の付加部分を読取る。一方、第１の重みの値が確保された値のセット内にない場合、システムは第２の重みフィールドから第２の重みの値を読取り、さらに第３の重みフィールドから第３の重みの値を読取る。

この発明の一実施例では、第１の重みの値が確保された値のセット内にある場合、システムは、第２の重みの値を第２のデフォルト値にセットし、第３の重みの値を第３のデフォルト値にセットする。

この発明の一実施例では、照合要素はユニコード規格（Unicode standard）に準拠する。

この発明の第１の実施例では、第１の重みの値は文字を識別する。さらに、第２の重みの値は文字のアクセント符号を特定し、第３の重みの値は文字の大文字小文字の区別情報を特定することができる。

この発明の一実施例では、照合要素はサイズが４バイトであり、そのうちの第１の重みフィールドは２バイト、第２の重みフィールドは１バイト、第３のフィールドは１バイトであり、第１の重みフィールドの値が確保された値のセットに属さない場合、第１の重みフィールドは照合要素の４バイトすべてを占める。

この発明の一実施例では、第１の重みの値の確保された値のセットは、１６進法の値０ｘＦＦＦ０〜０ｘＦＦＦＦを含む。

この発明の一実施例では、照合要素は照合重みテーブルからとられ、照合重みテーブルは、文字を照合の重みにマップして文字列の順序付けを確立するために使用される。

この実施例のある変形例では、さらに、システムは、列内の各文字を読取り、各文字について対応する照合要素を照合重みテーブルから参照して、列についてのソートキーを構築する。次に、このシステムは、各文字についての対応する照合要素をソートキーに追加
する。このソートキーがデータベース内の記録に関連付けられる場合、このソートキーはデータベースの言語インデックスを構築するために使用することができる。

詳細な説明
以下の説明は、当業者なら誰でもこの発明を製造および使用することができるように提供するものであり、ある特定の用途およびその必要条件の面から説明する。当業者には、開示された実施例のさまざまな変形例が容易に明らかとなるであろう。ここに規定される一般的な原則は、この発明の精神および範囲を逸脱することなく他の実施例および用途に応用することができる。したがって、この発明は、示された実施例に限定されることを意図しておらず、ここに開示される原則および特徴に一貫する最も広い範囲を与えられることを意図する。

この詳細な説明に記載されるデータ構造およびコードは、通常、コンピュータ読取可能な記憶媒体に記憶され、コンピュータの読取可能な媒体は、コンピュータシステムが使用するためにコードおよび／またはデータを記憶することのできる装置または媒体であればどのようなものであってもよい。これは、ディスクドライブ、磁気テープ、ＣＤ（Compact Disc）およびＤＶＤ（Digital Versatile DiscまたはDigital Video Disc）などの磁気および光学記憶装置、ならびに伝送媒体で実現されるコンピュータ命令信号（信号が変調される搬送波を備えるか、または備えない）を含むがこれらに限らない。たとえば、伝送媒体は、インターネットなどの通信ネットワークを含んでもよい。

コンピュータシステム
図１は、この発明のある実施例によるデータベース１０４を備えたコンピュータシステム１０２を示す。コンピュータシステム１０２は、マイクロプロセッサベースのコンピュータシステム、メインフレームコンピュータ、デジタル信号プロセッサ、持ち運び可能なコンピューティングデバイス、個人端末、デバイスコントローラおよび機器内の計算機関等どのような種類のコンピュータシステムを含んでもよいが、これらに限らない。

データベース１０４は、不揮発性の記憶装置にデータを記憶するためのシステムであればどのような種類のシステムを含んでもよい。これは、磁気記憶装置に基づくシステム、光学記憶装置に基づくシステムおよび磁気光学記憶装置に基づくシステム、ならびにフラッシュメモリおよび／またはバッテリバックアップメモリに基づく記憶装置を含んでもよいが、これらに限らない。データベース１０４は、記録の集まりの集まりを含むデータファイル１０６を含み、これら記録は挿入された順に記憶される。データファイル１０６は、インデックス１０８などの１つまたは複数のインデックスを通じて参照することができ、インデックスは、データファイル１０６内での記録の順序付けを特定する。この順序付けは、通常、データファイル１０６内の関連付けられるターゲットのコラムをソートすることで決定される。このソートがある特定の言語のソート順序を満たすため、ターゲットのコラムの各文字列は、まず、照合重みテーブル１１０の文字を参照することによって、ソートキーに変換される。照合重みテーブル１１０は、あり得る各文字についての照合要素を含むアレイにすぎないことに注意されたい。

照合要素の構造
図２は、この発明のある実施例による照合要素２０４の代替の構造を示す。図２に示されるように、照合要素２０４は、照合重みテーブルを参照することで生成される。

図示の実施例では、照合要素２０４は、データの４バイトを占め、２つのうちの１つの形をとり得る。第１の形では、照合要素２０４の最初の２バイトは、第１の重みフィールド２０６を含み、第３のバイトは第２の重みフィールド２０８を含み、第４のバイトは第
３の重みフィールド２１０を含む。

第２の形では、照合要素２０４の最初の２バイトは、０ｘＦＦＦ０〜０ｘＦＦＦＦの範囲内の確保された値を含む。この確保された値は、照合要素２０４の第３および第４のバイトが第２および第３の重みの値ではなく、第１の重みフィールドの延長部分を含むことを示す。この場合、第２および第３の重みの値は、デフォルト値にセットされる。

第２の形は１，０００，０００より多くの異なる文字をサポートすることに注意されたい。なぜなら、照合要素２０４の第１および第２のバイトの１６のあり得る値０ｘＦＦＦ０〜０ｘＦＦＦＦの各々は、照合要素２０４の第３および第４のバイトの１６ビット、または６５，５３６のあり得る値に関連付けられるためである。

さらに、第２および第３の重みの値は、デフォルト値にセットできることにも注意されたい。なぜなら、６５，５３６より大きい識別子を有する新しい文字は、主に漢字およびハングル字母である、中国、日本および韓国（ＣＪＫ）の文字であり、漢字／ハングル字母にはアクセント符号およびケースの区別はないためである。さらに、極東アジアでも、ラテン語に基づく文字および数字は、常にＣＪＫ文字の前に位置付けられる。

ソートキーの作成
図３Ａは、この発明のある実施例によるソートキーの作成方法を示す。図３Ａでは、列３０２は、個々の文字を照合重みテーブル１１０で参照することで、ソートキー３０４を含む照合要素（重み）の列に一文字ずつ変換される。

図３Ｂは、この発明のある実施例による、ソートキー３０４を作成するプロセスを示すフローチャート図である。列３０２内の各文字２０２について、システムは、文字２０２を読取り（ステップ３０６）、照合重みテーブル１１０で文字２０２についての照合要素２０４を参照する（ステップ３０８）。次に、システムは照合要素２０４をソートキー３０４に追加する（ステップ３１０）。

照合要素の読取り
図４は、この発明のある実施例による照合要素２０４の読取のプロセスを示すフローチャート図である。システムは、ソートプロセス中、またはソートキーの比較を必要とする何らかの他の動作中に照合要素２０４を受取ることによって開始する（ステップ４０２）。次に、このシステムは、照合要素２０４の最初の（上位の）２バイトが、０ｘＦＦＦ０に等しいかまたはそれよりも大きい確保された値を含むかどうかを判定する（ステップ４０４）。そうであれば、システムは、第１の重みの値が照合要素２０４の４バイトすべてであると解釈し、第２および第３の重みの値はデフォルト値にセットされる（ステップ４０６）。

照合要素２０４の最初の２バイトが確保された値を含まない場合、システムは、第１の重みの値を照合要素２０４の第１および第２のバイトにセットする。これは、照合要素２０４を１６ビットだけ右にシフトし、次に、残りの２バイトを第１の重みの値にすることで行なう。次に、第２の重みの値は照合要素２０４の第３（最下位から２番目）のバイトからとられる。これは、照合要素２０４を８ビットだけ右にシフトし、第２の重みの値を残りのワードの下位のバイトにすることで行なう。最後に、第３の重みの値は、照合要素２０４の第４の（最下位）バイトからとられる（ステップ４０８）。

この発明の実施例の上述の説明は、例示および説明の目的でのみ提示したものである。上述の説明は徹底的な説明を意図したものではなく、またはこの発明を開示された形に限定することを意図しない。したがって、当業者には多くの修正例および変形例が明らかで
あろう。さらに、上述の開示は、この発明を限定するためのものではない。この発明の範囲は特許請求の範囲に規定される。

この発明のある実施例によるデータベースを備えたコンピュータシステムの図である。 この発明のある実施例による照合要素の代替の構造を示す図である。 この発明のある実施例によるソートキーの作成方法を示す図である。 この発明のある実施例によるソートキーの作成のプロセスを示すフローチャート図である。 この発明のある実施例による照合要素を読取るプロセスを示すフローチャート図である。

Claims (12)

1. 多数の文字をサポートする照合要素の使用を容易にする装置であって、
   前記照合要素内の第１の重みフィールドから第１の重みの値を読取るように構成される割当機構を含み、
   前記第１の重みの値がある確保された値のセット内にある場合、前記割当機構は、前記照合要素内の全てのビットを含むように前記第１の重みフィールドを拡張するとともに、前記第２の重みの値を第２のデフォルト値にセットし、前記第３の重みの値を第３のデフォルト値にセットするように構成され、
   前記第１の重みの値が前記確保された値のセット内にない場合、前記割当機構は、
   前記照合要素内の前記第２の重みフィールドから第２の重みの値を読取り、
   前記照合要素内の前記第３の重みフィールドから第３の重みの値を読取るように構成され、
   前記第１の重みフィールドの大きさに応じて前記照合要素により表わされる文字の数が増加し、
   前記第１の重みの値についての前記確保された値のセットは、１６進法の値０ｘＦＦＦ０〜０ｘＦＦＦＦを含み、
   前記第１の重みの値は、ある文字を識別し、
   前記第２の重みの値は、前記文字のアクセント符号を特定することができ、
   前記第３の重みの値は、前記文字の大文字小文字の区別情報を特定することができ、
   前記照合要素はサイズが４バイトであり、そのうちの第１および第２のバイトは前記第１の重みフィールドであり、第３のバイトは前記第２の重みフィールドであり、第４のバイトは前記第３の重みフィールドであり、前記第１の重みフィールドの値が前記確保された値のセットに属する場合、前記第３および第４のバイトは、前記第１の重みフィールドの拡張部分であり、
   拡張された前記第１の重みフィールドは、中国、日本および韓国の文字を表わすために用いられ、文字の数は、１６ビットで表現可能な最大の数である６５，５３６よりも多い、装置。
2. 前記照合要素は、文字を照合の重みにマップして文字列間の順序付けを確立するために
   使用される照合重みテーブルからとられる、請求項１に記載の装置。
3. 列についてのソートキーを構築するためのキー構築機構をさらに含み、前記キー構築機構は、
   前記列内の各文字を読取り、
   前記照合重みテーブルから各文字についての対応する照合要素を参照し、
   各文字についての前記対応する照合要素を前記ソートキーに追加するように構成される、請求項２に記載の装置。
4. 前記ソートキーは、データベース内の記録に関連付けられ、
   前記ソートキーは、前記データベースの言語インデックスを構築するために使用される、請求項３に記載の装置。
5. 多数の文字をサポートする照合要素の使用を容易にするための方法であって
   コンピュータが、前記照合要素を受取るステップと、
   前記コンピュータが、前記照合要素内の第１の重みフィールドから第１の重みの値を読取るステップと、
   前記第１の重みの値がある確保された値のセット内にある場合、前記コンピュータが、前記照合要素内の全てのビットを含むように前記第１の重みフィールドを拡張するとともに、前記第２の重みの値を第２のデフォルト値にセットし、前記第３の重みの値を第３のデフォルト値にセットするステップと、
   前記第１の重みの値が前記確保された値のセット内にない場合、
   前記コンピュータが、前記照合要素内の前記第２の重みフィールドから第２の重みの値を読取るステップと、
   前記コンピュータが、前記照合要素内の前記第３の重みフィールドから第３の重みの値を読取るステップとを含み、
   前記第１の重みフィールドの大きさに応じて前記照合要素により表わされる文字の数が増加し、
   前記第１の重みの値についての前記確保された値のセットは、１６進法の値０ｘＦＦＦ０〜０ｘＦＦＦＦを含み、
   前記第１の重みの値は、ある文字を識別し、
   前記第２の重みの値は、前記文字のアクセント符号を特定することができ、
   前記第３の重みの値は、前記文字の大文字小文字の区別情報を特定することができ、
   前記照合要素はサイズが４バイトであり、そのうちの第１および第２のバイトは前記第１の重みフィールドであり、第３のバイトは前記第２の重みフィールドであり、第４のバイトは前記第３の重みフィールドであり、前記第１の重みフィールドの値が前記確保された値のセットに属する場合、前記第３および第４のバイトは、前記第１の重みフィールドの拡張部分であり、
   拡張された前記第１の重みフィールドは、中国、日本および韓国の文字を表わすために用いられ、文字の数は、１６ビットで表現可能な最大の数である６５，５３６よりも多い、方法。
6. 前記照合要素は、文字を照合の重みにマップして文字列間の順序付けを確立するために使用される照合重みテーブルからとられる、請求項５に記載の方法。
7. 列内の各文字を読取るステップと、
   前記照合重みテーブルから各文字の対応する照合要素を参照するステップと、
   各文字の前記対応する照合要素を前記ソートキーに追加するステップとによって、前記コンピュータが、前記列についてのソートキーを構築するステップをさらに含む、請求項６に記載の方法。
8. 前記ソートキーは、データベース内の記録に関連付けられ、
   前記ソートキーは、前記データベースの言語インデックスを構築するために使用される、請求項７に記載の方法。
9. コンピュータによって実行されると、多数の文字をサポートする照合要素の使用を容易にする方法を前記コンピュータに行なわせる命令を記憶するコンピュータ読取可能な記憶媒体であって、前記方法は、
   前記コンピュータが、前記照合要素を受取るステップと、
   前記コンピュータが、前記照合要素内の第１の重みフィールドから第１の重みの値を読取るステップと、
   前記第１の重みの値がある確保された値のセット内にある場合、前記コンピュータが、前記照合要素内の全てのビットを含むように前記第１の重みフィールドを拡張するとともに、前記第２の重みの値を第２のデフォルト値にセットし、前記第３の重みの値を第３のデフォルト値にセットするステップと、
   前記第１の重みの値が前記確保された値のセット内にない場合、
   前記コンピュータが、前記照合要素内の前記第２の重みフィールドから第２の重みの値を読取るステップと、
   前記コンピュータが、前記照合要素内の前記第３の重みフィールドから第３の重みの値を読取るステップとを含み、
   前記第１の重みフィールドの大きさに応じて前記照合要素により表わされる文字の数が増加し、
   前記第１の重みの値についての前記確保された値のセットは、１６進法の値０ｘＦＦＦ０〜０ｘＦＦＦＦを含み、
   前記第１の重みの値は、ある文字を識別し、
   前記第２の重みの値は、前記文字のアクセント符号を特定することができ、
   前記第３の重みの値は、前記文字の大文字小文字の区別情報を特定することができ、
   前記照合要素はサイズが４バイトであり、そのうちの第１および第２のバイトは前記第１の重みフィールドであり、第３のバイトは前記第２の重みフィールドであり、第４のバイトは前記第３の重みフィールドであり、前記第１の重みフィールドの値が前記確保された値のセットに属する場合、前記第３および第４のバイトは、前記第１の重みフィールドの拡張部分であり、
   拡張された前記第１の重みフィールドは、中国、日本および韓国の文字を表わすために用いられ、文字の数は、１６ビットで表現可能な最大の数である６５，５３６よりも多い、コンピュータ読取可能な記憶媒体。
10. 前記照合要素は、文字を照合の重みにマップして文字列間の順序付けを確立するために使用される照合重みテーブルからとられる、請求項９に記載のコンピュータ読取可能な記憶媒体。
11. 前記方法は、
    列内の各文字を読取るステップと、
    前記照合重みテーブルから各文字についての対応する照合要素を参照するステップと、
    各文字についての前記対応する照合要素を前記ソートキーに追加するステップとによって、前記コンピュータが、前記列についてのソートキーを構築するステップをさらに含む、請求項１０に記載のコンピュータ読取可能な記憶媒体。
12. 前記ソートキーは、データベース内の記録に関連付けられ、
    前記ソートキーは、前記データベースの言語インデックスを構築するために使用される、請求項１１に記載のコンピュータ読取可能な記憶媒体。

Images