HyperLogLog Implementation in Redis, pt.2

Redis: HyperLogLog の実装について その2

 

前回、Redis の HyperLogLog に 対して "A", "B", "C" という 3つの文字列を与えると
registers に 0x51, 0x7c, 0x88, 0x5e, 0xc1, 0x80, 0x42, 0x62, 0x88, 0x4d, 0x5a というバイト配列が格納された。

今回は、sparse 表現の実装をより詳しく見ていくことにする。

 

ハッシュ関数とレジスタ

そもそも Redis におけるレジスタとは何なのか。
ソースコードのコメントには、HyperLogLog型のキーは 16,384個の 6ビットレジスタで表現されるとある。

従って、キー 1個あたり
6 bit x 16,384 = 98,304 bit = 12,288 Byte = 12 KB
でカーディナリティが表現されることになる。

 

レジスタ値の求め方

任意のバイト配列から、記録すべきレジスタのインデックスと 6ビットの値を求める手順は以下のとおり。

• 入力に対して 64ビット版の MurmurHash2 アルゴリズムを適用し、
  ハッシュ値 (64ビット符号無し整数値) を得る
  
  • MurmurHash とは、衝突困難性と一様性に優れ、MD5 よりも高速なハッシュ関数
  • 実際の実装ではエンディアン・ニュートラル (ビッグエンディアンにもリトルエンディアンにも対応可能) に改変されている
• ハッシュ値の下位 14ビットの値をレジスタ・インデックスとして使う
  
  • 0 〜 16383 の値が得られ、何番目の箱にレジスタをセットするかが決まる。
• ハッシュ値の 下位から数えて 15ビット目から上位へ向かってビットを走査し、初めて「1」が登場する位置を調べる(=「0」のビットが何個連続しているかを数え、1を足す)
  
  • ただし、最上位のビットにはあらかじめ「1」をセットしておく
  • 1 〜 50 の値が得られ、これがレジスタの値となる
  • この値が 33 以上だった場合、sparse 表現ができないので自動的に dense 表現に変換される。

 

ランレングス圧縮

sparse 表現とは、すなわち上記のレジスタ情報をランレングス圧縮したバイト列である。

それは、Redis 独自の以下3種類のオペコードで構成される。

ZERO

00xxxxxx という 1バイトの表現。
xxxxxx を 6ビットの符号無し整数として解釈し、1 を足す。(1 <= x <= 64 とする)
「x」の個数ぶん、値が「0」のレジスタが連続していることを示す。

XZERO

01xxxxxx yyyyyyyy という 2バイトの表現。
xxxxxxyyyyyyyy を 14ビットの符号無し整数として解釈し、1 を足す。(1 <= x <= 16384 とする)
「x」の個数ぶん、値が「0」のレジスタが連続していることを示す。

VAL

1vvvvvxx という 1バイトの表現。
vvvvv を 5ビットの符号無し整数、xx を 2ビットの符号無し整数として解釈し、それぞれ 1 を足す。
(1 <= v <=32, 1 <= x <= 4 とする)
「x」の個数ぶん、値が「v」のレジスタが連続していることを示す。

 

読み解いてみる

冒頭の例をランレングス圧縮のオペコードに読み替えてみると、以下のようになる。

• 0x51, 0x7c => 0b01010001, 0b01111100 => XZERO:4477
• 0x88 => 0b10001000 => VAL:3,1
• 0x5e, 0xc1 => 0b01011110, 0b11000001 => XZERO:7874
• 0x80 => 0b10000000 => VAL:1,1
• 0x42, 0x62 => 0b01000010, 0b01100010 => XZERO:611
• 0x88 => 0b10001000 => VAL:3,1
• 0x4d, 0x5a => 0b01001101, 0b01011010 => XZERO:3419

従って、レジスタの状態は index:4477 -> 3、index:12352 -> 1、index:12964 -> 3 がセットされており
他は全てゼロであることがわかった。

レジスタの個数も、4477 + 1 + 7874 + 1 + 611 + 1 + 3419 = 12964 とピッタリ合っている。

実際、入力した 3個の文字列は

• A: index:12352 -> 1
• B: index:12964 -> 3
• C: index:4477 -> 3

に対応している。

 

 

Related Posts

• mog project: HyperLogLog Implementation in Redis, pt.1

Getting Started with AquaSKK

Aqua SKK を使う

 

日本語入力メソッドして、SKK を使いたい。(実は過去に一度使ったことがあるが挫折したので再挑戦)
Mac では Aqua SKK という実装があるのでそれを導入する。

 

環境

• OS X Yosemite: Version 10.10.3
• AquaSKK 4.2.5




SKK とは

Simple Kana to Kanji conversion program の略。形態素解析をユーザーが明示的に行うことで、変換ミスのストレスを軽減させることができるという非常にユニークな日本語入力メソッドだ。

詳しくは以下のリンク先を参照。

• SKKとは (エスケイケイとは) [単語記事] - ニコニコ大百科

 

セットアップ方法

 

インストール

公式ページはこちら

• AquaSKK - 日本語を快適に

だが、現在は GitHub 上で開発が進められている。 ここ

• Releases · codefirst/aquaskk

からダウンロード可能な最新版の dmg ファイルを実行するとよい。

インストールの完了にはログアウトが必要。

 

IME追加

• System Preferences -> Keyboard -> Input Sources と選択
• Japanese -> AquaSKK 統合を追加
• Command + Space で IME AquaSKK統合を有効化




AquaSKK のカスタマイズ

• メニューバー -> AquaSKK統合 -> 環境設定
• 入力設定 -> 入力操作: 「Enter による確定で改行しない」にチェックを入れると
  より流れるようなタイピングができる
• キーバインドの衝突の解消
  
  • iTerm2: iTerm2/Apple TerminalでAquaSKKを使う - みずぴー日記
  • 試してみたものの、統合モードのせいか、やはり iTerm2 の中で C-j が動作せず……

 

Sticky shift と SandS

SKK はシフトキーを多用する入力メソッドである。
そこで実際の SKK ユーザの大半は、シフトキーを押さなくてもシフトを実現できるような工夫をしている。

Sticky shift

特定のキーを押すことで、直後のキーを Shift オンの状態で入力できるようにする機能。
例えば、セミコロン「;」をスティッキーキーに指定した場合、「;foo;bar」と打鍵すると「FooBar」と入力されるようになる。(セミコロンなのは英語キーボードを使っているため)

Mac では、Karabiner (旧名 KeyRemap4MacBook) でその機能を実現できる。

• Karabiner - OS X用のソフトウェア
• Change Key -> For Japanese -> Change Semicolon(;) Key
  -> Semicolon to Sticky Shift_L (effective only when input source is Japanese)
  にチェックを付ければよい
  
  
• ただ、この場合 IME オンかつASCIIモードの場合にセミコロンを入力できなくなるのだが
  どうしたらいいものか。

 

SandS

Shift and Space。スペースキーと同時に他のキーを押した場合に Shift オンの状態にする。
親指でシフトを押せるようになるのがポイントだが、試したことはない。

 

基本的な入力方法

この資料が素晴らしい。

• No skk, no life.

 

かな入力モード

• 英数入力モード、全角英数入力モードで Ctrl-j
• q キーで「ひらがな」「カタカナ」を切り替え
• カタカナの入力自体は、読み入力モードで q を押すことでも対応可

英数入力モード

• かな入力モードで l

全角英数入力モード

• かな入力モードで Shift-L

読み入力(▽)モード

• 変換が必要な場合
• かな入力モードで Shift を押しながら単語の一打目を入力
• かな入力モードで Shift-Q
• かな入力モードで スラッシュ(/) を押すと英数字で読みを入力可能
• Ctrl-g でキャンセル
• Tab キーで見出し語の補完
• Space キーで変換モードへ

変換(▼)モード

• 候補送り: Space
• 候補戻り: x
• ユーザ辞書に登録した単語の削除: Shift-x
• 次の文字を入力するか、Ctrl-j で確定
• Ctrl-g で読み入力モードに戻る

単語登録

• 読み入力モードで候補送りし続ける
• クリップボードから貼り付け: Ctrl-y
• Ctrl-g で変換モードに戻る

変換ルール

• デフォルトのルール
  
  

  $ cat /Library/Input\ Methods/AquaSKK.app/Contents/Resources/kana-rule.conf |nkf
  # $Id$
  
  # このファイルは改行コードがLF、文字エンコーディングがEUC-JPでなければなりません。
  # 五つ目の項目は次状態です。無ければ項目自体を省略します。
  # エントリの順序には気を付けて下さい。例えば「ba」というエントリに出会うと、
  # AquaSKKはまず「b」という枝を探しますが、ここではまだ存在しないので
  # 「b」という空の枝を作成します。この後に「b」というエントリが現れると
  # そのエントリ「b」は既に定義されているのでどうなるか分かりません。
  
  # 最初の項目の,は半角カンマに置換されます。
  
  a,あ,ア,ア
  
  bb,っ,ッ,ッ,b
  ba,ば,バ,バ
  bi,び,ビ,ビ
  bu,ぶ,ブ,ブ
  be,べ,ベ,ベ
  bo,ぼ,ボ,ボ
  
  (snip)
  ...

• ぁぃぅぇぉっ: xa xi xu xe xo xtu
• ‥ … ・ 〜 『 』: z, z. z/ z- z[ z]
• ← ↓ ↑ →: zh zj zk zl

 

辞書の拡張

このあたりを使うと便利そう。

• Google IME SKK サーバー 作った - hitode909の日記

HyperLogLog Implementation in Redis, pt.1

Redis: HyperLogLog の実装について その1

だいぶ古い話だが、Redis 2.8.9 で新しいデータ構造 HyperLogLog が登場した。
その実装コードを読む。

• redis/hyperloglog.c at unstable · antirez/redis

（そして、モック作り に活かしたい）

2種類のデータ構造

Redis では、dense(密) と sparse(疎) の 2種類のデータ構造をシームレスに切り替えることで、最小限に近い空間計算量での高精度カーディナリティ推定を可能としている。

また、これらはいずれも STRING 型とよく似たデータ構造 (つまりバイト配列) をなしており、get コマンドを利用することでその実体を窺い知ることができる。

ヘッダの読み方

まずは実際に動かしてみる。

127.0.0.1:6379> get hll
(nil)
127.0.0.1:6379> pfadd hll A B C
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 3
127.0.0.1:6379> strlen hll
(integer) 27
127.0.0.1:6379> get hll
"HYLL\x01\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00Q|\x88^\xc1\x80Bb\x88MZ"




get で表示されたデータの先頭 16 bytes がヘッダとして定義されているもの。

struct hllhdr {
    char magic[4];      /* "HYLL" */
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* Reserved for future use, must be zero. */
    uint8_t card[8];    /* Cached cardinality, little endian. */
    uint8_t registers[]; /* Data bytes. */
};

• magic: 最初の4文字は、データが HyperLogLog であることを示す固定値「HYLL」が入る。
• encoding: 次の1バイトは、データ構造を示すフラグ。
  上記のように「\x01」であれば sparse(疎)、「\0x00」なら dense(密) を表す。
• notused: 将来のために確保されている、未使用の領域が3バイトほど続く。
• card: カーディナリティの値が64bitぶん、リトルエンディアンで保存されている。
  今回の場合は「0x03」「0x00」「0x00」「0x00」「0x00」「0x00」「0x00」「0x00」なので、
  カーディナリティ 3 を表す。

そして、registers の部分が HyperLogLog のデータそのもの。

今回の例では、「Q|\x88^\xc1\x80Bb\x88MZ」の部分 (11 bytes) がそれに該当する。

16進数表記をすれば、順に
「51, 7c, 88, 5e, c1, 80, 42, 62, 88, 4d, 5a」
である。

References

• HyperLogLog - Wikipedia, the free encyclopedia
• 元の論文

• 乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
• RedisのHyperLogLogを使ってユニークユーザー数を推定する « Rest Term

Scala: Converting Tuple to Function Parameter using FunctionN#tupled

Scala: tupled メソッドを使ってタプルを関数の引数として渡す

 

タプルを直接関数のパラメータとして受け渡したい場合には、Function2, Function3, ... トレイトの tupled を使うと便利。

scala> def f(x: Int, y: Int, z: Int): Int = x + y + z
f: (x: Int, y: Int, z: Int)Int

scala> (f _).tupled((10, 20, 30))
res0: Int = 60

特に Case Class の組み立てに役立つ。

scala> case class C(x: Int, y: Int, z: Int)
defined class C

scala> Seq((1, 2, 3), (4, 5, 6), (7, 8, 9)).map(C.tupled)
res1: Seq[C] = List(C(1,2,3), C(4,5,6), C(7,8,9))

同様に、curried メソッドも備わっている。

scala> (f _).curried(10)(20)(30)
res2: Int = 60

Scala: SeqLike#sortBy Never Compares in a Single Element Collection

Scala: sortBy は要素が一個だけの場合に比較を行わない

 

シーケンスの sortBy メソッドを利用し、要素を変換したあとにソートしたい。
変換処理で例外が発生する可能性がある場合の挙動。

シーケンスの要素が 1個だけの場合、コンペア自体が行われないため、期待した例外が送出されなかった。

scala> Seq.empty[String].sortBy(_.toInt)
res0: Seq[String] = List()

scala> Seq("a").sortBy(_.toInt)
res1: Seq[String] = List(a)

scala> Seq("a", "b").sortBy(_.toInt)
java.lang.NumberFormatException: For input string: "b"
  at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
  at java.lang.Integer.parseInt(Integer.java:492)
  at java.lang.Integer.parseInt(Integer.java:527)
  at scala.collection.immutable.StringLike$class.toInt(StringLike.scala:247)
  at scala.collection.immutable.StringOps.toInt(StringOps.scala:30)
  at $anonfun$1.apply(:8)
  at $anonfun$1.apply(:8)
  at scala.math.Ordering$$anon$5.compare(Ordering.scala:122)
  at java.util.TimSort.countRunAndMakeAscending(TimSort.java:324)
  at java.util.TimSort.sort(TimSort.java:189)
  at java.util.TimSort.sort(TimSort.java:173)
  at java.util.Arrays.sort(Arrays.java:659)
  at scala.collection.SeqLike$class.sorted(SeqLike.scala:618)
  at scala.collection.AbstractSeq.sorted(Seq.scala:41)
  at scala.collection.SeqLike$class.sortBy(SeqLike.scala:597)
  at scala.collection.AbstractSeq.sortBy(Seq.scala:41)
  ... 33 elided

Scala: Adding Two Long Values Safely

Scala: 2つのLong値を安全に足す

 

Long の足し算でオーバーフロー/アンダーフローが発生するかどうか検知したい。

BigInt に変換してから値を足し込み、有効な Long値かチェックする。

def safeAddition(a: Long, b: Long): Option[Long] =
  Some(BigInt(a) + BigInt(b)).withFilter(_.isValidLong).map(_.toLong)

実行例

scala> safeAddition(Long.MaxValue, 0)
res0: Option[Long] = Some(9223372036854775807)

scala> safeAddition(Long.MaxValue, 1)
res1: Option[Long] = None

scala> safeAddition(-1, Long.MinValue)
res2: Option[Long] = None

scala> safeAddition(Long.MaxValue, Long.MinValue)
res3: Option[Long] = Some(-1)

Running Scala REPL in Chat Room with Hubot

Hubot で Scala REPL を動かす

 

HUBOT はヒューボットと発音するのが正しいらしい。

HipChat などのチャットツールの特定の部屋で、特定のメンションを付けたメッセージを Scala コードとして REPL 上で実行し、その結果をチャットに返すのが目的。 REPL環境はメッセージのたびに毎回初期化される。

今回初めて Coffee Script に触ってみた。

 

コード

以下のようなスクリプトを scripts ディレクトリ配下に書く。

外部プロセスとして　scala コマンドを起動し、その標準入力にメッセージを流しこむだけ。

# Description:
#   ScalaのREPLを実行する
#
exec = require('child_process').exec

module.exports = (robot) ->
  robot.respond /((?:.|\n)+)/i, (res) ->

    if res.message.room == 'your_room'
      code = res.match[1]
      n = code.length
      res.reply n + ' Byte' + if n <= 1 then '' else 's'

      try
        scala = exec 'scala', (error, stdout, stderr) ->
          lines = ('' + stdout).split '\n'
          # 余計な行を省く
          lines = lines[4...-2]
          res.send '/code ' + lines.join('\n')

        scala.stdin.setEncoding = 'utf-8'
        scala.stdin.write(code + '\n')
        scala.stdin.end()
      catch e
        res.reply "command failed: " + e.message

• line 7: 改行を含むメッセージを正しく処理できるように、少しトリッキーな正規表現を使っている。
  res から直接メッセージ文字列を取得できれば、こんな必要はなさそうだが……
• line 12: コードゴルフ用にメッセージの長さを通知。
• line 15: child_process.exec を使って実行。
  これが非同期で実行されるというところが最初理解できずハマった。
• line 18: REPLの冒頭に表示されるバージョン表示などの冗長な出力部分をカット

たぶん、まだまだリファクタリングできるところは多そう。が、そもそも文法を学んでないので厳しい。

 

備考

• OSのシステムコマンドや外部接続、リソース消費などに対するセキュリティは全くの無防備状態なので注意。
• 将来的には conscript と連携して、各プロジェクトごとの sbt console に直接入って操作できるようにしたり、あるいはいくつか常駐プロセスを立ち上げておき、状態を永続化できるように拡張できたらよいと思う。

 

 

References

• 楽しいHubot / いろんな言語をbot化してチャットルームに呼ぼう！ - Qiita