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
Compressed Permuterm Index: キーワード辞書検索のための多機能＆省メモリなデータ構造 - Preferred Networks Research & Development
はじめましてこんにちわ。 4月からPFIで働いているまるまる（丸山）です。最近のマイブームはスダチです。 リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。 今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。 Paolo Ferragina and Rossano Venturini. “The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf] これを実装したので以下のgoogle codeに晒してみることにします。 http://code.google.com/p/cpi00/ 修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな
GoとSuffixArray | フューチャー技術ブログ
フューチャー夏休みの自由研究連載の5回目です。 はじめにTIG の辻です。 Go は標準ライブラリが充実しているとよく言われます。標準ライブラリだけで、HTTP サーバを作れたり、暗号化処理や、JSON や CSV といったデータ形式を扱うことができます。go list std | grep -v vendor | wc -l としてパッケージ数を見てみると、約 200 ものパッケージが存在することがわかります。本記事では、その多くの Go の標準ライブラリの中でも、個人的に面白いなと思ったライブラリを紹介したいと思います。suffixarray パッケージです。 suffixarray パッケージは Suffix Array を扱うライブラリです。suffixarray パッケージの魅力を感じるには、まず Suffix Array とは何か？を知る必要があるでしょう。 Suffix Ar
Run-Length FM-Index - koki
はじめに 本記事は データ構造とアルゴリズム Advent Calendar 2019 13日の金曜日の記事です． 前回（12 日目）：Immutableなデータ構造について（@takoshi さん） 次回（14 日目）：動的木上の最小シュタイナー木をtoptreeで解く（@niuez_さん） FM-index は検索対象のテキストから予め索引を構築しておくことで，テキストに含まれる任意のパターン文字列の個数を数えるクエリを，テキストのサイズに依らず高速に実行できるデータ構造です．加えて，suffix array や inverse suffix array の一部を追加で保持しておくことで，パターンの位置の列挙 やテキストの復元 といったクエリを高速に実行することができます（自己索引）． 主要な応用としてゲノム解析（例：HISAT2）などが挙げられます．身近なところでは，arXiv をコ
マルチキー・クイックソート(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
絵文字を扱う上で知っておくと良いかもしれないことをまとめてみました。 Ruiさんの記事を見て、「EmojiはSurrogate Pair以外にも、色々とおもしろい技術があるんですよ〜」思って書いてみました。 なお、書いた人はAndroidの人間なので、特に表記していない場合は主にAndroid上での動作のことを書いてます。 またQiita初めてなので読みにくい部分等がありましてもご容赦ください。 サロゲートペア(Surrogate Pairs) このエントリーを書くきっかけにもなったサロゲートペア。なぜこれが導入されたかの経緯は、Ruiさんのブログエントリーに譲るとして、技術的な解説をします。 サロゲートペアは、U+0000..U+FFFFに収まりきらなかった範囲のUnicodeコードポイント(U+10000..U+10FFFF)を、なんとか16bitでエンコードしようとして導入されました
ダブル配列で決定性有限オートマトンを表現する - Qiita
です． オートマトンを表現するとは，この遷移関数 $\delta$ をいかにして計算機上に実装するかということです．その最も簡単な方法は，上記した表のような各要素が遷移先状態を保持した $|Q| \times |\Sigma|$ のテーブル（状態遷移表って呼ばれたりします）を用いる方法です．このテーブルを仮に $T$ としたとき，$\delta(q,c) = T[q][c]$ です． 一方で，このテーブルのメモリ使用量は $\Theta(|Q| \cdot |\Sigma|)$ と結構大きいわけでして，見て分かる通り結構な数の要素が $nil$ です．このような $nil$ の表現にわざわざ要素を割り当てずに，切り詰めて遷移関数 $\delta$ が実装できればメモリ効率よくオートマトンが表現できそうです．そしてそれを叶えるのがみんな大好きダブル配列です． オートマトンのダブル配列表現 オ
類似文字列検索ライブラリResemblaを公開しました - LINE ENGINEERING
LINEでClovaの開発をしている上村です。これはLINE Advent Calendar 2017の13日目の記事です。今日は文字列の話をします。 はじめに 与えられた文字列によく似たものを大きな文字列集合から探すということは、古典的でありふれていながら奥が深く難しい問題です。文字列の類似度を正確に見積もるには複雑な計算が必要ですが、膨大な量のコーパスが与えられたときも可能な限り高速に応答を返す必要があります。 検索する文字列の性質をよく把握することも、品質のよい類似文字列検索を行うためには極めて大切です。ここで、今回考える問題の例を見てみます。 この例では、1文字ずつ違いを見つけ出したり、単語単位で見たり、文全体が疑問文や否定文であるかどうかを調べ、それらを総合的に見ることで最終的な判断を下しています。文字だけを見た場合、1文字の違いによって全く違う単語になることは見つけられませんし
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)の構築を実装し
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Number Parsing at a Gigabyte per Second – Daniel Lemire's blog