ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

Aho-Corasickに動的にキーワードを追加する

この記事はIQが1Advent Calendarの1日目の記事になります.
「起床時間とか就寝時間が1日目の記事になる」と言っていましたが,ギリギリ実装が間に合った(バグってるかもしれないが)ので起床時間と就寝時間はやめて文字列照合アルゴリズムについて紹介することにしました.
IQ1でもわかるように書くつもりです(これは嘘でIQ1なのでまともな文章が書けない)
(AhoなのでIQ1と指摘を受けました. IQ1はAhoですがAhoさんはwikiを見てもわかるとおりすごい人です.IQが異常に高そうです)

Aho-Corasickについて

複数のキーワードに対する文字列照合アルゴリズムとしてAho-Corasickというものがある.
Aho-Corasickについては Alfred V.Aho and Margaret J.Corasick Bell Laboratories "Efficient String Matching: An Aid to Bibliographic Search"という論文にかかれている.
このキーワード群を静的に構築する方法は下のブログに書いてある.
d.hatena.ne.jp
これのC++の実装はalgoogle.
algoogle.hadrori.jp

簡単説明するとTrieを構築した後にTrieでの検索に失敗した際の遷移関数を定義することで効率的に文字列照合を行うというものである.

このブログではキーワードを動的に追加する方法を紹介する.

キーワードの動的な追加方法

共立出版からでている「情報検索アルゴリズム」を参考に...

言葉の定義

goto関数 : 検索に失敗しない場合の遷移
failure関数 : 検索に失敗した際の遷移

この関数については上のブログでも定義されてる...(そっち見たほうがいい)
Aho-Corasickはこのfailure関数を幅優先探索で構築する.

これを動的に行う場合,更新による影響が及ぶ部分だけを更新すればよい.
更新による影響が及ぶ範囲というのは,新しく追加された部分にfailure関数が到達する部分である(これによりoutput関数も更新されるので).
下の図ではノード9,10に相当する.

これを動的に行うには,2つの段階が必要.
1. 追加するキーワードに対応するノードを作成し,追加されたノードのfailure関数とoutput関数を更新する
2. 既存のグラフのfailure関数とoutput関数を更新する

例えば...
既に構築されているキーワード群は { "ab", "abcde" , "bc" , "bab" , "d"}とし,新しく "bcde"を追加するとします

1ステップで赤色の更新を, 2ステップで緑色の更新を行います(output関数の更新は省略しました)
f:id:chakku000:20171201003835p:plain

ステップ1

赤いノードの追加 : Trieと同様なので省略
赤いfailure関数の追加
f:id:chakku000:20171201004809p:plain
node1->node2はfailure関数を,赤い線は追加されるnode2->node4というfailure関数を意味する.
薄い水色の部分は同じ文字の並びを意味する.

上の図の関係を見つければ,赤い辺をfailure関数として定めることができる.(多分ここが1番重要.ステップ2もこの考え方)

ステップ2

緑のノードの追加.
ここでも2つめの図と同じような考察をする.
例えば1つめの図のノード8のfailure関数は4を指す(f(8) = 4) .
そうすると
8 <-> node1
4 <-> node3
9 <-> node2
11 <-> node4
の対応が見え,図1における 9 -> 11 (つまり図2におけるnode2->node4)を貼ることができる.

図1においてこれを行うためには ノード4がノード8のfailure遷移先であることをノード4は知っている必要がある.そのためfailure関数の逆関数,逆failure関数も保持しておく必要がある.

ステップ2は繰り返し適用することで更新が必要な状態は全て更新される.
この繰り返し更新するのはqueueを用いて行えばよい

実装

C++における実装. addが動的にキーワードを追加する部分.
それ以外ははどろりさんの実装を真似ている.

class AhoCorasick{
    private:
        const int nodeSize = 30;
    public:
        vector<AhoCorasick*> nodes;
        AhoCorasick* failure;
        set<AhoCorasick*> rev_failure;
        vector<int> matched;    // 対応ノードにpattern[i]がマッチした
        vector<string> pattern;
        AhoCorasick() : nodes(nodeSize),failure(nullptr){
            for(int i=0;i<nodeSize;i++) nodes[i] = nullptr;
        }
        void rootinit(){
            for(int i=0;i<nodeSize;i++) nodes[i] = this;
        }

        // 静的に追加(from algoogle)
        void insert(const vector<string> pattern_){
            pattern = pattern_;
            // Trie構築
            AhoCorasick *r = this;
            failure = this;
            rev_failure.insert(this);
            for(int i=0;i<pattern.size();i++){
                r = this;
                for(int j=0;j<pattern[i].size();j++){
                    int c = pattern[i][j]-'a';
                    if(!r->nodes[c]) r->nodes[c] = new AhoCorasick;
                    r = r->nodes[c];
                }
                r->matched.push_back(i);
            }

            // 辺生成
            queue<AhoCorasick*> que;
            for(int i=0;i<nodeSize;i++){
                if(!this->nodes[i]) this->nodes[i] = this; // 存在しないノードのfailure
                else{
                    this->nodes[i]->failure = this; // 深さ1のfailure関数は全てrootに接続される
                    this->rev_failure.insert(this->nodes[i]);
                    que.push(this->nodes[i]);
                }
            }

            // failure関数の更新とmatchedの更新
            while(!que.empty()){
                r = que.front();que.pop();
                for(int i=0;i<nodeSize;i++) if(r->nodes[i]){
                    AhoCorasick* sfx = r->failure;
                    while(!sfx->nodes[i]) sfx = sfx->failure;
                    r->nodes[i]->failure = sfx->nodes[i];
                    sfx->nodes[i]->rev_failure.insert(r->nodes[i]);
                    copy(sfx->nodes[i]->matched.begin(),sfx->nodes[i]->matched.end(),back_inserter(r->nodes[i]->matched));
                    que.push(r->nodes[i]);
                }
            }
        }

        // 動的に追加
        void add(const string& keyword){
            int idx=0;
            int depth=0;  // 遷移回数
            AhoCorasick *r = this;
            vector<AhoCorasick*> s(keyword.size()+1,nullptr);   // s[i] : keyword[i-1]で遷移した先
            s[0] = this;
            // rootからの遷移は深さ1以上の状態からの遷移とことなる特徴を持つので特別に扱う
            if(nodes[keyword[0]-'a'] == this || nodes[keyword[0]-'a'] == nullptr){  // 対応するgoto関数が定義されているか?
                // 先頭文字に対するgoto関数が定義されていない場合,深さ1の状態だけは生成
                nodes[keyword[0]-'a'] = new AhoCorasick;
                s[1] = nodes[keyword[0]-'a'];

                nodes[keyword[0]-'a']->failure = this;      // 深さ1のfailure関数は必ずroot
                this->rev_failure.insert(nodes[keyword[0]-'a']);

                idx = 1;
            }else{
                // 先頭文字に対する状態遷移がある場合はgoto関数がfailになるまで既存の状態遷移をたどる
                while(idx < keyword.size() and s[idx]->nodes[keyword[idx]-'a']){
                    s[idx+1] = s[idx]->nodes[keyword[idx]-'a'];
                    idx++;
                }
                depth = idx;
            }


            //状態遷移の追加とfailure関数,matchedの更新
            for(int i=idx;i<keyword.size();i++){
                // 新しいノード作成
                s[i]->nodes[keyword[i]-'a'] = new AhoCorasick;
                s[i+1] = s[i]->nodes[keyword[i]-'a'];

                // 新しいノードの親ノードのfailureを辿る
                AhoCorasick *state = s[i]->failure;
                while(!state->nodes[keyword[i]-'a']) state = state->failure;

                // 新しいノードのfailure関数を設定
                s[i+1]->failure = state->nodes[keyword[i]-'a'];
                state->nodes[keyword[i]-'a']->rev_failure.insert(s[i+1]);

                // 新しいノードのmatchedを決定
                s[i+1]->matched = state->nodes[keyword[i]-'a']->matched;
            }

            // 追加ノードが無い場合のs[n]を定義
            if(!s[keyword.size()]) s[keyword.size()] = s[keyword.size()-1]->nodes[keyword[keyword.size()-1]-'a'];
            s[keyword.size()]->matched.push_back(pattern.size());

            // 既存状態の更新

            // 追加状態の親はs[depth]
            r = s[depth];

            queue<pair<AhoCorasick*,int>> que;
            for(AhoCorasick* node : r->rev_failure){
                que.push(make_pair(node,depth));
            }

            while(!que.empty()){
                r = que.front().first;
                int i = que.front().second;
                que.pop();
                while(i<keyword.size() and r->nodes[keyword[i]-'a']){
                    AhoCorasick* state = r->nodes[keyword[i]-'a'];
                    state->failure->rev_failure.erase(state);
                    state->failure = s[i+1];
                    s[i+1]->rev_failure.insert(state);
                    r = state;
                    i++;
                }

                if(i>=keyword.size()) r->matched.push_back(pattern.size());

                for(AhoCorasick* node : r->rev_failure){
                    que.push(make_pair(node,i));
                }
            }
            pattern.push_back(keyword);
        }

        // ret[tのindex] := t[index]から開始する文字列はpattern[ret[index][i]]にマッチする
        // 例えば pattern[0] = a , pattern[1] = ab , t = ab なら ret[0] = {0(a),1(ab)}
        vector<vector<int>> match(const string& s){
            AhoCorasick* r = this;
            vector<vector<int>> ret(s.size());
            //map<int,vector<int>> ret;
            for(int i=0;i<s.size();i++){
                int c = s[i] - 'a';
                while(!r->nodes[c]){
                    r = r->failure;
                }
                r = r->nodes[c];
                for(int j=0;j<r->matched.size();j++){
                    int sz = pattern[r->matched[j]].size();
                    ret[i-sz+1].pb(r->matched[j]);
                }
            }
            return ret;
        }
};

コメント

なんか実装バグってる気がする....(正しく実装できてる気が全くしない)
「情報検索アルゴリズム」の本にはキーワードの削除も載ってたけどそっちまで読む元気はなかった...

なんか間違いとかあったらtwitterにでもお願いします(正直このコードがバグっててもデバッグはしたくない)

情報検索アルゴリズム

情報検索アルゴリズム


AhoなのでIQが1!!!! (Ahoさんごめんなさい(土下座))

ARC085 D ABS

問題
D - ABS

自分の解法はO(N^2)だが解説の方法がO(1)だった。
この解説に最初ちょっと納得できなかったのでメモ

どこで納得が行かなかったかというと「Xがa_iまで取った時,Yはa_{N-1}までとる」という部分がよくわからなかった。
というのは「Xが途中までとって,その後Yがうまく選択したらもっと低い/高い値がでるのでは?」と考えたから。。。

「Xがa_iまで取り,そのあといくつかYが取った」場合を考える
f:id:chakku000:20171112022741p:plain

こんな感じで...

もしこの結果がmax(a_N-a_{N-1},a_N-W)よりも小さくなった(つまりYが良い選択をできた)とする。
この場合,Xは前からi個を選択したのが,「Xがスコアを最大化しようとする」という前提に反しているので矛盾。よって前からi個をXが選択してスコアがより低くなることはない。

逆にXが前からi個選択して結果がmax(a_N-a_{N-1},a_N-W)よりも大きくなったとする。
この場合,Yはa_{N-1}までを選択することでスコアをa_N-a_{N-1}にすることができる。
従って,max(a_N-a_{N-1},a_N-W)を超えることはない。


これで最初に提示した疑問は解決した...はず...

(考察に漏れがあればtwitterにでもリプください)

Vimconf2017に行ってきたんだよ

Vimconf2017に参加してきました
VimConf 2017 - An international Vim Conference

場所は秋葉原富士ソフト アキバホール.めっちゃでかい会場だった.
到着したらVimconfTシャツを貰ったりしてた.


発表

@haya14busa さんの発表
Vim,Me and Communityという発表.
EasyMotionの話とかIncsearch.vimの話とかこれまでのはやぶささんとvimの話を特に検索,移動周りの話を中心にしていた.
スライドに入っているいらすとやの絵が選択がうまかった...

@fatih さんの発表
vim-goの発表.
vim-goを使うためにgo言語をやりたいと思わせてくれる素晴らしい発表だった.

vim鼎談
@mattn_jpさん@kaoriyaさん@k-takataさんの話.
@mattn_jpさんを初めて見たけど服を着ていた.
spell checkを使うべきだと言ったりしていた.
(ただ,これを聞いてspell checkを使用してみたが意図的なものまでエラーとしてでてしまうのでgitのコミットとかくらいになら...って感じがする)
あとlanguage server(vim-lsp)とかの話も出てきた.これらは全く知らなかったので少し調べたい.

@cocoponさんの発表
Creating Your Lovely Color Schemeという発表
Iceberg.vimを作った人によるcolorschemeの作り方講座.
「コンセプトを決めて色はコンセプトにそって決める」や「主なカラーパレッドをまず作る」「カラーパレットは最初に1色決めてあとは色相の変化で」など,素晴らしい知見が得られた.
直後にカラースキーム弄り始めてしまった.

@t9mdさんの発表
vmpの発表
ATOMvimプラグインについての発表
Mutationとかの話

@senopenさんの発表
Vim and Compatibilityという発表
どこでも動くvimrcを作るみたいな話.キーワードはWrite .vimrc Once Wrok Vim Anytime/Anywhere.
POSIX原理主義の方だった.Vimの歴史とかも語られる.
確かにどこでも動くvimrcは魅力ではあるが,それを作るための労力は大きそう.とくにエンコーディングにも詳しく語っていた.
どこでも動くvimrcを書きたいならこのスライドは見るべき.そうでなくとも1度は見ておくべきって感じの発表だった.

@ShougoMatsuさんの発表
暗黒美夢王ことShougoさんの発表
正直この方の発表を目当てにvimconfに参加したみたいなところがある.
発表内容はNeosnippet.vim + Deoppet.nvim
Deoppet.nvimを使うなら来年まで待つべきらしい.
Deoppet.nvimにはExtended markというものが使用される.
といった内容.そしてdeopleteがVim8に対応したらしい.Windowsだとプロセス間通信が非常に遅いらしい.

@dice_zuさんの発表
How ordinary Vim user contributed to Vimという発表
Vimのコントリビュータになるためにはみたいな話.「毎日Vimをビルドして使っていると」とか「ある朝Vimをビルドして起動してみると」とか言ってて笑った.

@p_ck_さんの発表
The new syntax highlighter for vimという発表
vimのsyntaxは正規表現を使っているが,正規表現は人間には早すぎるので, iro.vimを作ったみたいな話.
iro.vimはパフォーマンスが良いらしい.

@lambdalisueさんの発表
gina.vimの紹介
Vimanという言葉が出てきた.どうもVimを使いやすくしようとする人々のことであるらしい.
gina.vimはGitを扱えるVimプラグインらしく,いまVimでgitを扱うならこれなのかな
発表を聞いてこのプラグインを入れてみたくなった.


感想

どの方の発表も素晴らしかった.個人的にはcocoponさんとfatihさんの発表が好きだった.
英語での発表者もいたが,同時通訳してくれていて嬉しい(同時通訳自体が1つのコンテンツだった)

お昼ごはん凄く美味しかった


Vim coffee

懇親会

Shougoさんと話すことが出来た.neoincludeがdeopleteに対応してるとかの話を聞けた.
aiya000さんのLT. Either Monadをvitalに入れた話とか.
koturnさんとryunixさんとも会うことができた.

Vimconfとても楽しかったです.
発表者の方々,発表お疲れ様です.
スタッフの方々,企画運営ありがとうございました.

json4sを使ってみた

scalajsonを扱いたいと思ったのでやったことのメモ

用意したjson
gist.github.com
pythonで生成したら日本語が...

とりあえずjson4sを使うためにbuild.sbtに

libraryDependencies += "org.json4s" %% "json4s-jackson" % "3.5.0"

とした.

URLからjsonを取ってきてjson4sでパースし,shigureに対応する要素を出力ということをしてみた

import scala.io.Source

import org.json4s._
import org.json4s.jackson.JsonMethods._

object Main{
  def main(args:Array[String])={
    val url = "https://gist.githubusercontent.com/chakku000/ea3bce545c397b2bbc3f211e074847d1/raw/fc0744f530bf993a5c059254a8101adc650d11ec/poi.json"
    val source : scala.io.BufferedSource = scala.io.Source.fromURL(url)
    val contents : String = source.mkString
    val json = parse(contents)    // JsonのAST表現
    val maps = json.values.asInstanceOf[Map[String,Any]]  // JsonのAstをMapに変換

    val shigure = getFromOption(maps.get("shigure"))
    println(shigure)
  }

  def getFromOption(v : Option[Any]) : String = {
    v match{
      case Some(s) => s.asInstanceOf[String]
      case None => ""
    }
  }
}

となった.

いくつかわからないことがあった.
一つは json.values.getClassとするとscala.collection.immutable.Mapとでるのでgetができるかと思ったが,json.values.getとするとjson.Valuesのメンバじゃないと怒られてしまう.なんでだろう?

感想

Scalaを初めてみたが,コップ本も詰んであるままなので読まないと....
質問できる人がほしい...

追記1

json.Valueにgetメンバがないと怒られるのは,json.valuesの型が静的にはMapして解釈できないのでは?という指摘を受けた.asInstanceOfで明示的に型を指定すれば静的にMap型として解釈できるのではというものである.

追記2

上のコードはもう少し簡単にできるらしいです.こんな感じで

import scala.io.Source

import org.json4s._
import org.json4s.jackson.JsonMethods._

object Main{
  def main(args:Array[String])={
    val url = "https://gist.githubusercontent.com/chakku000/ea3bce545c397b2bbc3f211e074847d1/raw/fc0744f530bf993a5c059254a8101adc650d11ec/poi.json"
    val source : scala.io.BufferedSource = scala.io.Source.fromURL(url)
    val contents : String = source.mkString
    val json = parse(contents)    // JsonのAST表現
    //val maps = json.values.asInstanceOf[Map[String,Any]]  // JsonのAstをMapに変換

    implicit val formats = DefaultFormats
    val shi : String = (json \ "shigure").extract[String]
    println(shi)
  }
}

tmux-256colorで<ctrl-l>が正常に動作しない場合

tmux 2.6
tmuxを使用している場合,.tmux.confに

set -g default-terminal "tmux-256color"

と書いている.

しかし,これが書かれた.tmux.confを読み込みtmuxを起動するとを押したときに正常に動作しない.
これは,恐らくtmux-256colorがないのでinstallする必要がある.
インストールは

sudo apt-get install ncurses-term

でできる.

疑問

なんでncurses-termにtmux-256colorがあるのだろうか?
ご存知の方がいたらおしえてください(._.)


tmux 2: Productive Mouse-Free Development

tmux 2: Productive Mouse-Free Development

Atcoder Beginner Contest 075に参加したよ

ABC075にScalaで参加しました.
といってもScalaScalaらしく書いてないので別にそんなに書くことも無いんですけど...

C問題

各辺を取り除いてワーシャルフロイドしてみる.O(N^4)くらいで通る.
ワーシャルフロイドじゃなくてdfsとかbfsとかでもよいが計算が間に合うならWFが楽かな.

Submission #1684530 - AtCoder Beginner Contest 075

D問題

コンテスト中に間に合わなかった.
というかコンパイルが通らなくて調べてたら終わっちゃった....
ScalaだとN=50でO(N^5)はなかなか通らない...こういうあたりC++なら普通に通りそう...

Submission #1685936 - AtCoder Beginner Contest 075

感想

せっかくScalaで参加してみたんだからもうすこしScalaっぽい書き方できればいいなぁ...

ちなみにDのコードはforではなくwhileを使うと早くなるみたいな提出している人がいる!

JAG夏合宿2017に参加してきました

9/22 ~ 9/24にオリンピック記念青少年総合センターで開催されたJAGの夏合宿に参加しました

チームIQ1は全員参加できたので前日IQ1メンバーででました.

Day0まで研究室の合宿に行ってて睡眠時間が異常に減ってたので3日間とも睡魔と戦ってた...

Day1
僕はA問題を解いてあとは座ってた.Aはn文字のものは26^n個使い切れる証明がわからなかったけど出してみたら通った.
チームでは7完してるので実質お茶汲み.
この日のIQ1はなぜか全員pythonだった

Day2
吹雪ちゃんが刻印有HHKBのUS配列を持ってくる.
9時集合10時開始なのに9:56とかに到着した.
B問題をバグらせて通せなかった.重複したパターンも数えてしまっていた.(ことが翌日判明した)
この日はすごくて5時間座ってただけだった.完全にお茶汲み要員.

夜のcodefes予選Aは「予選は通れないけどレートくらいは上がるだろう」みたいな見積もりで出たら大失敗してレートを下げるはめになった

Day3
この日はIQ1の吹雪ちゃんが無刻印USキーボードを持ってきた.(夕立と睦月ちゃんはいつもJISなんだけど!!!)


記号がどこにあるかわからなくてキー全探索してたら吹雪ちゃん笑ってた

A,B,Cを解いただけ.実はB,Cでバグらせてて戦犯感がある....事実上のお茶汲み要員
全体で22位.

D問題の考察をしたがbitDPだろうという予測しかたたずだめ.
G問題は何をしても微妙な計算量になりそうで考察が明後日の方向に吹き飛ぶ.

A,B,Cはホントは3人が並列に解くのが正しいんだけど,僕がA読む→解けるな→B読む→解けるな→C読む→解けるなって感じで解けそうならときに行くみたいなスタイルをしてしまった.
どこに簡単な問題があるかわからないからこの辺どうするかチームで固めたい.





全体を通して

チームコンテスト,ほとんど無いからこういう機会にできるとめっちゃ楽しい!!!

3日間US配列を使って気がついたことはなれない配列だとライブラリを写すのさえめちゃくちゃ面倒くさく感じる.
基本的に3日間ともチームに貢献できていないのでお茶汲み係としての腕を磨くしか無い.

オリンピックセンターのご飯は割と美味しかった.サラダが取り放題で睦月ちゃんが異常量サラダ食べてた.

チーム内での役割が完全に自明問題を片付ける人になってるのでそろそろ修行しないと迷惑かけそう...