tikedaのめう

日頃得られた知見と気付きをdumpするところ

柔軟なマップ検索webサービスをつくりたい 1日目

はじめに

たまにポツポツとアイディアが湧いてくるので、それを具現化したいと思い作ることにした。 パブリックに公開できるものを目指す。

目的

今回の目的は2つある。 - Webサービスのクライアントからサーバサイドまで、自ら作ること - 各機能の開発にかかる時間を見積もれるようになること Ajaxを用いたTwitterもどきを作った経験はあるが、所詮その程度しかないので、一度勉強も兼ねてWebサービスを立ち上げてみる。 アプリ開発までこぎつけたら良いが、アプリではまた別のアイディアを実装したい。

1日目 OpenLayers上で図形による範囲指定、GeoJSON形式の位置情報取得

この辺を参考にコードを改変。 Draw and Modify Features

できたものが以下になる。 github.com

Circleの場合はGeoJSON形式に直せる(表現できる)のか不明なので調査する必要がある。

あとDockerfileも書かなければいけないので、次回作ることとする。

できたGIFが以下のようなもの。 f:id:tikeda_meu:20180929225451g:plain

得られたGeoJSONを検索クエリとしてElasticsearchに発行する予定。

GeoShape Query | Elasticsearch Reference [6.4] | Elastic

2日目に続く...

日本語形態素解析エンジンKuromojiについて調べた

はじめに

とある事情(仕事)により、日本語の形態素解析エンジンKuromojiについて調べる必要があったので、ドキュメントとコードを読み込んだ。 形態素解析とは、ものすごく簡単に言うと、文章をその構造や品詞に細かく分解することです。分解された単位をトークンと呼ぶ。(イメージとしては、単語や助詞がトークンとなりえる。)

形態素解析 - Wikipedia

特に、自然言語処理(NLP)なんかでは馴染みがあるのでは?(私は素人なので...) 形態素解析は、主に利用する辞書の精度(網羅率)に大きく依存する形になります。例えば「ほげふが」という文章を解析するとして、辞書に「ほげ」と「ふが」が存在している場合、["ほげ", "ふが"]と2つのトークンに分解することができる。(これをトークナイズと呼ぶ。) 同じく文章をトークンに分解する方法として、N-gramがあります。Nに数字が入るわけですが、例えば2-gramで文章「ほげふが」をトークナイズする場合は、["ほげ", "げふ", "ふが"]と3つのトークンを生成することができる。

なおApatche版とAtilika版の2つが存在しますが、本記事では Atilika版 version 0.9.0を対象としている。

Kuromoji

概要

Java製の日本語形態素解析エンジン。 公式
kuromoji - japanese morphological analyzer

ソースコード github.com

単語辞書

Kuromojiでは、ユーザ側は用意されている単語辞書(例. kuromoji-ipadic)に加えて、ユーザ独自で固有名詞等を指定できるユーザ辞書を利用できる。 また、内部的にはこれらの辞書に含まれない単語を、「未知の」単語辞書として保持しているようです。ちなみに未知の単語辞書については、そのカテゴリによって自動的にトークン化される。例えば「123#.!」という文章がある場合、["123", "#.!"]と数字、記号のカテゴリにトークン化される。詳しくは以下の実装を確認してほしい。

kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

Kuromojiの解析モード

トークン化する際の解析粒度に応じて、モードが3つほど存在する。

  • Normalモード デフォルトモードで、辞書にのっとってトークナイズする。 未知の単語については、上記の方法にのっとり、カテゴリごとにまとめてトークナイズする。

  • Searchモード Normalモードに加えて、複数の言葉が組み合わさった単語を分解してトークナイズする。 例えば「日本経済新聞」という名詞があった場合、["日本", "経済", "新聞"]と分解する。 何が嬉しいかというと、全文検索エンジンなどで、単語を引っ掛けたい時に有効。

  • Extendsモード Searchモードに加えて、未知語をuni-gram (雲丹ではなくて「1」という意味)としてトークナイズする。 例えば、「サバゲー」が未知語の場合は、["サ", "バ", "ゲ", "ー"]となる。

内部で用いられるアルゴリズム

  • Patricia Trieを使ったFinite State Transducerによる辞書管理。
  • Viterbi アルゴリズムによって形態素ラティスを作成し、尤もらしいトークナイズをする。

形態素ラティス

下図のような、ノードがトークンとなったラティス。 各ノード・エッジにはコストが存在し、それぞれ単語辞書・解析モード別の計算式によって与えられる。 このコストを最小となる (≒ 尤もらしいトークナイズができている) パスを求めるためにViterbiアルゴリズムを用いる。

f:id:tikeda_meu:20180922143320p:plain

Viterbi

隠れマルコフモデルに基づいた動的計画法(DP)で、考えられる経路の中で尤もらしい経路を見つける。 隠れマルコフモデルに従うので、コストの部分について確率的な解釈が可能 (というかそうするのが一般) である。しかし今回のケースではコストが一意に決まるため、最小コストを確率ではなく一意に探索することが可能。

ビタビアルゴリズム - Wikipedia

Viterbiアルゴリズム - 機械学習の「朱鷺の杜Wiki」

http://www.phontron.com/slides/nlp-programming-ja-04-ws.pdf

時間計算量がO(T*N2)かかる? (T: 時間の終端、N:ノード数)

実装は以下。

kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

Patricia Trie

基数木と呼ばれる木構造のこと。 連想配列を使って各エッジに文字が張られるイメージ。 f:id:tikeda_meu:20180922145318p:plain

基数木 - Wikipedia

Pros

  • 省メモリ
  • 検索・挿入・削除 : O(k) (k: キーの長さ) なので、 (二分木と比べると、場合によっては)物凄く速い。
  • 日本語の場合は文字列長が小さいので、ここはかなり効いてくると考えられる。

    Cons

  • 文字列や、文字列に変換可能なデータしか扱えない。

Finite State Transducer (FST)

有限状態トランスデューサと呼ばれる。いわゆる有限状態オートマトンに各エッジの出力を加えたもの。 f:id:tikeda_meu:20180922145825p:plain

Luceneで使われてるFSTを実装してみた(正規表現マッチ:VMアプローチへの招待)

Kuromoji FST

Pros

  • Patricia Trieが利用可能・状態数が最小であることが保証されるため、省メモリ。
  • 決定性を持つため、入力に対する出力が一意に決定。
  • DAGなのでトポロジカルソート可能。
ラティスにおける最小コストの経路はトポロジカルソート+ Viterbiで高速に探索可能。トポロジカルソートはO(V+E) (V:ノード数, E:エッジ数)。

有向非巡回グラフ - Wikipedia

Cons

  • 先頭文字(prefix)の探索に時間がかかる。(日本語だと候補となる文字数が多すぎるので危険...) なので、先頭文字はcachingなどによる高速化で工夫される。

FSTで単語辞書を管理している。 (未知の単語辞書も含む) // Note that FST only allows the presorted dictionaries as input.

kuromoji/Builder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

ユーザ辞書を使った単語分割

こっちもFSTで保持。 surfaceが(Trie構造)FSTで保持している辞書

kuromoji/UserDictionary.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

若干しゃくとり法と似てるなと思った(は?)

qiita.com

以下が実装部分

 /** Lookup words in text
    * @param text text to look up user dictionary matches for
    * @return list of UserDictionaryMatch, not null */
    public List<UserDictionaryMatch> findUserDictionaryMatches(String text) {
        List<UserDictionaryMatch> matchInfos = new ArrayList<>();
        int startIndex = 0;
        while (startIndex < text.length()) {
            int matchLength = 0;
            int endIndex = 0;
            while (currentInputContainsPotentialMatch(text, startIndex, endIndex)) { //トークン検索
                String matchCandidate = text.substring(startIndex, startIndex + endIndex);
                if (surfaces.containsKey(matchCandidate)) {
                    matchLength = endIndex;
                }
                endIndex++;
            }
            if (matchLength > 0) { //マッチするようなトークンが見つかったらば,
                String match = text.substring(startIndex, startIndex + matchLength);
                int[] details = surfaces.get(match);
                if (details != null) {
                    matchInfos.addAll(
                        makeMatchDetails(startIndex, details)
                    );
                }
            }
            startIndex++;
        }
        return matchInfos;
    }

おわりに

まとめると、シンプルにかけます。 1. FSTによる管理で高速に辞書検索(トークンとなる候補をここで探す。) 2. 形態素ラティスを構築して尤もらしくトークナイズする(トークンとなる候補の中から、トークンを決定する。) 高速化を意識された実装になっていて、素晴らしいと思いました。

AtCoder Beginner Contest 109 に出場した

はじめに

こんばんはtikedaです。 先週の9/8(土)にAtCoderABC109が開催されたので、久々に出場しました。
最近、競プロのモチベがダダ↓↓↓だったのですが、@chokudaiさんにtweet(以下参照)を「いいね!」されてしまい、出ることに...

しかし今回は初めて全完できたので、ドヤ顔して記事を書くことができるのである(は?)

A

問題は以下を参照。
A - ABC333

AとBをかけたものが奇数か偶数かで判定すればよい。

僕のコードは以下で、ACを得た。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

int
main(void){  
  int a, b;
  cin >> a >> b;

  if( (a*b)%2 == 0){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
 
  return 0;
}

B

問題は以下を参照。
B - Shiritori

Bのくせに案外難しいめうと思ったが、map使って数える + 文字列のお尻と次の文字列の頭が一致しているか判定するのをすぐ思いつき実装した。実装に、ちょっと時間かかったのが残念なところ。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

map<string, int> mp;

int
main(void){  
  int n;
  cin >> n;
  string s[n];
  
  string p_s;
  int p_s_l;

  REP(i, n) cin >> s[i];
  
  REP(i, n){
    if( i > 0 && p_s[p_s_l-1] != s[i][0]){
      cout << "No" << endl;
      return 0;
    }    
    //cout << p_s[p_s_l - 1] << endl;    
    if(mp[s[i]] == 0){
      mp[s[i]]++;
    }
    else{
      cout << "No" << endl;
      return 0;
    }
    p_s = s[i];
    p_s_l = p_s.length();
  }
  cout << "Yes" << endl;
  return 0;
}

C

問題は以下を参照。
C - Skip

個人的に一番時間をかけてしまった問題で、難しかっためう + 1WA。 はじめは愚直にシミュレーションしてみた。Xから各y_iに対して距離(差の絶対値)を計算し、ソートした後に、最も近い距離をDの最大値として1ずつ減らしながらシミュレーションを行った。このやり方でACしたという話も聞いたので、自分の実装力の無いが故にどこかしらでバグってWAとなったと思われる。 ここで諦めて頭をつかうことにした。先程の距離を計算する際に、Xと各y_iの距離らの最大公約数が解となることに気づいたので、そのように実装したらACをした。 コーナーケースと思われるn=1の時は、単純にy_0とXの差の絶対値を取るだけで良いので、そのように実装した。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

ll gcd( ll m, ll n )
{
    if ( ( 0 == m ) || ( 0 == n ) ) return 0;
    while( m != n )
    {
        if ( m > n ) m = m - n;
        else  n = n - m;
    }
    return m;
}

ll lcm(ll a, ll b){
  if( (a==0) || (b==0)) return 0;

  return (a/gcd(a,b)*b);
}

int
main(void){  
  int n;
  cin >> n;
  ll X;
  cin >> X;
  
  ll x[n];
  ll s_x[n+1];

  REP(i, n){
    cin >> x[i];
    s_x[i] = x[i];
  }
  s_x[n] = X;  
  
  if(n == 1){
    cout << abs(x[0]-X) << endl;
    return 0;
  }
  
  SORT(s_x, n+1);
  SORT(x, n);

  ll diff[n];
  REP(i, n){
    diff[i] = s_x[i+1]-s_x[i];
    //cout << diff[i] << endl;
  }

  REP(i, n-1){
    diff[i+1] = gcd(diff[i], diff[i+1]);
    //cout << diff[i+1] << endl;
  }

  cout << diff[n-1] << endl;

  return 0;
}

D

問題は以下を参照。
D - Make Them Even

問題を読んだときに、いつかABCのC問題辺りでやったリバーシを思い出した。(問題がいつか忘れた。) 解法はいくつか存在するが、僕は以下のように解いた。

  1. 左端から右端を除く列へ、そのマスが奇数であれば-1, 右隣りのマスを+1する。
  2. 右端の列を上から下へ、そのマスが奇数であれば-1, 下のマスを+1する。

図解すると以下のようになる。

→→↓
→→↓
→→○

これでもWAをくらってしまったのだが、出力の際に行数nを入れ忘れたのが原因である。
許すまじn。

コードは以下。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

int a[575][575];

int ans1[250000];
int ans2[250000];
int ans3[250000];
int ans4[250000];

int
main(void){  
  int H, W, itr=0;
  cin >> H >> W;

  REP(i, H){
    REP(j, W){
      cin >> a[i][j];
    }
  }

  REP(i, H){
    REP(j, W-1){
      if(a[i][j]%2 != 0){
    a[i][j]--;
    a[i][j+1]++;
    //cout << i+1 << " " << j+1 << " " << i+1 << " " << j+2 << endl;
    ans1[itr] = i+1;
    ans2[itr] = j+1;
    ans3[itr] = i+1;
    ans4[itr] = j+2;
    itr++;
      }
    }
  }

  REP(i, H-1){
    if(a[i][W-1]%2 != 0){
      a[i][W-1]--;
      a[i+1][W-1]++;
      //cout << i+1 << " " << W << " " << i+2 << " " << W << endl;
      ans1[itr] = i+1;
      ans2[itr] = W;
      ans3[itr] = i+2;
      ans4[itr] = W;
      itr++;      
    }
  }

  cout << itr << endl;
  REP(i, itr){
    cout << ans1[i] << " " << ans2[i] << " " << ans3[i] << " " << ans4[i] << endl;
  }
  
  return 0;
}

最後に

ここまで見てくださってありがとうございました。参加が5回目?か6回目?ぐらいでようやっと茶色の半分に到達しました。まずは水色になれるよう精進します。めう。 それにしてもモチベーションが維持できないのでPaizaの問題でも解こうかな...辛い

NoSQLについてまとめてみる 〜後編〜

前回からの続きです。

tikeda-meu.hatenablog.com

 

NoSQLは、モデルによって大きく4種類に分けられます。

それぞれの特徴をざっと表にしました。

?はケースバイケースです。

種類 スケーラビリティ 性能 柔軟性 (高い表現力) 簡易さ
Key-Value Store o o x o
Column Store o o x o
Document Store o ? o o
Graph Store ? ? o x

 

次に代表的なDBを取り上げてみます。

Key-Value Store (KVS)

以下の記事ではantirez氏が同じKVS型DBのMemcachedとRedisを比較しています。

yakst.com

Memcachedは非常にシンプルでメモリ効率が良い一方、メモリフラグメンテーション、LRU性能、監視しやすさといった点ではRedisに軍配があがるとのこと。

Redisは会社でもたまに耳にするので、今度触ってみたいです。

Column Store 

列方向のaggregationが優秀らしい。(名前の通りか)

CassandraとHBaseの比較をしている以下のSlideShareがわかりやすかったです。

www.slideshare.net

pp. 55~が比較スライドとなっている。耐障害性や性能、手動・自動の違いがあったりなど、Column Store型の中でも違いが大きいらしい。障害発生時の挙動が異なるようなので、ユースケースごとに使い分けるべき?

Document Store 

MongoDBやElasticsearchがこれにあたる。個人的には一番馴染みが深い。PostgreSQLもDocument orientedに分類される?のか...? (RDBかと思っていたが、要確認)

特にMongoDBは、性能をとる代わりに、結果の整合性やトランザクションがサポートされていないです。

Elasticsearchは高性能・高スケーラビリティな全文検索エンジンで、通常の検索だけでなく、集計処理やソート、スコアリングといった処理も高速に可能です。実態はLucene Indexが動いていて、裏でsegments mergingなど起こったりしています。

あと余談ですが、ElasticsearchはCAP定理でいうPを落としている(と思われます。)というのもnode全体の生存監視やshardsの管理をするMaster nodeと候補となりうるMaster eligible nodeがそれぞれ分断された場合、分断後のネットワークらはどちらも動作可能であるからです。

Elasticsearchの話も、後々まとめたいです。

qiita.com

Graph Store 

Facebookのお友達つながりなんかを表現するのに向いてるグラフです。あまり馴染みがないのですが、以下のブログが具体的なイメージの参考になりました。

グラフDBのNeo4jを1日触ってみた - Wantedly Engineer Blog

こうした複雑な関係性をRDBMSで表現しようとすると骨が折れそう、というか無理ですね。

 

今回は、各モデルについてちょっとずつ言及する形で代表的なDBをまとめました。

実際に触ってみることで得られる知見もあると思うので、手を動かしていきたいですね。

 

NoSQLについてまとめてみる 〜前編〜

はじめに

こんばんは、tikedaです。

7月末までは時系列データ解析のお仕事に携わっていました。8月から元の部署へ戻り、お仕事させて頂いています。

今私がいるチームでは、主にストレージ系の研究開発に取り組んでいます。私自身はDBや分散ストレージの知識に乏しいので、これを機に勉強しようと思い、その証を、記事として残していこうと思っています。間違いなどありましたら、ご指摘いただけると幸いです。

前編は概要だけまとめます。

RDBとNoSQL

DBMS(Data Base Management System)をざっくり分けると、テーブルを組み合わせて表現するRDB(Relational Data Base)とその他のNoSQL(Not-only Structured Query Language)に分けられます。

それぞれの特徴やPros/Consは、以下の記事の解説がわかりやすいです。

qiita.com

トランザクションのサポートや拡張性など、色々なトレードオフがありますが、利用シーンによって使い分けることが大切だと感じました。

中でも今回は、NoSQLについて調べます。

 

NoSQLって何?

以下の記事が非常に参考になりました。

qiita.com

データモデルによって、大きく4種類に分けられます:

ざっとこんな感じです。

 

次回は 各DBの特徴についてまとめます。