perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary
すみません。タイトルはやや釣り気味です。 類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。 Luigi https://github.com/miki/Luigi 類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。（冷） 考え方と仕組み 類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。 昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。 そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。 で、今回考えたLuigiも実は近似型のインデッ
ブロック処理を決定性有限オートマトン(DFA)化した Text-Creolize-0.003 - Tociyuki::Diary
「練習で書いてみたText-Creolize-0.001 - Tociyuki::Diary」では、とりあえずブロックの構文を LL(1) で記述し、構文解析表を使って動かしていました。コードを作るにはてっとり早くて楽ができる反面、プッシュ・ダウン・オートマトンとしてスタックへ後続記号をいちいちプッシュしつつループを回す分が余計なオーバーヘッドになっていました。 ところで、この構文解析表を変形しているとき、この構文が正規文法であることに気がつきました。つまり、block、paragraph などが、有限オートマトンの状態に相当し、状態 A で記号 S を受理したとき必ず他の状態 B へ遷移し、再帰することなく最後まで遷移を繰り返していくだけで記号列を解釈することができます。変形した記号表は下のとおりです。しかも、常にすべての状態で記号に対して一意に遷移する先の状態が一つ決まっていますので、
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
