こんにちは！はてなアプリケーションエンジニアの 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） 表示可能な検索結果が偏る（ライフサイエンス辞書） という不満点があったので，並行して個人的な資料から検索を行うプログラムを作って使っていました． しかし，個
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
Googleが今日（米国時間2/28）、オープンソースの新しい圧縮アルゴリズムZopfliをローンチした。今の標準圧縮技術であるzlibライブラリに比べて5〜8%圧縮率が高いといわれ、また解凍アルゴリズムは今のWebブラウザが現用しているもので間に合うため、Webサーバがこれを採用すれば、データの伝送速度が上がり、Webをやや速くすることができるだろう。 Google が出力が deflate 互換の圧縮アルゴリズムをオープンソースにしたというので、ちょっとタイムラインで話題になっていた。圧縮アルゴリズム周りにはまってた頃から結構時間が経ってしまって色々忘れてしまったけど、少しニュースを捕捉してみようと思う。 Zopfli は deflate 互換なので、deflate アルゴリズムを解釈できる実装なら伸張できる。当然ブラウザが持ってる deflate 実装で伸張できるので、エンドユーザー
高速な文字列マッチング - 気ままなブログ
最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。 http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。 AC法については、日本語だと 情報検索アルゴリズム 作者: 北研二,津田和彦,獅々堀正幹出版社/メーカー: 共立出版発売日: 2002/01メディア: 単行本購入: 6人 クリック: 552回この商品を含むブ
私のブックマーク ： 簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。 解説記
最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。 この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明する。 新しい概念が出てきた時に気になるのは「どうやって実現するのか」「それができると何が嬉しいのか」という2点だと思う。 前者についてはこの記事(http://d.hatena.ne.jp/takeda25/20140201/1391250137)がわかりやすいのでここでは述べない。この記事では「完備辞書があると何が嬉しいのか」について説明する。 完備辞書とは 完備辞書はrankおよびselectという操作が定数時間で実行できるビット列のこと。rank(i)はi番目のビットより前にいくつ1があるかを返
渋日記@shibu.jp 渋川よしきの日記です。ソフトウェア開発とか、ライフハックを中心に記事を書いていきます。 HTML5アドベントカレンダー向けのエントリーです。ブラウザでできることがどんどん増えています。2013年に一部で熱狂的な話題となった本の高速文字列解析の世界 を読んで意識が高まったので、勢いにまかせてブラウザで動く検索エンジンを作ってみました。写真は著者の岡野原さんにお会いしたときにいただいたサインです。 ブラウザ上の検索エンジンと転置インデックスと東アジアの微妙な関係 全然調べていないので、歴史とかよくわからないのですが、僕が始めてブラウザ上で動く検索エンジンと出会ったのは、Sphinxです。SphinxはPythonで書かれたドキュメントツールです。ドキュメントツールというとJavaDocを始めとして各種あります。大きく、自然言語中心のもの(Texとか)と、APIリファレ
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは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++の利用
【monstar.fm - モンスターFM 〜音楽との出会い〜】
サイトの動作環境 Windows XP, 2000の場合 IE 6.0以降 Firefox 1.5以降 MacOSX 10.2以降の場合 Safari 1.2以降 Firefox 1.5以降 Flash Playerプラグインの最新版 ※その他の環境での動作状況については こちらをご参照ください。
Intro WebPackaging は以下の 3 つの仕様を組み合わせたユースケースである。 Signed HTTP Exchanges: Signing (コンテンツに署名する) Bundled HTTP Exchanges: Bundling (コンテンツを 1 つにまとめる) Loading Signed Exchanges: Loading (そのコンテンツをロードする) 本エントリでは、各仕様を Signing/Bundling/Loading と記す。 現状、 Signing および Loading の仕様策定が進んでおり、 Chrome は Experimental な実装を行っている。 全体的に仕様が大きく、今後も変更される可能性が高いため、今回は実装が進んでいる Signing に絞り、ユースケース、仕様、および本ブログへの適用を中心に解説する。 Signing (Si
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
文字列アルゴリズムの学びかた - Hatena Developer Blog
更新されたら真っ先に聴いているおすすめポッドキャスト - laiso
中学生にもわかるウェーブレット行列 - アスペ日記
STAP細胞関係のゲノムデータを解析してみた - biochem_fanのブログ
Shibu's Diary: 世界最速でMithril本をリリースした話
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
英語論文執筆のために arXiv からの例文検索サービスを作った話
Wavelet Tree - naoyaのはてなダイアリー
Zopfli - naoyaのはてなダイアリー
簡潔データ構造の入門の入門 - EchizenBlog-Zwei
Shibu's Diary: ブラウザ上で動く検索エンジンOktavia
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」：CodeZine
WebPackaging の Signed HTTP Exchanges | blog.jxck.io