TIM Labs

2017年7月アーカイブ

ちょっと代数も勉強しておくべきかと思い、群論について読んでいたら、「置換群とゲーム」という節があった。
例として、15並べ、Bubikキューブ、 Ten Billion、あみだくじが紹介されていたので、ゲームというよりパズルなのだが、まあいい。

さて、あみだくじだが、どのようなあみだくじをつくったことがあるだろうか。
縦棒が何本かあり、水平線で2つの縦棒を結ぶ線を書き加えるのが一般的だろうか。

しかし、そういうのは面白くない。
やはり、あみだくじは阿弥陀如来に由来していて、人間にはあみだくじはちょっと見ても分からないが、阿弥陀如来には一瞬で分かるはずである。
なので、阿弥陀如来にとっても手ごたえがあると思えそうな、もっと複雑なあみだくじを作ってみた。

amida-4.jpg
こういう「あみだくじ」を昔から作っているのだが、ちゃんとあみだくじとして機能しなかったことはない。
ちゃんと機能するとは、上のn箇所と下のn箇所はちゃんと1対1対応するということだ。
上のあみだの場合、ABCDのどれも下のどこかにたどり着き、かつ必ず異なるところにたどり着く。
つまり、出口での順番は、ABCDの置換に必ずなる。

証明については書くのが面倒なので省略するが、通常のあみだくじの証明と同じで、鳩ノ巣原理を用いればできる(はず)。


いま世の中に存在するあみだくじアプリは単純過ぎて面白味がない。
ぜひ、このような線の入れ方をする「あみだくじジェネレータ」を作ってみよう。


978-4-87311-778-2.jpeg退屈なことはPythonにやらせよう
Al Sweigart 著
相川 愛三 訳
A5判 618ページ
定価 3700円(本体)
ISBN978-4-87311-778-2
オライリー・ジャパン

オライリー 本書紹介・関連ファイルなど

原書: Automate the Boring Stuff with Python

本書は、2部構成になっている。

I 部  Pythonプログラミングの基礎

1章から6章までで、152ページある。
この部分は、本当にPythonプログラミングの基礎的な説明である。
まったくPythonを知らない、さらにプログラミングも知らない人が対象の説明である。
なので、多くの人は、第?部はパスして良い。

第 II 部 処理の自動化

7章から18章までで、512ページまである。
12章で、512-152 = 360ページなので、平均1章30ページ。
各章ごとに1つの技術分野を紹介する感じで、その技術を利用すると横着ができるという風に話が進んでいく。


7章 正規表現、8章 ファイルの読み書き、9章 ファイル管理、10章 デバッグ、11章 Webスクレイピング、12章 Excel、13章 PDF、14章 CVS/JSON、15章 時間制御、16章 メール、17章 画像処理、 18章 GUI
と言う感じで多岐にわたるのだが、1つについて30ページしか説明がないので、導入、概要の説明で終っている。

Pythonの基本部分はたいして大きくないので習得は容易と思うが、膨大なモジュールが存在し、一部のモジュール、たとえばNumPyなどは、標準拡張という感じで使うのが当たり前のようになっているが、それ以外については、必要になったら調べて使うという感じであろう。

本書は、できるだけ様々な分野について、横着する方法という切り口でPythonのモジュールを紹介した総合案内パンフレットみたいな感じである。
なので、本書を読んだだけではモジュールがどんなものかおぼろげにイメージが湧く程度であり、これをスタート地点として紹介されている各モジュールのサイトなどを頼りに本格的に勉強して使えるようになるだろう。


このところ、とても忙しくなって、書くペースが落ちてしまった。
というのも、R&D部門が新しいオフィスに移動作業中だからなのだ。
真新しいビルが用意され、そのビルの一室に入ることになった。

場所は、なんと、電気通信大学の100周年記念キャンパスの中になった。
キャンパス名に100周年記念キャンパスということで、どこか東京の郊外、不便なところにキャンパスが出来たわけではなく、元のキャンパスと道一つ(甲州街道)隔てた場所にある。

電気通信大学(電通大)については、いまさら説明することもないだろう。 Wikipediaで調べるのも良いと思う。
アンリツの前進である安中電機製作所内に1916年にできた無線講習所が本来の起源だと思うが、公的機関としてスタートしてから100年を100周年ということになっている。
無線が一気に世界の注目を集めたのはタイタニック号の沈没により、無線の重要性、情報通信の重要性が認識されたのだった。
それ以来、無線&通信はどんどん進歩し、今のインターネット時代を支えている技術である。
有線の通信だけだったら、インターネットはここまで幅広く使われることはなかっただろう。
歴史的なことは、電気通信大学の同窓会である目黒会ウェブマガジンの記事が詳しい。

ということで、ITの根幹の技術をずっと担ってきた電通大の中に研究拠点を設けて、新しいことができるかなと思っているところだ。

DSCN0481 (450x600).jpg DSCN0473 (600x450).jpg
キャンパス、建物はこんな感じで、ずいぶん立派なんだ。
2017年春に竣工し、この春から使い出したので、ピカピカである。

新しいだけではなく、実は、色々面白い仕掛けというか、いろいろあるのだが、今回は1つだけ紹介しよう。

ネット上でも話題になっている通り、ここの1階には電子パーツを売る24時間営業のコンビニ・セブンイレブンが入っている。

DSCN0480 (600x450).jpg DSCN0267 (450x600).jpg
さすがに電通大内のコンビニだけあって、工具やテスター、パーツなどが置かれているコーナーがあるのだ。
調布、府中、、、などで夜に電子部品が欲しいとなったら、秋葉原まで行かなくても、調布で入手可能なのだ。
甲州街道に面しているので、とても分かりやすいと思う。

実は、これだけではなかったのだが、それについては別の機会に紹介しよう。


Pythonには、様々なモジュールがある。
それを1つずつ毎週紹介すると何年も話が持ちそうだが、こちらの気力が持ちそうにない。実際、それほどたくさんのモジュールが存在するのだ。

Excelをいじるためのモジュールもいくつかあるようなのだが、今回はopenpyxlを紹介する。

openpyxl Documentationという立派なドキュメントがある。
英語のドキュメントで、311ページもあるので、真面目に読むのは大変だ。

A Python library to read/write Excel 2010 xlsx/xlsm filesがもう少し楽そうなドキュメントである。

実際には、東邦大学理学部のPythonからExcelファイルをいじるopenpyxl
あたりを出発点としてあれこれ探して次のプログラムをでっち上げただけである。


#!/usr/bin/env python

from PIL import Image, ImageColor
import openpyxl
from openpyxl.styles import PatternFill
from openpyxl.utils import get_column_letter

def coltostr(coltuple):
    r, g, b = coltuple
    a = 255
    return format(((a*256+r)*256+g)*256+b, '08X')

def image2excel(imagefile,excelfile,sheetname):
    im = Image.open(imagefile)
    width, height = im.size
    
    wb = openpyxl.load_workbook(excelfile)
    sheet = wb.get_sheet_by_name(sheetname)
    
    # セルサイズの調整
    for x in range(0,width):
        sheet.column_dimensions[get_column_letter(x+1)].width = 1
    for y in range(0,height):
        sheet.row_dimensions[y+1].height = 5.7
    
    # 画像ファイル ⇒ Excelワークシート
    for x in range(0,width):
        for y in range(0,height):
            colstr = coltostr(im.getpixel((x,y)))
            cell = sheet.cell(row=y+1, column=x+1)
            cell.fill = PatternFill(fill_type='solid',fgColor=colstr)
    
    wb.save(excelfile)
    im.close()

image2excel("アンパン.jpg","アンパン.xlsx","アンパン")
暑くなってきて頭が回らない。
ということで、カフェに逃げ込んで、こんなものを食べながら、どうでも良いことを考えた。

ampan300.pngすると、ついこんなイメージが頭に浮かんでしまった。

アンパンonExcel.png
画像の周りにいっぱい罫線ができている。
つまり、これは、Excel、OpenOfficeのCalcとか、その類だ。

ということで、Excelの各セルに、元のイメージファイルの画素を対応させてみよう。

アンパンの画像は、元は300x300だったのだが、いかにもセルに色を付けた感が出るように、64x64とそれなりに粗く(小さく)した。

アンパン.jpgさて、どうやって描こうか。
Excelだから当然VBAのプログラムを組めばよい、と思いたいが、VBAのプログラムは作りたくない。
どうしよう。

このところ、ずっとPythonをいじっているのだが、星の数ほどあるPythonのモジュールの中には、Excelのモジュールも当然あるはずだ、きっとある。

ということで、次回までに作ってみよう。
なお、アンパンは美味しかった。


NLTK (313x400).jpg

題名:入門自然言語処理

Natural Language Processing with Python
Analyzing Text with the Natural Language Toolkit

Steven Bird、Ewan Klein、Edward Loper 著、萩原 正人、中山 敬広、水野 貴明 訳
大型本、592項、本体3800円

2010年11月8日 発行

オライリー・ジャパン

Natural Language Toolkit

Natural Language Processing with Python (書籍)


人工知能、機械学習、ディープラーニングというと、画像処理関連がやたらに多いが、それ以外の分野もある。
その中でも、自然言語処理は非常に大きな、そして重要な分野である。

ことばをコンピュータで扱おうとすると、画像とは違った、あれこれ面倒なことがいっぱいある。
言葉を対象としている人工知能の本の場合、自然言語処理の部分の説明は非常に短く、いきなり読もうとしても用語が分からない、どんなツールがあるのか、サンプルデータがあるのか、だいたい分からないことだらけになる。

自然言語処理を対象としてAI関連の本で、自著で延々と説明するのは大変なので、読むべき自然言語処理の本が挙げられていることが多いが、そのなかで必ずといってよいくらい紹介されるのが、この『入門自然言語処理』である。

この本は、Pythonを使って、自然言語処理の基本を紹介している。
といっても、原書は英語で、日本語の場合どうなんだろうと思ったら、最終章が「Pythonによる日本語自然言語処理」となっている。

さて、この本、発行が2010年とかなり古く、原書は、2009年になっている。
そのため、Python3ではない。

この本で使われているのが、NLTK(Natural Language Toolkit)という、Pythonのツールキットである。
このツールキットは、アメリカのアイビーリーグの1つ、ペンシルベニア大学にて作られたものだ。


以上は前置きで、これから肝心なことを紹介しよう。

本書はとても古いのだが、Natural Language Toolkit のサイトでは、今も更新が続いており、ちゃんとPython 3 対応になっている。

ソフトだけでなく、書籍の方も、ネット上はちょこちょこと更新されているように見える。
さらに、これらは、オープンであり、自由に使えるので、とても助かる。

本は、文字だけでなく、プログラムや実行例が多数載っており、これらを自身のPython上で確かめるには、オンラインの書籍からコピペをいっぱいすることで、確認ペースも上昇する。

オンライン版は文章の部分は英語であるが、肝心なのはプログラム、実行例などであろう。
それほど大きくは変わっていないようなので、英語をどうしても読みたくない場合には、英語版を見ながら、文章を読むときだけ翻訳書に頼るという方法もある。

でも、結局面倒になるので、全部オンラインだけで済ませるのが効率がよく、かつお金もかからない。

英語を勉強するのではなく、英語で勉強しよう。
金もかからず、技術も身に付き、情報はいっぱい集まる。


前回、SATについて簡単過ぎる紹介をした。
もっと詳しく知りたい場合は、神戸大学情報基盤センターの田村教授の資料 情報基礎特論:制約プログラミング入門 (PDF, 98ページ)が相当詳しい。

SATには、制御文がない。つまり、if-else, while, for,...などの文が存在しない。
存在するのは、定義文、条件文だけである。
つまり、定義の範囲で、条件を全て満たす変数の値を探すだけである。
もちろん、条件を満たす解が1組以上ある場合もあるが、解の個数を、解なし(0)、解1(ユニーク解)、複数解(多重解)の区別もしてくれたりする。

さて、こんなSATは、どうやって問題を解いているだろうか。
結論から言うと、最終的には虱潰しをやっているだけである。
しかし、途中で検索を省略できる箇所、早々に決まってしまう箇所、選択肢が非常に狭められる場合などを考慮し、相当高速に虱潰しができるようになっている。

それでも、さすがに25x25のナンプレを調べつくすのには相当の時間がかかると予想した。

神戸大学の田村教授に16x16の問題を解いてもらったときの時間が
real    0m3.311s
user    0m5.244s
sys     0m0.280s
20x20の問題を解いてもらったときの時間が
real    0m5.079s
user    0m7.312s
sys     0m0.600s
であった。
組み合わせ問題なので、サイズが大きくなると急激に時間がかかるようになるものだが、マスの総数の増加割合よりやや時間がかかる程度であった。 これなら、25x25も解かれてしまうかも知れない。
25x25のヒント数の少ない問題を作るのは、非常に困難で、コンピュータリソースをやたらに食う。

25x25の問題を送ったら、1時間余したら返信があり、なんと
real    0m17.693s
user    0m21.312s
sys     0m0.332s
という短い時間の間に解かれてしまったのだった。 最近のSATの性能向上には目を見張るものがある。 SATは、明示的な、手筋のような解き方をプログラミングする必要がないので、解法アルゴリズムがまったく思いつかないような場合に有効な方法だ。 このまま高性能化が進むと、アルゴリズムを考えず、とりあえずSATに探させれば良い、と考えるようになりそうだ。

いや、SATの開発者は、効率向上のために、ものすごくアルゴリズムを最適化しているはずだ。

ナンプレ(あるいはSUDOKU)というパズルをご存知だろうか。
通常は、9x9の問題なのだが、つい、25x25の問題を作った者がいる。
問題に最初から示されている数のことをヒントと言い、その個数をヒント数と言うのだが、以下がヒント数146(現在世界最少)の問題である。

+--------------+--------------+--------------+--------------+--------------+
| . 12  .  .  .| .  .  .  .  .| .  .  .  9  .| .  . 15  .  .|22  .  .  .  .|
| .  .  .  .  .| .  9  . 19  .| .  . 10 11  .| .  .  .  .  .| .  .  .  .  .|
| .  4  . 22  .| .  .  .  .  .| .  .  .  .  .| .  . 12  .  .|20 15  1  .  .|
|16  1 20 15  .| .  .  .  .  .| .  .  .  .  .|14  .  4  . 22|12 25  .  .  .|
| .  .  .  .  .| .  7  2 11  .|23  . 19  8  .| .  .  . 13  .| .  .  .  .  .|
+--------------+--------------+--------------+--------------+--------------+
|13  .  8  .  2| .  .  .  .  .| .  .  7 23  6| .  9  . 19 11| .  .  .  .  .|
| .  .  .  . 23| .  .  .  . 16| .  .  .  .  .| .  .  .  .  .| 1  .  .  .  .|
| 7  .  .  . 10| 3  .  .  .  .| .  .  9 19  .| . 13  . 23  .| .  .  .  5  .|
| .  .  .  .  .|15  .  .  . 22| .  .  .  .  .| .  .  .  .  .|25 20  .  .  .|
| .  .  .  .  .|12  . 14  1 25| .  .  .  .  .| .  .  3  .  .|16  4 15  .  .|
+--------------+--------------+--------------+--------------+--------------+
| .  .  .  .  .| . 19  9  .  .| .  . 13  7  .| .  .  .  5  .| .  .  . 23 10|
| . 22  . 25 17| .  .  .  .  .| .  .  .  .  .|12  . 20  .  .| .  .  .  .  .|
| . 20 12 16  .| .  .  .  .  .| .  .  .  . 14|15 22  1  . 25| .  .  .  .  .|
| . 15  .  .  .| . 11  .  .  .| .  .  .  .  .| .  . 16  .  .| .  .  .  9  .|
| .  .  .  1  .| . 10  . 23  .| .  .  .  . 18| .  .  .  .  .| .  .  .  .  8|
+--------------+--------------+--------------+--------------+--------------+
|10  .  .  .  8| . 13  .  5  .| .  .  .  .  .| . 19  . 11 23| .  .  .  6  .|
| .  .  . 17  7| .  .  .  .  .| .  .  .  .  1| .  .  .  .  .| 4 22  .  .  .|
| .  .  .  . 11| . 23  .  .  .| .  .  .  . 20| .  .  .  2  .|14  .  .  .  .|
|19  . 23  .  5| .  8  .  9  .| . 21  .  .  .| . 10  .  7  .| .  .  .  .  .|
| .  3  .  .  .| .  .  .  .  .|25  4  .  . 12| .  .  .  .  .|15  1 16  .  .|
+--------------+--------------+--------------+--------------+--------------+
| .  .  .  .  .| .  .  .  . 15| . 12  .  . 25| 1  . 22  .  .| 3  .  .  .  .|
|23  .  .  . 19| .  2  .  .  .| .  .  .  .  .| .  .  . 10  .| .  .  .  7 11|
| .  .  . 18  .| .  .  .  .  .| . 20  .  .  .| .  .  .  .  .| .  .  .  .  .|
| .  .  .  .  .| .  .  .  .  4|14 15  .  . 22| .  .  .  .  .| .  .  . 10  .|
|11  .  .  .  9| .  .  .  .  .| .  .  .  .  .| .  .  .  .  .| .  .  . 19  .|
+--------------+--------------+--------------+--------------+--------------+
ナンプレの問題を解くプログラムはネット上にゴロゴロ転がっているのだが、大きいサイズに対応したソルバーはなかなか存在しない。
 小さいときには、手筋を実装せず、単に再帰だけでも十分高速に解けるのだが、それではサイズが大きくなると直ぐに破綻するはずだ。

この問題、なかなか解いてくれる人がいない。
ナンプレに限らないのだが、パズルの多くは、限られたルールとヒントから解くのである。
そして、こういう問題のことを、制約充足問題と言う。
日本語での説明は貧弱なので、ぜひ Constraint satisfaction problem を参照されたい。

さて、制約充足問題というと、すぐに思いつくのがSATであろう。
ということで調べると、SATでパズルを解く研究をしている神戸大学情報基盤センターが直ぐに見つかる。

ということで、上の25x25の問題を送ってみた。さて、どうなるだろうか?

このアーカイブについて

このページには、2017年7月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2017年6月です。

次のアーカイブは2017年8月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。