はじめましてこんにちわ。 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ライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな

ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下

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

package search; /** * 文字列に対するマッチ処理を行うためのインターフェイス。 */ public interface Matcher { boolean match(String target); } package search; import java.util.HashMap; import java.util.Map; /** * マッチ対象の文字列集合を前処理し、ツリー構造で保持する。 * NGワードチェックなど、マッチ対象の文字列集合がほぼ静的に決定されるケースで高速に動作する。 */ public class TreeMatcher implements Matcher{ private CharTreeNode rootNode = null; public TreeMatcher(String[] words){ this.rootNode = ne

この記事は Origami Advent Calendar 11日目の記事になります。 最近学習しているデジタル署名について、わからない人でもわかる基礎的なところから、簡単なサンプルプログラムの実装までまとめてみました。最後のサンプルプログラムを組むところまで実施すれば、デジタル署名のメリットや仕組みなどの基本的な部分は理解できるかと思います。プログラムはGoで書いてます。 デジタル署名について デジタル署名は公開鍵暗号方式の一種で、一般的には3つのアルゴリズムから成る。 鍵生成アルゴリズムG 署名者の"鍵ペア"（PK, SK）を生成する。PKは公開する検証鍵（公開鍵）、そしてSKは秘密にする署名鍵（秘密鍵）である。 署名生成アルゴリズムS メッセージmと署名鍵SKを入力とし、署名σを生成する。 署名検証アルゴリズムV メッセージm、検証鍵PK、署名σを入力とし、承認または拒否を出力する。