Parser之外的部分參考http://swtch.com/~rsc/regexp/regexp2.html ，代碼都模仿自http://code.google.com/p/re1/source/browse 。注意到正則表達式是operator-precedence grammar，可以用一個擴展的Shunting-Yard算法來解析，其中用了一些特殊構造處理後綴操作符和括號。

2012-11-02

完美迷宮生成算法

Perfect maze

Perfect maze又稱standard maze，指沒有迴路，沒有不可達區域的迷宮。用圖論的語言來說，就是可以用spanning tree表示的迷宮，保證迷宮中任意兩個格子間都有唯一的路徑。本文旨在探討如何隨機生成棋盤狀perfect maze。迷宮格子的鄰居的定義採用von Neumann neighborhood，即水平豎直方向相鄰的四個格子。

變形Kruskal算法

說得通俗點，就是“隨機拆牆”。

2012-10-06

自然語言處理之詞語抽取

多日之前看到了Matrix67的《互聯網時代的社會語言學：基於SNS的文本數據挖掘》，文中提到的方法是無監管的，而且無需詞典就能提取詞語，要素概括起來有兩點：詞的凝聚力，以及左右鄰字的信息熵。今天把這個方法實現了一下。

對於凝聚力，我的理解是可以用詞前後兩部分的pointwise mutual information來描述，比如對於“博物館”一詞，考慮“博”與“物館”之間，以及“博物”與“館”之間的pointwise mutual information，兩者取較小值作爲“博物館”這個詞的凝聚力。

2012-10-01

Force-directed算法(1)——Fruchterman-Reingold

簡介

Graph drawing即根據頂點和邊的拓撲關係，將這張圖展現出來。很明顯，表現的形式種類是非常多的，如果精確到每個頂點的座標，那麼方案有無窮多種。Graph drawing 目標是畫出一張美觀的圖的佈局來。美是個見仁見智的概念，何謂美？“每個本質在於旺盛的生命力，美的形象能夠感染人的情感和鼓舞人心”，展現出來的圖是否美每個人的看法可能都不一樣，但有一些通用的要素是大家一般共同認可的，比如邊的兩端不能靠得太近也不能離得太遠，相交邊的數目要儘量少，有對稱性等等。

2012-10-01

域名遷移至maskray.me

maskray.tk -> maskay.me

2012-09-10

並行N-body模擬

緣由

和專業有關係的第一門有趣的課結束了，覺得有必要記錄些什麼。這篇文章就用來紀念我覺得最有意義的一次作業。

要求

需要分別編寫MPI、Pthreads、OpenMP的並行實作。

層次

我不願意把代碼重複三份，分別爲三種並行庫編寫程式，所以就用 autotools 管理項目，用不同的選項來啓用不同的功能。這樣做的另一個好處是很容易支持MPI+Pthreads或者MPI+OpenMP甚至是MPI+Pthreads+OpenMP，儘管這樣混用不會帶來性能上的提升。

2012-07-25

SVT13117ECS上Gentoo安裝記(含內核配置)

購買

我需要一臺散熱小一點的筆記本，i5 ivy bridge，4G RAM，13.3/14 英寸，madper 推薦了款 HP 的 ultrabook，那東西賣得很暢銷，早已沒了，我就選了這個 SVT13117ECS。回家後第二次用附帶的 Windows，也是最後一次使用，把硬盤驅動等信息截圖用 nc 傳給了我的 Gentoo 臺式機。還是要吐槽一下 OEM Windows 7，500G 的硬盤只設置了三個分區，兩個是還原什麼的作用，隱藏的，留下一個400多GB的C盤。假使我使用 Windows 也免不了要重裝呢。

Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz MemTotal: 3952624 kB