AutoNumber関数周辺についての本当に詳しい解説2(ハッシュ編)

AutoNumber関数周辺についての本当に詳しい解説2(ハッシュ編)

Pocket

前回の記事につづき、QlikViewやQlik Senseの関数である「AutoNumber関数」について、深く掘り下げて見ていきましょう。
前回の「カウンタ編」では、RowNo関数、RecNo関数、AutoNumber関数についてご覧いただきました。
今回の「ハッシュ編」では、Hash128関数、Hash160関数、Hash256関数、AutoNumberHash128関数、AutoNumberHash256関数についてご覧いただきます。

これらの関数は、関数名が「Hash」ではじまるもの(Hash128関数、Hash160関数、Hash256関数)と、関数名が「AutoNumberHash」ではじまるもの(AutoNumberHash128関数、AutoNumberHash256関数)の、2つに大別できます。
それではまず、Hash関数の方から見ていきましょう。

Hash128関数、Hash160関数、Hash256関数


ハッシュとはなにか?

QlikViewやQlik SenseのHash関数について説明する前に、まずハッシュとは何なのか簡単に説明します。
ハッシュ自体は、QlikViewやQlik Sense特有のものではなく、他のツールやプログラミング言語などにもあるものです。

ハッシュ(ハッシュ関数)とは、かなり簡単にまとめると、ある文字列を規則性のない別の文字列に置き換える仕組みのことです。
元の文字列がすこしでも違えば、結果の文字列はまったく別のものになります。また、結果の文字列から元の文字列を推測することはできません。

一般的に使用されているハッシュ関数(MD5、SHA-1、SHA-2など)でも、QlikViewやQlik SenseのHash関数でも、結果の文字列は固定長です。固定長とは常に文字列の桁数がおなじという意味です。

ご注意
この部分は正確な説明をかなり省略しています。たとえば、”規則性のない”というのは元の文字列を推測できないという意味で、実際はある規則にもとづいて計算されています。実行するたびに結果が変わる乱数ではありません。
また、元の文字列を推測できないというのは、推測が難しいという意味であって、絶対に推測できないという意味ではありません。
ハッシュについて正確に理解するには、コンピュータ科学の専門的な知識が必要です。上の説明をはじめ、この記事の中にはコンピュータ科学の観点で言えば、正確でない記述が含まれていることをあらかじめご了承ください。


ハッシュについては、オンラインで試せるツールがありますので、早速使ってみましょう。
Hash function – tools.timodenk.com
テキストボックスになにか文字列を入力し、「Hash」ボタンをクリックすると、すぐ下に結果が表示されます。
中央のドロップダウンでは、ハッシュのアルゴリズム(ハッシュ関数の種類)を選択できます。ここでは「MD5」と呼ばれるものを選択しています。

「a」と入力すると、「0cc…」という長い文字列(正確には32桁の文字列)が表示されます。これがハッシュ関数によって生成された結果の文字列です。この文字列のことを「ハッシュ値」と呼びます。

以下が実行結果の例です。
元の文字列結果の文字列(MD5のとき)説明
a0cc175b9c0f1b6a831c399e269772661 
sample5e8ff9bf55ba3508199d22e984129be6元の文字列が一文字でも変われば、まったく違う結果を返します。
simple8dbdda48fb8748d6746f1965824e966a
Samplec5dd1b2697720fe692c529688d3f4f8d大文字小文字が変わっただけでも、まったく違う結果を返します。
Qlik Sense DesktopやQlikView Personal Editionは、無料で使えるBIツールです。c18446197055a9a62691e2faf0cf2ea4どんなに長い文字列でも結果の文字数は変わりません。
8c0c3027e3cfc3d644caab3847a505b0日本語や数字でもおなじです。
1c4ca4238a0b923820dcc509a6f75849b
(空文字)d41d8cd98f00b204e9800998ecf8427e空文字、半角ブランク、全角ブランクもすべて違う結果を返します。
 (半角ブランク)7215ee9c7d9dc229d2921a40e899ec5f
 (全角ブランク)1920baf9665480a79df488e00e69530a

オンラインで使えるツールには、他にも以下のようなものがあります。
hashr – the hash maker
MD5 create hash online – Hash & Encryption
「ハッシュ オンライン」などのキーワードで、Web上を検索すれば他にも見つかると思います。

以上、ここまでがハッシュの概要です。
ハッシュのアルゴリズムなどの話は非常に難しいのですが、ハッシュというのが大体どのようなものかはお分かりいただけたかと思います。

それでは、QlikViewやQlik Senseのハッシュについて見ていきましょう。

QlikViewやQlik SenseのHash関数

QlikViewやQlik Senseには、Hash128関数、Hash160関数、Hash256関数の3つのHash関数があります。
末尾の「128」「160」「256」は、ハッシュの計算で使用される値の桁数(ビット数)をあらわしています。たとえばHash128関数は内部的に128ビットの値を使用しているということになります。

“ハッシュのビット数”というのは内部的な処理の話ですので、ここでは単純に、結果の文字列の長さが違うと認識しておけば問題ありません。
逆に言うと、これら3つの関数の違いは結果の文字列の長さのみで、指定方法や用途に違いはありません。
関数名結果の文字列の長さ
Hash128関数22桁
Hash160関数27桁
Hash256関数43桁

実行結果の例
Hash128('a') IFU@3:'%))D]/FM==R=2_%
Hash160('a') IFU@3:'%))D]/FM==R=2_1IK4Y-
Hash256('a') IFU@3:'%))D]/FM==R=2_1IK4Y-D_!=PWV?U]-RN(II

使用される文字の種類は以下のとおりです。
英大文字26種類: ABCDEFGHIJKLMNOPQRSTUVWXYZ
数字10種類: 0123456789
記号28種類: ‘-!”#$%&()*,./:;?@[]^_`\+<=>
ご注意
使用される文字の一覧はヘルプに記載されていなかったため、独自に検証して確認しました。
検証に使用したロードスクリプトは、この記事の最後に掲載しています。


Hash関数の動作確認

それでは、QlikViewやQlik SenseでHash関数の動作を確認してみましょう。
今回は簡単なロードスクリプトのサンプルを用意してあります。インラインロードを使用して、データ値をスクリプト中に埋め込んでいるため、ロードスクリプトの編集画面にそのまま貼り付けてご利用いただけます。

Qlik Senseのデータロードエディタ(QlikViewのロードスクリプトの編集画面)に、以下のロードスクリプトを貼り付けて実行してください。
LOAD RowNo() as RowNo,
     元の文字列,
     説明,
     Hash128(元の文字列) as Hash128,
     Hash160(元の文字列) as Hash160,
     Hash256(元の文字列) as Hash256;
LOAD * INLINE [
    元の文字列, 説明
    a, 
    sample, 
    simple, 
    Sample, 
    Qlik Sense DesktopやQlikView Personal Editionは、無料で使えるBIツールです。, 
    あ, 
    1, 
    '', 空文字
    ' ', 半角ブランク
    ' ', 全角ブランク
];
Qlik Senseのテーブル(QlikViewのテーブルボックス)で、結果を確認します。
先ほどのオンラインツールと結果の文字列は異なりますが、ハッシュの原理(規則性のない文字列を返す、固定長の文字列を返すなど)は変わりません。


複数の文字列からハッシュ値を生成する

QlikViewやQlik SenseのHash関数では、以下のように複数の文字列を指定できます。
Hash128(<文字列1>, <文字列2>, ..., <文字列n>)
このように指定することで、複数の文字列からハッシュ値を生成します。言い換えると、複数の値の組み合わせが、一部でも違うと異なる結果を返すということです。
これは、つぎに説明するAutoNumberHash関数においても重要なポイントですので、覚えておいてください。

では、先ほどとおなじようにサンプルのロードスクリプトで動作を確認してみましょう。
LOAD RowNo() as RowNo,
     F1,
     F2,
     Hash128(F1, F2) as Hash128,
     Hash160(F1, F2) as Hash160,
     Hash256(F1, F2) as Hash256;
LOAD * INLINE [
    F1, F2
    001, 01
    001, 02
    002, 01
    002, 01
    002, 02
];
この例では、項目F1と項目F2の組み合わせからハッシュ値が生成されます。
Hash128(F1, F2)
上図で3行目と4行目はF1とF2の値が一致していますので、ハッシュ値もおなじになります。
それ以外はハッシュ値はすべて異なります。F1だけがおなじ場合やF2だけがおなじ場合は、生成されるハッシュ値は異なるということです。

以上、ここまでがHash関数の基礎についてです。
ハッシュの原理や、Hash関数の指定方法についてご理解いただけたと思います。
ここからは、規則性のない文字列を生成することになんの意味があるのか、具体的な使用例を2つ紹介いたします。


Hash関数の使用例1(値のマスキング)

まず、規則性のない文字列を生成するといってすぐに思いつくのは、値のマスキングです。たとえば、氏名や住所などの個人情報を非公開にしたい場合などが考えられます。
値を非公開にしたい場合に、単純に値を削除したり、または固定の文字列(****といった伏字など)に置き換えたりすると、値の区別がつかなくなってしまいます。

値の区別はしたいが、元の値は判別できなくしたいという場合は、Hash関数で文字列をマスキングするとよいでしょう。
“値は区別したい”の意図は、たとえばキーとして使用したい場合や、一意の件数を数えたい(Count Distinctしたい)場合が挙げられます。

指定例は以下のとおりです。
LET Salt = Rand(); //Rand関数で乱数を生成しています。
LOAD Hash256($(Salt), 顧客名),
:
FROM Table1;
LOAD Hash256($(Salt), 顧客名),
:
FROM Table2;
顧客名はHash関数により隠蔽されますが、おなじ顧客名はおなじハッシュ値になるため、キーとして使用したり、一意の件数を数えたりできます。
また、ここではRand関数を組み合わせることで、ロードスクリプトを実行するたびにハッシュ値が変わるようにしています。


Hash関数の利用例2(恒久的なキーの作成)

前回の記事で、AutoNumber関数でキーを作成する際の注意事項について説明しました。
注意事項2 おなじロードスクリプトから実行した場合のみ、キーとして使用できる
AutoNumber関数はデータを読み込んだ順に連番を振っていくため、別のロードスクリプトで作成されたキーでは関連付けができないという問題です。

あらためてヘルプの注意事項を確認してみると、Hash関数について言及されています。
autonumber – スクリプト関数 ‒ Qlik Sense
「!」の注意事項を再確認してください。以下はヘルプからの引用です。

autonumberキーは、テーブルが読み込まれた順番で生成されるため、おなじデータ ロードで生成された場合のみ結合できます。ソース データのソート処理から独立してデータ ロード間で恒久的に維持されるキーを使用する必要がある場合は、hash128関数、hash160 関数、hash256 関数を使用する必要があります。

「恒久的に維持されるキーを作成したい場合は、Hash関数を使用する」とのことです。
ここで言う、”恒久的に維持されるキー”というのは、実行するたびに1から連番を振る仕組みなどではなく、常におなじ値になるものという意味です。
テーブルや項目、アプリが違っても、おなじ値にはおなじ結果を返すという意味です。まさにHash関数の動作ですね。

ただし、Hash関数は単純にAutoNumber関数に置き換わるものではありません。
AutoNumber関数でキーを作成する利点として、データのサイズを小さくできるという点があります。長い文字列のキーを単純な連番に置き換えることで、データのサイズを小さくできます。
Hash関数は最小のHash128関数でも22桁の文字列ですので、AutoNumber関数で作成されたキーと比べるとデータのサイズは大きくなります。

まとめると、以下のような場合は、AutoNumber関数ではなくHash関数でキーを作成することを検討してください。
・ロードスクリプトが複数に分かれているため、AutoNumber関数ではキーを作成できない。
・元の文字列の桁数が長い(22桁を超える)ため、Hash関数でデータのサイズを節約したい。
・そのデータ自体は不要(またはマスキングしたい)場合。
たとえば、複数のシステムにまたがって使用されているお客様のメールアドレスなどは、この条件に合致することがあると思います。

以上でHash関数の説明は終了です。
指定方法や用途などをご理解いただけましたでしょうか。

つづいては、AutoNumberHash関数について見ていきましょう。

AutoNumberHash128関数、AutoNumberHash256関数

AutoNumberHash関数には、AutoNumberHash128関数とAutoNumberHash256関数の2種類があります。
末尾の「128」「256」はHash関数とおなじように、ハッシュの計算で使用される値の桁数(ビット数)をあらわしています。

Hash関数は「128」「160」「256」の3種類あるのに対し、AutoNumberHash関数は「128」と「256」の2種類のみです。
なぜ、Hash関数にだけ「160」があるのか疑問に思われるかもしれませんが、そういうものだと覚えてください。

AutoNumberHash128関数とAutoNumberHash256関数は、前回ご覧いただいたAutoNumber関数とおなじように、ある値から連番の項目を作成します。
AutoNumber関数との違いは、内部的にハッシュを使用していることです。


AutoNumber関数とAutoNumberHash関数の違い

内部的にハッシュを使用することでなにが違うかというと、AutoNumberHash関数はHash関数とおなじように複数の値を指定できます。
AutoNumberHash128(<項目1>, <項目2>, ..., <項目n>)
これにより、複数の項目の組み合わせが一意になるように連番が作成されます。
そのため、複合キー(複数の項目がキー項目になっている)を、単一のキーに置き換える場合に使用できます。

AutoNumber関数でも区切り文字を連結するなどして、複合キーを単一のキーに置き換えることはできます。
AutoNumber(項目1 & '-' & 項目2)

しかし、AutoNumberHash関数であれば、そもそも区切り文字などを意識する必要がありません。
AutoNumberHash128(項目1, 項目2)

もう一点、AutoNumber関数とAutoNumberHash関数では、Null値の扱いが異なる点にも注意してください。
Hash関数はNull値にも文字列を割り当てます。これに対して、AutoNumber関数はNull値にはNull値を返します。

実行結果の例
Hash128(Null()) NI<!H%G$DCY?<.=_`KMG).
AutoNumber(Null()) Null値
AutoNumberHash128(Null()) 1などの連番
これは、AutoNumberHash関数で関連付けのキーを作成している場合に注意が必要です。
もとの値がNull値のもの同士で、関連付けがおこなわれるためです。

これを回避するには、以下のような数式でNull値のチェックをしてください。
If(IsNull(項目1) or IsNull(項目2), Null(), AutoNumberHash128(項目1, 項目2)) as キー;


AutoNumberHash128関数とAutoNumberHash256関数の違い

前述のとおり、Hash関数はハッシュのビット数で結果の文字列の長さが変わります。たとえば、Hash128関数は22桁、Hash256関数は44桁の文字列を返します。
これに対して、AutoNumberHash128関数とAutoNumberHash256関数は、数値の連番を返しますので結果に違いはありません。
つまり、これら2つの関数で違うのは内部的な処理のみということになります。

では内部的な処理によってなにが変わるかと言うと、内部的に128ビットのハッシュを使うか、256ビットのハッシュを使うかによって、”生成できる値の数”が変わります。
しかし、QlikViewやQlik Senseにおいては”生成できる値の数”が違うというよりも、”値の衝突が発生する確率”が違うと捉えた方がいいでしょう。

この点について説明していきます。

・生成できる値の数は十分大きいため制約とならない
128ビットのハッシュと256ビットのハッシュでは、値の桁数(ビット数)が違うため生成できる値の数が異なります。
しかし、128ビットのハッシュでもQlikViewやQlik Senseで使用するのに十分な数の値が生成できます。

具体的に書きます。
128ビットのハッシュで生成できる値の数は、2の128乗です。計算すると約3.4 x 1038(10の38乗)種類の値が生成できることになります。
日本語の単位で言うと、”京”を2回掛け合わせたよりも大きな数です。

これに対して、QlikViewやQlik Senseには、一意の値の件数は約21億個までという制限があります。
これは、QlikViewやQlik Senseが内部的に32ビットのインデックスを使用しているためです。
ロードするデータ量の制限 ‒ QlikView
※21億というのは、あくまで一意の値の件数です。1項目につき21億”種類の”値が持てるということです。データの件数は21億件以上保持できます。

つまり、128ビットのハッシュでもQlikViewやQlik Senseで使用するのに、十分な数の値が生成できるということになります。

・値の衝突が発生する確率について
繰り返しになりますが、元の値が異なれば結果の値も異なるというのが、ハッシュ関数の特性です。

しかしこの特性も完璧ではありません。
ある文字列を別の文字列に置き換える以上、衝突が発生する可能性があります。
衝突というのは、元の値が異なるのに、結果の値がおなじになってしまうということです。
※ハッシュ関数で非常に多くの値を生成できるといっても、その数は有限です。それに対して元の値のパターンは無限に考えられますので、衝突をゼロにはできません。


しかしながら、衝突の可能性がわずかであるというのが、ハッシュ関数の特性です。
これ以上は、コンピュータ科学や数学の話になるため非常に難しいのですが、簡単に概要を理解するにはWikipediaの以下のページが参考になります。
誕生日攻撃 – Wikipedia
途中の説明や数式は、正直わたしもまったく分かりませんが、一番下の表と説明が参考になります。

以下はWikipediaからの引用です。

128ビットのMD5を文書のチェックサムとして使用する場合、8200億個の文書までならハードディスクでの誤り発生確率の範囲内に収まると言える

誕生日攻撃」『フリー百科事典 ウィキペディア日本語版』(http://ja.wikipedia.org/)。2017年3月15日16時(日本時間)現在での最新版を取得。

“8200億個の文書”とありますが、この部分は”8200億件のデータ”に置き換えてもおなじはずです。
また、”ハードディスクでの誤り発生確率”というのは、上の表によると10−15(10のマイナス15乗)のようです。

このことから以下のことが言えます。
128ビットのハッシュを使用する場合、データの件数が8200億件までであれば、衝突の確率は10−15(10のマイナス15乗)以内に抑えられる。

256ビットのハッシュを使用する場合、データの件数が1.5 × 1031(10の31乗)件までであれば、衝突の確率は10−15(10のマイナス15乗)以内に抑えられる。

値が大きすぎて、これがどの程度の確率なのか実感が湧きませんが、もはや狙って制御できるレベルの話でないことはわたしにも理解できます。

このことから、128ビットのハッシュでも十分なので、AutoNumberHash128関数を使うという考え方もあるでしょうし、念のためAutoNumberHash256関数を使うという考え方もあると思います。
いずれにしても、用途に応じて使い分けるようなものではないということは、お分かりいただけたかと思います。

以上でAutoNumberHash関数については終了です。
お疲れ様でした。


最後に…

2回に渡って、AutoNumber関数とそれにまつわる関数の詳細についてご覧いただきました。
前回の記事の冒頭に書いたとおり、”みなさまが普段何となく気になっているであろう疑問に、できるかぎり詳しくお答えする”ということを目標に、できる限り詳しく書いてみましたが、いかがだったでしょうか。

途中ハッシュ関数などについても言及しましたので、かなりマニアックな内容になっていたかと思います。
最後までお読みいただいた方は、本当にありがとうございました。



ロードするデータ量の制限 ‒ QlikView
http://help.qlik.com/ja-JP/qlikview/12.1/Content/limitations.htm
QlikViewのヘルプです。
一意の件数の制限が、約21億であることが書かれています。

誕生日攻撃 – Wikipedia
https://ja.wikipedia.org/wiki/%E8%AA%95%E7%94%9F%E6%97%A5%E6%94%BB%E6%92%83

Memory sizes for data types | Qlikview Cookbook
http://qlikviewcookbook.com/2008/05/memory-sizes-for-data-types/
QlikViewで使用されるデータ型ごとの、データサイズがまとめられています。
最後の「Sequential Integer Optimization」に、AutoNumber関数を使用してデータ容量がゼロになることの詳細がまとめられています。(英語)

QlikView hash functions and collisions – The Qlik Fix! The Qlik Fix!
http://www.qlikfix.com/2014/03/11/hash-functions-collisions/
QlikViewのHash関数について、非常に詳しくまとめられています。(英語)


検証用のロードスクリプトを以下にまとめます。

検証用ロードスクリプト


Hash関数で使用される文字の検証用スクリプト

Hash関数で使用される文字にどのようなものがあるのか、確認するためのスクリプトです。
Rand関数で乱数を生成し、そこからハッシュ値を生成しています。
LOAD RowNo() as RowNo,
    Mid(Hash128(Rand()), Ceil(Rand() * 22), 1) as Hash128Chr,
    Mid(Hash160(Rand()), Ceil(Rand() * 27), 1) as Hash160Chr,
    Mid(Hash256(Rand()), Ceil(Rand() * 43), 1) as Hash256Chr
AutoGenerate 100000;
本編で説明したとおり、Hash関数で使用される文字の一覧はヘルプに記載されていないため、独自に検証しています。
しかし、使用される文字種の数とハッシュ値の桁数から、生成できるハッシュ値の数を考えると、本編に掲載の文字種で間違いなさそうです。
英大文字A-Z 26種類、数字0-9 10種類、記号28種類の計64種類。

たとえばHash128関数は22桁の結果を返すため、生成できるハッシュ値の数は、64種類の文字が22桁あることから、64の22乗 = 2の132乗となり、128ビットのハッシュで生成できるハッシュ値の数である2の128乗をちょうど超えます。

Hash128関数(22桁) 64 ^ 22 = 2 ^ 132 > 2 ^ 128
Hash160関数(27桁) 64 ^ 27 = 2 ^ 162 > 2 ^ 160
Hash256関数(44桁) 64 ^ 44 = 2 ^ 264 > 2 ^ 258
※^を累乗の記号として記述しています。