htagsをつかってみる

結構大きめのソースコードを読んでると、ブラウザで読みたいなーと思うときがある。
ブラウザだとタブを開きまくれるし、タブの操作も楽だ。

色々調べてみるとhtagsというツールがあることを知った。
htagsを使うとブラウザでソースコードを見ることができる。 関数の呼び出し箇所から関数の定義先にジャンプできたり、ファイル中の関数一覧を表示する機能も付いている。

htagsはGNU GLOBALというソフトフェアの一部で、globalは他にもgtagsをいうツールを同梱しており、 gtagsでインデックスを作ってから、htagsでHTMLファイルを生成するという流れになる。

GNU GLOBALは、Macの場合だとHomeBrewを使えばコマンド一つで入る。

$ brew install global

そうするとgtags、htagsをいうコマンドが使えるようになっているはずだ。

公式ホームページによるとglobalはデフォルトではC、C++YaccJava、PHP4、アセンブラに対応しているらしい。 試しにRedisのソースコードをブラウザから見られるようにしてみよう。

公式サイトからRedisのソースコードを取ってきて、展開。

$ wget http://download.redis.io/releases/redis-3.0.5.tar.gz
$ tar zxvf redis-3.0.5.tar.gz

gtagsでインデックスを作り、htagsでHTMLファイルを生成。
(手元のMacBookProでは、gtagsコマンドは数秒、htagsコマンドは十数秒で終わった。)

$ cd redis-3.0.5
$ gtags -v
$ htags -ans

gtagsのvオプションは作業状況を出力するためのオプション。
htagsのa、n、sオプションは次の通り。

  • -a--alphabetの略でアルファベット順のインデックスを作成するオプション
  • -n--line-numberの略で行番号を表示するためのオプション
  • -s--symbolの略で関数だけでなく変数にもリンクを貼るためのオプション

gtagsコマンドを実行すると、ディレクトリ直下にGPATH、GRTAGS、GTAGSファイルが生成されている。
htagsコマンドを実行すると、ディレクトリ直下にHTMLディレクトリが生成されている。

HTML/index.htmlをブラウザで開くと、コードを見ることができる。

便利だけど、デザインがいまいちかな?

Rubyで類似文字列検索

類似文字列検索といえばSimStringが有名だけど、自分の環境でRubyバインディングが上手くビルド出来なかったので、自分で実装することにした。

SimStringのアルゴリズムは「高速な類似文字列検索アルゴリズム*1で公開されている。

アルゴリズム自体は思ったよりもシンプル。
文字列をngramの素性集合に変換して、文字列どうしの類似度はその素性集合どうしの共通要素数をもとに計算している。
転置インデックスを使ったり、探索を枝刈りしたりして高速な検索を実現している。

# -*- coding: utf-8 -*-

require 'set'

class Ruimoji
  def initialize
    @words = []
    @inv_index = {}
    @min_feat_size = 0
    @max_feat_size = 0
  end

  def serialize(f_path)
    File.open(f_path, 'wb') do |f|
      f.write(Marshal.dump(self))
    end
  end

  def self.load(f_path)
    File.open(f_path, 'rb') do |f|
      Marshal.load(f.read)
    end
  end

  def build_from_file(f_path)
    File.open(f_path) do |f|
      f.each_line do |line|
        registor_word(line.chomp)
      end
      @min_feat_size = @inv_index.keys.min
      @max_feat_size = @inv_index.keys.max
    end
  end

  def build(words)
    words.each do |word|
      registor_word(word)
    end
    @min_feat_size = @inv_index.keys.min
    @max_feat_size = @inv_index.keys.max
  end

  alias :append_words :build

  def append_word(word)
    registor_word(word)
    @min_feat_size = @inv_index.keys.min
    @max_feat_size = @inv_index.keys.max
  end

  def search(q_word, sim_val)
    raise 'invalid sim_val value' unless sim_val > 0.0 and sim_val <= 1.0
    low_b, upp_b = calculate_bound(q_word.size + 1, sim_val)
    low_b = @min_feat_size if low_b < @min_feat_size
    upp_b = @max_feat_size if upp_b > @max_feat_size

    q_feat_set = feature_set(q_word)
    result_indexes = []
    (low_b..upp_b).each do |feat_size|
      teta = min_over_lap(q_feat_set.size, feat_size, sim_val)
      result_indexes.concat(overlap_join(q_feat_set, feat_size, teta))
    end
    result_indexes.map do |w_index|
      @words[w_index].dup
    end
  end

  def search_with_score(q_word, sim_val, sort=true)
    raise 'invalid sim_val value' unless sim_val > 0.0 and sim_val <= 1.0
    low_b, upp_b = calculate_bound(q_word.size + 1, sim_val)
    low_b = @min_feat_size if low_b < @min_feat_size
    upp_b = @max_feat_size if upp_b > @max_feat_size

    q_feat_set = feature_set(q_word)
    result_indexes_with_score = []
    (low_b..upp_b).each do |feat_size|
      teta = min_over_lap(q_feat_set.size, feat_size, sim_val)
      result_indexes_with_score.concat(overlap_join(q_feat_set, feat_size, teta, true))
    end
    result_indexes_with_score.sort_by! {|(w_index, score)| -score } if sort
    result_indexes_with_score.map do |(w_index, score)|
      {:word => @words[w_index].dup, :score => score}
    end
  end

  private

  def registor_word(word)
    word_index = @words.size
    @words << word.dup.freeze

    feat_set = feature_set(word)
    feat_size = feat_set.size
    feat_set.each do |bigram|
      if @inv_index[feat_size].nil?
        @inv_index[feat_size] = {bigram => []}
      elsif @inv_index[feat_size][bigram].nil?
        @inv_index[feat_size][bigram] = []
      end
      @inv_index[feat_size][bigram] << word_index
    end
  end

  def feature_set(word)
    Set.new(
      ("$" + word + "$").each_char.each_cons(2).map do |(c1, c2)|
        c1 + c2
      end
    )
  end

  def calculate_bound(feature_size, sim_val)
    low_b = (feature_size * (sim_val ** 2)).ceil
    upp_b = (feature_size / (sim_val ** 2)).floor
    return low_b, upp_b
  end

  def min_over_lap(feat_size1, feat_size2, sim_val)
    (sim_val * Math.sqrt(feat_size1 * feat_size2)).ceil
  end

  def overlap_join(q_feat_set, feat_size, teta, with_score=false)
    pos_lists = retrieve_pos_lists(q_feat_set, feat_size)
    pos_lists.sort_by! {|pos_list| pos_list.size }

    occ_counter = count_index_occurrence(pos_lists, q_feat_set.size, teta)
    w_indexes = occ_counter.keys
    result_indexes = []
    (q_feat_set.size - teta + 1).upto(q_feat_set.size - 1).each do |i|
      remove_list = []
      w_indexes.each do |w_index|
        if pos_lists[i].bsearch {|idx| w_index - idx }
          occ_counter[w_index] += 1
        end

        if occ_counter[w_index] >= teta and (not with_score)
          result_indexes << w_index
          remove_list << w_index
        elsif occ_counter[w_index] + q_feat_set.size - i + 1 < teta
          remove_list << w_index
        end
      end
      remove_list.each do |remove_i|
        w_indexes.delete(remove_i)
      end
    end
    w_indexes.each do |w_index|
      result_indexes << w_index if occ_counter[w_index] >= teta
    end
    if with_score
      inv_denom = 1.0 / Math.sqrt(q_feat_set.size * feat_size)
      result_indexes.map do |w_index|
        [w_index, occ_counter[w_index] * inv_denom]
      end
    else
      result_indexes
    end
  end

  def retrieve_pos_lists(q_feat_set, feat_size)
    pos_lists = []
    q_feat_set.each do |q_feat|
      if @inv_index[feat_size] and @inv_index[feat_size][q_feat]
        pos_lists << @inv_index[feat_size][q_feat]
      else
        pos_lists << []
      end
    end
    pos_lists
  end

  def count_index_occurrence(pos_lists, q_feat_size, teta)
    counter = Hash.new(0)
    0.upto(q_feat_size - teta).each do |i|
      pos_lists[i].each do |w_index|
        counter[w_index] += 1
      end
    end
    counter
  end
end

次のようにして使う。

ruimoji = Ruimoji.new
words = [
  "スパゲッティー",
  "スパゲッティ",
  "スパゲッテー",
  "スパゲティー",
  "スパッティー",
  "スパゲッティーニ",
  "スパゲッティー・",
  "スパッゲッティー",
  "スパゲッティーニ・",
  "・・スパゲッティー",
  "スープスパゲッティー",
  "スパゲッティーモンスター"
]
ruimoji.build(words) # データベース構築
ruimoji.search("スパゲティー", 0.7)
# => ["スパゲティー", "スパッティー", "スパゲッティー"]
ruimoji.search("スパゲティー", 0.6)
# => [
#      "スパゲティー", "スパッティー", "スパゲッティー", "スパッゲッティー", "スパゲッティーニ",
#      "スパゲッティー・", "スープスパゲッティー", "スパゲッティーモンスター"
#    ]
ruimoji.search_with_score("スパゲティー", 0.7)
# => [
#      {:word=>"スパゲティー", :score=>1.0},
#      {:word=>"スパゲッティー", :score=>0.8017837257372732},
#      {:word=>"スパッティー", :score=>0.7142857142857142}
#    ]
ruimoji.build_from_file("words.txt")

で一行に一語書かれたファイルからデータを読み込んで、データベースを構築。

ruimoji.serialize("ruimoji.data")

で構築したデータベースをファイルに保存。

ruimoji = Ruimoji.load("ruimoji.data")

でファイルに保存したデータベースを読み込む。

大きいデータでは試してないけど、10万語程度のオーダーなら十分実用的な速度で動作すると思う。

最後に。
ここで公開したソフトウェアはMITライセンスに準じます。(ただし、ライセンスや著作権の掲載は要求しません。)

*1:岡崎直観, 辻井潤一「高速な類似文字列検索アルゴリズム」(情報処理学会創立50周年記念全国大会) 2010

Augmented BNF for Syntax Specification: ABNF (RFC5234)

ABNFはあるモノのシンタックスを形式的に定義するための言語。
URIもABNFをもとに定義されている。(RFC3986)
但し、RFC3986が参照しているABNFはRFC2234によるもの。

Wikipediaによると、RFC5234はRFC4234をアップデートしたもの。
そして、RFC4234はRFC2234とRFC733をアップデートしたもの。

Terminal Values

文字ベースのものと数値表現ベースのものがある。

文字ベース

Rule1 = "a"
Rule2 = "ab"

文字ベースのルールは大文字・小文字を区別しない。
なので、Rule1は a、A にマッチし、Rule2は ab、aB、Ab、AB にマッチする。

数値表現ベース

Rule1 = %d13 ; 10進表現
Rule2 = %x61 ; 16進表現



ABNFで表現された文字列をコンピュータで扱う場合、最終的にはバイナリとして表現されるが、バイナリ表現は文字コードによって異なる。
RFC5234ではABNFの文字コードについて特に何も規定していない。
なので、<%x61>(%x61はasciiで"a"を表す)が<"a">にマッチするかどうかは想定する文字コードによって変わってくる。

演算子

Concatenation

Rule = Rule1 Rule2

という形で、2つの文字列の結合を表す。 例えば、

foo = %x61  ; a
bar = %x62  ; b
Rule = foo bar

では、<Rule>は aba とマッチする。

Alternative

Rule = Rule1 / Rule2

という形でORを表す。 例えば、

foo = %x61  ; a
bar = %x62  ; b
Rule = foo / bar

では、<Rule>は a と b にマッチする。

Value Range Alternative

例えば、以下で<DIGIT1>と<DIGIT2>は同じルールを表す。

DIGIT1 = %x30-%x39
DIGIT2 = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

Square Group

演算子適用の優先順位を上げる。 例えば、

Rule = foo (bar / foo) foo  ; => (foo bar foo) / (foo foo foo)

Variable Repetition

Rule1 = <a>*<b>element
Rule2 = <a>*element
Rule3 = *<b>element
Rule4 = <a>element

と書き、ルール<element>の繰り返しを表す。
<Rule1>は<element>のa回以上b回以下の繰り返し。
<Rule2>は<element>のa回以上の繰り返し。
<Rule3>は<element>の0回以上b回以下の繰り返し。
<Rule4>は<element>のa回の繰り返し。
例えば、

Rule1 = 1*3foo  ; => foo / (foo foo) / (foo foo foo)
Rule2 = 2*foo   ; => (foo foo) / (foo foo foo) / ....
Rule3 = *2foo   ; => "" / foo / (foo foo)
Rule3 = 3foo    ; => foo foo foo

Optional Sequence

Rule = [Rule1]

例えば、

Rule = foo [bar] foo ; => (foo bar foo) / (foo foo)

演算子の優先順位

Value range > Repetition > Grouping > Concatenation > Alternative

「RDBMS解剖学」を読んだ

リレーショナルデータベースの仕組みについて書かれた平坦な本。とても読みやすい。

リレーショナルデータベースがクライアントからSQLクエリを受け取って結果を返すまでどういう処理を行っているかが書かれている。
パフォーマンス向上のためのログの利用(Write Ahead Logging)方法やログによる障害の復旧の仕組みについては、大雑把な処理の流れがイメージできるくらいに書かれてて良かった。
ここらへんの話はリレーショナルデータベースに限らず、データベース全般に通じる話。

RDBMS解剖学 よくわかるリレーショナルデータベースの仕組み (DB Magazine SELECTION)

RDBMS解剖学 よくわかるリレーショナルデータベースの仕組み (DB Magazine SELECTION)

設定ファイルを指定してzookeeperを起動

結論からいうと、

$ zkServer.sh start /path/to/zoo.cnf

で設定ファイル/path/to/zoo.cnfを指定してzookeeperを起動できる。

zkServer.shの61行目あたりを見ると以下のようになっていて2つ目の引数を変数に設定している。

if [ "x$2" != "x" ]
then
    ZOOCFG="$ZOOCFGDIR/$2"
fi

# if we give a more complicated path to the config, don't screw around in $ZOOCFGDIR
if [ "x$(dirname "$ZOOCFG")" != "x$ZOOCFGDIR" ]
then
    ZOOCFG="$2"
fi

でもヘルプを見ても

Usage: zkServer.sh {start|start-foreground|stop|restart|status|upgrade|print-cmd}

としか書いてないので微妙すぎる。

ちなみに、僕が確認したのはv3.4.6のコードで、GitHub上のコードを見るともうちょっと後のバージョンでは--configオプションで設定ファイルを持つディレクトリを指定できるようになるみたいだ。
ZOOKEEPER-1335. Add support for --config to zkEnv.sh to specify a con…

プロセスグループ・セッションについて勉強した

fabricというデプロイツールでサーバーを動作させるコマンドが上手く実行出来なくて、原因を調べるために勉強したメモ。(原因はまだよくわかってない)

プロセスグループ

名前の通り、プロセスの集合のこと。
あるプロセスからforkした子プロセスはデフォルトでは親プロセスと同じプロセスグループ。
また、下のようにパイプでつないだプロセス同士は同じプロセスグループになる。

$ command1 | command2 | command3

プロセスグループにはリーダーとなるプロセスがいて、プロセスグループリーダーという。
プロセスグループにはプロセスのようにidがあり、プロセスグループIDという。
プロセスグループIDはそのプロセスグループのリーダーのプロセスIDと同じ値を持つ。

プロセスグループは端末によるジョブ制御の基本的な単位となる。
つまりジョブ=プロセスグループ。

$ seq 100000000 | sort | uniq

を実行し、実行中に ^C(Control + c)を押すと、コマンドの実行が終了する。
^Cを押すと端末の機能により現在フォアグラウンドで実行中のジョブ(プロセスグループ)にSIGINTというシグナルが送信され、実行が終了させられる。

一方、killコマンドを使ってseqを実行しているプロセスを殺すとどうなるか。

$ seq 10000000 | sort | uniq &

とバックグラウンドで実行して、プロセスの情報を調べる。(コマンドは実行時間を稼げるコマンドを適当に並べただけ)

$ ps -o pid,pgid,sid,args
  PID  PGID   SID COMMAND
31089 31089 31089 /bin/bash
31580 31580 31089 seq 10000000
31581 31580 31089 sort
31582 31580 31089 uniq
31583 31583 31089 ps -o pid,pgid,sid,args

"-o"オプションで出力フォーマットを指定している。
パイプでつながれた3つのプロセスが同じプロセスグループ(そして同じセッション)に属してることがわかる。

ここで、seqを実行しているプロセスを殺してみる。

$ kill -2 31580

すると、しばらく経ってから標準出力に数字がいっぱい出力されるはずだ。

つまり、killでプロセスを殺した場合パイプでつながれた他のプロセスは生きたままだということだ。
これはkillコマンドの正しい動作であるけれど、端末のユーザーとしては不便極まりない。

ジョブ制御

先ほど唐突に出てきた、端末におけるジョブ制御について簡単にまとめておく。
ジョブ制御は一つの端末で複数のコマンド(ジョブ)を実行できるようにするもの。

$ command &

bashでコマンドの後ろに&を付けて実行すると、bashの機能により実行はバックグラウンドで行われ、そのコマンドの実行が終了していなくても他のコマンドを実行できるようになる。
このようにバックグラウンドで実行するジョブをバックグラウンドジョブという。
コマンドを普通に実行した場合、それはフォアグラウンドジョブとなり、実行終了まで待たされる。
端末は一つのフォアグラウンドジョブと複数のバックグラウンドジョブを持つことができる。

ジョブの状態にはフォアグラウンドで実行中、バックグラウンドで実行中以外に中断という状態がある。
フォアグラウンドでコマンドを実行中に ^Z(Control+z)を押すと実行が中断される。

$ seq 1000000000000 | sort
^Z
[1]+  Stopped                 seq 1000000000000 | sort

もう一度フォアグラウンドで実行したかったらfgと入力すればよい。
中断した状態でバックグラウンドで実行したかったらbgと入力すればよい。
バックグラウンドで実行中のジョブを中断させたかったらstopと入力すればよい。(なぜか僕の環境ではstopコマンドがないと怒られた)

セッション

セッションとはプロセスグループの集合である。
セッションにもセッションリーダーとなるプロセスがいる。
セッションのIDはセッションリーダーのプロセスIDと同じになる。
セッションは一つの制御端末を持つことが出来て、制御端末を持つセッションのセッションリーダーを制御プロセスという。 sshでログインして、インタラクティブなシェルを実行している場合、セッションリーダーはシェルである。

制御プロセスと制御端末の接続が切断されたら、カーネルは制御プロセスとフォアグラウンドプロセスジョブ内の全てのプロセスにシグナルSIGHUPを送信する。
bashが制御プロセスだった場合、bashはSIGHUPを受け取ると、exitする前に端末内の全ジョブにSIGHUPを送信する(実行中断中のジョブにはSIGCONTを送って実行を再開させてからSIGHUPを送る)。
SIGHUPを受け取ったときのデフォルトの動作は停止なのでプロセスは死ぬ。

sshが切れたときとかに実行中のプロセスが死んでしまうのはこのあたりのことが起こっている。
nohupコマンドはSIGHUPを無視するようにしてくれる。

色々と理解があやふや(特に端末)なので、所々間違っているかもしれない。

Prestoをビルドした

Prestoは分散SQLエンジンと呼ばれるソフトウェア。
Facebookが開発元だが、OSSとして公開されている。
ライセンスはApache Licence 2.0。

従来は分散SQLエンジンとしてHadoop上で動くHiveというものがあったが、HiveはSQLクエリーを多段のMapReduceに変換して処理を実行するので、 処理が重たく、リアルタイムな解析には向かなかった。

そこで、リアルタイムにビックデータをSQLできるものが色々と出てきた。
有名なところではCloudera Impala、Apache Drill、Prestoなど。
あと、多段のMapReduceではなくDAGに変換してくれるApache Tezとかいうソフトウェアもあって、これと一緒にHiveを使えば処理が早くなるらしい。

機能的な違いはほとんど把握してないが、Prestoに関していえば、今をときめくTreasure DataがPrestoをめっちゃ推してる(ように感じる)。

ビルドについて

ビルド環境はCentOS7。

PrestoのビルドにはJava8とMaven(3.2.3+)とPython(2.4+)が必要。
Java7しか入ってなかったので、yumでJava8を入れる。(もちろん、yumで入れたJava7を消してから)

$ sudo yum install java-1.8.0-openjdk

Mavenも入ってなかったので、入れることに。 yumで入れると、Java7も一緒に入れられ、せっかく入れたJava8が見えなくなるというつらい事象が発生した。 そこで本家からバイナリを落としてくることに。

$ wget http://ftp.riken.jp/net/apache/maven/maven-3/3.3.3/binaries/apache-maven-3.3.3-bin.tar.gz # バイナリをダウンロード
$ tar zxvf apache-maven-3.3.3-bin.tar.gz # tarボールを解凍
$ sudo cp -R apache-maven-3.3.3 /srv/apache-maven-3.3.3 # ディレクトリは適当な場所に移動(もっと適切な場所があるかもしれない)
$ export PATH=/srv/apache-maven-3.3.3/bin:$PATH # Mavenのコマンドを使えるようにパスを通す

Pythonはもう入っていたので何もすることはなし。

続いて、gitで適当なディレクトリにソースコードを落としてくる。

$ git clone https://github.com/facebook/presto.git

できたディレクトリに入り、ビルドと一緒にテストも実行するならmvn clean install、テストはスキップするならmvn clean install -DskipTestsとコマンドを打てばビルドが始まる。
今回はテストはスキップした。

あとは全てMavenさんがよしなにやってくれる。
ビルドが終わるまで20分ちょっとかかるのでアニメでも見ながら過ごせば良い。