2013-08-25

[轉載] 字符串匹配的 Boyer-Moore 演算法

轉載自:字符串匹配的Boyer-Moore算法 - 阮一峰的网络日志

上一篇文章,我介绍了KMP算法

但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的"查找"功能(Ctrl+F),大多采用Boyer-Moore算法



Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。

下面,我根据Moore教授自己的例子来解释这种算法。


1.



假定字符串为"HERE IS A SIMPLE EXAMPLE",搜索词为"EXAMPLE"。



2.



首先,"字符串"与"搜索词"头部对齐,从尾部开始比较。

这是一个很聪明的想法,因为如果尾部字符不匹配,那么只要一次比较,就可以知道前7个字符(整体上)肯定不是要找的结果。

我们看到,"S"与"E"不匹配。这时,"S"就被称为"坏字符"(bad character),即不匹配的字符。我们还发现,"S"不包含在搜索词"EXAMPLE"之中,这意味着可以把搜索词直接移到"S"的后一位。



3.



依然从尾部开始比较,发现"P"与"E"不匹配,所以"P"是"坏字符"。但是,"P"包含在搜索词"EXAMPLE"之中。所以,将搜索词后移两位,两个"P"对齐。



4.



我们由此总结出"坏字符规则"

后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置

如果"坏字符"不包含在搜索词之中,则上一次出现位置为 -1。

以"P"为例,它作为"坏字符",出现在搜索词的第6位(从0开始编号),在搜索词中的上一次出现位置为4,所以后移 6 - 4 = 2位。再以前面第二步的"S"为例,它出现在第6位,上一次出现位置是 -1(即未出现),则整个搜索词后移 6 - (-1) = 7位。



5.



依然从尾部开始比较,"E"与"E"匹配。



6.



比较前面一位,"LE"与"LE"匹配。



7.



比较前面一位,"PLE"与"PLE"匹配。



8.



比较前面一位,"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"(good suffix),即所有尾部匹配的字符串。注意,"MPLE"、"PLE"、"LE"、"E"都是好后缀。



9.



比较前一位,发现"I"与"A"不匹配。所以,"I"是"坏字符"。



10.



根据"坏字符规则",此时搜索词应该后移 2 - (-1)= 3 位。问题是,此时有没有更好的移法?



11.



我们知道,此时存在"好后缀"。所以,可以采用"好后缀规则"

后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

举例来说,如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5(从0开始计算,取最后的"B"的值),在"搜索词中的上一次出现位置"是1(第一个"B"的位置),所以后移 5 - 1 = 4位,前一个"AB"移到后一个"AB"的位置。

再举一个例子,如果字符串"ABCDEF"的"EF"是好后缀,则"EF"的位置是5 ,上一次出现的位置是 -1(即未出现),所以后移 5 - (-1) = 6位,即整个字符串移到"F"的后一位。

这个规则有三个注意点:

  1. "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀,则它的位置以"F"为准,即5(从0开始计算)。
  2. 如果"好后缀"在搜索词中只出现一次,则它的上一次出现位置为 -1。比如,"EF"在"ABCDEF"之中只出现一次,则它的上一次出现位置为-1(即未出现)。
  3. 如果"好后缀"有多个,则除了最长的那个"好后缀",其他"好后缀"的上一次出现位置必须在头部。比如,假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B",请问这时"好后缀"的上一次出现位置是什么?回答是,此时采用的好后缀是"B",它的上一次出现位置是头部,即第0位。这个规则也可以这样表达:如果最长的那个"好后缀"只出现一次,则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB",即虚拟加入最前面的"DA"。

回到上文的这个例子。此时,所有的"好后缀"(MPLE、PLE、LE、E)之中,只有"E"在"EXAMPLE"还出现在头部,所以后移 6 - 0 = 6位。



12.



可以看到,"坏字符规则"只能移3位,"好后缀规则"可以移6位。所以,Boyer-Moore算法的基本思想是,每次后移这两个规则之中的较大值。

更巧妙的是,这两个规则的移动位数,只与搜索词有关,与原字符串无关。因此,可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时,只要查表比较一下就可以了。



13.



继续从尾部开始比较,"P"与"E"不匹配,因此"P"是"坏字符"。根据"坏字符规则",后移 6 - 4 = 2位。



14.



从尾部开始逐位比较,发现全部匹配,于是搜索结束。如果还要继续查找(即找出全部匹配),则根据"好后缀规则",后移 6 - 0 = 6位,即头部的"E"移到尾部的"E"的位置。

(完)

[轉載] 虚数的意义

轉載自:虚数的意义 - 阮一峰的网络日志

有人在Stack Exchange问了一个问题:

"我一直觉得虚数(imaginary number)很难懂。

中学老师说,虚数就是-1的平方根。



可是,什么数的平方等于-1呢?计算器直接显示出错!

直到今天,我也没有搞懂。谁能解释,虚数到底是什么?

它有什么用?"

帖子的下面,很多人给出了自己的解释,还推荐了一篇非常棒的文章《虚数的图解》。我读后恍然大悟,醍醐灌顶,原来虚数这么简单,一点也不奇怪和难懂!

下面,我就用自己的语言,讲述我所理解的虚数。




一、什么是虚数?


首先,假设有一根数轴,上面有两个反向的点:+1和-1。



这根数轴的正向部分,可以绕原点旋转。显然,逆时针旋转180度,+1就会变成-1。



这相当于两次逆时针旋转90度。



因此,我们可以得到下面的关系式:

(+1) * (逆时针旋转90度) * (逆时针旋转90度) = (-1)

如果把+1消去,这个式子就变为:

(逆时针旋转90度)^2 = (-1)

将"逆时针旋转90度"记为 i :

i^2 = (-1)

这个式子很眼熟,它就是虚数的定义公式。

所以,我们可以知道,虚数 i 就是逆时针旋转90度,i 不是一个数,而是一个旋转量。




二、复数的定义


既然 i 表示旋转量,我们就可以用 i ,表示任何实数的旋转状态。



将实数轴看作横轴,虚数轴看作纵轴,就构成了一个二维平面。旋转到某一个角度的任何正实数,必然唯一对应这个平面中的某个点。

只要确定横坐标和纵坐标,比如( 1 , i ),就可以确定某个实数的旋转量(45度)。

数学家用一种特殊的表示方法,表示这个二维坐标:用 + 号把横坐标和纵坐标连接起来。比如,把 ( 1 , i ) 表示成 1 + i 。这种表示方法就叫做复数(complex number),其中 1 称为实数部,i 称为虚数部。

为什么要把二维坐标表示成这样呢,下一节告诉你原因。




三、虚数的作用:加法


虚数的引入,大大方便了涉及到旋转的计算。



比如,物理学需要计算"力的合成"。假定一个力是 3 + i ,另一个力是 1 + 3i ,请问它们的合成力是多少?



根据"平行四边形法则",你马上得到,合成力就是 ( 3 + i ) + ( 1 + 3i ) = ( 4 + 4i )。

这就是虚数加法的物理意义。




四、虚数的作用:乘法


如果涉及到旋转角度的改变,处理起来更方便。



比如,一条船的航向是 3 + 4i 。

如果该船的航向,逆时针增加45度,请问新航向是多少?



45度的航向就是 1 + i 。计算新航向,只要把这两个航向 3 + 4i 与 1 + i 相乘就可以了(原因在下一节解释):

( 3 + 4i ) * ( 1 + i ) = ( -1 + 7i )

所以,该船的新航向是 -1 + 7i 。

如果航向逆时针增加90度,就更简单了。因为90度的航向就是 i ,所以新航向等于:

( 3 + 4i ) * i = ( -4 + 3i )

这就是虚数乘法的物理意义:改变旋转角度。




五、虚数乘法的数学证明


为什么一个复数改变旋转角度,只要做乘法就可以了?

下面就是它的数学证明,实际上很简单。



任何复数 a + bi,都可以改写成旋转半径 r 与横轴夹角 θ 的形式。

假定现有两个复数 a + bi 和 c + di,可以将它们改写如下:

a + bi = r1 * ( cosα + isinα )

c + di = r2 * ( cosβ + isinβ )


这两个复数相乘,( a + bi )( c + di ) 就相当于

r1 * r2 * ( cosα + isinα ) * ( cosβ + isinβ )


展开后面的乘式,得到

cosα * cosβ - sinα * sinβ + i( cosα * sinβ + sinα * cosβ )


根据三角函数公式,上面的式子就等于

cos(α+β) + isin(α+β)


所以,

( a + bi )( c + di ) = r1 * r2 * ( cos(α+β) + isin(α+β) )


这就证明了,两个复数相乘,就等于旋转半径相乘、旋转角度相加。

(完)

[轉載] 調校 SQL 以徹底改善應用程式效能

轉載自:調校 SQL 以徹底改善應用程式效能

有些程式員在撰寫前端的應用程式時,會透過各種 OOP 語言將存取資料庫的 SQL 陳述式串接起來,卻忽略了 SQL 語法的效能問題。版工曾聽過某半導體大廠的新進程式員,所兜出來的一段 PL/SQL 跑了好幾分鐘還跑不完;想當然爾,即使他前端的 AJAX 用得再漂亮,程式效能頂多也只是差強人意而已。以下是版工整理出的一些簡單心得,讓長年鑽究 ASP.NET / JSP / AJAX 等前端應用程式,卻無暇研究 SQL 語法的程式員,避免踩到一些 SQL 的效能地雷。


1、資料庫設計與規劃
  • Primary Key 欄位的長度儘量小,能用 small integer 就不要用 integer。例如員工資料表,若能用員工編號當主鍵,就不要用身分證字號。
  • 一般欄位亦同。若該資料表要存放的資料不會超過 3 萬筆,用 small integer 即可,不必用 integer。
  • 文字資料欄位若長度固定,如:身分證字號,就不要用 varchar 或 nvarchar,應該用 char 或 nchar。
  • 文字資料欄位若長度不固定,如:地址,則應該用 varchar 或 nvarchar。除了可節省儲存空間外,存取磁碟時也會較有效率。
  • 設計欄位時,若其值可有可無,最好也給一個預設值,並設成「不允許 NULL」(一般欄位預設為「允許 NULL」)。因為 SQL Server 在存放和查詢有 NULL 的資料表時,會花費額外的運算動作 [2]。
  • 若一個資料表的欄位過多,應垂直切割成兩個以上的資料表,並用同名的 Primary Key 一對多連結起來,如:Northwind 的 Orders、Order Details 資料表。以避免在存取資料時,以叢集索引掃描時會載入過多的資料,或修改資料時造成互相鎖定或鎖定過久。



2、適當地建立索引
  • 記得自行幫 Foreign Key 欄位建立索引,即使是很少被 JOIN 的資料表亦然。
  • 替常被查詢或排序的欄位建立索引,如:常被當作 WHERE 子句條件的欄位。
  • 用來建立索引的欄位,長度不宜過長,不要用超過 20 個位元組的欄位,如:地址。
  • 不要替內容重複性高的欄位建立索引,如:性別;反之,若重複性低的欄位則適合建立索引,如:姓名。
  • 不要替使用率低的欄位建立索引。
  • 不宜替過多欄位建立索引,否則反而會影響到新增、修改、刪除的效能,尤其是以線上交易 (OLTP) 為主的網站資料庫。
  • 若資料表存放的資料很少,就不必刻意建立索引。否則可能資料庫沿著索引樹狀結構去搜尋索引中的資料,反而比掃描整個資料表還慢。
  • 若查詢時符合條件的資料很多,則透過「非叢集索引」搜尋的效能,可能反而不如整個資料表逐筆掃描。
  • 建立「叢集索引」的欄位選擇至為重要,會影響到整個索引結構的效能。要用來建立「叢集索引」的欄位,務必選擇「整數」型別 (鍵值會較小)、唯一、不可為 NULL。



3、適當地使用索引
  • 有些書籍會提到,使用 LIKE、% 做模糊查詢時,即使您已替某個欄位建立索引 (如下方例子的 CustomerID),但以常數字元開頭才會使用到索引,若以萬用字元 (%) 開頭則不會使用索引,如下所示:
    USE Northwind;
    GO
    SELECT * FROM Orders WHERE CustomerID LIKE 'D%'; --使用索引
    SELECT * FROM Orders WHERE CustomerID LIKE '%D'; --不使用索引
    

    執行完成後按 Ctrl+L,可檢閱如下圖的「執行計畫」。


    圖 1 可看出「查詢最佳化程式」有使用到索引做搜尋


    圖 2 在此的叢集索引掃描,並未直接使用索引,效能上幾乎只等於掃描整個資料表

    但經版工反覆測試,這種語法是否會使用到索引,抑或會逐筆掃描,並非絕對的。仍要看所下的查詢關鍵字,以及欄位內儲存的資料內容而定。但對於儲存資料筆數龐大的資料表,最好還是少用 LIKE 做模糊查詢。

  • 以下的運算子會造成「負向查詢」,常會讓「查詢最佳化程式」無法有效地使用索引,最好能用其他運算子和語法改寫 (經版工測試,並非有負向運算子,就絕對無法使用索引):
    NOT 、 != 、 <> 、 !> 、 !< 、 NOT EXISTS 、 NOT IN 、 NOT LIKE
  • 避免讓 WHERE 子句中的欄位,去做字串串接或數字運算,否則可能導致「查詢最佳化程式」無法直接使用索引,而改採叢集索引掃描 (經版工測試並非絕對)。
  • 資料表中的資料,會依照「叢集索引」欄位的順序存放,因此當您下 BETWEEN、GROUP BY、ORDER BY 時若有包含「叢集索引」欄位,由於資料已在資料表中排序好,因此可提升查詢速度。
  • 若使用「複合索引」,要注意索引順序上的第一個欄位,才適合當作過濾條件。



4、避免在 WHERE 子句中對欄位使用函數

對欄位使用函數,也等於對欄位做運算或串接的動作,一樣可能會讓「查詢最佳化程式」無法有效地使用索引。但真正對效能影響最重大的,是當您的資料表內若有 10 萬筆資料,則在查詢時就需要呼叫函數 10 萬次,這點才是真正的效能殺手。程式員應注意,在系統開發初期可能感覺不出差異,但當系統上線且資料持續累積後,這些語法細節所造成的效能問題就會逐步浮現。

SELECT * FROM Orders WHERE DATEPART(yyyy, OrderDate) = 1996 AND DATEPART(mm, OrderDate)=7
-- 可改成
SELECT * FROM Orders WHERE OrderDate BETWEEN '19960701' AND '19960731'

SELECT * FROM Orders WHERE SUBSTRING(CustomerID, 1, 1) = 'D'
-- 可改成
SELECT * FROM Orders WHERE CustomerID LIKE 'D%'

注意當您在下 UPDATE、DELETE 陳述式時,若有採用 WHERE 子句,也應符合上述原則。



5、AND 與 OR 的使用

在 AND 運算中,「只要有一個」條件有用到索引 (如下方的 CustomerID),即可大幅提升查詢速度,如下圖 3 所示:

SELECT * FROM Orders WHERE CustomerID='VINET' AND Freight=32.3800 
--使用索引,會出現下圖 3 的畫面

SELECT * FROM Orders WHERE Freight=32.3800 
--不使用索引,會出現上圖 2 的畫面


圖 3

但在 OR 運算中,則要「所有的」條件都有可用的索引,才能使用索引來提升查詢速度。因此 OR 運算子的使用必須特別小心。

若您將上方 AND 的範例,邏輯運算子改成 OR 的話,如下所示:

SELECT * FROM Orders WHERE CustomerID='VINET' OR Freight=32.3800

由於無法有效地使用索引,也會出現圖 2 的畫面。

在使用 OR 運算子時,只要有一個條件 (欄位) 沒有可用的索引,則其他所有的條件 (欄位) 都有索引也沒用,只能如圖 2 般,把整個資料表或整個叢集索引都掃描過,以逐筆比對是否有符合條件的資料。


據網路上文件的說法 [1],上述的 OR 運算陳述式,我們還可用 UNION 聯集適當地改善,如下:

SELECT * FROM Orders WHERE CustomerID='VINET'
UNION
SELECT * FROM Orders WHERE Freight=32.3800

此時您再按 Ctrl+L 檢閱「執行計畫」,會發現上半段的查詢會使用索引,但下半段仍用叢集索引掃描,對效能不無小補。



6、適當地使用子查詢

相較於「子查詢 (Subquery)」,若能用 JOIN 完成的查詢,一般會比較建議使用後者。原因除了 JOIN 的語法較容易理解外,在多數的情況下,JOIN 的效能也會比子查詢較佳;但這並非絕對,也有的情況可能剛好相反。

我們知道子查詢可分為「獨立子查詢」和「關聯子查詢」兩種,前者指子查詢的內容可單獨執行,後者則無法單獨執行,亦即外層查詢的「每一次」查詢動作都需要引用內層查詢的資料,或內層查詢的「每一次」查詢動作都需要參考外層查詢的資料。

以下我們看一個比較極端的例子 [2]。若我們希望所有查詢出來的資料,都能另外給一個自動編號,版工我在之前的文章「用 SQL Server 2005 新增的 ROW_NUMBER 函數撰寫 GridView 分頁」中有介紹過,可用 SQL Server 2005 中新增的 ROW_NUMBER 函數輕易地達成,且 ROW_NUMBER 函數還能再加上「分群 (PARTITION BY)」等功能,而且執行效能極佳。


圖 4 將 Orders 資料表的 830 筆資料都撈出來,並在右側給一組自動編號

現在我們要如上圖 4 般,將 Northwind 中 Orders 資料表的 830 筆資料都撈出來,並自動給一組編號,若用 ROW_NUMBER 函數的寫法如下所示,而且效能極佳,只要 2 ms (毫秒),亦即千分之二秒。

SET STATISTICS TIME ON
SELECT OrderID, ROW_NUMBER() OVER(ORDER BY OrderID) AS 編號
FROM dbo.Orders

但如果是在舊版的 SQL Server 2000 中,我們可能得用以下的「子查詢」寫法:

SET STATISTICS TIME ON
SELECT OrderID,
(SELECT COUNT(*) FROM dbo.Orders AS 內圈
WHERE 內圈.OrderID <= 外圈.OrderID) AS 編號
FROM dbo.Orders AS 外圈
ORDER BY 編號

但這種舊寫法,會像先前所提到的,外層查詢的「每一次」查詢動作都需要引用內層查詢的資料。以上方例子而言,外層查詢的每一筆資料,都要等內層查詢「掃描整個資料表」並作比對和計數,因此 830 筆資料每一筆都要重複掃描整個資料表 830 次,所耗用的時間也因此爆增至 170 ms。

若您用相同的寫法,去查詢 AdventureWorks 資料庫中,有 31,465 筆資料的 Sales.SalesOrderHeader 資料表,用 ROW_NUMBER 函數要 677 ms,還不到 1 秒鐘;但用子查詢的話,居然要高達 225,735 ms,將近快 4 分鐘的時間。

雖然這是較極端的範例,但由此可知子查詢的撰寫,在使用上不可不慎,尤其是「關聯子查詢」。程式員在程式開發初期、資料量還很少時感受不到此種 SQL 語法的重大陷阱;但等到系統上線幾個月或一兩年後,可能就會有反應遲緩的現象。



7、其他查詢技巧
  • DISTINCT、ORDER BY 語法,會讓資料庫做額外的計算。此外聯集的使用,若沒有要剔除重複資料的需求,使用 UNION ALL 會比 UNION 更佳,因為後者會加入類似 DISTINCT 的演算法。
  • 在 SQL Server 2005 版本中,存取資料庫物件時,最好明確指定該物件的「結構描述 (Schema)」,也就是使用兩節式名稱。否則若呼叫者的預設 Schema 不是 dbo,則 SQL Server 在執行時,會先尋找該使用者預設 Schema 所搭配的物件,找不到的話才會轉而使用預設的 dbo,會多耗費尋找的時間。例如若要執行一個叫做 dbo.mySP1 的 Stored Procedure,應使用以下的兩節式名稱:
    EXEC dbo.mySP1
    



8、儘可能用 Stored Procedure 取代前端應用程式直接存取資料表

Stored Procedure 除了經過事先編譯、效能較好以外,亦可節省 SQL 陳述式傳遞的頻寬,也方便商業邏輯的重複使用。再搭配自訂函數和 View 的使用,將來若要修改資料表結構、重新切割或反正規化時亦較方便。



9、儘可能在資料來源層,就先過濾資料

使用 SELECT 語法時,儘量避免傳回所有的資料至前端而不設定 WHERE 等過濾條件。雖然 ASP.NET 中 SqlDataSource、ObjectDataSource 控制項的 FilterExpression 可再做篩選,GridView 控制項的 SortExpression 可再做排序,但會多消耗掉資料庫的系統資源、Web server 的記憶體和網路頻寬。最好還是在資料庫和資料來源層,就先用 SQL 條件式篩選出所要的資料。



結論:

本文的觀念,不管是寫 SQL statement、Stored Procedure、自訂函數或 View 皆然。本文只是挑出程式員較容易犯的 SQL 語法效能問題,以期能在短時間瀏覽過本文後,在寫 ADO.NET 程式時能修正以往隨興的 SQL 撰寫習慣。文中提到的幾點,只不過是 SQL 語法效能議題的入門篇。後續有時間的話,版工會再補充在本帖的回應留言,或另開新主題。



參考文件:

[1] SQL查詢最佳化 (網際烏托邦):
http://www.ithome.com.tw/plog/index.php?op=ViewArticle&articleId=5421&blogId=620

參考書籍:

[2] SQL Server 2005 Performance Tuning 效能調校:
作者:胡百敬、姚巧枚、劉承修
出版社:悅知出版社
http://tlsj.tenlong.com.tw/WebModule/BookSearch/bookSearchViewAction.do?isbn=9789866761225&sid=41966

[3] SQL Server 2005 完全實戰:
作者:章立民
出版社:碁峰出版社

相關文件:

[4] 臺大醫院資料庫分割疏失,系統幾近停擺 (ITHome):
http://www.ithome.com.tw/itadm/article.php?c=43597

[5] 當DataGrid遇見100萬筆資料:
http://blog.sina.com.tw/4907/article.php?pbgid=4907&entryid=3921

[6] ASP.NET 2.0 GridView 範例集 - 「4-8-4、GridView的效能」:
http://blog.csdn.net/Code6421/archive/2007/12/22/1958167.aspx

[7] 有關開啟頁面時,一次載入數千筆資料的效能問題:
http://www.blueshop.com.tw:80/board/show.asp?subcde=BRD200709141021458MV

2013-08-17

[PHP] url, base64, sprite 三種格式的 icons.css 產生器

先做一個假設,如果 icon 的檔名就是 css 的 class 樣式名稱,那麼我們只要掃瞄資料夾的 Icon 圖檔,然後產生對應的 CSS 檔案,這樣就可以省去製作 Sprite 圖檔跟維護 CSS 對應的問題。

第一種 url 格式只是取得路徑的問題。

第二種 base64 格式可以透過 base64_encode(file_get_contents($path)); 就簡單的達成。

第三種 sprite 格式則使用 Imagick 去處理,會比較快樂。


接著以下就是如何達成的程式片段:

<?php

/*把目錄改變到當前文件下*/
chdir(dirname(__FILE__));

/*Sprite 圖與圖的間距*/
$spriteGap = 30;


/*=[ 取得圖檔資訊 ]=*/
$maxWidth = 0;
$maxHeight = 0;
$nextTop = 0;
$imageList = array();

foreach ( glob('icons/*.{png,jpg,gif}',GLOB_BRACE) as $path )
{
    $image = new Imagick($path);
    $name = pathinfo($path,PATHINFO_FILENAME);

    if(isset($imageList[$name])){ 
        throw new Exception("圖片名稱重複 [ $name ]"); 
    }

    $info = array(
        '{top}' => $nextTop,
        '{image}' => $image,
        '{width}' => $image->getImageWidth(),
        '{height}' => $image->getImageHeight(),
        '{name}' => $name,
        '{path}' => $path,
        '{isAnimate}' => false
    );

    $header = '';
    switch($image->getImageFormat()){
        case "PNG":
            $header = 'data:image/png;base64,'; break;
        case "JPEG":
            $header = 'data:image/jpeg;base64,'; break;
        case "GIF":
            $header = 'data:image/gif;base64,'; break;
        default: break;
    }

    $info['{uri}'] = $header.base64_encode(file_get_contents($path));

    $maxWidth = max($maxWidth, $info['{width}']);
    $maxHeight = max($maxHeight, $info['{height}']);

    
    /*檢查圖片是否為動畫*/
    $frameNum = 0;
    foreach($image->deconstructImages() as $i) {
        $frameNum++;
        if ($frameNum > 1) {
            $info['{isAnimate}'] = true;
            break;
        }
    }
    
    if(!$info['{isAnimate}']){
        $nextTop += $info['{height}'] + $spriteGap;
    }


    $imageList[$name] = $info;
}


/*=[ 製作 CSS Sprite 圖檔 ]=*/
$spriteImage = new Imagick();
$spriteImage->newImage($maxWidth, $nextTop, new ImagickPixel());
$spriteImage->setImageFormat('png');
$spriteImage->paintTransparentImage(new ImagickPixel(), 0.0, 0);

foreach ($imageList as $name => $info)
{
    if($info['{isAnimate}']){ continue; } /* 忽略 GIF 動畫 */

    /* 複製 Icon 圖檔到 Sprite */
    $spriteImage->compositeImage(
        $info['{image}'],
        $info['{image}']->getImageCompose(),
        0,
        $info['{top}']
    );

    $info['{image}']->destroy();
    unset($imageList[$name]['{image}']);
}

$spriteImage->writeImage('icons.sprite.png');
$spriteImage->destroy();
$spriteImage = null;


下載完整程式: php_make_icons_css.zip

[轉載] 公司職稱中英文對照表

轉載自:公司職稱中英文對照表

中文職稱英文職稱英文縮寫
董事長 / 會長Chairman 
副董事長 / 副會長Vice Chairman 
監事Supervisor 
常務監事Managing Supervisor 
董事 / 理事 / 總監Director 
董事總經理Managing DirectorMD
執行董事 / 常務董事Executive DirectorED
副董事 / 助理董事Associate DirectorAD
執行長Chief Executive 
執行長Chief Executive OfficerCEO
財務長Chief Financial OfficerCFO
資訊長Chief Information OfficerCIO
知識長Chief Knowledge OfficerCKO
營運長Chief Operating OfficerCOO
技術長Chief Technology OfficerCTO
管理長Chief Administrative OfficerCAO
行銷長Chief Marketing OfficerCMO
投資長Chief Investment OfficerCIO
總裁 / 社長President 
執行副總裁Executive Vice PresidentEVP
資深副總裁Senior Vice PresidentSVP
副總裁 / 副社長Vice PresidentVP
協理副總裁Associate Vice PresidentAVP
助理副總裁 / 協理Assistant Vice PresidentAVP
總經理General ManagerGM
副總經理Vice General Manager / Deputy General ManageVGM / DGM
副總經理 / 協理Associate General Manager / Assistant General ManagerAGM
執行助理Executive Assistant 
特別助理Special Assistant 
顧問Adviser / Consultant 
處長 / 協理Director 
副處長Vice Director / Deputy Director 
資深經理Senior Manager 
經理Manager 
副理 / 襄理Deputy Manager / Assistant Manager 
襄理Junior Manager / Senior Officer 
部門經理 / 課長Section Manager 
部門副理 / 副課長Deputy Section Manager 
廠長Factory Manager / Plant Manager / Factory Director 
副廠長Deputy Factory Manager 
專案經理Project ManagerPM
主任 / 組長Supervisor / Director / Chief 
業務主任Sales Executive 
專案專員 / 業務專員Account OfficerAO
專案執行Account ExecutiveAE
領班 / 組長Team Leader 
專員Specialist (Officer) 
儲備幹部Management AssociateMA
儲備幹部Management TraineeMT
代表Representative 
管理師Administrator 
會計Accountant 
稽核Auditor 
工程師Engineer 
研究員 / 分析師Analyst 
秘書Secretary 
辦事員 / 事務員Clerk 
職員Staff 
作業員Operator 
技術員Technician 
助理Assistant 

2013-08-07

[MySQL] 計算漢明距離

之前寫了用 PHP 計算圖片的 hash code,接著要怎麼去搜尋相似的圖片呢?

資料庫是一個很好的選擇,首先建立一個簡單的 Table:
CREATE TABLE image_hash (
    id         INT(11) NOT NULL AUTO_INCREMENT,
    filepath   VARCHAR(256) NOT NULL,
    hash       BIGINT(20) UNSIGNED ZEROFILL NOT NULL,

    PRIMARY KEY  (id)
) ENGINE=MYISAM;


再來要怎麼將 hash code 寫進資料表呢?我們可以利用 b'010101' 的 bit 表示語法將 hash code 64位元字串存進 BIGINT 裡面。
INSERT INTO image_hash_info (filepath, hash)
    VALUES('/home/jax/12.jpg', b'10100111...');


資料已經備齊了,最重要的就是怎麼計算漢明距離了,MySQL 提供了 BIT_COUNT() 的函數,可以計算數字中位元 1 的個數,所以剩下的就是 XOR 的運算了。
SELECT BIT_COUNT(29), BIT_COUNT(b'101010');
       -- -> 4, 3


找尋與某一個 hash code 相似的圖片
SELECT * FROM image_hash
    WHERE BIT_COUNT(hash ^ b'1010011110...') <= 10


參考來源:
MySQL 5.0 Bit Functions

2013-08-06

符號英文名稱

_underline底線
,comma逗號
;semicolon分號
:colon冒號
!exclamation mark驚嘆號
?question mark問號
//slash-slash, comment雙斜線, 註釋符
/slash斜線
...ellipsis省略號
.dot句號, 點
`grave accent重音號
^caret插入號
¨tandem colon單點號
~tilde波浪符
""double quotation marks雙引號
''single quotation marks單引號
()brackets, parentheses括號
(left parenthesis, open parenthesis, open paren左圓括號
)right parenthesis, close parenthesis, close paren右圓括號
[]square brackets方括號
[left square bracket, open bracket左方括號
]right square bracket, close bracket右方括號
{}curly brackets or braces大括號
{left curly brace, open brace, open curly左花括號
}right curly brace, close brace, close curly右花括號
@at小老鼠
$dollar sign金錢符號
*star星號
\backslash反斜线
&and
#pound井號
%percent百分號
+plus加號;正號
-minus減號;負號
dash破折號
-hyphen連字號
×is multiplied by乘號
÷is divided by除號
=equal等於
<>angle brackets尖括號
|pipe, vertical bar管線, 豎線
triangle三角形
square root平方根
less than sign小於號
greater than sign大於號
infinity無限號
is approximately equal to約等於號
is equivalent to全等於號
intersection of交集
union of連集
perpendicular to垂直於
angle
the integral of積分
since; because因為
hence所以
arrow箭號;參見號
parallel雙線號
celsius system攝氏度
°degree
σsigma, summation of總和
πpi圓周率
varies as與…成比例
circle