簡潔データ構造 - 共立出版
2019年度大川出版賞受賞！ 簡潔データ構造とは、データをエントロピーの限界まで圧縮して保存しつつ、検索等の処理を行う際にはあたかも非圧縮のデータに対してアクセスしているように扱えるデータ構造である。データを圧縮することにより、これまでのデータ構造よりも多くのデータを扱えるようになる。扱うデータによっては 1/100 まで圧縮できる。2000年以降、多くの理論的・実用的データ構造が提案されており、ゲノム情報処理等では実際に使われている。 本書は、基本的な簡潔データ構造（ビットベクトル、文字列、木構造等）の理論を説明する。初期の簡潔データ構造は非常に難解なものが多く、実装しても性能の出ないことが容易に想像できたが、後に提案されたものは理論的性能を保ったまま簡単化されており、容易に実装可能であり実際の性能も良い。本書ではそのようなデータ構造を中心に説明しているため、簡潔データ構造を実問題に適用
kuromoji.jsで形態素解析した結果とテキストの関係をビジュアライズする
azu/text-map-kuromoji: テキストを形態素解析した結果とテキストの関係をビジュアライズするエディタというツールを作った話。 くだけた表現を高精度に解析するための正規化ルール自動生成手法という論文誌では、「ヵゎぃぃ」，「ゎた Uゎ」みたいな普通の形態素解析では未知語として検出されるものをどうやって正規化していくかという話が書かれていました。 これを読んでいて面白かったのは形態素解析をした結果の未知語となった部分と穴埋め的にパターンを作って、そのパターンにマッチする同じようなテキストを探すというアプローチでした。 プログラミング言語と違って、大抵の自然言語パーサはパース失敗ではなく、単なる未知な言葉として検出されます。 また、その未知な言葉は常に増えていて、さきほどのくだけた表現を高精度に解析するための正規化ルール自動生成手法によると手動では登録できない増加量らしいです。
The Sync Scroll of Markdown Editor in Javascript
Hi, I am Hao (👋): a coder, a woodworker, a blogger, and a father. Markdown apps like StackEdit and MacDown have a feature called sync-scroll. It means that when the user is scrolling the editor, the previewer will also be scrolled based on the position of the editor. It is a really useful function because I can always see how it looks like in the real web page, so I want this function in my own M
GDBM で学ぶ Extendible Hashing
最近仕事で GDBM を使う機会があり、GDBM で使われている extendible hashing に興味を持ったのでまとめてみました。 なお、今回対象にしている GDBM のバージョンは 1.12 です。 アジェンダ GDBM とは ハッシュテーブルの基礎 ハッシュ関数 衝突処理 リハッシュ Extendible Hashing GDBM による Extendible Hashing ハッシュ関数 ファイルヘッダのデータ構造 バケットのデータ構造 バケット要素のデータ構造 衝突処理 ディレクトリの拡張とバケットの分割 データベースファイルは要素数が多いと肥大化する おわりに 参考 GDBM とは http://www.gnu.org.ua/software/gdbm/ 曰く GNU dbm (or GDBM, for short) is a library of database f
Myers Diff Algorithm - Code & Interactive Visualization
2017-06-07 - By Robert Elder Below you will find example source code and interactive visualizations that are intended to complement the paper 'An O(ND) Difference Algorithm and Its Variations' by Eugene W. Myers[1]. Multiple variants of the algorithms discussed in Myers' paper are presented in this article, along with working source code versions of the pseudo-code presented in the paper. Two ref
Fast CRC32
posted November 10, 2011 by Stephan Brumme, updated February 4, 2015 Error Checking Real life data tends to get corrupted because machines (and humans) are never as reliable as we wish for. One efficient way is make sure your data wasn't unintendedly modifiied is to generate some kind of hash. That hash shall be unique, compact and efficient: unique: any kind of modification to the data shall gene
LZ4m: Taking LZ4 Compression To The Next Level - Phoronix
Happy Holidays! If you enjoy all the original Linux hardware reviews and open-source news content on Phoronix, consider joining Phoronix Premium this holiday season. For Black Friday / Cyber Monday, there is a cyber week special to go premium and enjoy an ad-free experience, native dark mode, and multi-page articles presented on a single page. LZ4m: Taking LZ4 Compression To The Next Level Written
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
RNNで「てにをは」を校正する - にほんごのれんしゅう
RNNで「てにをは」を校正する 余談 2017/3/19に、どの深層学習フレームワークがこれから深層学習を始める人におすすめなのかというアンケートをtwitterで取らせていただきました。 五位 Theano(個別カウント) はじめに RNNによる文章校正がリクルートによって提案されて以来、調査タスクとして私のものとに来たりして、「できるんでしょう？」とか軽く言われるけど、実際には簡単にはできません。 RNNによる文章生成ができるから、校正もできるというのが人間の自然な発想なのかもしれませんが、英語と日本語の違いに着目した場合、英語がアルファベットのみで構築されるのに比べて日本語は、漢字・ひらがな・カタカナと非常に多く、同じように問題を適応すると、すごい高次元の問題を解くこととなり、理想的なパフォーマンスになかなかなりません。 まぁ、あんまり完成してるわけでない技術を完成したようにプレスリ
BSDiffバイナリ差分アルゴリズムの解説
BSDiff はバイナリ差分を扱うプログラムです。bsdiffとbspatchの二つのコマンドから成ります。bsdiffは旧ファイルと新ファイルを比較してパッチファイルを出力します。bspatchは旧ファイルにパッチファイルを適用して新ファイルを出力します。コマンドライン引数はbsdiff、bspatch共に旧ファイル、新ファイル、パッチファイルの三つをその順番で指定します。 Usage: bsdiff oldfile newfile patchfile Usage: bspatch oldfile newfile patchfile BSDiffは実行ファイルの修正差分を取ることを念頭に置いて設計されています。 一般にソースコードのある行に修正を加えた場合、実行ファイルの変化はその修正した行に直接対応する部分だけに留まりません。その行をコンパイルして出来たコード(マシン語列)の長さが変化
2016年のOSS圧縮ツール選択カタログ - Qiita
まだgzipで消耗し（略） 2016年、人類が待ち望んでいた、gzipを圧倒するOSS圧縮ツールzstd(Zstandard)がリリースされたにも関わらず、なんかあんまり話題になっていなくて寂しいので、ちょろいかんじの賑やかし比較記事を書きました。圧縮ツールのカタログ的に眺めていただけるかと思います。 はじめに （この記事で言う）圧縮ツールとは何か 圧縮ツールという呼び名は正確ではない（はず）です。平たく言えば、gzipやbzip2、xz、lz4などですが、人によっては、tarの裏側としてしか使ってなくて、聞いたこともないかもしれませんね。そういうときはまずgzipのmanpageとか読んでください。 しかし、そういうツールを何と呼べばいいのかわからないので、ここでは圧縮ツールと呼んでいます。 ややこしいですが、アーカイバではありません。アーカイブとは実態が一つのファイルになっているフォル
初心者がchainerで線画着色してみた。わりとできた。
ﾃﾞｰﾌﾟﾗｰﾆﾝｸﾞはコモディティ化していてハンダ付けの方が付加価値高いといわれるﾋﾟ-FNで主に工作担当のtai2anです。 NHKで全国放送されたAmazon Picking Challengeでガムテべったべたのハンドやロボコン感満載の滑り台とかを工作してました。 とはいえ、やっぱりちょっとディープラーニングしてみたいので1,2か月前からchainerを勉強し始めました。 せっかくなので線画の着色をしたいなーと思って色々試してみました。 線画の着色は教師あり学習なので線画と着色済みの画像のデータセットが(できれば大量に)必要です。 今回はOpenCVでカラーの画像から線画を適当に抽出しています。 抽出例 → カラーの画像を集めて線画を作ればデータセットの完成です。（今回は６０万枚くらい使っています） ネットワークの形ですが、U-netという最初の方でコンボリューションする時の層の出
Webプログラマと数学の接点、その入り口
フロントエンドのパラダイムを参考にバックエンド開発を再考する / TypeScript による GraphQL バックエンド開発
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
A Primer on Bézier Curves
A free, online book for when you really need to know how to do Bézier things. Read this in your own language: English 日本語 (24%) 中文 (37%) Русский (24%) Українська (2%) 한국어 (9%) (Don't see your language listed, or want to see it reach 100%? Help translate this content!) Welcome to the Primer on Bezier Curves. This is a free website/ebook dealing with both the maths and programming aspects of Bezier
ウェーブレット行列とFM-indexで全文検索を書いてみた - くじらにっき++
www.youtube.com 去年のはじめに高速文字列本を買ったのですが、アルゴリズムを眺めるだけで実装はしていませんでした。特にウェーブレット行列は実装が大変そうにしか見えなくて敬遠していたのですが、ICPCの夏合宿で @hirokazu1020 さんに「あれはアイデアさえ理解していれば実装するのは簡単だよ」という旨のことを言われたので、学校のプログラミングの演習の自由課題としてウェーブレット行列とFM-indexを実装してみました。 制作物はブラウザ上で動く青空文庫のインクリメンタル検索です。C++で書いたFM-indexをboost-pythonを使ってPythonから呼び出せるようにし、Flaskを使ってブラウザからのリクエストに応答するような仕組みにしてみました。アルゴリズムの本質的なところは全て自分で書こう！というモチベーションで始めたのですが、SA-ISが難しくてsais.
Lepton image compression: saving 22% losslessly from images at 15MB/s | Dropbox Tech Blog
Lepton image compression: saving 22% losslessly from images at 15MB/s This open-source project is no longer maintained or supported by Dropbox. Please refer to Lepton’s GitHub page for more information. ~ ~ ~ We are pleased to announce the open source release of Lepton, our new streaming image compression format, under the Apache license. Lepton achieves a 22% savings reduction for existing JPEG i
OS X 10.11 El Capitanで採用されたAppleの新しい圧縮アルゴリズム「LZFSE」を使ってベンチマークテストをしてみた。
OS X 10.11 El CapitanではAppleの新しい圧縮アルゴリズム「lzfse」が利用可能になっています。詳細は以下から。 AppleはWWDC 2015のSession712 ”Low Energy, High Performance: Compression and Accelerate”で新しい圧縮アルゴリズム「lzfse」を発表しました。このアルゴリズムの特徴はzlib level 5と同程度の圧縮率を保ちながら(x軸)、エンコード・デコードは数倍早く(y軸 注:logプロット)、 LZFSE is a new algorithm, matching the compression ratio of ZLIB level 5, but with much higher energy efficiency and speed (between 2x and 3x) fo
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Apple、新しい圧縮アルゴリズムLZFSEをオープンソース化
