顯示具有 程式 標籤的文章。 顯示所有文章
顯示具有 程式 標籤的文章。 顯示所有文章

2010-01-03

FaceBook處理邀請工具 - Accept Helper

因為國軍online中,久久才能上一次網,所以每次放假都累積一大堆的邀請。FaceBook的處理邀請介面蠻討厭的,都要跳到別頁,所以才做了這個Accept Helper,對我自己是蠻實用的,分享給各位。

簡介

接受邀請小幫手,提供更方便的介面一次處理多個邀請,不會每點一個連結都要離開本頁。

官方網站 http://nerv.appspot.com/fbp#accept_helper

安裝&使用

安裝

接受邀請小幫手 目前版本ver. 0.9.2

IE, FireFox, Opera: 右鍵點選上面這個連結,並選取"加入我的最愛(書籤)",IE會有安全性警告,請無視他

Google Chrome : 直接將上面這個連結拖曳到書籤列(若無書籤列可按Ctrl+B開啟)
這個連結在FaceBook中會被過濾掉內容,請到官方網站安裝。
最初的0.6版接受跟忽略按鈕弄相反了XD,如果現在開起來還是顯示0.6版,請重新安裝。

使用說明

要使用的時候,於Facebook的邀請頁面,直接到書籤(我的最愛)點一下接受邀請小幫手就可以了。

執行成功之後會看到以下畫面

說明:

  • 首先每個邀請的按鈕會被[接受!] [忽略]所取代,您可以直接按這兩個連結來處理邀請。
  • 開啟於選單則可以設定接受邀請之後頁面要顯示的位置,預設的本頁面中會顯示在畫面中那個白色的區塊(看不懂的話,實際使用就會馬上瞭解了),選擇開在本頁面中時可以上下拉動下面的灰槓調整大小。
  • 過濾使用者選單可以讓你依照邀請人只顯示來自那個人的邀請。
  • 接受第一個如字面,就是接受畫面中第一個邀請,同樣 適用於過濾使用者之後。

2009-10-08

Restaurant City 小幫手

這是因為我連續答錯幾題Restaurant City的每日小問題後決定製作的小幫手(怨念充滿)。

主要的功能就只是快速查詢Daily Quiz的問題跟答案而已以。官方網站 : http://nerv.appspot.com/rcp (其實就是這篇blog的內容XD)。

瀏覽器相容性:IE7&8、Firefox、Chrome、Opera。IE6未測不明 。跑很慢的電腦上未測試效果怎樣。

使用的方法有兩種:

Bookmarklet模式(書籤程式)

此模式可以將小幫手安插到Restaurant City的頁面上。
開好Restaurant City之後將下面這串貼到網址列再按下Enter(IE有時怪怪的,可多按幾次enter試試)。或者可以把下面這串當作網址加入書籤(我的最愛),然後在Restaurant City的頁面點選即可。

javascript:(function(){document.body.appendChild(document.createElement('script')).src='http://nerv.appspot.com/js/rcp/main.js';})();


像下面這樣按enter:

成功之後如下圖

在這個模式下會看到原本廣告的部份被清掉用來擺RC Helper。 Restaurant City的上多了重新整理跟隱藏Restaurant的功能的連結,其實不重要,有需要的人再使用就好。

嵌入模式

點選以下網址即可。注意!下面這個網頁會在網頁內新開一個Restaurant City,所以可以將原本開的Restaurant City網頁關掉。

使用方法

當使用上面任意一種方法成功之後,便可在問題出現的時候在keyword輸入關鍵字查尋,為了提高查詢的精準度,一些字會被忽略掉,選最關鍵的字,查詢的時候也不要輸入那些無關緊要的字,通常打一兩個字母答案就會出來了。

2009-10-01

Visual Ansi 釋出原始碼

Visual Ansi (官網 :http://web2.tmu.edu.tw/b101091044/va/ 官網還用學校的空間會不會太窮酸啦 )是自2003年用VB6開發的BBS繪圖軟體,本來我都會趁每年的寒暑之間改bug或加些新功能,可是去年實習根本沒心力去弄,所以最近一次的更新是在遙遠的2007年底。

本來有想趁畢業到當兵前夕再做一次更新,不過因為學了各種更有彈性的語言之後,現在反而覺得VB6寫起來綁手綁腳,加上打電動看動畫花掉太多時間以致....(被拖走),因此決定放棄繼續維護原本的Visual Ansi 。做下這個決定其實還蠻感傷的,算算從開始寫到現在也有六年的時間了,雖然裡面的程式碼醜陋又用了很多奧步,但是看了這麼久也是會有感情的。最近剛好有網友跟我要原始碼說想修改,我就順勢把原始碼放到google code上面供大家下載。

Visual Ansi 原始碼
http://code.google.com/p/visualansi/
語言 : Visual Basic 6
原始碼存取方式:SVN
授權:GPL
有意修改者請mail給我,幫你加入修改成員

其實蠻久以前就有人問我要不要把原始碼放出來,不過因為開始寫得時候對架構沒有規劃,那時候根本沒有想到會開放原始碼,所以不少地方用了一些骯髒的寫法,每年修改的時候,撰寫風格也有所改變,程式內部呈現一種混搭的狀態,這是我一直不敢開放原始碼的原因(引用PCMan作者的比喻 - 開放凌亂的原始碼就跟裸奔一樣XD)。不過現在年紀大了,可能臉皮隨之變厚就不太在意這種事(真的嗎?!!可以裸奔了嗎 (被巴 ),才很乾脆的把原始碼放出來。心裡當然是希望有熱血人士繼續維護,不過就算沒有,當程式範例讓其他人研究一下也不錯啦。

如果有時間的話(電動繼續打下去應該就沒有..),我會想開發web base的Visual Ansi Online或是用python+wxWidgets寫,不過以目前的狀態應該是空想.....快要國軍Online了XD

2009-02-25

Google App Engine準備開始提供收費服務

在Google App Engine 的Blog 發表了"New! Grow your app beyond the free quotas! ", 預計在90天之內開放超出Quota資源的付費資源。

超出Quota的收費是採用多少資源收多少費用的方式,你可以依照預算設定一個支付額度的上限,主要可設定項目只有Outgoing Bandwidth, Incoming Bandwidth, CPU Time, Stored Data, Recipients Emailed這五項。 不過當你啟用付費功能的時候,其他的Quota都會提高許多,詳細的內容可以看更新過後的Quota說明。但是像單檔10MB、資料庫每筆1MB的限制還是不會變。

在宣佈收費方式的同時 Google也決定對免費的Quota做了一些改變

  • CPU Time從46.30 hours/day減少到6.5hours/day
  • 頻寬從 10GB減少到1GB
  • 為了補償,從現在起 儲存容量從500MB增加到1GB


說實在的改很大,改不用錢。這個動作還是為了區隔出付費的使用者,不過我想對大部分的普通使用者影響應該不大,為了維持GAE的營運我認為是可以接受的 。

調低免費Quota也表示從GAE開放到現在,GAE的使用情形沒有google預期的熱絡。大部分的人都是用來建一些中小型網站。

不過之前並沒有付費的機制,只有固定Quota,我想也不會有商業使用者貿然將大型的project建構在GAE上。我認為GAE宣佈開放付費可以看作Google在對商業使用者招手說:「 GAE已經是一個成熟可以賣的產品了,請安心的購買吧!」 (尤其最近Google決定關掉一些服務,總是讓人會有種不信任感,會不會哪天建在GAE上的網站,突然被宣佈要關閉,而且最可怕的是,用它api寫出來的程式幾乎沒辦法直接轉移到其他地方..)

除此之外,GAE目只能使用python作為撰寫的語言(雖然有發表將支援其他語言的計劃,不過目前還是沒看到新的動靜) 也是沒那麼多人用的原因。儘管python的後勢看漲,看看TIOBE的排名 或是用Google Trend比較搜尋的結果,目前的python佔有率仍然比PHP少上許多,況且PHP幾乎都是用在Web上,而Python用在web上還算少數。GEA若推出PHP作為runtime language,想必可以立即吸引許多現有的的技術人力使用GAE。另外最被看好會支援的java來說,個人認為它雖然具有淺力,但是經濟效益還是沒有PHP來的高。主要還是因為使用java的人雖然很多,但是用在server side的比率還是比較少,而這個結構短期內不太可能會有變動。

GAE現在除了限制之外,還有一些沒支援但是對一些網站非常重要的功能,例如在背景執行、訂時執行的程式,不過在最近GAE在blog正式宣佈將會支援這些功能(A roadmap update!) 。

目前把GAE拿來作非玩票性質使用的網站還不多,不過隨著付費服務的開始,相信在今年GAE將會做出許多改變。

2009-01-02

Yahoo Media Player與網路電台 (shoutcast , icecast)

Yahoo Media Player (http://mediaplayer.yahoo.com/)是一個讓你在網頁上放置一個MP3播放器的一個javascript,只要很簡單的步驟就可以讓你blog或網站上的音樂檔連結一點就直接在網頁上播放(方法請看他網站 很簡單)。 這種東西並當然不是第一次出現,但是YMP的特色在於易用性、支援串流還有跨平台。

事實上 他是透過javascript控制一個flash來播放,所以mp3播放的部份可以跨平台。

另外在某些情況下它不只支援mp3,例如在windows上只要你windows media player可以播放的它都能放,例如你有裝ogg plugin 就可以用他撥ogg,不過這種還要收聽者電腦安裝其他東西的功能就顯得比較沒用一點。

我對這東西有興趣的地方在於支援串流以及跨平台的部份,這表示他可以當作一個不錯的網路電台撥放器。

Yahoo Media Player 載入完畢後會自動抓取網頁中所有連結網址(href)中有.mp3的部份,然後將他改成點擊就播放的連結。可是電台的收聽網址通常都不是mp3結尾。我們可以在連結的class加入htrack作為標示,YMP會抓取class有htrack的連結作為播放連結。如下:

<a class="htrack" href=http://xxxx.fff.xxxx:8000/fff>點此收聽</a>

目前大家最常用的shoutcast , icecast這兩個電台server,要使用YMP來收聽電台的話,電台音源必須要是mp3,除非聽眾的電腦有裝ogg plugin(要他電腦的windows media player可以播放ogg才算,其他foobar200, winamp等是內建ogg支援的 )。不過就我的測試,只有icecast的可以向上面的那個方式使用。如果電台是shoutcast的話,直接放"http://xxxx.fff.xxxx:8000","http://xxxx.fff.xxxx:8000/listen.pls"都沒辦法收聽。 在網路上找到的解法就是用http://xxxx.fff.xxxx:8000/;aaa.mp3 (那個aaa是可以隨便替換的),這個方法就是在shoutcast server網址的後面加上 ;(隨便打什麼字).mp3 。


<a class="htrack" href=http://xxxx.fff.xxxx:8000/;listen.mp3>點此收聽</a>
(這裡正常情況下 class="htrack"可以不用加 因為副檔名是mp3)

下面這個是我修改shoutcast server (windows版), 在介面中加入yahoo media player

修改的地方有 (有興趣的也可以用 hex editors自己改)
1. 在header加入:<script type="text/javascript" src="http://mediaplayer.yahoo.com/latest"></script>
2. Listen的連結改成<a class="tn1 htrack" href="./;listen.mp3">Listen</a>
3. header中的charset改成big5
注意:
如果是在開電台的電腦上看(網址是localhost)的話,可能會因為瀏覽器安全性設定的關係造成運作不正常(因為瀏覽器預設通常不能在localhost載入flash)。
下載 Shoutcast Server1.9.8 + Yahoo Media Player + Big5

補充一下一些資源:

Wiki http://yahoomediaplayer.wikia.com/wiki

API Document http://mediaplayer.yahoo.com/api/

2008-08-31

Google App Engine 與 Python 初玩雜唸 (二) ~ 破

開始上工前~

第一件做的是就是下載Google App Engine SDK (當然需要先裝python 2.5 )
就可以在我們的電腦上模擬Google App Engine的服務

安裝和使用方法可以看官網或是網路上都有很多這方面的文章,我就不贅述了

免費的開發工具有許多選擇,例如:

當然還有許多非專門寫python的一些軟體,例如notepad++等。

不過像notepad++我自己用起來是會有些空白對齊的問題,在notepad裡面看起來是對齊好的,不過python執行的時候會判定為沒有對齊的語法錯誤,只要用IDEL打開就會看到是不對齊的(可能是對tab跟space混搭判斷的差異)。

Komodo Edit是Komodo IDE公司出的的免費版本,也是不錯的選擇,不過功能比較少。

我自己是選擇使用Eclipse + PyDev,沒用過Eclipse 的人,可能在安裝上會覺得比較麻煩點。

Eclipse的安裝設定可以參考這篇文章用 Eclipse + PyDev 開發 Google App Engine 的程式或Google提供的說明(英文)Configuring Eclipse on Windows to Use With Google App Engine。

開始寫程式前~
(這標題跟上一個有什麼不一樣= =)

之前Google有在台北舉辦一個程式開發日的活動,裡面有兩個關於Google App Engine的演講,演講內容都有配字幕傳到youtube上。

Google 2008 台北程式開發日@ Youtube

如果你還沒寫過GAE的程式,可以先看一下入門的那個演講,進階最好是有寫一點過再看會比較進入狀況。這兩個演講都不錯,有時間的話建議看一下。

英文聽力不錯的話,可以去Google I/O的網站,Google I/O是 google在舊金山辦的一個演講+聚會,就像「2008台北程式開發日」那樣 ,不過規模整個大很多,那時的演講錄影和投影片都有放到網站上,其中也有一些是關於Google App Engine的。

Google在介紹GAE這個服務的時候,一直強調節約使用資源,這是現在蠻多網佔程式設計師比較少考慮的,現在一般的趨勢都是在比誰可以用最短的時間最少的程式碼開發網站。雖然我也是一個懶惰型的程式設計師,但是因為從小就在一些系統資源貧乏的環境下寫程式,所以在偷懶之餘會有多少顧一下效率的習慣。

GAE中有效利用資源的一些概念,之後有機會的話詳細介紹

  • 減少寫入Datastore的次數
  • 從Datastore讀取資料時,只取出要用的部份
  • 只在需要的時候才載入那部份的程式
    例如一個module只有在一個function才用到的時候,就在那個function裡面才import
  • 能用Memcache (GAE提供將資料存於記憶體的API)存的資料就用Memcache 存
  • 將不常變動的輸出資料(例如html、xml、json)存在memcache
  • 對於時常從Datastore取出的資料存於memcache
  • 減少對伺服器request的次數,例如將許多的javascript檔合併
  • 有效控制瀏覽器的cache (透過header)
  • ......

看到這裡,我想已經有些人注意到了...這篇文章的標題「破」..

跟裡面講的根本就沒關係嘛!!!!(翻桌)

實在是太生氣了!! 不寫了啦

(可以不要在演了嗎......)

2008-08-21

Google App Engine 與 Python 初玩雜唸 (一) ~ 序 ( + PHP免費伺服器 000webhost介紹)

為甚麼會去接觸Google App Engine ?

最近在玩一個小Project ,功能是讓別人可以在網頁上點歌,然後我電腦的Foobar2000就會自動去撥。配上網路電台的話,就是一個懶人開電台的方法。原本網頁程式是用PHP寫的,放在學校或朋友的機器上,結果機器掛掉,只好找別的地方放。我一度找到了一個非常棒的PHP免費伺服器「http://www.000webhost.com」。

先離題一下,說到 000webhost 也有一些可以講的XD

000webhost提供免費的PHP以及MySQL伺服器,php也沒什麼限制(例如可以讀寫檔案之類的),最棒的是..它不會在你的網站上面加廣告!

不過我使用上遇到的第一個問題就是「它會自動加統計流量的程式在你網頁後面」(危機1),雖然是看不到的一般使用上沒什麼問題,但我的網站用了大量的Ajax,傳回去的資料(json)後面被加上這段的話,javascript就沒辦法辨識了(雖然可以用javascript把它截掉,可是這樣真的很鳥),後來在網路上找了一下才找到關閉的方法,從官方的介面好像找不到這個網頁的連結......(密技)

關閉000webhost流量統計程式碼的方法
http://members.000webhost.com/analytics.php <-到這個網站
再輸入帳號密碼選disable code送出就好了

這樣似乎是解決了,網站也用了幾次,可是這中間偶爾會有使用者說有問題,終於有一次讓我自己遇到AJAX傳輸的時候出問題,結果趕快用firebug打開一看....

ㄍ..咳.咳..........,資料後面被加了一行字....powered by 000webhost 之類的  (危機2)..(靠..難怪那段時間點播都比較少..),不過這個出現的機率不高,個人感應起來大概100次的request會一個有加吧。

就在這個時候!!! 突然想到之前Google App Engine剛出來封測的時候,我好像有登記如果有名額就通知的功能,可是翻遍mail都找不到,想去再登記一次的時候...

Google App Engine (GAE)完全開放自由註冊了!!!!

寫到這裡突然發現..........

驚!!!!!!  ( 不是 4:44:44 )

是我整個離題了..........
趕快再標題後面加( + PHP免費伺服器 000webhost 介紹) 好了.........

一進去GAE之後一個帳號可以新增三個Project ,不過我後來用一用,突然變成可以10個,後來去翻說明也說是一個帳號10個,可能是為了防有人灌帳號佔project的名稱,要真的有用才會出現到10個 (還是說剛好我在用的期間改成10個?)

要使用之前最重要的就是知道它使用限制,寫在這裡 http://code.google.com/appengine/articles/quotas.html

事實上我對一個網站CPU會跑幾個Cycles沒什麼概念,這些限制裡面我比較在意的像是 「Size per File : 1MB」等容量、流量問題,這樣很明顯的有許多應用可能都沒辦法做,例如想在上面做影音之類的就不太可能。

除此之外在程式上也有許多限制,例如

  • 目前只支援Python
  • 沒有讀寫檔案功能
  • 所有的資料都要存在Datastore(一個跟一般不太一樣的資料庫) 跟memcache(記憶體暫存,可以跨不同的request,可以當作php的session想像...雖然不一樣 )
  • 每次從Datastore取資料最多1000筆
  • 每次連線都有幾秒的時間限制,無法持續連線
  • 對外接收的連線只限通過port 80
  • 要主動對外連線只能使用它提供的URL Fetch API

老實說...如果對網頁程式開發不熟悉的人,要入手Google App Engine真的不太容易。

如果熟 Python的話還可以一試,對沒有網頁程式開發經驗的人建議先從其他種程式入手。

有經驗的人都會覺得綁手綁腳了,雖然說如果習慣Google App Engine的開發方式,做起網站來也是蠻快的。

不過問題就在於目前關於GAE開發的資訊太少,我自己本身在寫的時候也十分依賴寫PHP時的經驗。

另外就是Python這個語言也是門檻,我自己也是個python的新手,但是這麼多種程式語言之前其實都有些重疊,個人在寫python的時候就有看到javascript形影的感覺,翻一翻說明文件還是OK的。

不過我覺得python的官方文件不太好,我是拿PHP來跟它比較啦,相較起來PHP的document做的真的不錯,例如每個內建或extension的function跟class說明都很精美詳細,一個function或是一個物件的method就給它一頁介紹和範例。

還有一個特色就是,PHP說明文件裡每個主題下面都可以讓使用者留言,許多function有用的應用和範例都是在下面留言找到的,相較之下python的說明就很少,例如某物件的某method說明可能會短到只有一行這樣....,不過這當然跟它背後支持的使用者社群大小有關。

今天先講(離題)到這裡

待續.....

(揪~竟 還會有下一篇嗎?? 部落格的上一篇文章是三個月前發的耶XD )

2008-04-18

用python清foobar2000的Custom Info

我foobar2000有在用custom info這個components,他可以讓你在foobar2000裡面幫音樂增加artist、album、title等..以外的欄位,除了管理音樂方便,還可以配合Inactive Tracks (foo_skip) 、Playback Statistics Custom (foo_playback_custom) 等等,可是每次想用它的remove dead entries功能(清失效的檔案路徑)都會錯誤,我猜可能是因為日文的關係...,他使用的資料庫是sqlite3加上要處理unicode的檔名,剛學的python剛好可以派上用場,幾行就稿定了:

他的資料庫(custominfo_sqlite.db)格式
table : quicktag
fields: url ,subsong,fieldname,value

Python程式碼

# -*- coding: utf-8 -*-
import sqlite3
import os
con = sqlite3.connect(r"custominfo_sqlite.db")
cur = con.cursor()
cur.execute('select url from quicktag group by url')
res = cur.fetchall()
dead_fp=[]
for row in res:
    (url,)=row
    fp=url.replace('file://','')
    if not os.path.exists(fp) :
        print fp
        url2='file://'+fp
        cur.execute('delete from quicktag where url=?',(url2,))
        dead_fp.append(url2)
con.commit()
con.close()



對了...有人要拿去用的話,一定要記得備份custominfo_sqlite.db

壓縮javascript

Packer
http://dean.edwards.name/packer/

YUI Compressor
http://developer.yahoo.com/yui/compressor/
(還可壓CSS)

說到javascript的壓縮,如果可以的話,從server side用gzip壓縮是最好的選擇(設定apache、透過php等都可做到),可是有時候放這些檔案的地方不提供這些功能的時候,就可以用YUI Compressor這類的程式來減少javascript的大小,原理不外乎就是把註解、斷行、空白刪掉,將local變數的名稱用一兩個字的英文數字取代。這時候有沒有習慣使用區域變數可是會影響壓縮出來的大小。

Packer
要取代區域變數名稱記得勾選Shrink variables,除了上述的壓縮方式,他還支援使用Base62 encode +eval這個方法來壓縮。

YUI Compressor
java寫的,除了javascript還可以壓CSS,因為開發者認為eval的方法很不好,所以並沒有支援。使用方式網頁或readme寫的很清楚。他是以命令列的方式執行,所以如果要一次轉一堆東西的話會比較方便(他自己沒提供,我是說自己寫個script)。要注意的是編碼問題,他預設是偵測你系統上的編碼來辨識輸入的檔案,檔案裡面全是英文就沒差,像是有用到utf-8的非英文字他就會跳錯誤給你看,所以記得指定charset,例如:
java -jar yuicompressor-2.3.4.jar --charset UTF-8 ui.js -o ui.min.js

之前用Packer 有發生過轉完javascript執行就跳錯誤的問題,YUI Compressor目前還沒遇到。

2008-04-13

[Note] Weekly Summary 2008/4/13

The wxPython tutorial
http://zetcode.com/wxpython/
wxPython 的詳細教學,圖文並茂。

Featherweight Virtual Machine
http://sourceforge.net/projects/fvm-rni/
羽量級VM,不過好像只能在windows上虛擬windows?還有出論文...

GREUtils
http://code.google.com/p/greutils/
XULRunner 的framework,由阿土伯開發。

AnimeVision
http://animevision.sourceforge.net/
管理動畫軟體,挺有趣的,不過感覺UI設計的不是很好

Classy Query
http://ejohn.org/blog/classy-query/
把jQuery的功能分類正名,雖然這樣變得有系統多了,感覺就像YUI那樣,不過失去了jquery的那種magic,而且重點是要多打很多字XD

2008-02-10

jQuery 1.2.3 Released

http://jquery.com/blog/2008/02/08/jquery-123-air-namespacing-and-ui-alpha/

這次更新我才注意到有.data(),平常都用.attr()來存一些東西。

jQuery UI 1.5 跟jQuery Enchant 1.0的alpha版也同時釋出

看了一下jQuery UI 1.5 的demo,沒注意到比1.0多了什麼東西,等之後release的feature list 再看看吧。

jQuery Enchant 的功能是一些動畫效果,在jQuery1.1.X的時候有個jQuery Interface裡面的effect也可以做一樣的事,不過跟jQuery1.2.X似乎有點不合,用的時候出現一些錯誤,下次有機會可以試試jQuery Enchant 。

2008-01-15

PHP處理HTML安全

HTML Purifier
http://htmlpurifier.org/
HTML Purifier is a standards-compliant HTML filter library written in PHP.

Safe HTML
http://chxo.com/chxo-scripts/safe_html/index.html
http://pear.php.net/package/HTML_Safe
safe_html() is a free php function that takes a conservative approach to sanitizing user input while still allowing some markup through.


2007-02-04

AJAJ, PHP JSON Javascript

AJAX(Asynchronous JavaScript and XML)是最近很熱門的技術,除了使用XML當作溝通的格式之外,現在又跑出了一個JSON可以應用在AJAX上,等等...應該正名叫做AJAJ(Asynchronous JavaScript and JSON)了!!

2006-11-04

Sequence Alignment :: Similarity - dynamic programming

其實這是通識課作業XD

用來比對DNA、mRNA、cDNA序列相似度的方法,計分方式為相同的鹼基+1分、不同的-1、對上空白則-2,兩個序列不改變序列順序而允許插入空白(gap;null)的情況下做排列組合比較取出最高分者。計算出來的分數可以代表這兩個序列的相似度,越高分相似度就越高,例如ACG對上AC可以是(以-代表gap) (1)ACG對AC-:1+1-2=0、(2)ACG對A-C:1-2-1=-2、(3)ACG對-AC:-2-1-1=-4。

這好像叫做Needleman-Wunsch algorithm,但本來他是用暴力算法,就是同時列出兩個序列並包含gap的可能組合做計分,後來發現利用prefix計分來推算分數可以降低運算複雜度。
  null A G
null (0,0) (0,1) (0,2)
A (1,0) (1,1) (1,2)
C (2,0) (2,1) (2,2)
G (3,0) (3,1) (3,2)
  null A G
null 0 -2 -4
A -2 1 -1
C -4 -1 0
G -6 -3 0

比較序列s:ACG與序列t:AG;例如在(2,1)就是比較(null)A與(null)AC得分為-1。p,s null對上null為0分 比較快的推算法就是說,(i,j)可以從(i-1,j)、(i-1,j-1)、(i,j-1)推來,因為(i-1,j)、(i-1,j-1)、(i,j-1)都已經是最佳解了,所以只要取他們中推算到(i,j)最高的那個分數。

以PHP實做的程式碼,另外還有個豪華物件版 XD可以輸出prefix觀察比對過程 <?php function Similarity_csv_lite($s1,$s2) { $datas=array(); $csv=', '; //建立初始值 $datas[0][0]=0; for ($i=1;$i<=strlen($s1);$i++) { $datas[$i][0]=-2*$i; } for ($j=1;$j<=strlen($s2);$j++) { $datas[0][$j]=-2*$j; $csv.=','.$s2[$j-1]; } //開始推算 for ($i=1;$i<=strlen($s1);$i++) { for ($j=1;$j<=strlen($s2);$j++) { $tmp_value=0; $tmp_p=($s1[$i-1]==$s2[$j-1])?1:-1; $datas[$i][$j]=$datas[$i-1][$j]-2;; //(i-1,j) $tmp_value=$datas[$i-1][$j-1]+$tmp_p; //(i-1,j-1) $datas[$i][$j]=($tmp_value>$datas[$i][$j])?$tmp_value:$datas[$i][$j]; $tmp_value=$datas[$i][$j-1]-2; //(i,j-1) $datas[$i][$j]=($tmp_value>$datas[$i][$j])?$tmp_value:$datas[$i][$j]; } } $csv.="\r\n ,".join(',',$datas[0]); for ($i=1;$i<=strlen($s1);$i++) { $csv.="\r\n".$s1[$i-1].','.join(',',$datas[$i]); } return $csv; } echo Similarity_csv_lite('GACGGATTAG','GATCGGAATAG'); ?>