こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
ポッドキャストはリスナーの存在が見えづらいらしく聴いてるとアピールしないと更新停止してしまいがちなので定期的に感想を書いていく 聴く環境について ポッドキャストの探し方 BUSINESS WARS / ビジネスウォーズ News Connect あなたと経済をつなぐ5分間 #ニュースコネクト Off Topic // オフトピック fukabori.fm バンクーバーのえんじに屋 texta.fm プログラム雑談 Misreading Chat mozaic.fm kkeethのエンジニア雑談チャンネル 購読一覧 聴く環境について クライアントはGoogle Podcastを使っているんですけど終了してしまうし*1最近はSpotifyに誘導されがちなので、今後移行先をどうしようか迷っている そもそもGoogle Podcastの購読一覧ってどこから見るんだろうと疑問だったが、https:/
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
分散データシステム入門の決定版『データ指向アプリケーションデザイン』をたった30分で学んでみた #DataEngineeringStudy | DevelopersIO
基調講演「30分でわかるデータ指向アプリケーションデザイン」 ・ スピーカー 斉藤 太郎氏 Twitter：@taroleo / Github：@xerial Principal Software Engineer , Treasure Data 東京大学理学部情報科学科卒。情報理工学 Ph.D。データベース、大規模ゲノムデータ処理の研究に従事。その後、スタートアップであるTreasure Dataに加わり、アメリカ、シリコンバレーを拠点に活動中。日本データベース学会上林奨励賞受賞。OSSを中心にプログラミングやデータ処理を簡単にするためのプロダクトを作成している。 「30分でわかるデータ指向アプリケーションデザイン」最新の論文にも触れながら、分散データシステムの世界の魅力を伝えていきます。後半、@tagomoris https://t.co/TQ2TnsFIOT… — Taro L.
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
高速文字列解析の"別"世界 - 気ままなブログ
1月に「高速文字列解析の世界」を購入してから半年が経ちました。以下、文字列本と呼びます。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (4件) を見る 全文検索として、「CSA」や「FM-Index」が紹介されていますが、「全文検索システム」を作るには、これらだけでは不十分です。なぜなら、以下のような特徴があるからです。 文書IDの識別が遅い。 各文書IDに出現する頻度を求めるのが遅い。 ちなみに、転置インデックス(or N-gramインデックス)を使った場合、これらの処理は高速ですね。 インデックスを圧縮しているのだからしょうがないとも考えられますが、作りたいですよねぇ、「全文検索システム」。こ
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
2019年のテック系ポッドキャスト - フロントエンド・モバイル・WEB・インフラ・アジャイルなど - このすみノート
最近は忙しく、テック系ポッドキャストをあまり聴けていない日々が続いていたのですが、また聴き始めることにしました。 ただ、以前書いた「2017年とテック系Podcast(ポッドキャスト)を、紹介しつつ振り返る」という記事から、すでに1年以上が経過しています。 www.konosumi.net 最近のポッドキャストはまったくわからない状況だったので、新たに購読するポッドキャストを再検討することにしました。 テック系ポッドキャストの探し方 Podcast Freaks テック系ポッドキャストの紹介 アジャイルラジオ テストラジオ Misreading Chat engineer meeting podcast dex.fm w2o.fm 人生fm Researchat.fm UIT_INSIDE Tech系フリーランスが選ぶ最近の気になるトピックス(テクフリ) mozaic.fm プログラム雑談
本記事の目的と注意 注意! 私は、NGS については amplicon sequencing の解析経験(しかも半年)しかない。本記事は、データを解析して、STAP論文(Obokata et al, Nature 2014. Article と Letter)に対して何らかの結論を導くのが目的ではない。これだけリード数が少なくて、しかもサンプルがポリクローナルな混合物であることを考えると、ここから何かを結論するのは極めて慎重にならないといけないと思う。したがって、結果の「解釈」には立ち入らない(し、その能力もない)。本記事は、「ネットで話題になっているデータを、自分も解析してみたい!」と、「行為」そのものに魅力を感じる方のために、私が行った操作の流れを紹介するものである。 私は当初 RNA-seq のデータを解析しようとしたが、リファレンス・トランスクリプトームに存在しない再構成後の T
渋日記@shibu.jp 渋川よしきの日記です。ソフトウェア開発とか、ライフハックを中心に記事を書いていきます。 オライリー・ジャパンから、Mithrilの本を出しました。今まで本は何冊も出してきましたが、今回が初の単著です。O'reilly Authorの帽子もいただきました。出版にあたってはいろいろな方々にお世話になりました。ありがとうございました。もちろん、購入していただいた方、興味をもってシェアしていただいた方々もありがとうございます。 ちょっとお酒が入って酔っぱらっている状況ですが、本について紹介しようと思います。 Mithrilのどこに惹かれたのか？ この業界は常に新しいものがたくさんでてきます。本当にエポックメイキングなものもあれば、車輪の再発明的なものもあります。とはいえ、それらは0/1で区切ることはできなくて連続的なものですし、さらに複数の項目が関連しあっていたり絡まって
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
arXiv の論文から例文を検索する Hyper Collocation というサービスを公開しました． 以下はあまり整理されていない製作の記録です． 英語論文執筆用の例文検索サービス 英語での論文執筆の際に，専門用語を含む例文や言い回しのパターンを知りたいことが多々あります．有用なサービスとしては ライフサイエンス辞書のコーパス検索 Springer Exemplar (2018/2/1頃に終了) がありますが， データがライフサイエンス系の論文に限られている（ライフサイエンス辞書） ソートの基準が頻度順ではないため典型的な例文が上位にこない ストップワードに近い頻出語を検索した際の 検索が重い（Springer Exemplar） 表示可能な検索結果が偏る（ライフサイエンス辞書） という不満点があったので，並行して個人的な資料から検索を行うプログラムを作って使っていました． しかし，個
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
文字列アルゴリズムの学びかた - Hatena Developer Blog
更新されたら真っ先に聴いているおすすめポッドキャスト - laiso
中学生にもわかるウェーブレット行列 - アスペ日記
STAP細胞関係のゲノムデータを解析してみた - biochem_fanのブログ
Shibu's Diary: 世界最速でMithril本をリリースした話
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
英語論文執筆のために arXiv からの例文検索サービスを作った話