Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
A/Bテストよりすごい？バンディットアルゴリズムとは一体何者か - Qiita
オバマ大統領の再選に大きく寄与したことで大きな注目を集めているA/Bテスト。A/Bテストを導入した、することを検討している、という開発現場も多いのではないだろうか。 そんな中、Web上で次のような議論を見つけた。 20 lines of code that will beat A/B testing every time Why multi-armed bandit algorithm is not “better” than A/B testing 一言でまとめると「A/Bテストよりバンディットアルゴリズムの方がすごいよ」「いやいやA/Bテストの方がすごいし」ということだ。 で、バンディットアルゴリズムとは一体何者なのか？ そこでBandit Algorithms for Website Optimization (O'REILLY)を読んでみた。その結果分かったことを踏まえてざっくりと
Problem Solving with Algorithms and Data Structures using Python — Problem Solving with Algorithms and Data Structures
Problem Solving with Algorithms and Data Structures using Python¶ By Brad Miller and David Ranum, Luther College Assignments There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text. Acknowledgements¶ We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online versi
IME本でも紹介されているLOUDSのパワーアップ版、DFUDSを調べた - EchizenBlog-Zwei
「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると効率が良い。 さて、そんなLOUDSにはパワーアップ版ともいうべきDFUDS(Depth First Unary Degree Sequence)というデータ構造がある。DFUDSはLOUDSが定数時間で扱える操作(parent(親ノードの位置を得る), i-th child(i番目の子ノードの位置を得る), degree(子ノード数を得る))に加えてsubtree size(現在のノードを根とする部分木のノード数を得る)という操作が定数時間で実現できる。よってDFUDSを使うと、トライでpredic
自然言語処理とか機械学習とかグラフとか簡潔データ構造とか全部入った良書｢日本語入力を支える技術｣がすごい - EchizenBlog-Zwei
@tkngさんの力作「日本語入力を支える技術」が2/8に発売される。既に秋葉原のヨドバシ有隣堂や池袋のジュンク堂本店では早売りされている様子。ってことで早速購入してきた。 本書が扱うテーマはGoogleIMEのような「日本語入力」のシステム。これだけだとさして興味ないや、って人も多いかもしれない。ところがこの日本語入力というのは技術的には形態素解析に非常に近い。自然言語処理やテキストマイニングに関わる方にとっては形態素解析は最も基本的かつ重要な技術。その仕組みを知っておくのは非常に重要だと思う。 また日本語入力(形態素解析)は技術的には機械学習、グラフの最短経路問題、簡潔データ構造など多くの分野が関わっているので「日本語入力」を理解することでこれらの多くの基礎技術の具体例を体感できるというメリットがある。 そんな日本語入力をまとめて勉強できるのが本書「日本語入力を支える技術」である！ばーん
algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found
2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い 珠玉のプログラミング Jon Bentley / 小林健一郎訳 絶賛風邪こじらせ中につきコードと戯れることに。 新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。 最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。 ソートしたいものに適当に番号を振っておく 番号がついたバケツを用意する ソートしたいものの番号がついたバケツにそれを放り込む 必要があればバケツの中身を同じやり方でソートする 番号順にバケツの中身をぶち
RE: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記
Twitter ID も livedoor ID もないので直接コメントできないが，sort (GNU coreutils) の名誉のために，ここにメモしておく． 404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な まず第一印象として，この程度のサイズのファイルのソートで sort (GNU coreutils) がいまどきこんなに遅いはずはない．LC_ALL=C で追試すると，やはり bucketsort との差は無くなった．上の記事（に対するツイート）は Twitter 上でもそれなりにリツイートされているように見えるのだけど，この実行時間に違和感を感じる人が全くいないのはどういうことなのだろうか．sort を実際に使う人がほとんど見ていないのか，それとも計算量が違うから速くて当然という思い込みか．
Suffix Arrayメモ - Negative/Positive Thinking
はじめに Suffix Arrayあたりをちょっと調べてみたのでとりあえずメモ。 調べてみたら結構研究されていて全部まとめるのが面倒あとできちんと理解しておきたい。 Suffix Array(接尾辞配列)とは 文字列に対して、その文字列の接尾辞集合を辞書順ソートしたもの ここでの接尾辞集合は「abcd」という文字列の場合、以下の4つの接尾辞になる abcd bcd cd d これは各インデクスから最後までの部分文字列なので、元の文字列があればインデクスから部分文字列を得ることができる 与えられた文字列からある文字列が含まれるかどうかを検索したい場合、Suffix Arrayは辞書順に並んでいるので、2分探索することで高速に検索することができる 構築方法 普通のQuicksort 普通に文字列をソートする方法 QuicksortにO(n log n)、文字列比較にO(n)かかる Mamber
データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
米Google、情報鮮度評価の検索アルゴリズム改良を発表、検索の35%に影響 ::SEM R (#SEMR)
米Google、情報鮮度評価の検索アルゴリズム改良を発表、検索の35%に影響 グーグルが検索結果の鮮度に関する検索アルゴリズムの変更を発表、影響は検索の35%。コンテンツの新しさ・新鮮さへの理解を深めるように改善されている。 公開日時：2011年11月04日 07:45 米Googleは2011年11月3日、コンテンツ鮮度（Content Freshness）を適切に評価することで関連性を高めることを目的に、ランキングアルゴリズムを変更したことを発表した。この変更は、検索の35%に影響するという。 アルゴリズム変更は、主に情報鮮度に関するもので、検索クエリに対して最も最新のものを検索結果に表示することを可能とする。検索結果の鮮度についてはQDF （Query Deserves Freshness）がよく知られているが、これを更に推し進め精度を高めるもの。昨年導入した新しい検索インフラ・カフ
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 転置インデックスとは検索エンジンに用いられるインデックスで apple 1, 3 orange 1, 2, 4, 6のように各単
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
