転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。 転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。 この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。 目次 転置インデックスの基本 転置インデックスのデータ構造と特性 転置インデックスのアクセスパターン 近年のインデックス圧縮技法 Variable-Byte Family VByte Varint-GB Varint-G8IU Masked-VByte Stream-VByte Opt-VByte Simple Family Simple9 Simple16

はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5]という配列が与えられた時、確率10%で0、40%で1、50%で2というインデックスを返すような関数が欲しい。 普通に考えると部分和をとって乱数を一度振り、どの場所が選択されたか二分探索で調べる、というアルゴリズムが思いつくが、これは要素数Nに対して$O(\log(N))$の手間がかかる。logの手間というのは無視できることが多いが、この関数呼び出しが頻繁にある場合には無視できないコストになる。 さて、こんな用途のためにWalker's Alias Methodというアルゴリズムがある。この手法は一度$O(N)$の手間で配列を作ってしまえば、後は$O(1)$でインデックスを選ぶことができる。 例えば重みとして[3, 6, 9, 1, 2, 3, 7, 7, 4, 8]という10個の要素を

はじめに このブログに書かれていること 自己紹介 注意 Part1 古典暗号 2つの暗号方式 スキュタレー暗号 アルゴリズムと鍵 シーザー暗号 原理 頻度分析 アルベルティ暗号 ヴィジュネル暗号 如何にしてヴィジュネル暗号は破られたか Part2 近代暗号 エニグマ エニグマの登場 エニグマの基本構造 如何にしてエニグマは突破されたか 前提条件 必ず異なる文字に変換される性質を利用 ループを利用 まとめ 参考文献 採用情報 はじめに このブログに書かれていること 前半 古代暗号から始まる暗号の歴史 エニグマの構造と解読法について 後半（後半ブログは こちら） RSA暗号の基本 楕円曲線暗号の基本 自己紹介 こんにちは！株式会社ABEJAの @Takayoshi_ma です。今回のテックブログですが、ネタに5時間程度悩んだ挙句、暗号を取り上げることにしました！暗号化手法の解説にとどまらず、そ

ECサイトで買い物中に表示されるおすすめ商品から、動画サイトで自動的に再生される関連動画まで、現代のインターネットユーザーはさまざまな場所で「レコメンデーション」に接しています。そんなレコメンデーションに欠かせない5つのアルゴリズムを、グラフデータベースサービスを手がけるMemgraphが解説しています。 Five Recommendation Algorithms No Recommendation Engine Is Whole Without https://memgraph.com/blog/five-recommendation-algorithms-no-recommendation-engine-is-whole-without ◆1：幅優先探索 幅優先探索(BFS)とは、木構造やグラフの探索に用いられるアルゴリズムです。仕組みは単純で、ある開始ノードを選択したらそれとつなが

「AI（人工知能）の民主化」と呼んでいいほど、AIを自ら開発・運用しようという機運が高まっている。データサイエンティストではない一般的なビジネスパーソンが統計や機械学習アルゴリズムに自ら触れ、データを分析してその結果を業務に活用し始めている。実際にアルゴリズムに触れる機会が増えたと感じる読者も多いだろう。 一方で、「アルゴリズムが色々とあり過ぎて、どこから勉強を始めるべきか分からない」といった悩みの声をよく聞く。そこで本特集はコンサルティングファームで働く現役データサイエンティストの視点から、ビジネスに使える最新のアルゴリズムを10種類選んで紹介する。 データサイエンスで利用されるアルゴリズムには、一つ一つ違った特性があり、業務シーンによって向き不向きがある。そこで本特集ではビジネスに使えるアルゴリズムを、以下の4項目の観点で評価した。 簡便性……専門知識が不要で、すぐに実装できること 汎

情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。

今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場

はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の

セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い

この記事は、前出の本に入れる予定だったコラムのうちの一つです。 正確にいうと、本に入れる予定だったけど、メイン側で締め切りをぶっちぎっていたら、コラムを追加できるような空気じゃなくなって、書くのをやめたものです。 本の宣伝を兼ねて、没にしたコラムに日の目を見させて、あわよくば第二版で入ればいいなー、という内容です。 データサイエンティストの頭の中「偉い人たちは頭がおかしい」と言っても、それは相対的なものであるため、比較対象であるデータサイエンティストの頭の中を覗いてみましょう。 データサイエンティストは組織におけるデータ活用状況について、レベル分けして考えます。そして、基本的に前のレベルが実現できなくては、次のレベルに進むことはできないと考えています。 以下のレベル分けは私が適当に思い描いているものですが、同業者なら大よそ一緒なんじゃないかと思います。 Lv0: データ収集、ログ設計Lv1

(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の

ECサイト向けのレコメンデーション・エンジンを構築すると仮定しましょう。 構築する方法としては、コンテンツベースか協調フィルタリングを使用する2つの進め方があります。それぞれのメリットとデメリットを見てみましょう。そして、コンテンツベースエンジンを 簡単に実装する方法 について探りましょう(Herokuにデプロイ可能です)。 コンテンツベースを使用するとどのようになるのか先に知りたい方は、ほぼ同じレコメンデーション・エンジンが Groveの商品（紹介）ページで使用 されていますので、見てみてください。 コンテンツベースのレコメンデーション・システムはどのように機能するのか 商品説明や商品名、価格などの実際のアイテムプロパティなどが使用されるため、コンテンツベースシステムで構築されていると周りには思われているのではないでしょうか。これまで一度もレコメンデーション・システムの使用を検討したこと

分散システムについては、もう随分と前から学びたいと思っていました。ただ、それは一度首を突っ込んだら最後、ゴールのない迷路に迷い込むようなものなのです。どこまでも続いているウサギの穴のようなものです。分散システムに関する文献は星の数ほど存在します。様々な大学からたくさんの論文が発表されているばかりでなく、膨大な数の書籍もあるのです。私のような全くの初心者には、どの論文を読んだらいいのか、どの書籍を買ったらいいのか、見当もつきません。 そんなとき、一部のブロガーが、 分散システムエンジニア （それがどういう意味であれ）になるなら知っておくべき論文というものを推奨しているのを見つけました。その一部を紹介しましょう。 FLP , Zab , Time, Clocks and the Ordering of Events in a Distributed Systems , Viewstamped

Qiita の 「見逃せない投稿」 を独自に評価してランキングするサービス Qaleidospace を作りました。 本投稿では、そのようなサービスを作ろうと思った理由、投稿を評価するアルゴリズム、システム構成について書きます。 余談ですが、今なら Yearly Ranking がほぼ 2015 年の投稿ランキングとなっており、眺めていて楽しいです。 TL;DR Qiita の「見逃せない投稿」をランキングするサービス Qaleidospace を作った。 適切な評価システムがあれば、書き手も読み手もみんな幸せになれるはず。 ストック数だけで評価すると、初心者向けの投稿やキャッチーなキーワードを散りばめただけの投稿が注目されやすい。誰がストックしたのかを重視して「見逃せない投稿」を評価する。 風変わりなシステム構成: GitHub Pages でホスティング + Swift で書かれたバッ

Webサービスでアカウントを登録する際、パスワードを入力する度にその安全度を表してくれる強度メーター。皆様もおそらく目にしたことがあるのではないでしょうか。GoogleやFacebook、Twitterのような大規模なサービスでも、サインアップ画面等に設置されています。 このUIの要素は、MSR(Microsoft Research)の論文によると類推されづらいパスワードを促してサービスの安全性を高めることに効果的だということが証明されています。 お客様自身の大事な情報を守る上でとても重要なパスワード。ヌーラボアカウントでも、類推されにくいより強度の高い設定を促すためにパスワード強度メーターを設置しました。 この記事では、パスワード強度メーターを設置するに当って得た知見をもとに、その裏側の仕組みをご紹介させていただきます。 パスワード強度ってなに ？ そもそもパスワード強度とはなんなのか。

※この表は神嶌 敏弘先生が人工知能学会誌に連載した解説記事『推薦システムのアルゴリズム』から転載したものです。 アルゴリズムの説明 ■ 協調フィルタリングとは アイテム利用者の行動履歴を元にレコメンドする方法です。Amazonの『この商品を買った人は、こんな商品も』機能が有名です。協調フィルタリングによるレコメンドはユーザの行動を元にレコメンドする方法です。 ■ 内容ベース（コンテンツベース）フィルタリングとは アイテムの特徴ベクトルで類似度ソートしてレコメンドする方法です。 グルメサイトでユーザが入力した『新宿・エスニック料理』というキーワードに関連付けられたお店が表示される場合が該当します。内容ベースによるレコメンドはアイテムの特徴を元にレコメンドする方法です。 特性の詳細について ■ 多様性 協調: o 内容ベース: x 内容ベースでは商品内容に記載されていない情報はレコメンドされま

Photo by Oferico 皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？ 仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。 今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。 ■アルゴリズムを学ぶ意味 例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しか

こんにちは。会員事業部ビジネス開発グループの高田です。 クックパッドは今年、株主優待制度として、プレミアムサービス一年間無料クーポンを贈呈しました。本エントリではクーポンコードを打ち間違えて、意図せず他の人のクーポンコードを使用するのを防ぐために工夫した話をご紹介します。 はじめに クーポンコードは入力のしやすさを優先して数字だけの文字列にしました。はじめは rand 関数を使って生成しようとしていたのですが、数字の打ち間違えや順序間違いで、意図せず誤使用してしまうのを防ぐためにチェックサムを加えるのがいい、と同僚から助言をもらいました。 いくつか調べて見たところ、Luhn アルゴリズムが上記を満たしていたので利用することにしました。 Luhn アルゴリズムの利用 Luhn アルゴリズムとは、誤り検出のためのチェックサム符号で、1 桁の間違いや隣接する数字の順序間違いを検出できるという特徴

ログイン

2015年05月27日: 表が見にくいというご意見を頂いたため、原文著者に連絡のうえ体裁を修正しました。 上位のレベルには下位のレベルの知識も蓄積されているということに注意してください。つまり、レベル n であれば n より低いレベルの知識も全てあります。 コンピュータサイエンス データ構造