フューチャー夏休みの自由研究連載の5回目です。 はじめにTIG の辻です。 Go は標準ライブラリが充実しているとよく言われます。標準ライブラリだけで、HTTP サーバを作れたり、暗号化処理や、JSON や CSV といったデータ形式を扱うことができます。go list std | grep -v vendor | wc -l としてパッケージ数を見てみると、約 200 ものパッケージが存在することがわかります。本記事では、その多くの Go の標準ライブラリの中でも、個人的に面白いなと思ったライブラリを紹介したいと思います。suffixarray パッケージです。 suffixarray パッケージは Suffix Array を扱うライブラリです。suffixarray パッケージの魅力を感じるには、まず Suffix Array とは何か？ を知る必要があるでしょう。 Suffix A
お手軽PerlでSuffixArrayに挑戦
試しにPERLでSuffixArrayついでにソートの勉強 下記のページを参考にしている http://www.namazu.org/~satoru/unimag/9/ ここに記述されているコードは、実験のために書かれているので、 へんなところはご容赦を... インデックスを作ってみる Cで書かれたサンプルをperlでかいてみた。 PERLでもquicksortの関数はあるが、一応PERLでかいてみた。 バイナリー形式でインデックスファイルを書き出している。 テストのためのサンプルプログラムなので、書き出したあとよみだして表示している。 pushを使って配列を拡大しているが、これってスピード的にいいのだろうか？ pack,unpack関数はいろいろ使いでありそう！！ 1: #!/usr/bin/perl 2: 3: #2003/03/14 4: #UNIXマガジン2002 10月号 横着プ
『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。 以下、そのソースコードとメモ書き。 線形構築 汎用ソートアルゴリズムと今回実装したSA-ISアルゴリズムでのSuffixArray構築時間の簡単な比較。 百文字〜一千万文字の文字数のテキストを入力として与えて、その構築時間を計測。 百文字千文字一万文字十万文字百万文字一千万文字 汎用ソート*20.000 sec0.002 sec0.023 sec0.358 sec5.604 sec94.196 sec SA-IS0.031 sec0.120 sec0.135 sec0.335 sec2.580 sec2
全文検索エンジンを試作してみたよ - やればできる子の日記とJavascriptを組み合わせてもうちょっとなにかできないかなあと思って、JavascriptでSuffixArrayを作ってみました。 上手い具合に組み合わせるアイデアが思いつけなかった(どうせ全文検索用のインデックスを保持しちゃうので、別途SuffixArrayを保持する意味がなさそう)ので、素のまま公開しちゃいます。 ちなみに、Javascriptも自信ないです。僕はJSでのべ2000行程度しか書いたことないはず。 /* Suffix Array構築のアルゴリズムは色々研究されています。 以下のコードはかなり最悪なアルゴリズムなので、実用の際は調査してください。*/ function genSA(text){ var sa = new Array(text.length) for(var i = 0; i < text.l
hatena-bookmark-xul/chrome/content/common/05-SuffixArray.js at master · hatena/hatena-bookmark-xul
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
RubyでSuffixArrayを使う場合には普通saryを使うと思いますが、勉強のためにたつをさんのPerlのコードを参考にRubyで実装してみました。SuffixArrayって意外と簡単に作れるんですね。 今回は自分でバイナリサーチのアルゴリズムを実装しています。Ruby標準では提供されていないのかな。んー。 #!/usr/bin/env ruby class Array def bsearch(key, left = 0, right = self.size - 1, &comp) return -1 if left > right mid = (left + right) / 2 case comp.call(mid) when 0 mid when -1 bsearch(key, mid + 1, right, &comp) else bsearch(key, left, mid
Tips for writing clear, performant, and idiomatic Go code
PHP で SuffixArray による結構速い全文検索というのをつくってみようと思い立ち実装してみました。 SuffixArray を実装することによって単純に検索した場合 O(n) の計算量を O(logn) に減らすことが出来ます。またこの方法は漏れなく検索することができ、なおかつインデックスサイズも少ないという他方法（転置インデックス等）に対しても利点があります。 準備として文書集合をつっこんでインデックス集合を作成します。 実行として単語とインデックスをつっこんで、ヒット確認します。 usort 時に変数の渡す方法が PHP では普通の方法で提供されていないため 開発用メモ » Blog Archive » php：関数に変数をバインドしたい を利用させてもらいました。ありがとうございます。 <?php require_once('binder.php'); function
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GoとSuffixArray | フューチャー技術ブログ
SA-IS: SuffixArray線形構築 - sileのブログ
JavascriptでSuffixArray - やればできる子の日記
RubyでSuffixArray - 趣味的にっき
suffixarray package - index/suffixarray - Go Packages
PHP による SuffixArray による結構速い全文検索 - 横転プログラミング