TorasenLab@はてな このページをアンテナに追加 RSSフィード

2011-10-06

opencvのインストールログ

| 23:24 | opencvのインストールログを含むブックマーク opencvのインストールログのブックマークコメント

環境

  • Ubuntu 10.04 64ビット
  • python 2.6.5

インストールログ

基本的に

no title

に書いてあるとおり実行しました。

一部インストールするパッケージを変更しています。

IPPやTBBはインストールしていません。pythonラッパーはインストールしました。

sudo aptitude -y install build-essential
sudo aptitude -y install cmake
sudo aptitude -y install pkg-config
sudo aptitude -y install libpng12-0 libpng12-dev libpng++-dev libpng3
sudo aptitude -y install libpnglite-dev libpngwriter0-dev libpngwriter0c2
sudo aptitude -y install zlib1g-dbg zlib1g zlib1g-dev
sudo aptitude -y install libjasper-dev libjasper-runtime libjasper1
sudo aptitude -y install pngtools libtiff4-dev libtiff4 libtiffxx0c2 libtiff-tools
sudo aptitude -y install libjpeg62 libjpeg62-dev libjpeg62-dbg libjpeg-progs
sudo aptitude -y install ffmpeg libavcodec-dev libavcodec52 libavformat52 libavformat-dev
sudo aptitude -y install libgstreamer0.10-0-dbg libgstreamer0.10-0 libgstreamer0.10-dev
sudo aptitude -y install libxine1-ffmpeg libxine-dev libxine1-bin
sudo aptitude -y install libunicap2 libunicap2-dev
sudo aptitude -y install libdc1394-22-dev libdc1394-22 libdc1394-utils
sudo aptitude -y install swig
sudo aptitude -y install libv4l-0 libv4l-dev
sudo aptitude -y install python-numpy


sudo aptitude -y install libpython2.6 python-dev python2.6-dev


sudo aptitude -y install libjpeg-progs libjpeg-dev


sudo aptitude -y install libgstreamer-plugins-base0.10-dev


mkdir ocv
cd ocv/
# sudo aptitude install subversion
svn co https://code.ros.org/svn/opencv/trunk

cd trunk/opencv/
mkdir release
cd release/
cmake -D CMAKE_BUILD_TYPE=RELEASE -D CMAKE_INSTALL_PREFIX=/usr/local -D BUILD_PYTHON_SUPPORT=ON -D BUILD_EXAMPLES=ON ..
make
sudo make install

sudo ldconfig
cd unix-install
pkg-config opencv --libs

動作チェック

C++でのチェック

ダウンロードしたファイルのtrunk/opencv/samples/cpp/ディレクトリのファイルがコンパイルできるかどうか。

コンパイルは、

g++ example.cc `pkg-config opencv --cflags --libs`

など。

pythonラッパーのチェック

pythonでimport cvが成功するかどうか。

ダウンロードしたファイルのtrunk/opencv/samples/python/delaunay.pyがpythonで実行できるかどうか。

参考

no title

2011-09-14

見出し語化の高速化

| 00:59 | 見出し語化の高速化を含むブックマーク 見出し語化の高速化のブックマークコメント

nltkのWordNetLemmatizerを力ずくで高速化した。

環境

Python 2.6.5

コード

# -*- coding: utf-8 -*-

from collections import defaultdict
import nltk
from nltk.corpus import wordnet as _wordnet


_STEMMER = nltk.PorterStemmer().stem
_LEMMATIZATION_POS_PRIORITY = (_wordnet.NOUN, _wordnet.VERB,
                               _wordnet.ADJ, _wordnet.ADV)
_POS_LIST = (_wordnet.ADJ, _wordnet.ADV, _wordnet.NOUN, _wordnet.VERB)


def stem_form(form):
    return _STEMMER(form)


def _detect_pos(form):
    form = form.replace(' ', '_')
    synsets = _wordnet.synsets(form)
    if not synsets:
        return None
    pos = None
    stem = stem_form(form)
    for synset in synsets:
        if stem_form(synset.name[:-5]) == stem:
            pos = synset.pos
            break
    if pos is None:
        pos = synsets[0].pos
    if pos == _wordnet.ADJ_SAT:
        pos = _wordnet.ADJ
    return pos


def lemmatize_with_wordnet(form, pos=None):
    if pos is None:
        pos = _detect_pos(form)
        if not pos:
            return form
    assert(pos in _POS_LIST)
    return nltk.WordNetLemmatizer().lemmatize(form, pos=pos)


def _lemmatize_form_with_wordnet(form, pos_set):
    assert(pos_set)
    if len(pos_set) == 1:
        target_pos = pos_set.copy().pop()
    else:
        target_pos = _detect_pos(form)
        if not target_pos or target_pos not in pos_set:
            for pos in _LEMMATIZATION_POS_PRIORITY:
                if pos in pos_set:
                    target_pos = pos
                    break
    assert(target_pos in _POS_LIST)
    return nltk.WordNetLemmatizer().lemmatize(form, pos=target_pos)


def _construct_inflected_form_to_lemma_dictionary():
    all_inflected_forms = defaultdict(set)
    for pos, excepted_forms in _wordnet._exception_map.iteritems():
        if pos == _wordnet.ADJ_SAT:
            continue
        for excepted_form in excepted_forms:
            all_inflected_forms[excepted_form].add(pos)

    for pos in _POS_LIST:
        substitutions = _wordnet.MORPHOLOGICAL_SUBSTITUTIONS[pos]
        for lemma in _wordnet.all_lemma_names(pos=pos):
            lemma = lemma.replace('_', ' ')
            all_inflected_forms[lemma].add(pos)

            form = lemma
            if pos == _wordnet.NOUN and form.endswith('ful'):
                suffix = 'ful'
                form = form[:-3]  # len('ful')
            else:
                suffix = ''
            for new_suffix, old_suffix in substitutions:
                if form.endswith(old_suffix) or old_suffix == '':
                    if old_suffix == '':
                        inflected_form = form + new_suffix
                    else:
                        inflected_form = form[:-len(old_suffix)] + new_suffix
                    inflected_form += suffix
                    all_inflected_forms[inflected_form].add(pos)
    inflected_form_to_lemma = {}
    for inflected_form, pos_set in all_inflected_forms.iteritems():
        lemma = _lemmatize_form_with_wordnet(inflected_form, pos_set)
        inflected_form_to_lemma[inflected_form] = lemma.replace('_', ' ')
    return inflected_form_to_lemma


_INFLECTED_FORM_TO_LEMMA = _construct_inflected_form_to_lemma_dictionary()


def lemmatize_with_dict(form):
    try:
        return _INFLECTED_FORM_TO_LEMMA[form.lower().replace(' ', '_')]
    except KeyError:
        pass
    return form.lower()


def _test():
    test_forms = ('media', 'playing', 'player', 'possesses', 'sung', 'became',
                  'begun', 'fallen', 'men', 'buses', 'initial', 'initialization')
    print 'original\tstemming\twordnet_lemmatizer\tlemmatize_with_dict'
    for form in test_forms:
        print ('{0}\t{1}\t{2}\t{3}').format(form,
                                            stem_form(form),
                                            lemmatize_with_wordnet(form),
                                            lemmatize_with_dict(form))


if __name__ == '__main__':
    _test()

'''
original        stemming   wordnet_lemmatizer   lemmatize_with_dict
media           media      medium               medium
playing         play       playing              playing
player          player     player               player
possesses       possess    posse                possess
sung            sung       sung                 sung
became          becam      become               become
begun           begun      begin                begin
fallen          fallen     fall                 fall
men             men        man                  man
buses           buse       bus                  bus
initial         initi      initial              initial
initialization  initi      initialization       initialization
'''

nltkのWordNetLemmatizerの動作は、入力語句に対して以下の手順で見出し語化を行っているようです。

  1. 入力語句が例外リストに載っていないかどうかチェックする。載っていれば別途処理する。
  2. 末尾置換ルールを用いて入力語句の末尾を置換する。
  3. 辞書の見出し語に語句が存在しているかどうかをチェックする。
  4. 末尾置換ルールが無くなるまで手順2.と3.を繰り返す。

手順1.の例外リストとは、主に不規則変化(sing-sang-sungなど)を解決するための手順のようです。

手順2.と手順3.では、あらかじめ用意された末尾置換ルールを使用します。

例えば入力語句が名詞であり、xesで終わっている場合、末尾からxesを取り除き、代わりにxを追加する。その後、置換した単語が辞書の見出し語にあるかどうかをチェックする。例えば入力語句がboxesであるとき、末尾のxesをxに置換しboxとし、その後boxが辞書の見出し語にあるかどうかチェックする。

ソースコードを読む限り、nltkのWordNetLemmatizerは本家WordNetのC言語実装と同様の手順で見出し語化を行っているらしい。

末尾の置換、検索、を繰り返しているので実行速度が遅い。

そこで、これら例外リストと置換ルールを使用して、WordNetLemmatizerが処理できる語句をすべて生成する。

それらWordNetLemmatizerが処理できる語句をキーとし、それらの見出し語を値とする辞書(_INFLECTED_FORM_TO_LEMMA)を作成した。

{'boxes': 'box', 'box': 'box', ..., 'media': 'medium', 'medium': 'medium', ...}のような活用形がキーであり、見出し語が値である辞書。

実行速度テスト

Page not found - American National Corpus Legal Law Language Medical Malpracticeから抽出した16,814,123個の英単語(296,528種類)に対して、見出し語化にかかる時間を測った。

nltkのWordNetLemmatizerによる見出し語化(lemmatize_with_wordnet)では3583秒(およそ1時間)、

nltkのWordNetLemmatizerによる見出し語化(lemmatize_with_wordnet)の入出力をキャッシュした場合では80秒、

今回作成した作成した辞書を使用した見出し語化(lemmatize_with_dict)では20秒、

となった。結局入出力をキャッシュした場合と大差無い結果になった。

しかし、入出力をキャッシュする場合、WordNetに登録されていない単語や固有名詞などが入力されるたび、キャッシュのサイズが大きくなる。

その点、今回作成した辞書のサイズは固定されているので、メモリ消費量の増加などを気にしなくて良い。

今回作成した辞書にも問題点がある。今回作成した辞書では、入力語句から出力が一意に決まるが、通常は一意には決まらない。例えば、betterの見出し語はwellかgoodかは品詞を用いない限り決めにくい。

2011-08-06

pythonによる文字列の正規化

| 00:31 | pythonによる文字列の正規化を含むブックマーク pythonによる文字列の正規化のブックマークコメント

テキストマイニングなどを行うためには文書、文、単語などの文字列の正規化が重要です。

単語の大文字小文字の統一、半角全角の統一などをする必要があります。

文字列の正規化のために利用しているpythonコードを以下に書いておきます。

今後増える可能性もあります。

実行環境

Ubuntu 10.04 64ビット

python 2.6.5

unicode型に変換する

def unicode_ignore_invalid_char(text):
    if isinstance(text, str):
        return text.decode('utf-8', 'ignore')
    return text

変換不能な文字列を無視してstr型からunicode型に変換する。

str型に変換する

def str_ignore_invalid_char(text):
    if isinstance(text, unicode):
        return text.encode('utf-8', 'ignore')
    return text

変換不能な文字列を無視してunicode型からstr型に変換する。

入出力の文字列型を統一する

from functools import wraps

def consistent_texttype(function):
    @wraps(function)
    def _consistent_texttype(*args, **kwargs):
        assert(1 <= len(args))
        input_text = args[0]
        is_unicode = False
        if isinstance(input_text, unicode):
            is_unicode = True
        elif not isinstance(input_text, str):
            is_unicode = isinstance(input_text[0], unicode)  # for collections
        output_text = function(*args, **kwargs)
        if isinstance(output_text, unicode) or isinstance(output_text, str):
            if is_unicode:
                return unicode_ignore_invalid_char(output_text)
            return str_ignore_invalid_char(output_text)
        if is_unicode:
            return map(unicode_ignore_invalid_char, output_text)
        return map(str_ignore_invalid_char, output_text)
    return _consistent_texttype

入力文字列がstr型であるとき出力文字列もstr型にし、入力文字列がunicode型であるとき出力文字列もunicode型にするデコレータ。

unicodeを正規化する

import unicodedata

@consistent_texttype
def normalize_unicode(text, form='NFKC'):
    assert(form in ('NFC', 'NFKC', 'NFD', 'NFKD'))
    unicode_text = unicode_ignore_invalid_char(text)
    normalized_text = unicodedata.normalize(form, unicode_text)
    return normalized_text

半角カタカナを全角カタカナに変換したりする。

例えば呂鬟據璽検ハンカクカナをハンカクカナに変換する。

HTMLエンティティを変換する

from BeautifulSoup import BeautifulSoup

@consistent_texttype
def unescape_entities_with_beautifulsoup(htmltext, prettify=False):
    soup = BeautifulSoup(htmltext, convertEntities=BeautifulSoup.HTML_ENTITIES)
    if prettify:
        return soup.prettify()
    return soup.__repr__()

BeautifulSoupを利用してHTMLエンティティを変換する。

例えば&gt;を>に変換する。

from BeautifulSoup import BeautifulStoneSoup

@consistent_texttype
def unescape_entities_with_beautifulstonesoup(htmltext, prettify=False):
    soup = BeautifulStoneSoup(htmltext,
                              convertEntities=BeautifulStoneSoup.HTML_ENTITIES)
    if prettify:
        return soup.prettify()
    return soup.__repr__()

BeautifulStoneSoupを利用してHTMLエンティティを変換する。

BeautifulSoupを利用した場合と同じかもしれない。

from htmlentitydefs import name2codepoint
import re

# derived from BeautifulSoup
# __author__ = "Leonard Richardson (leonardr@segfault.org)"
# __version__ = "3.1.0.1"
# __copyright__ = "Copyright (c) 2004-2009 Leonard Richardson"
# __license__ = "New-style BSD"
def _unescape_entity(match):
    x = match.group(1)
    if x in name2codepoint:
        return unichr(name2codepoint[x])
    elif 0 < len(x) and x[0] == '#':
        if 1 < len(x) and x[1] == 'x':
            return unichr(int(x[2:], 16))
        return unichr(int(x[1:]))
    return u'&{0};'.format(x)


@consistent_texttype
def unescape_entities(htmltext):
    unicode_htmltext = unicode_ignore_invalid_char(htmltext)
    unescaped_text = re.sub(u'&(#\d+|#x[0-9a-fA-F]+|\w+);',
                            _unescape_entity, unicode_htmltext)
    assert(isinstance(unescaped_text, unicode))
    return unescaped_text

BeautifulSoupのHTMLエンティティ変換部分を抽出し、少し変更を加えたもの。

HTMLエンティティ変換のためだけにBeautifulSoupを利用するのは高価すぎると考えるときはこちらを利用する。

BeautifulSoupはNew-style BSDライセンスです。

語幹を抽出する(ステミング)

import nltk

@consistent_texttype
def stem_term(term, porter=True):
    if porter:
        return nltk.PorterStemmer().stem(term)
    return nltk.LancasterStemmer().stem(term)

英語用。例えばinitial, initializeをinitiにする。

見出し語化・レンマ化(lemmatization)

import nltk
from nltk.corpus import wordnet

@consistent_texttype
def lemmatize_term(term, pos=None):
    if pos is None:
        synsets = wordnet.synsets(term)
        if not synsets:
            return term
        pos = synsets[0].pos
        if pos == wordnet.ADJ_SAT:
            pos = wordnet.ADJ
    assert(pos in (wordnet.NOUN, wordnet.VERB, wordnet.ADJ, wordnet.ADV))
    return nltk.WordNetLemmatizer().lemmatize(term, pos=pos)

英語用。WordNetを用いて単語の見出し語化を行う。

例えばis, areをbeに、potatosをpotatoにする。

品詞(pos)の指定がなければsynsetsのうち、一番最初に現れる品詞を使用する。

小文字にする

text.lower()

もしくは、

import string

def lower_text(text):
    return string.lower(text)

大文字にする

text.upper()

もしくは、

import string

def upper_text(text):
    return string.upper(text)

先頭のみ大文字にする

text.capitalize()

もしくは、

import string

def capitalize_text(text):
    return string.capitalize(text)

参考サイト

ほんじゃら堂 - ほんじゃら堂

参考文献

入門 自然言語処理

入門 自然言語処理

2011-07-22

nkf python インターフェースのインストール

| 22:49 | nkf python インターフェースのインストールを含むブックマーク nkf python インターフェースのインストールのブックマークコメント

環境

  • Ubuntu 10.04 32ビット
  • python 2.6.5

インストール方法

$ mkdir temp  # 作業用ディレクトリの作成
$ cd temp
# http://sourceforge.jp/projects/nkf/ から nkf-2.1.1.tar.gz をダウンロード
temp$ tar zxvf nkf-2.1.1.tar.gz
temp$ cd nkf-2.1.1/

temp/nkf-2.1.1$ wget ftp://city.plala.jp:1221/NkfPython/NKF_python20090602.tgz
temp/nkf-2.1.1$ tar zxvf NKF_python20090602.tgz
temp/nkf-2.1.1$ cd NKF.python/
temp/nkf-2.1.1/NKF.python$ sudo python setup.py install
# Python.h: No such file or directory と表示された場合は、以下を実行する
# sudo aptitude install python-dev
temp/nkf-2.1.1/NKF.python$ cd ../../../
$ sudo rm -rf temp

使用方法

import nkf
flag = '-w'
output = nkf.nkf(flag, input_text)

input_code = nkf.guess(input_text)

参考リンク

no title

nkf for pythonの入れ方と使い方 - ふにゃるん

2011-05-28

Pythonにおける並行処理について

| 23:47 | Pythonにおける並行処理についてを含むブックマーク Pythonにおける並行処理についてのブックマークコメント

気になったのでPythonのGIL(Global Interpreter Lock)が並行処理にどの程度影響するかについて少し実験しました。

はじめに

まず、「並行」処理と「並列」処理という言葉を区別する必要があります。下記参考文献の「並行コンピュータ技法」によると、

 システムが複数の動作を同時に実行状態(in progress)に保てる機能を備えている場合を並行(concurrent)と言い、
複数の動作を同時に実行できる場合を並列(parallel)と言います。
 重要な概念、違いは「実行状態」という点です。
...中略...
 「並行」は「並列」を含有します。

だそうです。同書によると、1つのCPUコアが2つのスレッドを切り替えながら処理する場合は「並行」処理に含まれるようです。「並列」処理では複数のCPUコアが必須で、複数のスレッドが複数のCPUコアにより同時に実行される事を「並列」処理と言うようです。

目指すべきは「並行」処理ではなく「並列」処理な気がします。

テスト環境

  • Intel Core i7-920 Processor (2.66 GHz × 8)
  • Memory 9GB
  • Ubuntu Lucid 10.04 64bit
  • Python 2.6.5

テストコード

1. 逐次処理でのCPU負荷の大きい処理

# sequential_cpu.py


def _cpu_bound_work():
    i = 0
    while i < 100000000:
        i += 1


if __name__ == '__main__':
    for _ in xrange(8):
        _cpu_bound_work()

2. threadingでのCPU負荷の大きい処理

# threading_cpu.py

import threading


def _cpu_bound_work():
    i = 0
    while i < 100000000:
        i += 1


class TestThread(threading.Thread):
    def run(self):
        _cpu_bound_work()


if __name__ == '__main__':
    mainthread = threading.currentThread()
    for _ in xrange(8):
        thread = TestThread()
        thread.start()
    for thread in threading.enumerate():
        if mainthread != thread:
            thread.join()

3. multiprocessingによるCPU負荷の大きい処理

# multiprocessing_cpu.py

import multiprocessing


def _cpu_bound_work():
    i = 0
    while i < 100000000:
        i += 1


class TestProcess(multiprocessing.Process):
    def run(self):
        _cpu_bound_work()


if __name__ == '__main__':
    for _ in xrange(8):
        process = TestProcess()
        process.start()
    for process in multiprocessing.active_children():
        process.join()

4. 逐次処理によるIO待ちの大きい処理

# sequential_io.py

import time


def _io_bound_work():
    time.sleep(10.0)  # to simulate i/o bound work


if __name__ == '__main__':
    for _ in xrange(8):
        _io_bound_work()

5. threadingによるIO待ちの大きい処理

# threading_io.py

import threading
import time


def _io_bound_work():
    time.sleep(10.0)  # to simulate i/o bound work


class TestThread(threading.Thread):
    def run(self):
        _io_bound_work()


if __name__ == '__main__':
    mainthread = threading.currentThread()
    for _ in xrange(8):
        thread = TestThread()
        thread.start()
    for thread in threading.enumerate():
        if mainthread != thread:
            thread.join()

6. multiprocessingによるIO待ちの大きい処理

# multiprocessing_io.py

import multiprocessing
import time


def _io_bound_work():
    time.sleep(10.0)  # to simulate i/o bound work


class TestProcess(multiprocessing.Process):
    def run(self):
        _io_bound_work()


if __name__ == '__main__':
    for _ in xrange(8):
        process = TestProcess()
        process.start()
    for process in multiprocessing.active_children():
        process.join()

テスト結果

1. 逐次処理によるCPU負荷の大きい処理

$ time python sequential_cpu.py
real	0m45.265s
user	0m45.230s
sys	0m0.020s

2. threadingによるCPU負荷の大きい処理

$ time python threading_cpu.py 
real	1m8.033s
user	1m7.420s
sys	0m16.930s

3. multiprocessingによるCPU負荷の大きい処理

$ time python multiprocessing_cpu.py 
real	0m10.969s
user	1m24.960s
sys	0m0.040s

4. 逐次処理によるIO待ちの大きい処理

$ time python sequential_io.py 
real	1m20.095s
user	0m0.010s
sys	0m0.010s

5. threadingによるIO待ちの大きい処理

$ time python threading_io.py 
real	0m10.029s
user	0m0.020s
sys	0m0.000s

6. multiprocessingによるIO待ちの大きい処理

$ time python multiprocessing_io.py 
real	0m10.035s
user	0m0.020s
sys	0m0.010s

まとめ

1,4の逐次処理が遅いのは当然として、2のthreadingモジュールを使用してCPU負荷の大きい処理を行った場合の実行速度がかなり遅いです。

pythonのGILの影響で、並列処理ができていない事が原因なのでしょう。3のmultiprocessingモジュールを使用した場合はGILを回避できるようです。

並列処理できないthreadingモジュールを使う意味はあるのでしょうか。少なくとも5のように、IO待ち時間が長い処理を複数回行う場合はthreadingモジュールを使用する意味はあるようです。webページのクローラなどには向いているようです。

やはりthreadingモジュールよりもmultiprocessingモジュールを使用した方がいい気がする。(もしくはos.forkを使用するか)

参考

17.2. multiprocessing ? Process-based parallelism — Python 3.7.0a0 documentation

2.6に新搭載のmultiprocessingを見て俺のPythonがおっきした件 | TRIVIAL TECHNOLOGIES 4 @ats のイクメン日記

Tricorn Labs » Python 2.6 multiprocessing package を触ってみた。 [GIL回避]