全文検索エンジンについて学んでいたのだけど、転置インデックスのデータ構造という観点から見るといろいろ面白かったのでまとめてみる。 転置インデックスの具体的な構造 全文検索では、転置インデックス(Inverted index)という仕組みを使う。詳しくは第3回…

ヒーローは眠らない (富士見L文庫)作者:伊丹央KADOKAWAAmazon読んだ。戦隊モノを撮るプロデューサーの話で、そういうストーリーを読んだことがなく、新鮮に読めた。語り口調もテンポよく、飽きずに一気に読めて、非常に楽しめた。基本的にはお仕事物という感…

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏作者:山田 浩之,末永 匡技術評論社Amazon検索エンジン自作入門を見ていて、WikipediaのXMLデータから文書を1000件含むXMLファイルを作成するワンライナーが出てきて、非常に勉強になったのでメモ。…

社内の技術勉強会で極大部分文字列というワードが出てきたので、自分で調べた内容をメモ。内容があっているかは保証しない。 極大部分文字列とは何か 定義は 全ての部分文字列を考慮した文書分類 に書いてある これによると、「極大部分文字列の必要十分条件…

田中圭一さんの「うつヌケ」というコミックエッセイを読んだ。とにかくむちゃくちゃ良かった。うつヌケ うつトンネルを抜けた人たち 【電子書籍限定 フルカラーバージョン】 (角川書店単行本)作者:田中 圭一KADOKAWAAmazonいろんな人にインタビューしていて…

アルゴリズム読み物を読みたくて、いろんなところでオススメされている数学ガールの乱択アルゴリズムを読んだ。なかなか興味深かった。数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)作者:結城 浩Softbank Creative/Tsai Fong BooksAmazonこの本で興味…

最近アルゴリズムの勉強でJavaを使っていて、いい機会だしどうせならJavaの言語の詳細な機能や考え方などを知りたいと思っていた。Javaをやっている人に聞いてみると「パーフェクトJava」が良いということなので読んでみた。改訂2版 パーフェクトJava作者:井…

[asin:B01N7JQX9K:detail]読んだ。肉体を改造したヤクザが魔王と呼ばれ、それを合法的に狩る職種のことを勇者と呼ぶような世界のお話。設定が独特な一方、肉体を強化する薬を投入すると、それぞれの人ごとに特殊な力を習得できるため、その点では王道ファン…

あるPatternがあるText中のどこに含まれるかという文字列マッチングの実装を最近してみている。前回、Suffix Trieでの文字列マッチングを行った。blog.shibayu36.orgSuffix Trieを利用すると、Suffix Trieを最初に構築したあと、実際にパターンを検索するの…

興味本位で自分のアルゴリズム実装repository( https://github.com/shibayu36/algorithms )のテストをCircleCIで動かしてみようと考えた。基本的にCircleCIはcircle.ymlに設定を追加したら終わりなのだけど、何を設定すればいいか少し調べる必要があったので…

以前 Javaで冪集合を生成する - アルゴリズム学習(その3) - $shibayu36->blog; で冪集合を作るメソッドを実装していた。しかし、以前の実装だとListでしか冪集合を作ることができなかった。最近パーフェクトJavaを読んで、ジェネリクスについて学んだので、…

和倉温泉に旅行に行きました。観光 & プログラミングをしていました。AKB丼(甘エビ・カニ・ブリ丼)を食す。 生卵を買うと、自分で温泉卵に出来る。塩分が強い温泉なので、自然と味がついていた。 こいつ自分も卵のキャラなくせに、絶対に子供を温泉卵にしよ…

文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。今回は…

アルゴリズムを学習していると、ある実装の速度がどのくらいか計測したいことがよくある。これまでは、currentTimeMillisを利用して、愚直にベンチマークを取っていたのだけど、結構だるい感じだった。調べてみると、jmh と nanobench という二つのツールが…

なんとなくアルゴリズム系の読み物読んでみたかったので読んだ。世界でもっとも強力な9のアルゴリズム作者:ジョン・マコーミック日経BPAmazonこの本は、著者が3つの基準で選んだ「偉大なアルゴリズム」について、エンジニアでなくても分かるような簡単な言葉…

最近、コンピュータサイエンスなどの基礎的な知識を学習するように心がけている。できる限り今後も長い期間役に立つ、寿命の長い技術や知識を付けておきたいためである。その一貫で アルゴリズムを学習 してみている。 学習をはじめて感じた課題 しかし、と…

前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズムで…

アニメーションが遅い問題を調査していて、どうやって原因を特定すれば良いかわからない状態だった。それをチャットで会話していたら同僚が「Chrome Developer ToolsのTimeline -> Bottom-Up -> Group by URL使うと良さそう」みたいなことを教えてくれた。使…