Indeed MPH:高速で小さいイミュータブルなキー・バリューストア - Indeed エンジニアリング・ブログ
膨大なデータを抱えるアプリケーションをスケールする際に、どのようなストレージを導入するべきなのでしょうか？どうしたら大量のデータセットを安全に保存し、効率的に読み書きを行えるのでしょうか？こうした疑問は、よく SQL か NoSQL のどちらを使うべきかという議論になりがちですが、どちらもそれぞれメリットとデメリットがあります。 ですが、もしデータデースにまつわる問題を全て回避できる三番目の選択肢があるとしたらどうでしょうか？ コンシューマは数分おきにしか更新を必要としていないかもしれません。この場合、データセットをメモリ内に読み込めると、劇的にアクセス速度があがり、大規模のスケールが可能になります。このことから、 Indeed では多くのプロジェクトで、必要なデータの完全なコピーを、各コンシューマに渡しているので、 SQL 対 NoSQL の議論をする必要がありません。これを実現するに
Perfect Hashing
Initial hash returns (A,B), final hash is A^tab[B] The perfect hash algorithm I use isn't a Pearson hash. My perfect hash algorithm uses an initial hash to find a pair (A,B) for each keyword, then it generates a mapping table tab[] so that A^tab[B] (or A^scramble[tab[B]]) is unique for each keyword. tab[] is always a power of two. When tab[] has 4096 or more entries, scramble[] is used and tab[] h
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
DAWG(4-1): 完全ハッシュ関数 - sileのブログ
四回目の前半。 DAWGのキーに一意なIDをマッピングするための最小完全ハッシュ関数を実装。 ※ ただし今回実装分は、"最小"のつかないただの完全ハッシュ関数まで 参考元 『Simple and Space-Efficient Minimal Perfect Hash Functions』*1を参考にした。 ただし、まだ実装に必要な箇所に軽く目を通しただけなので、詳細は理解していない。 ※ いつものことだけど、ちゃんと知りたい人はもとの論文を参照のこと 概要 とりあえず現状での理解。※ 間違っている可能性あり! 定義: 完全ハッシュ関数(PHF, perfect hash function): N個のキーを0からM未満の一意な値(整数値?)にマッピングする関数 ※ M >= N 最小完全ハッシュ関数(MPHF, minimal perfect hash function): N個のキーを0
文字列から浮動小数点数に変換する、なるべく速く - toge's diary
TL;DR 文字列から浮動小数点数に変換するならfastfloat使いましょう。 私が試せる環境で比較する限り、とても速いです。 細かいことが気になります C++でちょっとしたプログラムを書くときにいつも気になるのが 「文字列データから指定データ型への変換処理をどうやって効率的に書くか」 です。私だけかもしれませんが。 特に悩んでしまうのが「文字列→浮動小数点」です。 std::scanf, std::stringstreamを使うものは大抵すごく遅い std::strtodstd::stodはstd::stringへの変換が入るので避けたい std::from_charsは(libstdc++が)浮動小数点型に対応していない boost::sprit::qiが何故か速いのだけれどこのためにboost::sprit使うのは重い と色々制約が多いのです。どうにかならないものか。 fast_f
Run-Length FM-Index - koki
FM-index は検索対象のテキストから予め索引を構築しておくことで，テキストに含まれる任意のパターン文字列の個数を数えるクエリ$ \mathrm{count} を，テキストのサイズに依らず高速に実行できるデータ構造です．加えて，suffix array や inverse suffix array の一部を追加で保持しておくことで，パターンの位置の列挙 $ \mathrm{locate}やテキストの復元 $ \mathrm{extract}といったクエリを高速に実行することができます（自己索引）． 主要な応用としてゲノム解析（例：HISAT2）などが挙げられます．身近なところでは，arXiv をコーパスとした高速な英文コロケーション検索を提供する Hyper Collocation でも用いられています（解説）． FM-Index に関しては，高速文字列解析の世界 や 簡潔データ構造
マルチキー・クイックソート(multikey-quicksort)で高速に文字列ソート - EchizenBlog-Zwei
一般にソートアルゴリズムの計算量はソート対象となるデータ数NについてO(N^2)とかO(NlogN)等で評価する。数値データのソートであれば特に問題はないのだが、文字列データの場合は一回の比較に対して文字列長Mに比例する計算量O(M)がかかってしまう。例えばクイックソートであればO(NlogN)ではなくO(MNlogN)となる。よってMが非常に大きい場合はソート性能の劣化を招く。 文字列ソートに付いてはBently&Sedgewickのマルチキー・クイックソート(multikey-quicksort)という改良版クイックソートが存在する。このソート法は、ある工夫によって一回の比較を文字列長Mに依存しない形で実現している。 例えば文字列appleとapplicationの比較について考える。 # 先頭の文字を比較 [a]pple = [a]pplication # 2文字目を比較 a[p]p
bit vectorで編集距離の計算を高速化する - Retrieva TECH BLOG
レトリバ製品開発部の@ysk24okです。 本記事ではbit vectorを用いて編集距離の計算を高速化するアルゴリズムを紹介します。論文はこちらです。 dl.acm.org クエリの長さを、検索対象のテキストの長さを$n$としたとき編集距離の計算量は$O(mn)$であることが知られていますが、bit vectorを活用することでword長を$w$とすると計算量を$O\bigl(\frac{m}{w}n\bigr)$（$m\leq w$のときは$O(n)$）に低減できる手法になります。 1999年発表の古い論文ですが、この論文で提案されているアルゴリズムが弊社の製品に実装されていて初見では理解できなかったことに加え、日本語での論文解説が無いようだったので解説記事を書くことにしました。 編集距離（Levenshtein Distance）とは 近似文字列照合（approximate stri
ダブル配列で決定性有限オートマトンを表現する - Qiita
はじめに Qiitaデビューです．@kampersandaです． この記事では，さまざまな文字列処理アルゴリズムの理論的基礎となっている決定性有限オートマトン（以下，オートマトンと書きます）をダブル配列により表現する方法を紹介します．この記事で紹介する手法は以下の論文で提案されているものです． 前田敦司, 水島宏太. オートマトンの圧縮配列表現と言語処理系への応用. プログラミングシンポジウム, pp. 49–54, 2008. まずダブル配列について簡単に説明しますと，ダブル配列とはトライと呼ばれるラベル付き木を表現するためのデータ構造の一つです．検索が非常に高速であり，形態素解析器MeCabの辞書引きなどに用いられています．トライのダブル配列表現についての解説はブログや書籍などで多く拝見されます．Wikipediaのトライ木にも説明が載っています．一方で，実はオートマトンも表現できると
Index 1,600,000,000 Keys with Automata and Rust - Andrew Gallant's Blog
It turns out that finite state machines are useful for things other than expressing computation. Finite state machines can also be used to compactly represent ordered sets or maps of strings that can be searched very quickly. In this article, I will teach you about finite state machines as a data structure for representing ordered sets and maps. This includes introducing an implementation written
A Branchless UTF-8 Decoder
This week I took a crack at writing a branchless UTF-8 decoder: a function that decodes a single UTF-8 code point from a byte stream without any if statements, loops, short-circuit operators, or other sorts of conditional jumps. You can find the source code here along with a test suite and benchmark: https://github.com/skeeto/branchless-utf8 In addition to decoding the next code point, it detects
SymSpell対BK木：100倍速い文字列のあいまい検索とスペルチェック | POSTD
注釈：500,000単語収録の辞書内における1,000単語の検索時間 X:最大編集距離 Y:検索時間/ms 従来、スペル修正や文字列のあいまい検索には、 BK木 が適していると言われてきました。しかし、これは本当でしょうか。 また、 スペル修正に関する私のブログ に寄せられたコメントには、BK木が、あいまい検索のためのデータ構造として優れていると言及されていました。 そのような経緯から、今回、BK木と他の選択肢のベンチマークを取って比較してみようと思い立ったわけです。 近似文字列検索アルゴリズム 近似文字列検索では、文字列リスト内の文字列を検索し、特定の 文字列メトリック に従って、それに近い文字列を返します。 文字列メトリックは多数あり、例えば レーベンシュタイン距離 、 Damerau-Levenshtein距離 、 ハミング距離 、 ジャロ・ウィンクラー距離 、 Strike a m
Java9 でも String クラスがリファクタリングされていました （JEP 254: Compact Strings 編） - 地平線に行く
本日、ついに JavaSE 9 がリリースされました！ そこで、かねてから噂になっていた JEP 254: Compact Strings がどのように実装されているのか調べてみました。 Compact Strings の概要 これまで String クラスや StringBuilder クラスなどの内部では、文字列を UTF-16 でエンコードして char 配列で保持していました。 つまり、一文字あたり*1常に char ひとつ = 2バイト分のメモリを使っていました。 しかし、これだと 1 バイトで表せる LATIN1（ASCII コード ＋ ラテン文字）の文字列の場合、その半分が 0x00 になるという無駄がありました。 そこで、内部表現を変更し、文字列が LATIN1 のみで構成されるときは 1 文字を 1 バイトで保持するようにリファクタリングされました。 ちなみに、LATIN
先読みと後読みの可能な、O(N)の正規表現エンジンの実装
https://cybozu.connpass.com/event/53121/ での発表資料です。
文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog;
前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog; しかし、前処理としてSuffix ArrayからLCP Array(Longest Common Prefix Array)という構造をさらに作っておくと、という計算量で文字列マッチングが出来るようになるらしい。そこで、今回はLCP Array(Longest Common Prefix Array)の構築を実装し
Coursera の Algorithms on Strings 受けました - たにしきんぐダム
Cousera の Algorithms on Strings を受講していて、平日にお昼ご飯食べながらビデオを見たり休日とかに課題をやったりしていたのですが先日完走しました！(講義は4週分なのですが忙しかったり難しかったりで2ヶ月くらいかかってしまった) お金を払うと課題提出システムみたいなのが使えて提出したプログラムの時間/空間計算量を教えてくれるらしいけど無料でも授業ビデオと資料にはアクセスできた めちゃくちゃ良かったのでみんなも受講しましょう www.coursera.org きっかけはアルバイト先で開催されていたのに参加させてもらったのと、 ISUCON6予選で高速な文字列マッチングアルゴリズムが全く分からず悔しい思いをしたから(正規表現の更新・キャッシュをうまく頑張れば十分な点数は獲得できたみたいですが...)でした。 学んで終わりじゃ多分忘れるから何とか応用とかできたら良い
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Number Parsing at a Gigabyte per Second – Daniel Lemire's blog