トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
チームラボ / teamLab
森ビル デジタルアート ミュージアム：エプソン チームラボボーダレス Feb 09, 2024 - 麻布台ヒルズ、東京 NOW OPEN
第7回 転置索引の構築 | gihyo.jp
はじめに これまで、転置索引の構造や具体的なデータ構造を見てきました。今回は、検索したいテキスト文書から、どのようにこの構造を構築するかを説明していきます。 ディスクベースの構築方法 第3回では、表を作成しそれを転置させることで転置索引を構築しました。実際にコンピュータに処理をさせる場合も、メモリ上の2次元配列で同様に構築することが可能となります。しかし、通常の転置索引は非常に疎な表となるため、この方法ではメモリを使いすぎてしまいます。また、リンクリストなどのメモリ上でのデータ構造を用いることにより、上記の方法と比較して少ないメモリ量で構築することもできます。 これらの方法はいずれも、対象とする文書集合を変換した転置索引が実メモリに収まる場合にのみ可能となる方法となります。しかし多くの場合、転置索引は実メモリよりも大きくなります。そのような場合はディスクを用いた構築方法が必要となり、効率的
第4回 形態素解析のしくみ | gihyo.jp
ソフトウェア的な索引では見出し語に対して、その見出し語が使われている文書（ファイル名、文書ID等）のリストを保存します。検索時は索引から見出し語を見つけ、その見出し語が使われている文書のリストを取得するだけなので、高速に検索が行えます。 全文照合方式と索引方式には、それぞれメリットとデメリットがあります。全文照合方式は、検索のたびに対象のテキストデータをメモリ上に読み込んで照合処理を行うため、大量の検索対象の場合、どうしても検索時間がかかるという欠点があります。 索引方式は、高速に検索が行える反面、あらかじめ索引を作成しておかなければなりません。索引の作成処理は、かなり負荷の高い処理になってしまいます。 このため、全文照合方式と索引方式には、それぞれ向き、不向きがあります。利用する場面に応じて使い分けるのがポイントです。検索対象が少量で検索回数も少ないなら全文照合方式、検索対象が大量で頻繁
接尾辞配列 - Wikipedia
接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（英: suffix array）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。接尾辞木の配列版。主に文字列探索、全文検索などに利用される。1990年に Udi Manber と Gene Myers が発表した[1]。
無題ドキュメント
次に、各Suffixにおける大小関係を定義します。この大小関係は辞書式順序です。辞書式順序とは、辞書に並んでいる通りの順番であり、簡単に言えば、 (1)両Suffixを頭（左）から順番に一文字ずつ比較していき、初めて違うところで、文字の大小関係で比較を行う (2)もし、二つを比較していき、片方のSuffixが終わりに達してしまったら、そちらの方が小さいと定義する。 例えば、(1)は上の例でいえば、 S5 と S7を比較するとすると S5 adabra S7 abra 一文字目は両方ともaで、同じなので二文字目（赤い部分）を比較すると、dとbであり、文字の大小関係で d > b なので S7 < S5 という大小関係がつきます。 (2)については、S0 と S7を比較すると S0 abracadabra S7 abra で、頭から4文字は同じであり、S7はデータの最後に達しました。この
【SEOリサーチ】本文のテキストが鍵を握る！ Yahoo!検索アルゴリズム2009年12月更新分の調査レポート
『MarkeZine』が主催するマーケティング・イベント『MarkeZine Day』の 最新情報をはじめ、様々なイベント情報をまとめてご紹介します。 MarkeZine Day
Mipmap - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Mipmap" – news · newspapers · books · scholar · JSTOR (June 2009) (Learn how and when to remove this message) In computer graphics, a mipmap (mip being an acronym of the Latin phrase multum in parvo, mea
B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
第6回 日本語における転置索引 | gihyo.jp
はじめに 前回までの数回では、転置索引の論理的構造や実装のための具体的なデータ構造について見てきました。今まで特に触れてきませんでしたが、これらの説明はすべて英語の文書を対象としたものでした。 英語は単語の間に空白を置くため、文を空白で区切ることで単語を抽出することができます。しかし、日本語の文では各単語はつながっているため、日本語で転置索引を構築する場合は英語と同じように、文を単語や文字の並びに分けてあげる必要があります。今回は、その方法について説明します。 文を単語や文字の並びに分割する方法 日本語のように単語が空白で区切られていない文を単語に分割するには、大きく分けて以下の2つの方法があります[1]。 形態素解析による分割 N-gram（q-gram）による分割 以下では、それぞれについて説明していきます。 形態素解析による分割 形態素解析（Morphological Analys
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
Rubyで最短経路を探索しよう！ - hp12c
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか 次に同じ質問がきたときに 「1時間いらないっしょ、こんなの」 と是非ともほざくために 今から勉強します ダイクストラ法による最短経路探索 図におけるＳ点からＧ点に到達するための最短経路を求めたい 各ノードを結ぶエッジを糸としてＳ点をゆっくりと持ち上げた場合 緊張する糸が変移しながら最終的にＳ−Ｂ−Ｄ−Ｇを結ぶ糸が緊張して これが最短経路と分かる*1 計算機上でこの現象をシミュレートしたものを ダイクストラ法というらしい 今各ノードとそこから伸びるエッジの情報(コストと接続先)を渡して その最短経路および総コストを出力するプログラムを考えてみよう data = { :s => [[5, :a], [4, :b], [2, :c]], :a => [[5, :s], [2, :b], [6, :g]], :b => [[4, :s
その13 OBBとOBBの衝突
ホーム＜ゲームつくろー！＜衝突判定編＜ OBBとOBBの衝突 3D衝突編 その13 OBBとOBBの衝突 衝突の本丸の1つ「OBBとOBB」の衝突です。大きさの違うお互いに3次元的に回転した直方体が衝突しているかどうかを調べるというのはやはり簡単ではありませんが、これができると多種多様な方面で役に立ちます。OBB同士の衝突として主流なのは「分離軸判定」と呼ばれる方法でして、ここでもそれについて見ていきます。ちょっと深呼吸してご覧下さい(^-^; ① 「分離軸」判定とは？ OBBの衝突には「分離軸」という物が登場します。これがいったい何なのか？まずは下の図をご覧下さい。 上のOBBは明らかに衝突していません。この時、両方のOBBを分ける直線が「絶対に」存在します。この直線は、ちょっと小難しい言葉で言うと分離超平面（Separating hyperplane）と呼ばれています。直線なのに平面と
scale out の技術 (in UNIX magazine, April 2009)
scale outの技術 首藤 一幸 Last-updated: January 5, 2010 注: このページの文章は以下の記事の元原稿です。 首藤一幸, "スケールアウトの技術", クラウドの技術, pp.88-101, (株)アスキー・メディアワークス, ISBN978-4-04-868064-6, 2009年 11月 6日 アスキー・メディアワークス社の 書籍紹介ページ Amazon.co.jp の ページ 首藤一幸, "スケールアウトの技術", UNIX magazine 2009年 4月号, pp.78-91, (株)アスキー・メディアワークス, 2009年 3月 18日 データベースに求められる性能を試算したところ、 十台、百台…数万台のサーバが必要になった。 クラウドを構築する側はこういう問題に直面し、解決しようとしてきた。 台数に比例した性能を引き出すこと、つまりsca
key-valueストアの基礎知識
首藤 一幸 Last-updated: January 5, 2010 注: このページの文章は Software Design 誌 2010年 2月号に掲載された以下の記事の元原稿です。 Software Design 誌編集部の了承の元に、本ウェブページに掲載しております。 首藤一幸: "key-valueストアの基礎知識", Software Design 2010年 2月号, p.14-21, (株)技術評論社, 2010年 1月 18日 クラウド、特にPaaS向けのソフトウェア開発が現実のものとなり、 そこではリレーショナルデータベースとは違ったデータベースが 勢いを増しています。 その代表であるkey-valueストアを解説します。 もくじ key-valueストアとは なぜkey-valueストアか key-valueストアの使いどころ key-valueストアとNoSQLの
Rubyでもっとも重要なライブラリは何か？PageRankで計算してみた - aike’s blog
最近、PageRankを計算するPHPソースコードを公開している人がいたので、Rubyで書き直してみました。 PHPからRubyへは移植というよりほとんど写経のような感じでそのままポーティングできます。 pagerank.rb #!/usr/bin/ruby # original PHP source http://phpir.com/pagerank-in-php def calculatePageRank(linkGraph, dampingFactor = 0.15) pageRank = Hash.new tempRank = Hash.new nodeCount = linkGraph.length linkGraph.each {|node, outbound| pageRank[node] = 1/nodeCount tempRank[node] = 0 } change =
PageRank In PHP
Google was a better search engine than it’s predecessors for a number of reasons, but probably the most well known one is PageRank, the algorithm for measuring the importance of a page based on what links to it. Though not necessarily that useful on its own, this kind of link analysis can be very helpful as part of a general information retrieval system, or when looking at any kind of network, suc
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Summed-Area Tables And Their Application to Dynamic Glossy Environment Reflections
https://dl.acm.org/citation.cfm?id=800031.808600
ページランクとは(PageRank)