關於小黃(狗)

(圖片摘自: 癡心的小黃狗)

我家以前是開雜貨店的緊鄰著一個傳統市場．祖母與我妹非常喜歡小狗，常常在逛市場的時候就會帶著一隻流浪狗回來說:” 這隻狗一直跟著我，我們就來養他吧”

就這樣，前前後後我家的雜貨店也收養了接近 10 隻狗 （不包括後來生的送人）．裡面最讓我記憶的就是小黃這隻小土狗．

他很壞，每個進來我家的人都會被他兇過．不過他一離開家裡面就乖乖的不敢亂叫．

他很黏，不論去哪都要跟．常常小時候要出去坐公車得要先把他綁好好，不然就跟你到公車站台（當然他不敢上車）．

那個年代，我們都將他放在店面的旁邊讓他亂跑．他也都很乖的不會亂下客人，並且乖乖的店門口當招牌．

有一天，小黃忽然不見了．我們四處尋找都找不到，就在大概第十天左右得時候．祖母懷疑可能被抓狗隊的人抓走，我們到收容所的時候．他已經嚇到沒有力氣癱坐在那邊．大概就差一兩天就變成十二夜的主角．

他回家之後不知道是不是心理的陰影，就再也不敢亂跑了．只敢乖乖的在家裡面．直到他走了之前．

收容所的狗，每一隻其實都曾經是你我的寶貝．他們透過不同的原因進了收容所，卻因為得不到適當得收容得要走向安樂死的路．

這就是我寫這個 Line 機器人的原因，希望大家有事沒事可以滑滑 Line 看看有沒有你喜歡的朋友，一起帶他回家好嗎？

Line Bot - Pet Need Me

Github: https://github.com/kkdai/LineBotPetNeedMe

透過 Line 來查看台北市目前有哪些流浪動物需要領養？ 請用你的 QR Code 掃描並且加入為好友．

主要功能:

目前僅僅支援顯示台北市流浪動物資料，並且顯示該動物圖片．打入任何自就會依序顯示．

歡迎各位建議任何新的功能．

使用方式:

就掃描上面的 QR Code ，加入好友之後．隨便傳任何文字給他就會回傳一個動物資料給你．你不斷傳，他就會一個個動物給你看．

資料來源:

「臺北市開放認養動物」API存取

致謝

感謝g0v的許多人不斷地提起這個專案，讓我可以注意到並且能夠一起幫忙．

摘自: https://twitter.com/SciencePorn/status/578075637274955776/photo/1?ref_src=twsrc%5Etfw 我很喜歡這張圖，因為 NERDS (喜歡鑽研知識的人） 生活的滿意度只會隨著年齡越來越高．

關於本文

這是一篇好文章，所以我決定將他整理一些重點出來希望能做一些簡單的導讀． 也順便把自己的心得寫出來．

全文

全部文章在這裡 https://goo.gl/ZuglAs

投影片

導讀:

TL;DR 這是一個 42 歲的開發者所寫經驗分享文章．並且列出一些他 18 年多身為軟體開發者的經驗談．許多部分看完後都會希望自己當時就能夠了解，所以很推薦不論是新手或是老手都要好好閱讀這一篇文章．

故事很長，一切從 1997 年開始講起．那是一個令人懷念的年代 (FF7 發售，微軟入股蘋果，鐵達尼號上映），那是作者第一年身為軟體開發者的年份． 當時他的第一份工作是從事 ASP 並且使用 EditPlus 在微軟的平台上面．十八年過去，作者一共做過六份工作其中被炒魷魚兩次，出過兩本書，從事過不少演講．

他整理了他的一些心得，希望年輕的開發者（或是有志將軟體開發作為終生志業的人）一些建議，其中條列如下:

1. Forget The Hype (忘記各種程式語言與架構的炒作與熱潮)

不少的新的語言與技術來來去去，作者不是要你不要去學習新事物．而是不要因為有太多的新事物而恐慌或是自我放棄．持續鑽研你目前在學習的，並且可以每年挑一些你有興趣的項目深入了解．

[反觀我自己]: 各種後端與前端語言來來去去，我將我的時間學習了 Python (會持續) ， Ruby, Scala (會持續) 與 Golang (會持續)．但是透過使用 Golang 可以有更多的時間去了解系統架構與直接面對問題，讓寫程式變得更有趣．

2. Choose Your Galaxy Wisely (慎選你的星系)

為了維持原文，我還是使用星系這個字．這邊指的是你學習跟從事的技術要慎選．舉例而言微軟星系（泛指: .Net, C# ….) 或是 Apple 星系 (Objective C++ , Swift …) ．慎選你喜歡的星系，因為那會影響你未來的發展．

[反觀我自己]: 過去十年主要針對微軟星系，目前主要就是後端的 Ubuntu 星系 ，各種後端程式語言都是我目前主要針對的．當然還有 Docker 相關技術．

3. Learn About Software History (了解各種軟體的歷史)

作者認為如果你喜歡一種程式語言，一種架構你就需要好好的了解他的由來與故事．

[反觀我自己]: 比如說：我喜歡 Golang ，我就應該要了解以下的一些問題:

• Golang 是誰發明的?
  • Ans: 由 Google 內部的三位大神 Robert Griesemer，Ken Thompson( C 語言的共同發明者) 與 Rob Pike ( UTF-8 的共同發明者)．在 2007年於 Google 內部共同起草發明．
• 他主要解決什麼問題? 為何以前做不到?
  • Ans: 根據第一份 Golang Talk
  • 原因為:
    • Go fast!
    • Make programming fun again.
    • 世界在變，但是系統語言卻已經十年沒變．
    • 系統語言往往編譯過久
  • 為何以前做不到: (在舊的程式語言上做不到)
    • 新增函式庫不是一個正確的方向．
    • 需要從新思考整個架構來開發新的程式語言．
• 目前這個技術的最新狀況如何?
  • Ans: Golang 目前是 1.6.2 (2016/05/03) ，並且支援 HTTP2 並且可以透過 gomobile 在手機上也可以使用相關套件．

4. Keep on Learning (持續學習!!)

不論你喜歡哪些新的技術或是新的程式語言．你都應該持續的學習．裡面並且建議：

• 每年學習一個新的程式語言．
• 每年讀六本書． (作者推薦 Peopleware , The Psychology of Software Programming, Facts and Fallacies of Software Engineering, Agile!: The Good, the Hype and the Ugly, Rework 跟 Geekonomics 都是好書)

[反觀我自己]:

• 程式語言部分： 2014 (Ruby, Scala) 2015 (Go, Swift) 2016 還沒有決定．
• 讀書部分: 每年讀沒有超過六本書，但是讀過不少論文並且有上過一些 Moocs．

5. Teach (指導其他人)

這邊指的不是一定要開堂授課，你可以是寫一篇部落格來講解你學習的新事物．因為教導是最好的學習方式．

[反觀我自己]: 還好部落格從來沒停過，個人也認為寫部落格的過程可以讓我不斷地檢視我瞭解的部分．並且弄懂所有的細節（希望！）．不過還是希望能夠多多指導其他人（比如說 meetup 或是 talk )

6. Workplaces Suck (工作場所糟糕透了)

不要去期望軟體公司會給你任何職涯的規劃，相反的不少公司會將你認為是另外一種的勞工只會將你放在你擅長的位子，所以也有軟體公司變成血汗工廠的相關文章． 作者同時也認為開放性座位對於需要高度腦力工作的軟體工作者是一種最不好的設計（使用 “cancer” 這個詞)． 而對於工作上的指派，作者也建議大家應該要好好了解每個任務的內容．有任何疑問應該要提出來討論，對於不了解的事物盲從是最不好的選擇． 甚至不惜抗拒權威或是離職才是正確的選擇，不要讓這樣的工作風氣扼殺了你的熱情．

Myth: Open offices result in massive collaboration.

Reality: 2 people loudly collaborate; 30 must wear headphones to get any work done.

— Jochen Wolters (@jochenWolters) April 7, 2016

[反觀我自己]: 我一向對於任何”不合理”的任務指派都會有意見，甚至不斷地提出抗議．（當然結果可能都不好!) 但是如果因為這樣就不提出，那麼我們還剩下什麼呢?

7. Know Your Worth (了解自我的市場價值)

這篇是要大家充分的瞭解自己的市場行情（也就是薪水），根據這篇文章通常一個軟體工程師應該要能創造出他自己薪水等級的十倍價值．事實上可能遠遠不止如此，所以作者建議我們要勇敢地去爭取更多的薪水．甚至你可以公開你的薪水等級，讓更多人知道你是否被低估（或是高估）任何（自認為）有妳相同能力的人，都應該拿到一樣的待遇．

[反觀我自己]: 這件事情還真是難做到，在一間公司待久之後．最容易降低的就是薪水提升的幅度．這件事情還得努力學習，讓自己的市場價值更高．同時我們也要不斷檢視，我們自己能不能創造出自己薪水的十倍價值．

8. Send The Elevator Down (虛心地接受任何意見)

這邊我的解讀可能跟作者原先的不同．他有提到膚色與種族的優勢，但是我想到的卻是你的職位，你可能會聽到許多來自於部下或是後輩的建議（或是批評）．不要快速地想要反駁或是抵制，充分的瞭解過後或許可以坦誠自己的見解或許是有盲點的．必要時甚至可以道歉並且快速修正． 如同許多書上有提到的 : “你雇用一個員工，一定是要比你還強的．這樣你才能將事情交給他辦，你自己做更需要更大視野的任務”

[反觀我自己]: 參加社群後，最容易有這種感覺． 太多令人欽佩的後輩了，每個人都有著淵博而清楚的知識．我們不需要否認，更不需要去挑惕或是批評．我們要謙虛的接受並且吸收，成為我們自己的養分．

9. LLVM (LLVM)

作者認為 LLVM 會是下一個重要的資訊業的星系 (Galaxy) ，目前已經有許多的程式語言支援 LLVM 了．所以作者建議我們可以花一些時間去了解，或許去學習相關的程式語言．

[反觀我自己]: 雖然 Python 與 Swift 都有學習，但是還不是我最上手的程式語言之一．這一個部分我會好好謹記於心，好好學習．

10. Follow Your Gut (相信你的直覺)

作者在 2000 年就覺得 .NET 會引領接下來的幾年，在 2007 年 iPhone 的發表會就了解他的相關技術會是緊接著幾年的發展趨勢．

當然，這是作者的直覺．但是，你也應該充分地相信你的直覺．你也應該相信你的直覺，並且努力的去追求與學習．

[反觀我自己]: 我在 2014 年開始學習許多不同的程式語言， Python, Ruby, Objective C, Java, Swift, Scala 與 Rust ．最後學習到 Golang． 我直覺認為 Golang 會是 Server-side (或是說 Service-side ) 最重要的程式語言之一．所以我會努力學習．

11. APIs Are King (API 是王道)

這邊很推從好的 API 設計是很重要的．不僅僅影響 server 與 client 的溝通，更會影響到好的軟體品質． 也提出 chunky is better than chatty （簡單的說：就是不要將 API 拆的太精簡，使得 API call 需要往來相當的多次)

同時作者也建議不要太依賴 REST ，不仿看看 socket.io, ZeroMQ, RabbitMQ, 或是 Erlang． 並且也應該開始架設自己的機器人．

[反觀我自己]: 沒有想過，原來 chunky 的設計準則在某些狀況下竟然比 chatty 更好，這樣好好學習． 我有架設自己的機器人來幫助我處理一些日常伺服器維護的瑣碎事項．

12. Fight Complexity (將複雜的事情簡單化)

永遠要秉持著 KISS 原則 (“Keep it short and simple”) 來處理任何事情． 面對困難或是負責的事情，有著不少工具可以幫助你將設計簡單化．

[反觀我自己]: 我一直認為能夠越有能力的人，越能夠將複雜的事情簡單的講解．或是寫成一段簡單的程式碼來實現．這個能力是我們都要不斷學習的．

Conclusion (結論)

“年齡永遠不會是一個問題，只要你的心不斷催促你持續寫程式，持續製造新的東西．你永遠都會是年輕的”

這是作者給我們的結論，他也希望我們能夠保持一顆年輕的心．不斷學習． 2016 是一個嶄新的一年，有著許多新奇的事件發生 (微軟擁抱 Ubuntu，並且讓 SQL Server 在 Linux 上執行，機器人 (AlphaGo) 的大反攻 ) ．我們不會知道有什麼會發生，但是他希望我們都記住這些精神，並且微笑向前．

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

• 主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

• 會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

雖然第一天就把本週的專案(Golang Line Bot 建置在 Heroku) 寫好了，但是其他時間都在玩自然語言的引擎 Language Understanding Intelligent Service (LUIS) ．也稍微想了一下到底需要 Bot 來做些什麼事情．

Go

HOWTO: CROSS-COMPILE A GO APP FOR WINDOWS FROM LINUX

原本 Go 要做 cross-compile 其實不難，但是如果在 Go 有使用到 C 的部分 ，可能就要參考一下這一篇文章．

Replicating SQLite using the Raft consensus protocol

將原先的 SQLite 透過 Raft Consensus 的演算法轉身一變成為具有etcd能力的 RDB．

找尋Golang Libs 的地方

分門別類可以找，根據你想找的類別來看看．

Convert pictures to ascii art use golang

將圖形轉換成ASCII，應該可以貼在 PTT? XD

Building the simplest Go static analysis tool

Line Bot 官方 Go SDK

蠻方便的，可以很輕易的傳送圖片跟訊息．不過寫法實在有一點像是 Java XDDD

http://dave.cheney.net/2016/04/27/dont-just-check-errors-handle-them-gracefully

DFC 認為除了只是簡單的檢查 error 之外，你更需要的應該是要根據 error 的不同好好的處理他，衍伸閱讀: Errors are values

A slides collection for Go Conference 2016 Spring

Announcing Apex Software Inc

大神 TJ Holowaychuk 離開 Node.JS 之後轉陣營到了 Go之後的創業作 - Apex 裡面也同時開源了不少的 Go 的套件．

Python

Android/JAVA/NODE.JS

Docker

iOS/Swift

網站文章

Bots won’t replace apps. Better apps will replace apps.

這裡有中文版 (Bot不会取代app，更好的app才会)

基本上作者就是覺得，不論 Bot 多麼的具有智慧，跟 Bot 對話就像是 以前時代的 DOS Console 一樣，需要不斷地下指令．但是 App 就像是後來出的 Windows 視窗介面 (GUI) ．後者永遠不會被前者取代，但是如何讓使用者更容易與有效的使用你的服務才是重點．

網站收集

有聲書/影片心得

Linus Torvalds: The mind behind Linux

Linus Torvalds 改變了這個世界兩次: (1) 一次是撰寫了 linux kernel 並且將它開源 (2) 發明了原始碼版本控制系統 “git”

對於程式設計師而言，最有(品味) “taste” 的莫過於 Linus Torvalds ，這段影片不錯 ． 一些摘要如下:

1. Linus 認為他不是一個可以面對群眾的人 (People Person)，他認為 Open Source 是一個很好面對大家的方式．因為大家討論的程式碼 (對他而言) 是非黑既白的絕對觀點． 並不像政治或是其他具有太多的模糊地帶．

2. 關於程式碼品味部分，他有舉一個簡單的Linked-List 為範例．他認為當你的程式碼能夠將所有的狀況反覆思考後當成是一種 通用的條件 (generic case)，你的程式碼就具有好的品味． 反之，太多的條件判斷(ex: if )來處理就不是一種好的品味．

3. 對於 Linux 與 open source 的未來發展， Linus 認為他不是一個願景者 (visionary) ．他是一個工程師，他執著於每一個目前存在於 Linux 的小 bug ．他希望把每一個小細節都處理好．

Youtube: Fork the Government (g0v) by 唐鳳

唐鳳談他的成長過程與他參與 g0v 的過程．其中也有不少 g0v專案的介紹．

本週專案

這邊會寫一些我的Project 52的成果.

本週專案: https://github.com/kkdai/linebotTemplate

透過一些教學來教導你如何在 Heroku 上面架設自己的 Line Bot ． 裡面的 Golang 程式碼其實相當簡單，主要是測試使用． 但是主要部份是教導要如何 Deploy．

更新: 由於 GitHub.com/line/line-bot-go/line-bot 底層更新，相關 vendor 也更新了．

前提

LINE 推出了機器人 API ，並且透過(幾乎不審核) 的方式來開放機器人的功能． 大家可以來試試看．

如何建立自己的 LINE Bot 機器人

1. 先去 LINE 官方網站申請機器人帳號 (LINE Bot )

• 請先確認有在 LINE Developer Console 開啟帳號
• 然後建立一個 Messaging API Channel
• 在 “Basic Setting” 頁面，取得 Channel Secret
• 在 “Messaging API” 頁面，去申請 Channel Access Token
• 在 “Basic Setting” 頁面，將 LINE 官方帳號管理介面打開
• 到回覆設定的選項中，選擇啟動 “webhook”

2. Deploy LINE Bot template

記得到 https://github.com/kkdai/LineBotTemplate 然後點選下方的 Deploy 按鈕，將基本的程式碼 Deploy 到你的 heroku 之中．

• 輸入剛剛取得的 Channel Access Token跟 Channel Secret 。
• 請記住你設定的 Heroku App ID ，稍後會使用到。

3. 回到 LINE Bot Dashboard 設定基本資料

到你的 “Ｂasic account information” 來設定，以下一些資料需要填好:

• Callback URL: https://{YOUR_HEROKU_SERVER_ID}.herokuapp.com/callback

好了… 加入你的機器人．開始跟他講話吧．

這份程式碼是最簡單的範例，設定好之後他只會重複你打的文字．更多的功能會放在另外一份．

影片教學

可以根據以下影片的教學來看如何在五分鐘之內部署自己的 LINE Bot

想要修改代碼嗎？參考以下的影片教學吧

還有任何問題?

在這裡留下你的問題，或是在 github 上面開啟 issue 詢問

參考鏈結:

• Golang (heroku) で LINE Bot 作ってみる
• LINE BOT をとりあえずタダで Heroku で動かす
• 阿美語萌典 BOT

圖片來自:

.@proppy is explaining why Haskell is a tool the way soldering iron is a tool. pic.twitter.com/Fv722CUOtp

— JBD (@rakyll) April 18, 2016

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

• 主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

• 會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

本週大部分時間再看 KMP 字串比對演算法的進階使用 ACA 演算法，還有玩玩 VS Code． 反而比較少時間看一些網路文章． 單純紀錄就好．

Go

SHRINK YOUR GO BINARIES WITH THIS ONE WEIRD TRICK

這篇教導你透過 go build -ldflags="-s -w" 來將你的 go app binary 變小，根據這篇文章說可以縮小到七倍，似乎有點誇張．不過可以關注看看，瞭解一下方法．

Go Conference 2016 Spring

04/23 在日本舉行的 Golang Conference ，可以看看有沒有什麼有趣的文章．

High-precision indoor positioning framework for most wifi-enabled devices

透過 WiFi 的技術來做高精度的室內定位

A modern and intuitive terminal-based text editor

Micro 一個現代又直覺的 terminal-based editor ，支援基本的一些熱鍵組合與 75 種 syntax highlighter

paper An Implementation and Analysis of a Kernel Network Stack in Go with the CSP Style

網路有關的論文，裡面是用 Golang

JVM Akka.Actor to Go

Akka Actor for Go

A TOTP-based, PiFace powered door lock for Cork’s Forma Labs biohackerspace.

Door lock wite full in Go

Python

Python Taipei Meetup note@Just for noting

紀錄的蠻好的，連 slide 都有整理好．

Android/JAVA/NODE.JS

Docker

iOS/Swift

網站文章

计算机领域的日系书籍

這幾本日文書籍的翻譯書真的都不錯，我的淘寶清單又多了不少書籍．

Line Bot 透過 Let’s Encrypt 來加密 HTTPS 的方法

從 g0v 上面的討論看到，必須要這樣才能讓Line Bot API Server 接受 request 與 callback ．

g0v 的 阿美語萌典 Line BOT

重要的是，裡面寫了不少 Line Bot 製作經過上遇到不少的困難點． 這最近在 g0v slack 有不少討論． 主要是因為 Line Bot API 對於 HTTPS 的管制有點 ~bug~ 嚴格，所以很多都會出問題． 有想做 Line Bot 的人可以先看看…

網站收集

COSCUP 2016 開放原始碼貢獻者 VIP 方案

有參加 Open Source 的記得要申請 VIP 方案．不然 COSCUP 很難報名的．

有聲書/影片心得

TechTalk@TW

TechTalk 是台灣很棒的技術podcast 請來將這都還是挺知名的。 不少講題是我蠻有興趣的，包括:

• Walter (Scala meetup organizer) 講 Scala (不過是 2012)
• ANT 來講 Redis
• PCMan 講 LXQt

本週專案

這邊會寫一些我的Project 52的成果.

本週專案: https://github.com/kkdai/aca

演算法的介紹文章本週專案: 繼續深究字串比對演算法，到下一個部分 AC Algorithm ，有興趣的可以看一下．

必須得說: 要在 jekyll 上面搞 Latex 真的很花時間.. 上一次玩 Latex 已經是研究所寫論的時候，語法又都忘光光.. 哈

前提

前一篇文章介紹到字串比對的演算法 KMP 那時候在 Twitter 上面就有人介紹我說其實可以繼續去研究字典樹 (trie) 與 Aho–Corasick Algorithm

@Evan_Lin KMP + Trie 的概念可以延伸成 AC-Automaton 單文本多模板匹配自動機，有興趣可以研究看看 https://t.co/v87XrLLiwT

— Quexint  (@Quexint) April 15, 2016

所以就開始研究這一篇 slide 想不到意外的有趣．於是也把本週專案也決定改成 AC Automation ．

本週專案: Aho–Corasick algorithm automation implement in Golang

開始介紹 Aho–Corasick Algorithm (AC Algorithm)

為何需要 AC Algorithm?

原先在 KMP Algorithm 我們解決了可以在一個長字串 (haystack) 裡面找到所有具有單個字串 (needle) 的位置集合． 並且可以把時間複雜度縮小到 \(O(n + m)\) 其中 \(n\) 是 haystack 的字串長度，而 \(m\) 是 needle 的長度．

那麼.. 問題來了： 如果我們要比對的 needle 是多數個呢？ （比如說掃毒程式) 那這時候時間複雜度就會變成以下狀態:

( 題外話: 參考這篇可以在 Jekyll 裡面加上 Latex )

以下是時間複雜度的推導過程: TL;DR \(O(n + km)\) .

透過 KMP 如果要處理多個搜尋字串的時間複雜度

要尋找字串集合 (needles) \(P\) 其中 \(P = { P_1, P_2, ... P_k }\)

目標字串 (haystack) \(T[1 ... m]\)

在 KMP 之中，我們已經知道要計算一個 needle \(P_i\) 的時間複雜度為 \(O( n_i + m)\)

所以要處理多個字串 \(P\) 就必須要經過: ( Latex 有點忘記，詳細推導後補)

\[\begin{align*} ((| P_1| )+ m) + ((| P_2| )+ m) + .... ((| P_k| )+ m) &= \sum_{i=1}^k | Pi | + k*m \end{align*}\]

AC Automation 的時間複雜度

先講結論，要能夠比 KMP 的 \(O(n + km)\) ， ACA 時間複雜度為 \(O(n + m + z)\) 其中 \(z\) 是字串重複出現的次數．

建立字典樹

要開始討論 AC Automation 之前，必須要先會建立字典樹．字典樹的建立會是一個類似以下的範例：

這張圖是透過 [say, she, shr, her] 來建立的字典樹 (trie) ．但是這個字典樹還沒有建立錯誤索引． 可以看得出來，字典樹就是透過 prefix tree 來建立而成． 這邊的數字之後會討論到．

關於字典樹的錯誤索引

這邊字典樹錯誤索引的建立可以參考 KMP 的 fail index ，但是有些不同． 以下是我的見解:

KMP Fail Index (Function) :

• 透過單個搜尋字串建立
• 建立每個字元的錯誤索引 ( fail index )也就是比對到該字元如果發生錯誤，需要退到哪個 index 繼續之後的比對．
• Fail Index 在 KMP 中特別注意到連鎖字元 也就是 ABCEABC 其中的 ABC 就被認為是連鎖字元． 會直接尋找該字元前面的錯誤索引 (Fail Index) 避免在比對的時候多餘的移動． （這也是 KMP 勝過 MP 的重點)

在 AC Automation 裡面的錯誤處理索引方式跟 KMP 有些不同，整理如下:

ACA Fail Index :

• 針對處理多個字串
• 專注在多個字串重複出現的字元，不專注在連鎖字元

以這張圖來看，一開始左邊的 a 標記成 \(a_l\) 而右邊的 a 標記成 \(a_r\) ． 以下條列式脈絡給大家了解: 並且將每一個節點編號 [ root(0), \(a_l\) (1) , \(b_r\) (2) , \(b_l\) (3), \(a_r\) (4) ].

• 將 root node 放入 node list ，並將移動的目標節點 移動到 node list 的第一個 (也就是 Root)
• 目標節點往 \(a_l\) 走，該點的 fail index 為計算方式為:
  • Parent node 的 fail index 是否有相當的位置 a
  • 如果 Parent node 是 root ，則該點的 fail index 為 root
• 目標節點往 \(b_r\) (這邊是採取 BFS 走法) ，方法跟 $ a_l $$ 一樣，結果 fail index 也是 root
• 將目標節點 移動到 node list 的第二個 (也就是 \(a_l\) )
• 將目標節點 移動往 \(b_l\) 移動，該點的 fail index 計算方式，如下:
  • 由 \(a_l\) 的 fail index 也就是 root 來看是否有 b 的路徑 ( 有的！ 就是 \(b_r\) (2) )
  • 所以 \(b_l\) 的 fail index 記錄為 2 ，也就是說當他往下比對發生錯誤的時候，會移動到 \(b_r\) (2) 繼續比對．
• 為了確保大家了解，再做一個，將目標節點 移動到 node list 的第三個 (也就是 \(b_r\) ) ，並且往 \(a_r\) 移動． 他的 fail index 計算如下:
• 由 parent \(b_r\) 的 fail index （也就是 root ) 往下看是否有 a
• 有找到由 root 出發的 a 也就是 \(a_l\) (1)
• 將 \(a_r\) 的 fail index 記錄為 1

這裡的時間複雜度為 \(O(n)\) 其中 \(n\) 就是每個字串建立ACA 的時間．

AC Automation 的查詢

假設我們透過 [she, his, hers, he] ，建立了以下的AC Automation ．

並且我們有一個字串 haystack = ashersa 來做搜尋的用．我們的思考脈絡如下:

• 挑出第一個字 haystack[0] = a，從節點 root (0) 開始，沒有a 的路徑，往下
• haystack[1] = s，(0) 有 s 的路徑，往節點 (3) 走
• haystack[2] = h，(3) 有 h 的路徑，往節點 (4) 走
• haystack[3] = e，(4) 沒有 e的路徑，往 fail index (1) 走，並且走到 (2)
• haystack[4] = r，(2) 有 r 的路徑，往節點 (8) 走
• haystack[5] = s，(8) 有 s 的路徑，往節點 (9) 走，並且找到整串字串 hers
• haystack[6] = a, (9) 沒有 a 往 (0) 走

搜尋的時間複雜度為 \(O(z + m)\) 其中 \(z\) 就是每個字元重複出現的次數．

心得

AC Algorithm 其實寫程式的部分並不難．如同所有樹狀結構的演算法一樣，如何能夠清楚地呈現，並且能夠清楚的除錯才是困難的．

不過，由於 Latex 忘得差不多．這一篇寫起來，在弄 Latex 的時間反而是最多的． 哈..

參考文章

• 跳跃表，字典树（单词查找树，Trie树），后缀树，KMP算法，AC 自动机相关算法原理详细汇总
• Biosequence Algorithms, Spring 2005 Lecture 4: Set Matching and Aho-Corasick Algorithm
• Wiki: Aho–Corasick algorithm