2011年10月31日月曜日

日本語OCR



O2-toolと、nhocr、freetypeをインストール。
なんかO2-toolのインストールに失敗すると思ったら、O2-dtoolだったというオチ
まずfreetypeとO2-toolを普通にインストール。ただし、prefixを指定すること。(O2-toolのデフォルトが変)



./configure prefix=/usr/local
make
sudo make install



次に、nhocrインストール



$./configure prefix=/usr/local --with-O2tools=/usr/local



test/run-testでサンプル実行。
うーん、精度悪い。でもまぁ言葉としておかしいところを修正すればそれっぽくなるか。

ここまでやっといて自分の目的とは違うなぁってことに気づく。
画像中から文字っぽいところを探しだしてパターンマッチングでいいきがする、、、、。





2011年10月30日日曜日

traceroute



pingと違って、途中の経路でもpingと同じような情報が得られる。





CSVに対してSQLが使えるDBD::CSV



参考
でかいCSVの中から一部だけ抽出して処理するときに使えそうですね。




2011年10月29日土曜日

HTMLから特定要素のテキストを抜き出す。



簡単。get_tagのところは複数指定可



my $p = HTML::TokeParser->new(\$html_data);
if ($p->get_tag("title")) {
warn $p->get_trimmed_text;
}





Path::Classを使って、ディレクトリ以下のHTMLファイル読み込み。



はじめてのPath::Class
slurpがあるとはー。



my $dir = dir($dir_path);
my @file_paths;
$dir->recurse(
callback => sub {
my $entry = shift;
return if $entry->is_dir;
return if $entry !~ /\.html\z/;
push @file_paths, $entry->absolute;
}
);

for my $path (@$paths) {
my $html_data = Encode::decode('utf-8', $path->slurp);
}





二進化十進数 (BCD、Binary-coded decimal )

BCD

仕組み
  • 十進数の各桁(0~9)を2進数で表す。127(10) は0001 0010 0111(2) という3つのBCD
利点
  • 10進数から2進数に変換すると循環小数が生まれるが、BCDなら大丈夫。
  • BCDを16進数に変換すると、10進数に変換したときと同じ表現になる。(A-Fは使用せず0-9までしか使用してないから)
BCDベースの形式
  • ゾーン形式
  • パック形式

ゾーン10進数(アンパック進数)

仕組み
  • 4桁のゾーンビットと4桁の数値ビットのペア
  • ゾーンビット
    • 数値であることを表す部分
    • 文字で数値を表したときのコードと互換性あり
      • つまり文字コードの違いが問題になる
      • 8ビット文字コードはEBCDICとASCII (JIS8)の二種類に大別されるためあまり問題にならない。

  • 符号ビット
    • 1桁目のゾーンビット部分は符号ビット
    • EBCDICでは1100(2),JIS8コードでは1101(2)
    • ベンダーによって方式が異なることが多く問題になりやすい

パック10進数

仕組み
  • BCD形式で末尾4bitに符号ビットを付加したもの。
  • 符号ビット
    • ゾーンと同じくEBCDICでは1100(2),JIS8コードでは1101(2)
利点
アンパック(ゾーン)だと1桁に8bit必要で無駄が多い。
1バイトで1つなので、以下のような場合は、先端に0000を付加する必要がある。
+1234  0000 0001 0010 0011 0100 1100
-1234  0000 0001 0010 0011 0100 1101

EBCDIC(エビシディック)

  • BCDを拡張したIBMの文字コード
  • 非常に扱いにくい1バイトコード

UTF-EBCDIC

  • EBCDICと互換性があり、Unicodeを表現できる文字コード
  • 設計時に対象だったメインフレームではあまり使われずUTF-16が使われている

2011年10月24日月曜日

Moose アトリビュート



和訳マニュアル アトリビュート


アトリビュート(属性)



has 'weight' => (
is => 'ro',
writer => '_set_weight',
default =>
sub { ( 'small', 'medium', 'large' )[ int( rand 3 ) ] },
required => 1,
clearer => 'clear_weigth',
predicate => 'has_weight',
);



  • is

    • ro,rwの指定



  • isa

    • クラス指定

    • Int,Str,単純にObjectってあるのは何だろ



  • writer

    • 属性名とは異なる名前で書き込みメソッドを呼び出す

    • 外部からは読み取り専用だが、内部では書き込みしたい場合に使用。



  • predicate

    • 値がセットされていれば真を返す

    • undefが明示的に代入されている場合も真。



  • clearer

    • 値をセットされていない状態にする

    • undefとは異なり、predicateで偽になる。



  • required

    • 属性を必ずコンストラクタに渡す。

    • 値が必須なわけではないので、undefかも。



  • default

    • 単純なスカラ

    • サブルーチンリファレンス => 代わりにbuilderメソッドが推奨

      • サブルーチン以外のリファレンスを渡すとエラー。





  • builder

    • _build_属性名 がメソッド名になる。

    • 継承もオーバーライドも可能

    • roleの属性でbuilderのメソッド名を指定しておいて、roleを使用するクラスで、その名前のメソッドを定義することもできる。





package HasSize;
use Moose::Role;
requires '_build_size'; # Roleを使用するクラスに必要なメソッド

has 'size' => (
is => 'ro',
lazy => 1,
builder => '_build_size',
);

package Lilliputian;
use Moose;

with 'HasSize';

sub _build_size { return 'small' }



  • lazy

    • defaultが単純なスカラーでない場合と、builderの場合は必ず使用。

      • default値が他のobjectと依存関係の場合があるから

      • cpu処理を減らす





  • lazy_build

    • 複数オプションをまとめて設定





has 'size' => (
is => 'ro',
lazy_build => 1,
);

has 'size' => (
is => 'ro',
lazy => 1,
builder => '_build_size',
clearer => 'clear_size',
predicate => 'has_size',
);




  • init_arg

    • クラスのコンストラクタで使用する名前を属性名とは別のものにする。以下は属性名はbignessだが、コンストラクタではsizeで属性値を設定する。

    • init_arg => undefにした場合はコンストラクタで初期値を設定することはできない。プライベートな属性に便利。






has 'bigness' => (
is => 'ro',
init_arg => 'size',
);




  • weak_ref

    • 属性に値がセットされたときは常にScalar::Util::weakenを呼ぶ

    • 循環参照になるかもしれないオブジェクトを作るとき便利



  • trigger

    • 属性が更新された「後に」呼び出すメソッド

    • trigger発動の条件

      • 属性が更新された場合(類似のafterメソッドモディファイアは読み込みでも呼ばれる)

      • 属性の値がコンストラクタに渡されたとき



    • triggerが呼ばれない条件

      • defaultやbuilderで値がセットされた場合



    • 更新前の値と更新後の値が引数にとれる。

    • 初めて設定される場合は引数の数がひとつ少ないので識別できる。



  • handles(委譲)

    • handles => { hair_color_hex => 'as_hex_string' }

    • hair_color_hexを呼ぶと、as_hex_stringが呼ばれるだけ?



  • トレート?

    • Roleのこと

    • 複数指定できるのが利点

    • ネイティブトレート

      • Hash(Moose::Meta::Attribute::Native::Trait::Hash)

      • Number (Moose::Meta::Attribute::Native::Trait::Number)

      • Counter (Moose::Meta::Attribute::Native::Trait::Counter)

      • String (Moose::Meta::Attribute::Native::Trait::String)

      • Bool (Moose::Meta::Attribute::Native::Trait::Bool)

      • Array (Moose::Meta::Attribute::Native::Trait::Array)





  • オーバーライド

    • 子クラスで属性名の前に+を付けるだけ



  • 複数属性の定義

    • has [ 'x', 'y' ] => ( is => 'ro', isa => 'Int' );







2011年10月22日土曜日

クエリログが存在しないときのクエリ補完



クエリログのない状況下でのクエリ補完


クエリのログをとってない場合どうやって補完するのか。



  • ジャンルが絞り込めるなら、そのコーパスを使用する

  • コーパスから入力中クエリを使用して検索



問題点



  • 入力中クエリでコーパスから検索しても精度が低い



提案手法



  • 入力中のクエリで、完全なフレーズと不完全なフレーズに分ける。

  • 不完全なフレーズでコーパスから検索

  • 一般的すぎるフレーズを避ける

    • TF-IDF

    • 短いフレーズが優先されすぎないようにパラメータチューニング(短いフレーズを含む長いフレーズと比べると短いフレーズの出現回数が常に多いため。ex.「言語処理」だと短い「言語」のほうが出現回数が多い)



  • 完全なフレーズも修正補完

    • 完全と不完全フレーズが両方存在する文書を探して、正規化。完全一致はスパースネスを起こすのでしない。






感想


こういう正統派は実践で使いやすそう好き





2011年10月17日月曜日

YAPC2011感想



ほんとは、自分はYAPCを糧にコードを書くつもりであって、感想は書かないつもりだったのだけど、


YAPC参加した、関わった人は是非ブログを書いてね!ほんと頼むよ!それ見たくて運営やってるようなもんだから! #yapcasia


と言われては書かないわけにはいかないかなーと。


自分はITやるなら人がいっぱいいる東京しかない、と思って今年東京にきて、YAPCは初参加でした。
今回、東京に出てくるまでは向こう側の人たちでしかなかった人たちと沢山話しが出来て楽しかったです。
ただやっぱり雑談をしただけでは物足りず、この人たちとPerlerとして会話ができるようにがんばりたいと思いました。


見てろよ来年ーー




2011年10月12日水曜日

木構造とか



2分木



  • O(¥log m)

    • m:木の深さ

    • 2分木なので、深さの対数log2 (均等に振り分けないと無駄に深くなるけど)




Trie木



  • O(n)

    • n:文字列長

    • すでに辞書式ソート済みなので、文字列長で検索できる。



  • メモリ

    • 多数の短い文字列群は、共通するキーをもつ確率が高いのでメモリを節約できる。

    • 逆に長い文字列はパトリシア木が良い。




パトリシア木



  • トライ木であるノードからあるノードまでの間、1本道で分岐がない場合、ひとつのノードにまとめてしまう。

  • 常に成功する場合に適している

    • ひとつのノードにキー値がまとまってるからかな




suffix木



  • wikipedia

  • suffixで生成された部分文字列をキーとして木に登録

  • 接尾辞リンク

    • ひとつ前の接尾辞を指す BANANA <- ANANA <- NANA <- ANA <- NA <- A





AC法



  • マッチングに失敗した際に、次に調べるべきノードを予め登録しておくもの

    • ある入力文字列(ex.東京都)に特定のキーワード(Trieに登録済み)が存在するかを調べる際に、ある経路でマッチングに失敗したときに、入力文字列を一文字削って、それ(ex.京都)をTrie木の頭から調べるのではなく、次にどこから始めるべきか、予め登録して高速化している。



  • 入力文字列を一文字ずつ削る場合の話なので、事前に形態素解析してある場合は失敗したらそこまでなので、AC法は必要ない。