Articles

Microsoft tries to one-up Google PageRank．剛剛看到的一則消息~

文中主要描述微軟亞洲研究院在SIGIR'08 Conference發表了一篇名為「BrowseRank: Letting Web Users Vote for Page Importance」的論文~

論文中有提到一些Google PageRank演算法的毛病~ 譬如：我們可以惡意地建立許多連結到我們自身擁有的網站，以提高網站的PR值分數~ 而另一個則是它並沒有考慮到使用者在瀏覽其網站時所花費的時間~

所以這篇論文希望能以「User Behavior Data」來評估網站的重要性~ 舉一個例子：為何PageRank針對adobe官方網站的重要性有那麼高的PR值？因為許多網站都有提供Flash Player或Acrobat Reader的連結~ 但．並非代表人們常去瀏覽adobe網站~

那「User Behavior Data」該如何取得？論文提到兩種方式~ 一種是利用類似Web Server的Log file方式來取得，另一種則是安裝Browser plug-in來記錄~ 而記錄的類型主要分為「Input」(網址列輸入)和「Click」（超連結)~

至於論文中所提到的BrowseRank演算法細節~ 呃... 我就看嘸嚕... XDDD

不過不可抹滅的~ Google所為人稱道的PageRank演算法，仍然為全世界的網頁帶來重要性的排序~

可見微軟多麼地大力想要多吃點搜尋引擎市場~　雖然還買不下Yahoo! Search，但至少已花了１億美元買下Powerset...

最近忙著比賽的事項~ 所以有點久沒有來po文了~ XDD~

How to Write a Spelling Corrector．這是今天Lab所發出來的訊息~ 重點就在於「Spelling Corrector」拼字檢查器，就類似像Google所提供的功能~ 當我們拼字錯誤時，它能提供建議修正~ 詳細的演算法請參考上述網頁資源~

底下我加上一些小程式方便測試：

import re, collections

def words(text):
	return re.findall('[a-z]+', text.lower()) 

def train(features):
	model = collections.defaultdict(lambda: 1)

	for f in features:
		model[f] += 1

	return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'
def edits1(word):
	n = len(word)
	return set([word[0:i]+word[i+1:] for i in range(n)] +                     # deletion
	           [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
	           [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
	           [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet])  # insertion

def known_edits2(word):    
	return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): 
	return set(w for w in words if w in NWORDS)

def correct(word):    
	candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
	return max(candidates, key=lambda w: NWORDS[w])

if __name__ == "__main__":
	running = True
	while running:
		str = raw_input('Please input a word: ')
		if str == 'q':
			running = False
		else:
			print correct(str)
	else:
		print 'Done'

執行結果：(按Q離開程式)

C:\>corrector.py
Please input a word: speling
spelling
Please input a word: korrecter
corrected
Please input a word: q
Done

執行效率似乎還蠻快的~ 有空再來深入看看~ 不過我想是沒空了...... XD

．原始檔下載(含索引檔)

由於學校下學期有門NLP課程要全程使用「Hadoop」來授課，為了開發方便~ 所以這裡介紹如何在Windows平臺上來玩Hadoop~

作業環境

．Windows XP Home Edition

．Hadoop 0.17.1

．JDK 6 Update 7

環境設置

．設定「JAVA_HOME」環境變數

．安裝Cygwin -- 可參考「如何安裝Cygwin」

．設定「Cygwin/bin」至「PATH」環境變數

．將「hadoop-0.17.1.tar.gz」搬移至「C:\cygwin\home\家目錄」。

Hadoop設定

開始啟動「Cygwin」之後，先切換到「家目錄」解壓縮「hadoop-0.17.1.tar.gz」。

tar zxvf hadoop-0.17.1.tar.gz

執行Hadoop範例

這裡我們用一個簡單的「WordCount」來測試~

mkdir input
cd input
echo "hello world bye hello" > file1.txt
echo "hadoop hello goodbye hadoop" > file2.txt
cd..

然後執行下述指令：

bin/hadoop jar hadoop-0.17.1-examples.jar wordcount input output

看看結果吧~

cat output/*
bye     1
goodbye 1
hadoop  2
hello   3
world   1

相關資源

．Hadoop/Windowsでの実行

．Hadoop Quickstart

．H_Yamaguchi日記

．Running Hadoop on Windows

．Running Hadoop On OS X 10.5 64-bit (Single-Node Cluster)

．How to install OpenSSH sshd server and sftp server on a Windows 2000 or Windows XP or Windows Vista

．Setting up a Single-Node Hadoop "Cluster" on Windows XP

由於對於「Google Android」不甚熟悉，所以在上一篇的po文「初探Google Android」我不了解如何Dump出「.dex」檔案中所包含的opcode，還因此麻煩院內的同事(avain) ^^a 幫我詢問相關的資源，雖然沒有直接的解決我所要的需求，不過也提供我一個Google在五月底舉辦的Google I/O所發佈的Dalvik handouts，感謝呢! ^^

還好，今天終於發現了解決方案，原來Android OS就提供了一個「dexdump」的小工具，所以我們可以利用Android SDK所提供的「Android Debug Bridge (adb)」工具來操控Android Emulator，並透過remote shell command來達成我們的需求~

由於我先前已經開發了一個簡單的Android App來測試，所以現在直接啟動Android Emulator，然後執行Android SDK所提供的「Android Debug Bridge (adb)」工具來操作，而我只要輸入下列指令即可Dump出來：

adb shell dexdump -d -f -h /data/dalvik-cache/data@[email protected]@classes.dex > FirstAndroid.txt

接下來就花點時間去讀懂它了~ XDD

........................
source_idx    : 7 (FirstAndroid.java)
insns         : 17 16-bit code units
0004b4:                                        |[0004b4] tw.idv.ring.FirstAndroid.onCreate:(Landroid/os/Bundle;)V
0004b8: fa02 5800 3200                         |0000: +invoke-super-quick {v2, v3}, [0058] // vtable #0058
0004be: 2100 0200                              |0003: new-instance v0, Landroid/widget/TextView; // class@0002
0004c2: 7002 0200 2000                         |0005: invoke-direct {v0, v2}, Landroid/widget/TextView;.<init>:(Landroid/content/Context;)V // method@0002
0004c8: 1801 0000                              |0008: const-string v1, "Hello, Android" // string@0000
0004cc: f802 1e01 1000                         |000a: +invoke-virtual-quick {v0, v1}, [011e] // vtable #011e
0004d2: f802 6f00 0200                         |000d: +invoke-virtual-quick {v2, v0}, [006f] // vtable #006f
0004d8: 0e00                                   |0010: return-void
exceptions    : (none)
positions     : 
        0x0000 line=11
........................

相關資源

．{HOWTO} Poke into the dex file

．How to decompile .dex file on Android

有一陣子沒碰Google Android，不過自從上次聽完Google Developer Day之後，對於Dalvik virtual machine內部的設計以及不同於JVM所客製化設計的「Shared Constant Pool」就一直抱持著想一探究竟的興趣~ 所以今天簡單的試了一下~ 想看看這樣以Register-based VM在opcode上面的執行情況是如何~

我用Google Android SDK所提供的小工具「dx」來看看「.dex」(Dalvik Executable)的檔案格式~

dx --verbose-dump --dex --dump-to=FirstAndroid.dump FirstAndroid.class

不過為何那一個個opcode都被「code-address」所取代掉了...？

....................
                           |codes:
0001c8: 0400 0000          |[1c8] tw.idv.ring.FirstAndroid.<init>:()V
                           |0000: code-address
                           |0000: code-address
                           |0000: code-address
                           |0000: code-address
                           |0000: code-address
                           |0000: code-address
0001cc: 7001 0000 0000     |0000: invoke-direct {v0}, android.app.Activity.<init>:()V // method@0000
                           |0003: code-address
                           |0003: code-address
0001d2: 0e00               |0003: return-void
                           |0004: code-address
                           |debug info @ [2f9]
                           |line starts at 7
                           |00000000: prologue end
                           |00000000: line 7
                           |End Sequence
....................

有人知道怎麼dump出這些「.dex」格式所對應的opcode嗎？

我不是很了解整個Android~ 希望有人可以分享~ ^^

相關資源

{Google Code} Android - An Open Handset Alliance Project