livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary
すみません。タイトルはやや釣り気味です。 類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。 Luigi https://github.com/miki/Luigi 類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。（冷） 考え方と仕組み 類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。 昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。 そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。 で、今回考えたLuigiも実は近似型のインデッ
Variable Byte Code と UTF-8、またはUTF-24が存在しないわけ : 404 Blog Not Found
2009年08月05日00:30 カテゴリLightweight Languages Variable Byte Code と UTF-8、またはUTF-24が存在しないわけ 実は、これに非常に良く似た符号化を、我々は日々目にしています。 γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー 通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 UTF-8です。 UTF-8は、0x0から0x10FFFFまでの整数を、以下のようにしてバイト列に変換します。 Range/Offset0123 0x00-0x7F0xxxxxxx 0x80-0x3FF110xxxxx10xxxxxx 0x400-0xFFFF1110xxxx10xxxxxx10xx
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
String::Dictionary - naoyaのはてなダイアリー
String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル
ダイクストラ法, 貪欲アルゴリズム - naoyaのはてなダイアリー
現実逃避をしながらウェブを眺めていたら ダイクストラ法（最短経路問題） にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。 何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションができていました。 http://bloghackers.net/~naoya/ppt/090319dijkstra_algorithm.ppt 実装もしてみました。隣接ノードの表現は、ここではリストを使いました。 #!/usr/bin/env perl use strict; use warnings; package Node; use base qw/Class::Accessor::Lvalue::Fast/; __PACKAGE__->mk_accessors(qw/id done cost edges_to prev/); package Q
[を] Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二
Mastering Algorithms with Perl : 404 Blog Not Found
2006年11月02日19:00 カテゴリ書評/画評/品評 Mastering Algorithms with Perl 定番アルゴリズムを徹底理解！：ITproが もブクマされておりますが、それよりもこちらの方がおすすめ。 Mastering Algorithms With Perl J. Orwant / J. Hietaniemi / J. MacDonald 以前404 Blog Not Found:Hash != Associative Arrayでもちょこっと紹介しましたが、ここで改めて紹介しておきます。 本書"Mastering Algorithms with Perl"には「定番アルゴリズムを徹底理解！」のアルゴリズムは全て載っている上、それぞれのベンチマークもちゃんと取ってます。"with Perl"とありますが、Perl色はそれほど強くないので、他のLLのユーザーにも役
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
