1000x Faster Spelling Correction algorithm (2012)
Source: https://www.flickr.com/photos/theredproject/3968278028Update1: An improved SymSpell implementation is now 1,000,000x faster. Update2: SymSpellCompound with Compound aware spelling correction. Update3: Benchmark of SymSpell, BK-Tree und Norvig’s spell-correct. Recently I answered a question on Quora about spelling correction for search engines. When I described our SymSpell algorithm I was
AdaGradが12倍速くなる魔法
AdaGradは学習率を自動調整してくれる勾配法の亜種で、いろんな人が絶賛しています。 勾配を足し込む時に、各次元ごとに今までの勾配の2乗和をとっておいて、その平方根で割ってあげるだけと、恐ろしくシンプルです。 Adaptive Subgradient Methods for Online Learning and Stochastic Optimization John Duchi, Elad Hazan, Yoram Singer. JMLR 2011. 丁度、 @echizen_tm さんがブログを書いてました。 AdaGrad+RDAを実装しました。 通常のSGDなどは学習率をだんだん減衰させながら勾配を足していくわけですが、どの様に減衰させるかという問題にいつも頭を悩ませます。 AdaGradでは最初の学習率こそ外から与えますが、減衰のさせ方や減衰率といったハイパーパラメータから
Hash functions: An empirical comparison - strchr.com
Abstract: Benchmark program for hash tables and comparison of 15 popular hash functions. Created 17 years ago by Peter Kankowski Last changed 5 years ago Contributors: Nils, Ace, Won, Andrew M., and Georgi 'Sanmayce' Filed under Algorithms Hash tables are popular data structures for storing key-value pairs. A hash function is used to map the key value (usually a string) to array index. The functio
MinHash for dummies
Duplicate document detection is becoming increasingly important for businesses that have huge collections of email, web pages and documents with multiple copies that may or may not be kept up to date. MinHash is a fairly simple algorithm that from all my Googling has been explained very poorly in blogs or in the kind of mathematical terms that I forgot long ago. So in this article I will attempt t
History of Lossless Data Compression Algorithms
Introduction There are two major categories of compression algorithms: lossy and lossless. Lossy compression algorithms involve the reduction of a file’s size usually by removing small details that require a large amount of data to store at full fidelity. In lossy compression, it is impossible to restore the original file due to the removal of essential data. Lossy compression is most commonly use
Red Blob Games: Introduction to A*
In addition to finding a shortest path, these algorithms can be used for distance maps, flow field pathfinding, connected components, map analysis, garbage collection algorithms, flow networks, and procedural map generation. There are many optimizations and specializations of these algorithms. Representing the map# The first thing to do when studying an algorithm is to understand the data. What is
Gale-Shapleyアルゴリズム
パートナーがいない男（X）は、まだプロポーズをしたことのない相手の中で一番好きな人にプロポーズをする。 プロポーズされた女は、 フリーの場合、そのプロポーズを受け入れる。 すでに婚約中の場合、 今の婚約相手よりもXの方が魅力的であれば、今の婚約相手を振って、Xのプロポーズを受け入れる。 Xよりも今の婚約相手の方が魅力的であれば、Xのプロポーズを断る。 このアルゴリズムが本当に正しく動作するのか考えてみました。 ーまず、このアルゴリズムは停止するのか？ アルゴリズムは、パートナーがいない男が存在する間は停止しない。パートナーという関係は男集合から女集合へのbijectiveな写像なので、「パートナーがいない男が存在する」と「パートナーがいない女が存在する」は同値。 女は、一度でもプロポーズされると、それ以降はうまく男をキープすることで常にパートナーのいる状態を継続できる。よって、すべての女が
ダンジョン生成してみよう - 株式会社BEFOOL ブログ
こんにちは、あゆめぐです。 今回はダンジョン生成の基本部分。 アルゴリズムそのまま実装したものの状態まで書きました。 はい、相変わらずjavascriptです。 どこかのタイミングでいい加減にc#にしないとな〜と思うんですがjavascriptそのままいろいろ持ってけて便利すぎるんだ〜。 ほら私が好きなActionScript3.0もenchant.jsにしてもjavascript系だからね。 ##考え方 ダンジョンマップを生成するアルゴリズムの解説 こちらの二分割を繰り返す方法の方です。 しかしながらこの実装だとアルゴリズムばればれなのでここからいろいろカスタマイズしないと。 均等に分割する方法はまだ作成していないので気が向いたときにやってみようかと思います。 他にもダンジョン生成にはいろんなアルゴリズムがあって 迷路自動生成アルゴリズム 上記サイトのような本当にダンジョンというのもあり
ノイズの話 - Pentanium Blog?
これはレイトレ合宿2!!アドベントカレンダーの4週目の記事です。 梅雨真っ盛りでぱっとしない天気が続きますがレイの追跡の具合はいかがでしょうか。 7月に入ったとはいえアドベントカレンダーはまだまだ序盤。 後のほうにガチな人がいらっしゃるのでレイトレと関係あるのか微妙なネタでもまだ許されると信じていきます。 さて、レンダリングしているとテクスチャが欲しくなって、とりあえずチェッカーをつくってみたりします。 それに飽きてきたらノイズです。ノイズですよねッ!? もうノイズがあるだけでそれはそれはCGらしくなります。 しかも模様だけにとどまらず、バンプやディスプレイス、プロシージャルなオブジェクトと使い道もたくさんある素敵なやつです。 そんなわけでちょっとノイズでも作ってみようかと思います。 とりあえず2Dの画像をつくることにして、深いことを考えずに乱数で埋め尽くすとこんな感じになります。 flo
ノイズ耐性のある二分探索 - www.kotha.netの裏
観測にノイズが乗っても対処できる二分探索が意外と簡単に書けることが分かったのでメモ。 問題 (n-1)個の整数からなる列がある。そのうち左からi個は(-1)であり、それ以外は1である。 n=6, i=3の例 -1 -1 -1 1 1クエリを繰り返すことでiを求めたい。各クエリは整数kであり、答として左からk番目の整数の値が得られる。ただし、この答にはノイズが加算される。ノイズは標準偏差σ(既知とする)の正規分布に従う。 解法 iがどの値を取るかの確率分布を持っておいて、クエリの答が得られるたびにベイズの定理に従って更新する。最初はn通りの一様分布。クエリは、得られる情報量の期待値を最大化するように選ぶ。これには、(-1)と1の境界よりも右にあるか左にあるかが半々に近い位置を選べば良い。 iの確率分布が十分に偏ったら終了。 実験 以下では、iが特定の値を取る確率が95%を越えた時点で探索を終
Optimizations on Locality sensitive hashing forest data structure
In order to get LSH forest approximate nearest neighbor search method into a competitive and useful state, optimization was a necessity. These optimizations were based on the portions of the LSH forest algorithm and implementation of that algorithm. There are two general cases of bottlenecks where requirement for optimization arises. Memory usage of the data structure. Speed of queries. Let's disc
FM-Indexes and Backwards Search
Last time (way back in June! I have got to start blogging consistently again) I discussed a gorgeous data structure called the Wavelet Tree. When a Wavelet Tree is stored using RRR sequences, it can answer rank and select operations in $\mathcal{O}(\log{A})$ time, where A is the size of the alphabet. If the size of the alphabet is $2$, we could just use RRR by itself, which answers rank and select
Visualizing Algorithms
The power of the unaided mind is highly overrated… The real powers come from devising external aids that enhance cognitive abilities. —Donald Norman Algorithms are a fascinating use case for visualization. To visualize an algorithm, we don’t merely fit data to a chart; there is no primary dataset. Instead there are logical rules that describe behavior. This may be why algorithm visualizations are
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
VisuAlgo moves to https://visualgo.net/en
http://aleksandar-prokopec.com/resources/docs/my_thesis.pdf
Account Suspended
Everyday Algorithms: Elevator Allocation
http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
Reddit - Dive into anything
2014 TCO Marathon Round 3 (yowa)
