今日この名前をどこかで聞いた気がするので、少し調べてみました。 http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance 2つの文字列間の類似度を測る指標として編集距離という概念は有名でいくつかバリ...
Damerau–Levenshtein Distanceを試す
今日この名前をどこかで聞いた気がするので、少し調べてみました。 http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance 2つの文字列間の類似度を測る指標として編集距離という概念は有名でいくつかバリ...
最近傍探索2011 - Preferred Networks Tech Blog
こんにちは、二台目のmbaを買うのをためらっている岡野原です。 アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。 アイテムが低次元（例えば2, 3次元）の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元（数百万次元）中の点であったり、アイテム間の距離のみが定義されている場合（カーネル関数など）です。アイテム数は数万から数億ぐらいを想定しています。 最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、 「アイテム集合X = x1,
wat-array : wavelet木を利用した高速配列処理ライブラリ - Preferred Networks Research & Development
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。 例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置 といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。 例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
最近のバイナリハッシングをいくつかJavaで実装してみた - rubyu's blog
去年の終わりから、バイナリハッシングを使った近似近傍検索をいろいろ調べていたのですが、ぼちぼち一段落したので、ひと通りまとめておきます。 バイナリハッシングとは。 個の 次元の点からなるデータセット で、元空間での近傍点を、類似したバイナリコードに関連づける技術。 要するに、実数ベクトルの検索をマトモにやるには、最近のデータは膨大すぎるのでお手上げ。なので、元空間での距離をなるべく保ったまま、バイナリコードに落としましょう。 そうすると、バイナリ一致か、1ビット違うか、2ビット違うか...と、捜索していくにしても、元空間のデータでやるより高速で、しかもストレージ容量を削減できるというわけです。 その ビットのバイナリコード を作るために、 個のハッシュ関数が使われる。 ハッシュ関数は と定義される。ここで、 はデータセット。 は射影ベクトル。 は閾値。 線形写像ベースのハッシングはシンプル
ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei
ACL2011の論文で「Faster and Smaller N-Gram Language Models」というのが気になったので読んでみた。 ACL Anthology » P11 Faster and Smaller N-Gram Language Models Adam Pauls, Dan Klein; 2011 本論文はこれまで提案されている言語モデルの圧縮・高速化の手法を実装して比較したよ、というもの。各種法が丁寧に解説されており、性能比較もよく知られているツールであるSRILMをベースラインとして行っているので参考になる。サーベイ論文として優れていると感じた。 本論文で紹介されている手法はモデルのサイズ圧縮と高速化の2点に関するもの。 まずはサイズ圧縮について。これはTRIEを使うことで各Nグラムの共通したプレフィクスを圧縮するのが基本らしい。でTRIEについてはノードの持
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
圧縮アルゴリズム完全検証 - なぜか数学者にはワイン好きが多い
以前も簡単に圧縮コマンドの結果を比較したことがありましたが， 圧縮率比較 - なぜか数学者にはワイン好きが多い Kyoto CabinetやApache Hadoopがlzoライブラリの採用を始めたため，改めてベンチマークしてみました． 使用した圧縮コマンドは， gzip - Wikipedia bzip2 - Wikipedia xz (ファイルフォーマット) - Wikipedia lzop - Wikipedia の4種類． 大容量テキストファイル4ギガ前後のファイルで，Wkipediaの生データを使いました． Wikipedia:データベースダウンロード - Wikipedia ↑の中のjawiki-latest-pages-articles.xmlです． 圧縮・伸張時間 圧縮サイズ 総評gzipは圧縮速度は速くは無いですが，解凍速度は速く，圧縮サイズは中くらい． bzip2は圧縮
Video Lectures | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare
X Exclude words from your search Put - in front of a word you want to leave out. For example, jaguar speed -car Search for an exact match Put a word or phrase inside quotes. For example, "tallest building". Search for wildcards or unknown words Put a * in your word or phrase where you want to leave a placeholder. For example, "largest * in the world". Search within a range of numbers Put .. betwee
Tutorials – Welcome to Metanet Software Inc
N Tutorial A – Collision Detection and Response N Tutorial A – Collision Detection and Response table of contents SECTION 0: General Introduction SECTION 1: Separating Axis Theorem SECTION 2: Separating Axis Theorem for AABBs SECTION 3: Separating Axis Theorem for Circles SECTION 4: Separating Axis Theorem for Points SECTION 5: Fast-Moving Objects SECTION 6: Conclusion […] 1 comment
オセロにおけるビットボード - Wikipedia
現在、削除の方針に従って、この項目の一部の版または全体を削除することが審議されています。 削除についての議論は、削除依頼の依頼サブページで行われています。削除の議論中はこのお知らせを除去しないでください。 この項目の執筆者の方々へ： まだ削除は行われていません。削除に対する議論に参加し、削除の方針に該当するかどうか検討してください。また、本項目を既に編集されていた方は、自身の編集した記述内容を念のために控えておいてください。
Copy-on-write B-tree finally beaten. | Hacker News
I did not read the paper yet, but COW btrees are interesting for practical reasons since it is possible to update the tree just writing in append-only mode, that is nearly the only way to avoid fsync (or alike) but still avoiding trivial corruptions (the new root node is always written at the end of the update). Otherwise you either use fsync as a write barrier or live with the problem that from t
sparsetable - steps to phantasien t(2007-09-07)
Matz日記 で紹介されている google-sparsehash を眺めてみた. ひさびさに Google 気分. :~/src/sparsehash-0.8 omo$ wc `find src/google/ -type f` 253 1348 10336 src/google//dense_hash_map 237 1309 9884 src/google//dense_hash_set 238 1244 9616 src/google//sparse_hash_map 223 1214 9245 src/google//sparse_hash_set 919 4776 37957 src/google//sparsehash/densehashtable.h 42 189 1187 src/google//sparsehash/sparseconfig.h 884 4642 371
What are the lesser known but useful data structures?
There are some data structures around that are really useful but are unknown to most programmers. Which ones are they? Everybody knows about linked lists, binary trees, and hashes, but what about Skip lists and Bloom filters for example. I would like to know more data structures that are not so common, but are worth knowing because they rely on great ideas and enrich a programmer's tool box. PS: I
Damn Cool Algorithms: Levenshtein Automata - Nick's Blog
Posted by Nick Johnson | Filed under python, tech, coding, damn-cool-algorithms In a previous Damn Cool Algorithms post, I talked about BK-trees, a clever indexing structure that makes it possible to search for fuzzy matches on a text string based on Levenshtein distance - or any other metric that obeys the triangle inequality. Today, I'm going to describe an alternative approach, which makes it p
疎行列のデータ構造入門再び - nursの日記
やあみんな。秋シーズンもいよいよ本番だね、今日なんかはもみじ狩りに最適なんじゃないかこれ。 以前疎行列のデータの持ち方について書いたけど読み返してみると本命のCCSやCRSの説明は最後までせずに回り道だけして終ってしまうという非常に残念な内容となっていたので反省もこめてちょっと書き直してみたよ。 みんなはCCSとかCRSとかって聞いたことあるかな。疎行列とは殆どの要素がゼロで、非ゼロ要素はわずかしかない行列のことだ。なので、だったらゼロでないもののみを覚えておけばいいじゃないかという発想だ。 簡単のため、５ｘ５の疎行列を考えよう（実際はもっと大きい要素数のケースが多いし、もっと疎なわけだが） 0.0, 2.0, 0.0, 0.0, 0.0 0.0, 0.0, 2.0, 0.0, 0.0 0.0, 1.0, 5.0, 2.0, 0.0 0.0, 3.0, 0.0, 0.0, 2.0 0.0,
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.usenix.org/event/atc11/tech/final_files/Chawla.pdf
Google Code Archive - Long-term storage for Google Code Project Hosting.
Introduction to Algorithms
https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/02-buffertrees.pdf