第二十四個夏天後

2010年10月22日星期五

dotEPUB - 將網頁轉成 EPUB

今年中也曾想過作這種事，這 dotEPUB 是其中的一個雛型！可以搭配 Firefox 的 bookmarks 的用法，當你瀏覽到某一個網頁時，點選一下 bookmark ，就等同於將網頁 link 送到 dotEPUB，並且 dotEPUB 就回傳一份打包好的 EPUB 檔案，也可以看看下面的示範影片

2010年10月21日星期四

Javascript K-means Clustering

嘗試用 Javascript 寫了 K-means algorithm，在這過程之中，讓我回想起兩年前用 C 寫 Betweenness Centrality 的點滴！偶爾拿來訓練腦袋也不錯！

在這過程之中，發現一件事情，那就是 K-means 原先是想要把一堆資料分成 K 群為目標，那是否有可能收斂時，卻沒有 K 個群呢？這個我在自己的測資中，有發現這個現象，但我不曉得是不是演算法哪邊寫錯了，還是本來就存在這個問題？

黑色代表五筆資料，紅色代表一開始假設的族群中心點

例如原先共有 5 筆資料，以二維平面來說，假設資料全部都縮在角落，然後一開始決定 k=2 時，恰好設定在兩個對角，導致在判斷 5 筆資料要歸屬那個群族時，變成一個是空的，另一個有 5 筆資料，如此下去，很快就收斂，但資料就變成只有一個族群了。解決的方式就是一開始指定群族的位置時，直接指定在實際存在的點上，這樣可以確保每個族群一開始至少有一個點。

程式碼：

try{
        console.log( 'begin' );
}catch(err){
        console = {}
        console.log = function(){}
}

//
// pointer_list = []
// pointer_list[0] = { 'x':x , 'y':y , 'group_index':-1, 'distance':-1 }
//
var pointer_list = new Array();
for( var i=0,cnt=raw_pointer.length ;i<cnt ; i++ )
        pointer_list.push( { 'x':raw_pointer[i]['x'] , 'y':raw_pointer[i]['y'] , 'group_index': -1 , 'distance':-1 } );

var group_cnt = 100;

//
// center = []
// center[0] = { 'group_list':[] , 'x':x , 'y':y }
//
var center = new Array();
for( var i=0 ; i<group_cnt ; ++i )
        center.push( { 'group_list':[] } );

for( var i=0, cnt=pointer_list.length ; i<cnt ; ++i )
{
        var c_index = parseInt( i / ( cnt / group_cnt ) );
        if( center[ c_index ]['x'] == undefined )
        {
                center[ c_index ]['x'] = pointer_list[i]['x'];
                center[ c_index ]['y'] = pointer_list[i]['y'];
                //center[ c_index ]['group_list'].push( i );
                pointer_list[i]['group_index'] = c_index;
                pointer_list[i]['distance'] = 0;
        }
}
console.log( 'group:'+group_cnt+',pointer:'+pointer_list.length );
var wanna_finish = 0;
var run_cnt = 0;
var max_run_cnt = 30;
while( !wanna_finish && run_cnt < max_run_cnt )
{
        wanna_finish = 1;
        for( var i=0, cnt=pointer_list.length ; i<cnt ; ++i )
        {
                for( var j=0; j<group_cnt ; ++j )
                {
                        var diff_x = Math.abs( center[j]['x'] - pointer_list[i]['x'] );
                        var diff_y = Math.abs( center[j]['y'] - pointer_list[i]['y'] );
                        var diff = Math.sqrt( diff_x*diff_x + diff_y*diff_y );
                        if( pointer_list[i]['group_index'] < 0 || pointer_list[i]['distance'] > diff )
                        {
                                pointer_list[i]['group_index'] = j;
                                pointer_list[i]['distance'] = diff;
                        }
                }
                center[ pointer_list[i]['group_index'] ]['group_list'].push( i );
        }
        for( var i=0 ;i<group_cnt ; ++i )
        {

                var cnt = center[i]['group_list'].length;
                var x = 0;
                var y = 0;
                for( var k=0 ; k<cnt ; k++ )
                {
                        x += pointer_list[ center[i]['group_list'][k] ]['x'];
                        y += pointer_list[ center[i]['group_list'][k] ]['y'];
                }
                center[i]['x'] = x/cnt;
                center[i]['y'] = y/cnt;

                if(
                        center[i]['old_x'] == undefined || center[i]['old_y'] == undefined
                        || center[i]['old_x'] != center[i]['x'] || center[i]['old_y'] != center[i]['y']
                 )
                {
                        wanna_finish = 0;
                        center[i]['old_x'] = center[i]['x'];
                        center[i]['old_y'] = center[i]['y'];
                }
                console.log( run_cnt+' @ Group:'+cnt+',center['+i+']:('+center[i]['x']+','+center[i]['y']+')');
        }
        if( !wanna_finish )
        {
                if( run_cnt < max_run_cnt )
                {
                        for( var i=0 ; i<group_cnt ; ++i )
                                center[ i ]['group_list'] = [];
                }
                for( var i=0, cnt=pointer_list.length ; i<cnt ; ++i )
                {
                        pointer_list[i]['group_index'] = -1;
                }
        }
        run_cnt ++;
        console.log( 'WannaFinish:' + wanna_finish + ' @ Run:' + run_cnt );
}

其他資訊：

group_cnt：代表最後的 k 是幾個，此例為 100 個

max_run_cnt：一種額外的終止條件，避免 k-means 找太久，此例為 30 次

center：array list，記錄找出來的族群資訊，分別有 x, y 座標，以及 group_list 是 array list，記錄 pointer 在 pointer_list 的 index 位置

pointer_list：array list，記錄 x,y 座標，以及所屬的 group (記錄 index) 和與該 group 中心點的距離

Cross-domain Ajax Query

無聊玩了一下 Ajax Query，在 http://localhost/ 呼叫 htt://www.example.com/test.php 取得資料，過程中用 Firebug 查看網路跟 Javascript，很奇妙地是回傳 200 OK 但又被打個 X ，一直搞不太懂為啥會這樣，結果過了三十分鐘後我才想起來！這就是 cross-domain 的 request 問題！也就是使用 Javascript 在 A site 去 Query 另一個 domain, B site, 的問題。

說真的我都還沒解過，只知道曾聽人說可以用 callbacok function 來解，但怎樣解？我不知道。昨晚嘗試使用，才發現 callback function 是搭配 JSON 格式，這類的專有名詞是 JSONP，全名是 JSON with padding，細節可以在 Wikipedia - JSON 查看。

舉一個範例

假設在 A domain 下，進行 Ajax Query，查詢 B domain 的資料，如 http://b.domain/test.php，並且 http://b.domain/test.php 支援 JSON 和 JSONP 的使用

假設使用 http://b.domain/test.php?callback=my_func 時，即啟動 JSONP 的方式，而不加 callback 參數時，僅 JSON 格式的回傳

如果沒有加 callback 參數時，http://b.domain/test.php，那回傳的資料可能是：

{'x':1,'y':2}

若加上 callback=my_func 時，http://b.domain/test.php?callback=my_func，則回傳

my_func({'x':1,'y':2})

而這種透過 callback 的使用方式：

新增一個 function 名為 my_func

使用動態新增 script 的方式

範例：

<html>
   <head>
       <meta http-equiv="content-type" content="text/html; charset=UTF-8"/>
       <title>Use JSONP</title>
       <script type="text/javascript">
           function initialize()
           {
               var action_url = 'http://b.domain/test.php?callback=my_func';
               var script = document.createElement("script");
               script.setAttribute("src",action_url);
               script.setAttribute("type","text/javascript");
               document.body.appendChild(script);
           }
           function my_func(data)
           {
               console.log( data );
               //alert(data);
           }
       </script>
   </head>
   <body onload="initialize()">
   </body>
</html>

如此一來，在 my_func 中，就會收到 {'x':1,'y':2} 的資訊，並且可以用 data['x'] 和 data['y'] 來取值囉！

2010年10月19日星期二

用 Python 寫 CGI

參考資料：

cgi — Common Gateway Interface support

Penzilla.net's Python Tutorial - CGI Scripting Basics

Embedding Python In Apache2 With mod_python (Debian Etch)

Appending to Your Python Path

之前用 Python 寫了一隻 tool，然後希望透過 web 來傳參數使用，於是就想透過 Python 實做 CGI 好了！在此不聊 Web Server 的設定，假設只需在 ~/public_html/cgi-bin 或 ~/public_html/cgi-bin 還是 ~/public_html/ 內擺放此 cgi 就行了！

注意事項：

該檔案要給予執行權限，如 chmod 755

從 CGI 呼叫 tools 做完在透過 stdout 接收，很可能會碰到編碼問題
- f = popen( 'tools arg' , 'rb' )
  d = f.read()
  f.close()
  
  print d
- 解法就是，改用 import 的方式，使用其 function 回傳的。我猜可能是因為 popen 可能是使用執行者的環境變數，跟你自己執行時不一樣。

如果 Python 版本不符合需求，那就自己編吧！

範例(my.cgi)：

#!/home/user/tarball/bin/python
# -*- coding: utf-8 -*-
import cgitb
cgitb.enable()

import cgi

print "Content-Type: text/html"     # HTML is following
print                               # blank line, end of headers

form = cgi.FieldStorage()

if 'pattern' in form:
        pattern = form['pattern'].value
        page = form['page'].value if 'page' in form and int( form['page'].value ) > 0 else 1

        import sys
        sys.path.append( "/home/user/mypylib" )
        from mylibs import *
        x = online_query( query=pattern , page=int(page) )
        print x.encode( 'utf-8' )

首先一開始是使用 /home/user/tarball/bin/python 自己編的 Python，理由純粹只是要用 PycURL 而已，可以參考安裝 cURL、Python 和 PycURL @ Ubuntu Server。

接著則是 CGI 的標準用法，開頭要印出 "Content-Type: text/html\n\n" 的訊息，以 C 語言就是：

#include <stdio.h>
#include <stdlib.h>

int main()
{
printf( "Content-Type: text/html\n\n" );
return 0;
}

然後，則是使用 cgi.FieldStorage() ，就能得知 POST/GET 的資訊，此例是 pattern 跟 page 這兩個參數。

最後，則是使用自己的寫的 python code，全寫在 /home/user/mypylib/mylibs.py 裡，需要透過 sys.path.append 增加搜尋的路徑，而 online_query 回傳的是 UTF-8 的資料，因此輸出時，需要在 encode 一下。

以上算是一個很簡單的筆記吧

2010年10月18日星期一

OPDS Catalog, OpenSearch, and Stanza

想要產生 OPDS Catalog 以及提供 OpenSearch 的功能，如圖右上角，讓 Stanza 這個閱讀器可以看得懂，但 OPDS Catalog 1.0 的規格還沒有完全支援（今天是 2010/10/18，Stanza 軟體是 3.0.3 版本），因此像是一些 link 中 rel 這個 attribute ，填入 OPDS Catalog 1.0 的規格後，也會導致 Stanza 讀不出來，之前測試的結果，把 rel 留空白應該可以。

最近想要試的是 OpenSearch，在 OPDS Catalog 1.0 中 7.5 裡有的定義：

7.5. Search

An OPDS Catalog MAY provide a search facility through an [OpenSearch] description document. Links to [OpenSearch] description documents MUST use the “search” relation value and the “application/opensearchdescription+xml” media type as defined in the “Autodiscovery” section of the [OpenSearch] specification.

<link rel="search"
      href="search.xml"
      type="application/opensearchdescription+xml"/>

In an [OpenSearch] description document, the search interface SHOULD use the media type associated to OPDS Catalogs:

<Url type="application/atom+xml;profile=opds-catalog"
     template="http://example.com/search?q={searchTerms}" />

OPDS Catalog Feed Documents MAY include elements from the [OpenSearch] namespace such as “opensearch:totalResults” or “opensearch:itemsPerPage” in [OpenSearch] responses.

只是我嘗試的結果，那個 type 沒被認出來，倒是直接用 type="application/atom+xml" 就可以看到，以 Feedbooks Catalog 為例：

所以，可以很偷懶乾脆一起寫：

至於 opensearch.xml 描述檔該怎樣寫，也可以直接參考 Feedbooks OpenSearch，甚至我還在想，乾脆全部導到 Feedbooks 也不錯

7.5. Search

An OPDS Catalog MAY provide a search facility through an [OpenSearch] description document. Links to [OpenSearch]
description documents MUST use the “search” relation value and the
“application/opensearchdescription+xml” media type as defined in the
“Autodiscovery” section of the [OpenSearch] specification.

<link rel="search"
      href="search.xml"
      type="application/opensearchdescription+xml"/>

In an [OpenSearch] description document, the search interface SHOULD use the media type associated to OPDS Catalogs:

<Url type="application/atom+xml;profile=opds-catalog"
     template="http://example.com/search?q={searchTerms}" />

OPDS Catalog Feed Documents MAY include elements from the [OpenSearch] namespace such as “opensearch:totalResults” or “opensearch:itemsPerPage” in [OpenSearch] responses.

訂閱：文章 (Atom)

2010年10月22日 星期五