こんにちは、 @kz_morita です。 Rust で AtCoder に参加しているのですが，以前は CLion を用いてコードを書いていました． その時の記事は以下になります． 競技プログラミングのためのCLion環境を構築した 今回は neovim だけで環境が整うように，色々探していたところ cargo-compete というすばらしいライブラリを見つけてこれを使ったら，非常に AtCoder がやりやすくなったので，簡単に紹介します． インストールと前準備 コンテストの前にインストールと前準備をする必要があります． 以下のとおりです． $ cargo install cargo-compete # AtCoder用のディレクトリ作成 $ mkdir atcoder $ cd atcoder # atcoder ように初期化 $ cargo compete init atcoder コンテストの流れ コンテストは以下のような流れでおこなってきます． # コンテスト開始後，コンテストを作成 # 以下は ABC196 の例 $ cargo compete new abc196 # 上記でできるディレクトリへ移動 $ cd abc196 # 問題ページをブラウザで開く $ cargo compete open # rust でコードを解く.

こんにちは、 @kz_morita です。 最近また，競技プログラミングをちゃんとやろうと思い，まずは全探索からということで bit 全探索の問題を解いたりしていました． C - Switches 今回は，Rust で bit 全探索する方法についてまとめます． bit 全探索とは bit 全探索は，全探索の一つで組み合わせを列挙するような用途に使用できます． 例えば { A, B, C, D } の文字列の部分集合を全探索するようなケースを考えます． これは，二進数で，0000 ~ 1111 までの数値を考え，各桁のbit を { A, B, C, D } と対応付けると すべてのパターンを探索できるといった考え方です． すなわち，{ A, B, C, D } からなるすべての部分集合を求めるには，0 ~ 31 (0 <= i < (1«4)) まで数え上げれば良いことになります． 0000 => {} 0001 => { A } 0010 => { B } 0011 => { A, B } 0100 => { C } 0101 => { A, C } .

こんにちは、 @kz_morita です。 今回は，Apache Benchmark を用いて負荷テストをしたのでその方法についてまとめます． 負荷をかけてみる Apache Benchmark を用いると比較的簡単にWebサービスなどに対して負荷をかけることができます． よく使うオプションとして，-c と -n と -t があります． -c: 並列数を指定できます -n: リクエスト数を指定できます -t: 負荷をかける秒数を指定できます 以下にコマンドの例と，実行結果の例を載せます． # 10 並列で，10秒間 負荷を与える $ ab -c 10 -t 10 http://localhost:1313/ This is ApacheBench, Version 2.3 <$Revision: 1807734 $> Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/ Licensed to The Apache Software Foundation, http://www.apache.org/ Benchmarking localhost (be patient) Server Software: Server Hostname: localhost Server Port: 1313 Document Path: / Document Length: 58811 bytes Concurrency Level: 10 Time taken for tests: 2.

こんにちは、 @kz_morita です。 自分は，普段 Thinkpad P43s に Windows10 と Ubuntu18.04 LTS をデュアルブートして使用しているのですが，あるとき windows10 で Minecraft で遊びおえて，さて作業するかと再起動したら Ubuntu が立ち上がらない．．．という状態になっていました． 今回は，その復旧のためにやったことをログとしてまとめておこうと思います． 環境と背景 もともとの, Ubuntu の環境ですが以下のような手順で行っていました Windows のドライブを縮小する Ubuntu の iso をダウンロードする UNetBootin というツールで USB に Ubuntu の LiveCD を書き込む LiveCD から Ubuntu をインストール Ubuntu のセットアップなどについては，以前記事を書きました なので，grub2 のブートローダーが起動後に動いていて，その画面で ubuntu を起動するか，Windowsを起動するか (Windows Boot Manager) を選択できるようになっていました． しかし，Windows で Windows Update をして再起動したところ，grub2 のブートローダーが立ち上がらず直接 Windows が立ち上がるようになってしまいました． 復旧作業 とりあえずぐぐる とりあえず，「ubuntu not booting after windows update」 などで調べると同様の事象はよく起こるようです．

こんにちは、 @kz_morita です。 最近， Web配信の技術 - HTTPキャッシュ・リバースプロキシ・CDNを活用する の本を読んでいて，Cache-Control 難しいなと思ったのでメモがてらまとめます． Web配信の技術 - HTTPキャッシュ・リバースプロキシ・CDNを活用する Cache-Control ヘッダー HTTP でキャッシュに関係する設定を行うヘッダーです．リクエスト時とレスポンス時の両方に指定できるようです． リクエスト時 Cache-Control: max-age=<seconds> Cache-Control: max-stale[=<seconds>] Cache-Control: min-fresh=<seconds> Cache-Control: no-cache Cache-Control: no-store Cache-Control: no-transform Cache-Control: only-if-cached レスポンス時 Cache-Control: must-revalidate Cache-Control: no-cache Cache-Control: no-store Cache-Control: no-transform Cache-Control: public Cache-Control: private Cache-Control: proxy-revalidate Cache-Control: max-age=<seconds> Cache-Control: s-maxage=<seconds> また，対応していないブラウザもありますが，以下の拡張もあります． Cache-Control: immutable Cache-Control: stale-while-revalidate=<seconds> Cache-Control: stale-if-error=<seconds> https://developer.mozilla.org/ja/docs/Web/HTTP/Headers/Cache-Control RFCは HTTP/1.1: キャッシュ処理 (日本語訳) で仕様が策定されています． キャッシュの種類 キャッシュの性質による種別について書いていきます． キャッシュには，private と shared があります．

こんにちは、 @kz_morita です。 今回は，Kotlin でリストをシャッフルする方法についてまとめます． 破壊的シャッフル Kotlin の Array 型 もしくは，MutableList 型に shuffle というメソッドが用意されているのでこちらを利用します． fun main() { val list = mutableListOf(1,2,3,4,5,6,7) list.shuffle() println("Shuffled: ${list}") } これを実行すると以下のような結果が得られます． Shuffled: [7, 5, 2, 6, 3, 4, 1] 破壊的な，シャッフルなのでもとのリストを変更するため，List 型 (Immutable) には使用できません（定義されていません） fun main() { val list = listOf(1,2,3,4,5,6,7) list.shuffle() // Compile Error! println("Shuffled: ${list}") } fun <T> Iterable<T>.shuffled(): List<T> 非破壊的シャッフル Shuffled というメソッドが用意されているのでこちらを利用します． fun main() { val list = listOf(1,2,3,4,5,6,7) val shuffledList = list.

こんにちは、 @kz_morita です。 前回の記事 で深さ優先探索を実装したので今回はその幅優先探索バージョンになります． ちなみに，ソースコードこちらに雑に上げてます． https://github.com/foresta/rust-tree データ構造 前回と同じものですが再掲します． #[derive(Clone, Debug, PartialEq, Eq)]pubstruct TreeNode{pubval: String,publeft: Option<Rc<RefCell<TreeNode>>>,pubright: Option<Rc<RefCell<TreeNode>>>,}よくある木構造だと enum で表現して Box を使うものをよく見ると思いますが LeetCode で前提となっていた Rc<RefCell<TreeNode>> 形式で今回は考えます． 木構造自体は以下のようなものを作ります． fn create_tree_node()-> Rc<RefCell<TreeNode>>{// // A // B C // D E F // G H I J K // letmuta=TreeNode::new("A");letmutb=TreeNode::new("B");letmutc=TreeNode::new("C");letmutd=TreeNode::new("D");letmute=TreeNode::new("E");letmutf=TreeNode::new("F");letg=TreeNode::new("G");leth=TreeNode::new("H");leti=TreeNode::new("I");letj=TreeNode::new("J");letk=TreeNode::new("K");d.left=Some(Rc::new(RefCell::new(g)));d.right=Some(Rc::new(RefCell::new(h)));e.right=Some(Rc::new(RefCell::new(i)));f.left=Some(Rc::new(RefCell::new(j)));f.right=Some(Rc::new(RefCell::new(k)));b.left=Some(Rc::new(RefCell::new(d)));b.right=Some(Rc::new(RefCell::new(e)));c.right=Some(Rc::new(RefCell::new(f)));a.left=Some(Rc::new(RefCell::new(b)));a.right=Some(Rc::new(RefCell::new(c)));Rc::new(RefCell::new(a))}BFS (breadth-first search) 今回は幅優先探索なので，以下のようにアルファベット順で走査します． // // A // B C // D E F // G H I J K // A → B → C → D → E → F → G → H → I → J → K 幅優先探索でも再帰的な関数で実現することができます．

こんにちは、 @kz_morita です。 LeetCode で遊んでいて Rust で木構造の実装をしたのでまとめておきます． ちなみに，ソースコードこちらに雑に上げてます． https://github.com/foresta/rust-tree データ構造 以下のようなデータ構造で木構造を表現します． #[derive(Clone, Debug, PartialEq, Eq)]pubstruct TreeNode{pubval: String,publeft: Option<Rc<RefCell<TreeNode>>>,pubright: Option<Rc<RefCell<TreeNode>>>,}よくある木構造だと enum で表現して Box を使うものをよく見ると思いますが LeetCode で前提となっていた Rc<RefCell<TreeNode>> 形式で今回は考えます． 木構造自体は以下のようなものを作ります． fn create_tree_node()-> Rc<RefCell<TreeNode>>{// // A // B C // D E F // G H I J K // letmuta=TreeNode::new("A");letmutb=TreeNode::new("B");letmutc=TreeNode::new("C");letmutd=TreeNode::new("D");letmute=TreeNode::new("E");letmutf=TreeNode::new("F");letg=TreeNode::new("G");leth=TreeNode::new("H");leti=TreeNode::new("I");letj=TreeNode::new("J");letk=TreeNode::new("K");d.left=Some(Rc::new(RefCell::new(g)));d.right=Some(Rc::new(RefCell::new(h)));e.right=Some(Rc::new(RefCell::new(i)));f.left=Some(Rc::new(RefCell::new(j)));f.right=Some(Rc::new(RefCell::new(k)));b.left=Some(Rc::new(RefCell::new(d)));b.right=Some(Rc::new(RefCell::new(e)));c.right=Some(Rc::new(RefCell::new(f)));a.left=Some(Rc::new(RefCell::new(b)));a.right=Some(Rc::new(RefCell::new(c)));Rc::new(RefCell::new(a))}DFS 深さ優先探索するので，以下の順番で走査します． A → B → D → G → H → E → I → C → F → J → K

こんにちは、 @kz_morita です。 ラムダノートの Vol.1, No.1 をみて TCP の再送制御を見てとてもおもしろかったので，将来の自分用にRFCのリンクをまとめておきます． n月刊ラムダノート Vol.1, No.1(2019) TCP の再送制御の課題 トランスポート層のTCPのミッションは，通信相手にパケットを届けることだが，インターネットの経路にてパケットが失われてしまうことが多々あり，そのパケットの喪失を検出する必要があります． パケットの無事に届いたことを確認するためには，パケットの受信者からの確認応答を受け取ることで実現できるので，一定時間経っても確認応答が帰ってこないパケットを喪失したとみなすことができ，再送することができます． この「一定時間」を 再送タイムアウト時間 といい, いかに効率の良い再送タイムアウト時間を設定するかというのが，TCPの再送制御の課題なのかなと思います． 再送タイムアウト時間が短ければ，パケットの喪失を見逃す機会は減りますが，不要な再送が増えネットワーク上に無駄なパケットが大量に流れてしまうことになります．逆に再送タイムアウトがながければパケットの喪失を検知出来ない可能性があります． 書籍の中で，RFCがいくつか紹介されていたので，ざっと目を通しつつまとめておきます． RFC RFC 7323 - TCP Extensions for High Performance RFC 7323 RFC 7323 (日本語訳版) 3. TCP TImestamps Option の内容が書籍内でも記載されていました． TCP ヘッダの拡張オプションのタイムスタンプオプションを利用して，RTT (ラウンドトリップタイム) つまりパケットを送信してから確認応答が帰ってくるまでの時間を計測する内容についてです． RFC 6298 - Computing TCP’s Retransmission Timer RFC 6298 RFC 6298 (日本語訳版) 計測した，RTT値から再送タイムアウト値を計算する方法について書かれています．

こんにちは、 @kz_morita です。 今回は，Rustで API Server を作る上で，4層のレイヤードアーキテクチャを試してみたのでまとめていきます． 今回作成したものはこちらのリポジトリにあげています． https://github.com/foresta/rust-api-architecture-sample レイヤードアーキテクチャについて DDDや，クリーンアーキテクチャで採用されている，関心事単位で層を区切るアーキテクチャで主に，APIのHTTP周りの処理，アプリケーションの手続き，業務ドメイン，DBなどのインフラみたいに層があります． 今回は，以下のディレクトリ構造のような，レイヤーを作成してみました． ./src ├── domains ├── infrastructures ├── usecases ├── server └── main.rs domain: 業務ドメインなど，できるだけ外部のライブラリには依存しない infrastructures: DBなど, diesel などを使用する usecases: アプリケーション用の手続き server: HTTP 周りの処理,主に actix-web をつかって routing したりなど また，Rustにおける Module の分け方については，前回のこちらの記事を参照してみてください． Rust における module について 実装 今回は，document という title と body を持つデータのCRUDを実装してみました． 実際の処理の流れどおり，main → server → usecases → domains → infrastructures という順番で紹介してみます． main.rs 今回は，main の処理はシンプルに server を実行するだけとしました．依存関係の注入などは server 側でやっています．

こんにちは、 @kz_morita です。 今回は，Rust における module についてまとめます． ファイル内でモジュールを定義 Rust では，mod キーワードで module を定義することが出来ます． mod greet{pubfn hello(){println!("Hello world");}}fn main(){greet::hello();}モジュール内で定義した，関数などをモジュール外から呼び出すと場合には，pub キーワードが必要になります． mod greet{pubfn hello(){println!("Hello world");}fn private_hello(){println!("Private Hello world ");}}fn main(){greet::hello();greet::private_hello();// Compile Error }上記のコードは以下のようなエラーが表示されます． error[E0603]: function `private_hello` is private --> src/main.rs:13:12 | 13 | greet::private_hello(); | ^^^^^^^^^^^^^ private function | note: the function `private_hello` is defined here --> src/main.rs:6:5 | 6 | fn private_hello() { | ^^^^^^^^^^^^^^^^^^ error: aborting due to previous error For more information about this error, try `rustc --explain E0603`.

こんにちは、 @kz_morita です。 2020 年もあっという間に終わってしまい，2021 年が始まったので今年のやりたいことや目標を書いてみます． 2020年はどうだったのか 2020年の抱負とかやりたいこと 2020 年は仕事の Engineering 以外にも，自分のやりたいことやサービスを作ったり，Computer Science を学んだりすることが目標でした． 結果としては，仕事や副業で色々なチャレンジはできたのは結構良かったです．新しい技術へのチャレンジなども多く出来ました．ただ仕事以外の部分があまり出来ませんでした． 2021年の抱負 2021 年は以下を頑張りたいです． Computer Science の学習 情報検索システムについて 英語 体力を付ける Computer Science の学習 Computer Science は引き続き学習していきたいです．特に情報検索周りをやっていきたいですが，それ以外にももっと基礎的な能力が足りてないので，学んでいきます． 具体的には，データ構造とアルゴリズム，OS，コンパイラ周りなど．すべてできるとは思いませんが，興味ある分野をすこしずつ学べたら良いなぁと思っています． 情報検索システムについて 情報検索は，面白くて現在学んでいる最中なので引き続きやっていきます． 情報検索を学んでて思ったこととしては，情報検索は効率化，高速化の分野なのだなぁということです． 検索は，全文検索ですべて調べ尽くせばかならずみつかるものですが，それをいかに実用できるレベルまで高速化するか？という話がおおく，その過程でいろいろな情報科学の知識（データ構造など）が出てくるので調べていて面白いです． 簡単な検索システムをつくってみたりしていきたいです． 英語 普段検索していくと，英語のドキュメントを読むことが多いですがその読むスピードが遅かったり，なにかと英語が自分の行動のキャップになることを実感してきました． 別に英語のプロフェッショナルになる気はないですが，自分の行動に制限をかけないレベルには学んでいきたいです． 体力を付ける 30歳一歩手前にきて，継続的に作業したり学んでいくのにも体力がひつようだと実感するようになってきました．今後一生なにかの作業をしていたいので，そろそろ運動や健康に気をつけて体力をつけていきます． まとめ 色々やりたいことがありますが，今年も健康で元気に楽しく暮らしていきたいですね． 振り返りをする時に，今年は頑張ったなぁ，充実していたなぁと思える一年にしていこうと思います．

こんにちは、 @kz_morita です。 今回は、Cypress を用いた E2E テストの DOM の特定方法についてまとめます。 セレクターによる DOM の特定 通常、DOM を特定するのは、ID や Class やHTML要素を指定して行います。 JS では以下のような感じです。 // ID 指定 var dom1 = document.querySelector('#id'); // クラス指定 var dom2 = document.querySelector('.hoge'); // 要素指定 var dom3 = document.querySelector('ul > li'); Cypress でDOM を特定するためにも同じような方法が用いられ、以下のように要素の取得をすることができます。 cy.get("#id") cy.find(".class") しかし、DOM に ID や、class が振られていなくて要素の特定が難しいケースがあります。とくに、CSS in JS などで css 用に class を振っていない場合もあるかと思います。 実際に開発しているサービスでは、emotion というライブラリを用いていて、結果としてDOMの特定が難しいという問題がありました。 また、クラスや要素で DOM を特定する方法は、DOM の構成が変わったりする場合に、E2E テストが変更に弱くなってしまったりします。 テスト用の data 属性をつける Cypress の公式 ドキュメントによると、テスト用の data 属性をつける方法が推奨されています。

この記事は、 write-blog-every-week Advent Calendar 2020 の 22 日目の記事です。 こんにちは、 @kz_morita です。 年末になり、今年を振り返るモードになっていますが、今年もなんとか週一でのブログ更新を続けることができました。 週一で書き始めたのが、2018年8月31日の この記事 からなので、2年3ヶ月 ほど続いたことになります。 こんなに続いたのは、完全に write-blog-every-week のおかげです。今年もありがとうございました。 write-blog-every-week については、こちら Write Blog Every Week 勢いで週一ブログ書くslackグループを作った write-blog-every-week について word cloud で振り返る 昨年の記事 でもやりましたが、今年のブログを word cloud で振り返ってみます。 手法は、去年と同じなので、よかったら参考にしてみてください。 word cloud で今年のブログを振り返る どうやら、Rust についてが多かったようです。 確かに、rust タグの記事をみてみると今年で、7 件書いていたようです。 rust タグ あとは、情報検索とネットワーク周りもおさらいしていたので、検索 や、通信 のようなワードも大きいですね。 可視化してみると面白いです。 来年に向けて 今年も振り返るとたくさんブログを書いたなぁと思います。 前半は仕事で忙しかったですが、終盤で自分がずっとやりたかった検索周りの話や、Rust について記事をかけていたのはよかったかなぁと思います。 来年も、自分が学びたいことを中心にブログを書き続けていきたいですね。 来年のブログ振り返りで、面白い wordcloud が見れるように頑張ります。

こんにちは、 @kz_morita です。 今回は，情報検索システムのクエリのスペルミスの修正について概要をまとめます． スペルミス修正とは Webの検索システムにおいて，ユーザーが入力したクエリがスペルミスしている可能性もあり，スペルミスの修正を行う場合もあります． Google 検索などでも，「もしかして○○」といったものが表示され，スペルミスを検知していることがわかります． 編集距離 スペル修正を行う場合以下のような実装を行う必要があるかと思います． １. 誤ったスペルのクエリに対して，もっとも近いものを選択する ２. 正しいスペルのクエリが複数ある場合には，より一般的なものを選択する ここで，もっとも近い というワードが出てきましたが，検索クエリと辞書内にある用語の距離を図る必要があります．つまり文字列と文字列の距離を判定するロジックが必要になります． そこで 編集距離 (レーベンシュタイン距離) という考え方があります． 文字列 s1 から s2 に変換するために以下のような編集走査を何回行う必要があるか？その最小値を編集距離と呼びます． 文字列に文字を挿入する 文字列から文字を削除する 文字列の文字を別の文字に置き換える 具体的に例えば，s1 = cat , s2 = dog といったケースを考えます． cat を dog に変換するためには， c -> d , a -> o , t -> g といった操作を行えば良いことから，cat と dog の編集力は 3 ということが出来ます． 一番ちかいクエリが複数あるケース たとえば，入力されたクエリが grnt だとした場合に，以下のような用語が修正先の候補として考えられます． grant grunt これらはどちらも，編集距離でいうと 1 になるため，どちらを候補として返せばよいかを決める必要があります．

こんにちは、 @kz_morita です。 情報検索のシステムについて勉強中で，以下のような記事をこれまでにまとめました． 情報検索の概要について 情報検索と転置インデックスについて 検索システムと辞書・用語 今回はワイルドカードのクエリについてまとめます． ワイルドカードクエリとは ワイルドカードクエリとは，以下のようなクエリのことを指します． pro*ing このようなクエリに対して，programming や，processing などといったワードで検索したような文書を返すことを目的にしたものです． このような検索を実現するための手法について見ていきます． 辞書とデータ構造 その前に，検索システムにおける語彙とそれを扱うデータ構造についてまとめます． 検索システムでは，検索されたワードに対して一定の正規化などを行った後にそのワードを辞書から見つけ出す必要があります．辞書から見つければその後は，ポスティングリストを参照し文書IDを得るといった流れになります． 辞書から見つけるのには，通常の全探索だと語彙数を N としたときに O(N) の計算量となります． 効率よく探すために以下のようなデータ構造が用いられます． ハッシュ 探索木 ハッシュ ハッシュは，用語を特定のハッシュ関数でハッシュ化して格納するもので，計算量は (ハッシュ計算する時間を除いて) O(1) になり高速です． ただし，デメリットもあります． まず，ハッシュの衝突です．ハッシュの計算結果は十分大きい数の数値のため通常は衝突を気にするケースはあまりありませんが，Web 検索システムなど扱う語彙の数が膨大なシステムnの場合は，本当に衝突を気にする必要がないかどうかをよく検討する必要がありそうです． ２つめに，似ている語彙を探すことが困難なことがあります．語彙がすこしでも違えば，まったく別のハッシュ値になることも普通にありえるので柔軟的に扱うのは難しいです． 探索木 探索木は，データを木構造で扱うことで O(logN) の計算量で探索できるようにしたものです． 以下のようなものが代表的です． 二分木 (binary-tree) B 木 (B-tree) 詳細はここでは扱いませんが，検索システムでは，B-tree が用いられることが多いそうです． B-tree については，下記のサイトなどがわかりやすかったです． RDBMSで使われるB木を学ぼう （1/3）－ ＠IT ワイルドカードクエリの実現方法 後方一致 まずは，以下のような後方一致のワイルドカードクエリについて考えます． prog* 後方一致のクエリに関しては，以下の図のように 探索木を辿っていって prog までたどれたらその子供の木でアクセスできる用語すべてのリストが用語リストになります． この用語のリストの論理積のクエリととらえて，あとは転置インデックスから文書IDを取得すれば prog* の検索を実現できます．

こんにちは、 @kz_morita です。 2020年も気がつけばのこりあとわずか．ということで今年触った技術とかやったことについて振り返ってみます． 記憶と Tweet をたよりに思い出せる限り書いていこうと思います． 1月 ~ 3月 大まかに，アセンブリとかRust に入門したりしてました． 業務では，Kotlin とか gradle 周りがメインだったようです． アセンブリに触れてみる この月は，「プログラムはなぜ動くのか？」という本を読んでいました． プログラムはなぜ動くのか？を読んだ そこから派生して，アセンブリ言語についていろいろと調べてました． その結果として，簡単な C言語のプログラムからアセンブリされたコードを眺めるということをしてました． アセンブリコードを眺めてみる HHKB Hibrid Type-S 原価バーいって触ってきたりしてました．結局買ってません． 原価バーいってHHKB Hibrid Type-S 触って来たけど、良かった！ 静音化した HHKB BTと打感そんなに変わらなかったから購入はないかな。 pic.twitter.com/GVXXqBhp8F — kz_morita 𓆏 (@kz_morita) January 13, 2020 Rust 入門 やっていき pic.twitter.com/PpjYIr6KE5 — kz_morita 𓆏 (@kz_morita) January 29, 2020 所有権とか，ライフタイムとかと戦っていました． Rustの所有権について Rustのライフタイムについて あとは，actix-web とかフレームワークをさわったりしてました． Rustのactix-web を触ってみる 業務 業務では，新規プロジェクトが始まって，Kotlin の開発環境とか，gradle とかと戦っていました． 新しいプロジェクトが，Front が，React + TypeScript で，サーバーサイドが Kotlin という構成だったのでそのあたりのキャッチアップが多かったです．

こんにちは、 @kz_morita です。 今回は，検索システムにおいてインデックスを構築する際の辞書と用語についてまとめます． 辞書と用語 検索システムは，検索クエリに合致する文書を探すことが目的のシステムです． 効率的に探すために，インデックスを事前に構築します． 情報検索と転置インデックス 上記の以前書いた記事にもありますが，インデックスには用語集である辞書と，その用語が出現する文書IDを記した，ポスティングリストがあります． 文書の取得からこの辞書を構築するまでについて手順を説明します． 辞書作成の手順 辞書を作成するには，おおまかに以下のような手順が必要になります． 文字列の取得 語彙の決定 語彙の正規化 これらについてまとめます． 文字列の取得 検索システムの検索対象である文書ですが，データある以上もとのデータは byte 列になります． これを文字列として認識するためにはいくつかの懸念点があります． 文字コード byte 列を文字列として認識するためにはその文書がどの文字コードで書かれているかということを知る必要があります． 文字コード判別の手段として以下のようなものがあります． 機械学習分類 ヒューリスティック ユーザー選択 文書メタデータ 多くは，下３つが使われているようです． ちなみに文書メタデータは，HTML の meta 属性のようなものと考えると良さそうです． ファイルタイプ ファイルのタイプにより特別な復号化が必要な場合があります． zip docx xml PDF たとえば，zip であれば解凍する必要がありますし，xml などでも，&amp; など特別なエンコードをもとに戻したりする必要があります． 言語 アラビア語など文書の読む方向が違うような言語についても，必要があれば考慮する必要があります． 語彙の決定 文字列が取得できたら，そこから語彙を決定します．語彙を決定するために文字列から Token 列を得る必要があります． Token 化は文書の言語に依存するため，分類器などを用いて言語を推定します． たとえば，英語などは単語がスペースで区切られているため分割は比較的簡単ですが，日本語などでは区切られてないため形態素解析などで語分割を行います． とはいえ，英語などでも，アポストロフィの扱いなど考えなければならない点があります． Token 列が取得できたら，語彙として使用しないワードをストップワードとして登録して辞書から除外することがあります． たとえば，日本語の助詞などをストップワードに登録することが多いです． ストップワードをつくることのメリットしては，助詞などはとても頻度が多いため辞書とポスティングりすとの個数を大幅に減らせることにあります． ただし，歌のタイトルや，格言など，ストップワードが大きく影響をうけるような分野もあるため，Web検索などでは使用されない傾向にあるそうです． その代わりとして，言語統計などを用いて，頻出語をどのように扱い削減するかに焦点が当てられています． 語彙の正規化 語彙が決定したら，正規化を行います． 表記が異なっていても，等価として扱いたいものを一つに正規化をします． たとえば，USA と U.

こんにちは、 @kz_morita です。 E2E Test を Github Actions で実行する際に，VPN 内にある API Server にアクセスする必要があったのですが，Security Group に Github Actions の Public IP を追加する方法でうまく動かすことが出来たので今回はそのことについてまとめます． 背景とか Web Client 側の E2E テストを実施するにあたり，API Server に接続する必要があったのですが，開発環境の API Server は VPN 内からのみアクセスできるようになっていました． そのため，Github Actions から API Server にアクセスすることが出来ず E2E テストが失敗していました． E2E Test 時のみ アクセスすることができるように，Security Group に Github Actions の Public IP を追加する対応をしました． 実現方法 以下のような yaml で Security Group に Github Actions の Public IPを追加することができました. name:E2E Test with Cypress (Node.

こんにちは、 @kz_morita です。 Cypress を使って現在開発しているプロジェクトに，E2E Test を導入してみたらなかなか良かったので，Cypressの特徴などについてまとめていきます． Cypress とは https://www.cypress.io/ Cypress は JavaScript の E2E テストのフレームワークです． 環境の構築がとても簡単で，テストもシンプルにかけるのが特徴的です． たとえばインストールはこれだけです． $ npm install cypress テストも以下のように比較的にシンプルに書くことが出来ます． describe('Login Test', () => { it('Login', () => { // user データ を取得 cy.fixture('users').then((users) => { // localhost:3000 にアクセス cy.visit('http://localhost:3000') // ヘッダー内のログインボタンをクリック cy.get('header').contains('ログイン').click() // メールアドレスのフォームに，テストデータの メールアドレスを入力 cy.get('#email').type(users.email) // パスワードフォームに，テストデータのパスワードを入力 cy.get('#password').type(users.password) // ログインボタンをクリック cy.get('button[type="submit"]').click() // ヘッダーからログインボタンが消えていることを確認する cy.get('header').should('not.contain', 'ログイン') }) } Test Runner と Dashboard Cypress には Test Runner と Dashboard があります．

こんにちは、 @kz_morita です。 今回は，React + TypeScript + emotion で作成している環境に対して Storybook を導入しようとして手こずった点があったのでその点について簡単にまとめます． 環境について 今回の環境は以下の通りです． - React: 17.0.1 - TypeScript: 4.0.3 - @emotion/core: 10.1.1 - @emotion/styled: 10.0.27 また，emotion の css props を /** @jsx jsx */ という JSX Pragma を書かずに使用するために，@emotion/babel-preset-css-prop を導入しています． webpack は，できるだけ編集したくないため， react-app-rewired と customize-cra を用いて以下のようにカスタマイズをしています． package.json "scripts": { "start": "HTTPS=true react-app-rewired start", "build": "react-app-rewired build", "test": "react-app-rewired test", "eject": "react-app-rewired eject", }, config-overrides.js const { override, addBabelPreset } = require('customize-cra'); module.

こんにちは、 @kz_morita です。 今回は，検索に使われる転置インデックスについてまとめます． 検索におけるインデックスとは 情報検索システムの目的は，ユーザーが入力したクエリに関連する文書を見つけることにありますが，文書が大量にある場合は全文検索では到底探しきれないためインデックス付けを行います． インデックスをつける際は，どのような用語がどの文書に現れるかを知る必要があります． そこで，文書と用語を行列で表す方法があります．具体的には以下のようなものになります． 文書を以下のようなものだと仮定します． 文書1: I have a pen. 文書2: This is a pen. 文書3: I am grad to see you. すると，出てくる単語は，I, have, a, pen, This, is, am, grad, to, see, you となります．これらの対応表を書くと以下のとおりです． (現れるところは 1 それ以外は 0) I have a pen This is am grad to see you 文書1 1 1 1 1 0 0 0 0 0 0 0 文書2 0 0 1 1 1 1 0 0 0 0 0 文書3 1 0 0 0 0 0 1 1 1 1 1 上記を結合行列といいます．

こんにちは、 @kz_morita です。 情報検索の概要について学んだことをまとめます． 情報検索とは 情報検索の目的は，大規模なコレクションのなかから必要な情報を含むデータや文書を見つけることです． 見つけたいデータは，テキストや画像，音声など様々あります．（主にテキストの検索について語られれていることが多いと思います) テキストなどのように探したいデータは非構造的なものが多いため，どのように効率的に探すのかといったことが重要です． 情報検索の規模も，個人的な PC 内の検索といった比較的小さいものから，Web 検索といった膨大な量の文書の中から必要なデータを探すといったものがあり，その中間に各ドメインごとの検索といったものもあります． adhoc 検索 1回のクエリでユーザーがほしい文書，情報を検索して取得するものを adhoc 検索と呼びます． ユーザーがクエリとして入力していないもので，それがユーザーに対して価値がある欲しい情報であれば，関連している文書として返すことも重要になっています． 論理検索モデル Google 検索などでも採用されていると思いますが，検索したい用語を AND や OR や NOT で結合して検索できるものが 論理検索モデルです． dog AND cat などと検索して，犬と猫が同時に現れる文書を検索するようなモデルになります． 検索の方法 検索の方法は様々ありますが，まず一番シンプルなのは線形に全探索することだと思います．いわゆる grep です． こちらは，シンプルである程度の規模の文書のコレクションであれば効果的ですが以下のようなことは難しいです． 大規模のコレクションを高速に処理する より柔軟な検索クエリに対応する (たとえば，NEAR 検索 dog の近くに cat と書かれている文書 etc) 検索結果をランク付けする これらを解決するために，文書をあらかじめインデックス付けをすることが重要です． 検索システムの評価 検索システムは，どれだけユーザーの要求する結果を返せるのかというところが評価対象になります． 評価指標としては以下の２つなどがあげられます． 適合率 (precision) : 返した文書のうちに価値あるものの割合 再現率 (recall) : 関連する全文書のうち検索システムが返した文書の割合 まとめ 情報検索の概要についてざっくりまとめました．次はインデックス周りについてまとめていきたいと思います． 参考 情報検索の基礎

こんにちは、 @kz_morita です。 今回は，React で Webサービスを構築している際に，Facebook ログインを実装しようとしてちょっと躓いたことをまとめます． 環境と対象のコード 今回のシステムが，Web-Server と API-Server が別れており，Web-Server では主に，ページのレンダリングやリダイレクト周りの処理を行い，提供するコンテンツに関しては，API-Server から取得するといった構成になっていました． graph LR; Browser--WebServer; WebServer--APIServer; Browser --APIServer; facebook login には， react-facebook-login を利用していました． import React from 'react'; // 独自のデザインのFacebookLogin ボタンを用意するため，こちらを import import FacebookLogin from 'react-facebook-login/dist/facebook-login-render-props'; export const LoginPage: React.FC = () => { const handleAuthWithFacebook = React.useCallback( (response: FacebookAuthResponse): void => { if (response == null || response.accessToken == null) return; // Facebook の accessToken つかって，signin する処理 signinWithFacebook(response.