After years of development this feature packed editor is waiting for you.
For the impatient, go directly to the download page. For the curious,
read the announcement. Happy Vimming!(Bram Moolenaar)
Announcement
http://groups.yahoo.com/group/vimannounce/message/161
Download
http://www.vim.org/download.php
2006年4月30日 星期日
Search bots behavior analyzed
Introduction
In the previous edition - Binary Search Tree 2 - a large scale experiment on
search engine behaviour was staged with more than two billion different web
pages. This experiment lasted exactly one year, until April 13th. In this
period the three major search engines requested more than one million pages
of the tree, from more than hundred thousand different URLs. The home page of
drunkmenworkhere.org grew from 1.6 kB to over 4 MB due to the visit log and
the comment spam displayed there.
This edition presents the results of the experiment.
http://drunkmenworkhere.org/219
--
圖很漂亮，英文好多 =.=
In the previous edition - Binary Search Tree 2 - a large scale experiment on
search engine behaviour was staged with more than two billion different web
pages. This experiment lasted exactly one year, until April 13th. In this
period the three major search engines requested more than one million pages
of the tree, from more than hundred thousand different URLs. The home page of
drunkmenworkhere.org grew from 1.6 kB to over 4 MB due to the visit log and
the comment spam displayed there.
This edition presents the results of the experiment.
http://drunkmenworkhere.org/219
--
圖很漂亮，英文好多 =.=
The name of Dapper + 1 = Edgy Eft
This mail charts the territory post-Dapper for those of us who like to
dream a little.
First things first. The codename of Dapper+1 will be:
The Edgy Eft
And here's why. Edgy is all about cutting edge, perhaps bleeding edge,
brand new code and infrastructure. It will be the right time to bring in
some seriously interesting but definitely edgy new technologies which
lay the groundwork for the next wave of Ubuntu development.
An Eft is a youthful newt, going through its first exploration of the
rocky territory just outside the stream. And that's exactly what we hope
the development team will do with Ubuntu during the Edgy cycle - explore
slightly unfamiliar and uncharted territory that is perhaps a little out
of the mainstream.
So dream a little about Xen for virtualisation, Xgl/AIGLX and other
wonderful wobbly window bits, the goodness of Network Manager, a first
flirt with multiarch support for true mixed 32-bit and 64-bit computing
on AMD64, the interesting possibilities of the SMART package manager...
and other pieces of infrastructure which have appeared tantalisingly
on the horizon.
We can afford to take some risks with Dapper+1, because Dapper has turned
out so well. We have a great answer for people who need super-solid
and super-predictable results: Dapper is still fresh, will continue to work
on modern hardware for some time, and has plenty of legs in its support
cycle left to run.
In terms of the management of the release, we will have some fun with the
core Canonical team. I'm promising to impose (almost ;-) zero from-the-top
requirements for Edgy, this release is entirely up the to development
team to envision and implement. Of course, feature proposals need to
go through a review and approval process, and we'll make sure everyone
has enough on their plate to keep busy during the cycle, but almost
everything that lands in Edgy will be driven from the development team,
who get to play with whatever new technologies they fancy along the way.
So that should give us a nice big bump in infrastructure and bling.
I would encourage members of the community who have been thinking of
a cool new feature or plan to seize the opportunity to get it into Edgy.
The tradeoff, of course, will be that some of these new ideas will not
land perfectly first time. So there may be shakiness, or outright
bumpiness, in Edgy. We will for the first time possibly have to say
to new users ""Edgy gets security updates etc for 18 months but seriously
consider Dapper if you need the most polished platform"". I think that's
a worthwhile tradeoff, because I think a clean-the-pipes type release
like Edgy is a good way for us to re-energise the team and the distro.
Risk is good, when you give it a place and a time. And Dapper+1 is
the right time for us to take a few risks.
All of this will be managed using the Launchpad spec tracker, now called
Blueprint. You can find the current set of ""out there maybe"" specs for
Ubuntu at:
https://launchpad.net/distros/ubuntu/+specs
Go ahead and start drawing up braindump specs in the wiki for ideas you
would like to get into Edgy, and registering them there. Don't put too
much time into the detail of the specs because we should stay focused on
the business of polishing up Dapper until June 1st. In the week after
the Dapper release we will open up the Edgy archive and start reviewing
and prioritising Edgy specs, and two weeks after release we will have
the next Ubuntu Developer Summit, where the core team's specs will get
finalised and approved.
This ""meta cycle"" of aggressive new features, slowly converging over a
series of releases on a solid and consistent look-and-feel and underlying
platform, has worked very well for us over the course of the past two
years. We didn't plan it this way, but I suspect the next two to three
years will look similar - we'll start of with a release that has a lot
of edge and new tech (remember Warty?) and polish that up till we see
the timing is right for a really polished enterprise ""long term support""
release, like Dapper. We've no concrete plans for the next Dapper, only
that we'll know a release or two in advance when the time is right.
The past two years have been a privilege and a pleasure. Dapper is the
full expression of what we have learned in this first phase, and I have
every reason to believe it will be a hit. Once that's out the door, it
will be a great opportunity to rock-'n-roll up our sleeves, play with new
ideas, kick some new tyres and of course dig some new foundations. We may
strike gold, we will likely uncover some dirt, but it should be fun and it
should be funky. Let's live on the Edge a while.
Mark
--
https://lists.ubuntu.com/archives/ubuntu-announce/2006-April/000064.html
dream a little.
First things first. The codename of Dapper+1 will be:
The Edgy Eft
And here's why. Edgy is all about cutting edge, perhaps bleeding edge,
brand new code and infrastructure. It will be the right time to bring in
some seriously interesting but definitely edgy new technologies which
lay the groundwork for the next wave of Ubuntu development.
An Eft is a youthful newt, going through its first exploration of the
rocky territory just outside the stream. And that's exactly what we hope
the development team will do with Ubuntu during the Edgy cycle - explore
slightly unfamiliar and uncharted territory that is perhaps a little out
of the mainstream.
So dream a little about Xen for virtualisation, Xgl/AIGLX and other
wonderful wobbly window bits, the goodness of Network Manager, a first
flirt with multiarch support for true mixed 32-bit and 64-bit computing
on AMD64, the interesting possibilities of the SMART package manager...
and other pieces of infrastructure which have appeared tantalisingly
on the horizon.
We can afford to take some risks with Dapper+1, because Dapper has turned
out so well. We have a great answer for people who need super-solid
and super-predictable results: Dapper is still fresh, will continue to work
on modern hardware for some time, and has plenty of legs in its support
cycle left to run.
In terms of the management of the release, we will have some fun with the
core Canonical team. I'm promising to impose (almost ;-) zero from-the-top
requirements for Edgy, this release is entirely up the to development
team to envision and implement. Of course, feature proposals need to
go through a review and approval process, and we'll make sure everyone
has enough on their plate to keep busy during the cycle, but almost
everything that lands in Edgy will be driven from the development team,
who get to play with whatever new technologies they fancy along the way.
So that should give us a nice big bump in infrastructure and bling.
I would encourage members of the community who have been thinking of
a cool new feature or plan to seize the opportunity to get it into Edgy.
The tradeoff, of course, will be that some of these new ideas will not
land perfectly first time. So there may be shakiness, or outright
bumpiness, in Edgy. We will for the first time possibly have to say
to new users ""Edgy gets security updates etc for 18 months but seriously
consider Dapper if you need the most polished platform"". I think that's
a worthwhile tradeoff, because I think a clean-the-pipes type release
like Edgy is a good way for us to re-energise the team and the distro.
Risk is good, when you give it a place and a time. And Dapper+1 is
the right time for us to take a few risks.
All of this will be managed using the Launchpad spec tracker, now called
Blueprint. You can find the current set of ""out there maybe"" specs for
Ubuntu at:
https://launchpad.net/distros/ubuntu/+specs
Go ahead and start drawing up braindump specs in the wiki for ideas you
would like to get into Edgy, and registering them there. Don't put too
much time into the detail of the specs because we should stay focused on
the business of polishing up Dapper until June 1st. In the week after
the Dapper release we will open up the Edgy archive and start reviewing
and prioritising Edgy specs, and two weeks after release we will have
the next Ubuntu Developer Summit, where the core team's specs will get
finalised and approved.
This ""meta cycle"" of aggressive new features, slowly converging over a
series of releases on a solid and consistent look-and-feel and underlying
platform, has worked very well for us over the course of the past two
years. We didn't plan it this way, but I suspect the next two to three
years will look similar - we'll start of with a release that has a lot
of edge and new tech (remember Warty?) and polish that up till we see
the timing is right for a really polished enterprise ""long term support""
release, like Dapper. We've no concrete plans for the next Dapper, only
that we'll know a release or two in advance when the time is right.
The past two years have been a privilege and a pleasure. Dapper is the
full expression of what we have learned in this first phase, and I have
every reason to believe it will be a hit. Once that's out the door, it
will be a great opportunity to rock-'n-roll up our sleeves, play with new
ideas, kick some new tyres and of course dig some new foundations. We may
strike gold, we will likely uncover some dirt, but it should be fun and it
should be funky. Let's live on the Edge a while.
Mark
--
https://lists.ubuntu.com/archives/ubuntu-announce/2006-April/000064.html
Shannon 信息論及數字通信之父
香農：信息論及數字通信之父
發表日期：2004年12月14日 出處：《計算機教育》第10期 作者：劉瑞挺
20世紀中葉，信息論、控制論、系統論等標新立異的新理論相繼問世，有力地「晃動
」著傳統的科學框架。克勞德·香農是一位美國數學工程師，作為信息論的創始人，人們
認為他是20世紀最偉大的科學家之一。他在通信技術與工程方面的創造性工作，為計算機
與遠程通信奠定了堅實的理論基礎。人們尊崇香農為信息論及數字通信時代的奠基之父。
確實，他對人類的貢獻超過了一般的諾貝爾獲獎者。回顧20世紀的信息革命風暴，經他闡
明的信息概念、連同「比特」這個單位已經深入人心，成為今天日常生活都離不開的詞彙
。
克勞德·香農(Claude Elwood Shannon，1916-2001)1916年4月30日誕生於美國密西
根州的Petoskey。在Gaylord小鎮長大，當時鎮裡只有三千居民。父親是該鎮的法官，他
們父子的姓名完全相同，都是Claude Elwood Shannon。母親是鎮裡的中學校長，姓名是
Mabel Wolf Shannon。他生長在一個有良好教育的環境，不過父母給他的科學影響好像
還不如祖父的影響大。香農的祖父是一位農場主兼發明家，發明過洗衣機和許多農業機械
，這對香農的影響比較直接。此外，香農的家庭與大發明家愛迪生(Thomas Alva Edison
，1847-1931)還有遠親關係。
香農的大部分時間是在貝爾實驗室和MIT(麻省理工學院)度過的。在「功成名就」後
，香農與瑪麗(Mary Elizabeth Moore)1949年3月27日結婚，他們是在貝爾實驗室相識的
，瑪麗當時是數據分析員。他們共有四個孩子：三個兒子Robert、James、 Andrew Moore
和一個女兒Margarita Catherine。後來身邊還有兩個可愛的孫女。
2001年2月24日，香農在馬薩諸塞州Medford辭世，享年85歲。貝爾實驗室和MIT發表
的訃告都尊崇香農為信息論及數字通信時代的奠基之父。
攻讀學位
1936年香農在密西根大學獲得數學與電氣工程學士學位，然後進入MIT念研究生。
1938年香農在MIT獲得電氣工程碩士學位，碩士論文題目是《A Symbolic Analysis
of Relay and Switching Circuits》(繼電器與開關電路的符號分析)。當時他已經注意
到電話交換電路與布爾代數之間的類似性，即把布爾代數的「真」與「假」和電路系統的
「開」與「關」對應起來，並用1和0表示。於是他用布爾代數分析並優化開關電路，這
就奠定了數字電路的理論基礎。哈佛大學的伽登納(Howard Gardner)教授說，「這可能是
本世紀最重要、最著名的一篇碩士論文。」
1940年香農在MIT獲得數學博士學位，而他的博士論文卻是關於人類遺傳學的，題目
是《An Algebra for Theoretical Genetics》(理論遺傳學的代數學)。這說明香農的科
學興趣十分廣泛，後來他在不同的學科方面發表過許多有影響的文章。
在讀學位的同時，他還用部分時間跟溫尼法·布什(Vannevar Bush)教授進行微分分
析器的研究。這種分析器是早期的機械模擬計算機，用於獲得常微分方程的數值解。1941
年香農發表了《Mathematical theory of the differential analyzer》(微分分析器的
數學理論)，他寫道：「大多數結果通過證明的定理形式給出。最重要的是處理了一些條
件，有些條件可以生成一個或多個變量的函數，有些條件可使常微分方程得到解。還給出
了一些注意事項，給出求函數的近似值(不能產生精確值)、求調整率的近似值以及自動控
制速率的方法。」
特殊癖好
大家從照片上看，可能以為克勞德·香農是一位文質彬彬的書生。事實上，他有許多
愛好，特別令人難以置信的是香農可以熟練地玩一套雜技。不是在舞台上，而是在日常生
活中，例如在貝爾實驗室的走廊裡。
從MIT到香農寬敞的住宅只有幾英里。他的住宅裡放滿了各種樂器，諸如有5台鋼琴、
30多種其他樂器，從短笛到各種銅管樂器應有盡有。童年時代，他熱衷於裝無線電收音機
、練莫爾斯電報碼、搞密碼學等。在Gaylord 上中學時他還當過Western Union 的信使。
在他的玩具室裡，有一個雜耍傑作，由3個醜人一起玩11個環、7個球和5個棍子，通
過鐘錶機構驅動。可見當他還是孩子時就喜愛雜耍，香農的一生都迷戀於平衡與控制穩定
性。他的平衡興趣與能力是十分有名的，一個膾炙人口的故事是他經常騎著獨輪車
(unbicycle)、手裡拋著三個球來到貝爾實驗室的大廳。有時他還踩著高蹺騎摩托，使同
事害怕不已。他發明過有兩個座位的獨輪車，不過恐怕沒有人敢與他共享。他還把獨輪車
造成偏離地心的，騎在上面忽高忽低，像鴨子行走似的。
他設計並建造了下棋機器、迷宮老鼠(左圖)、雜耍器械以及智力閱讀機。下國際象棋
的機器包括用3個指頭能抓起棋子的手臂、蜂鳴器以及簡單的記錄裝置。他還建造了供孩
子們到湖邊玩耍的升降機，長約600英尺，設有座位。這些活動表明了香農的主張，即好
奇心比實用性對他的刺激更大。他的名言是：「我感到奇妙的是事物何以集成一體。」
參加工作
1941年香農以數學研究員的身份進入新澤西州的AT&T貝爾電話公司，並在貝爾實驗室
工作到1972年，從24歲到55歲，整整31年。1956年他當了MIT的訪問教授，1958年成為正
式教授，1978年退休。
人們描述香農的生活，白天他總是關起門來工作，晚上則騎著他的獨輪車來到貝爾實
驗室。他的同事D. Slepian寫到：「我們大家都帶著午飯來上班，飯後在黑板上玩玩數學
遊戲，但克勞德很少過來。他總是關起門來工作。但是，如果你要找他，他會非常耐心地
幫助你。他能立刻抓住問題的本質。他真是一位天才，在我認識的人中，我只對他一人使
用這個詞。」
香農與John Riordan一起工作，1942年發表了一篇關於串並聯網絡的雙終端數的論文
。這篇論文擴展了麥克馬洪(Percy A. MacMahon，1854-1929)1892年在Electrician上發
表的論文理論。1948年則創立了信息論(information theory)。
在漫長的歲月，他思考過許多問題。除在普林斯頓高等研究院工作過一年外，主要都
在MIT和Bell Lab度過。需要說明的是，在二次世界大戰時，香農博士也是一位著名的密
碼破譯者(這使筆者想到比他大4歲的圖靈博士)。他在Bell Lab的破譯團隊主要是追蹤德
國飛機和火箭，尤其是在德國火箭對英國進行閃電戰時起了很大作用。1949年香農發表了
另外一篇重要論文《Communication Theory of Secrecy Systems》(保密系統的通信理論
)，正是基於這種工作實踐，它的意義是使保密通信由藝術變成科學。
信息理論
1948年香農在Bell System Technical Journal上發表了《A Mathematical Theory
of Communication 》。論文由香農和威沃共同署名。前輩威沃(Warren Weaver，
1894-1978)當時是洛克菲勒基金會自然科學部的主任，他為文章寫了序言。後來，香農仍
然從事技術工作，而威沃則研究信息論的哲學問題。順便提一句，該論文剛發表時，使用
的是不定冠詞A，收入論文集時改為定冠詞The。
這篇奠基性的論文是建立在香農對通信的觀察上，即「通信的根本問題是報文的再生
，在某一點與另外選擇的一點上報文應該精確地或者近似地重現」。這篇論文建立了信息
論這一學科，給出了通信系統的線性示意模型，即信息源、發送者、信道、接收者、信息
宿，這是一個新思想。此後，通信就考慮為把電磁波發送到信道中，通過發送1和0的比特
流，人們可以傳輸圖像、文字、聲音等等。今天這已司空見慣，但在當時是相當新鮮的。
他建立的信息理論框架和術語已經成為技術標準。他的理論在通信工程師中立即獲得成功
，並刺激了今天信息時代所需要的技術發展。
香農考慮的信息源，產生由有限符號組成的詞。它們通過信道進行傳輸，每個符號開
銷有限的信道時間。這裡涉及到統計學問題，如果xn是第n個符號，它是由固定隨機過程
源xn產生的，香農給出一個分析信號誤差序列的方法，它是傳輸系統固有的，可以通過設
計相應的控制系統控制它。
在這篇論文中，香農首次引入「比特」(bit)一詞，如果在信號中附加額外的比特，
就能使傳輸錯誤得到糾正。按照物理學的習慣，把電流單位叫做「安培」，如果給「比特
流」一個單位名，那麼叫做「香農」是比較合適的。
通信的數學理論是香農在數學與工程研究上的頂峰。他把通信理論的解釋公式化，對
最有效地傳輸信息的問題進行了研究。香農的文章立即被世界各國的通信工程師和數學家
採用，大家詳細地論述它、擴展它、完善它。這個學科立刻繁榮起來，成為科學史上光輝
燦爛的一頁。後來，香農感到由他扮演重要角色而開始與通信革命走得有些過遠。他寫道
：「信息理論可能像一個升空的氣球，其重要性超過了它的實際成就」，真是大師的氣魄
。
熵的概念
香農理論的重要特徵是熵(entropy)的概念，他證明熵與信息內容的不確定程度有等
價關係。熵曾經是波爾茲曼在熱力學第二定律引入的概念，我們可以把它理解為分子運動
的混亂度。信息熵也有類似意義，例如在中文信息處理時，漢字的靜態平均信息熵比較大
，中文是9.65比特，英文是4.03比特。這表明中文的複雜程度高於英文，反映了中文詞義
豐富、行文簡練，但處理難度也大。信息熵大，意味著不確定性也大。因此我們應該深入
研究，以尋求中文信息處理的深層突破。不能盲目認為漢字是世界上最優美的文字，從而
引申出漢字最容易處理的錯誤結論。
眾所周知，質量、能量和信息量是三個非常重要的量。
人們很早就知道用秤或者天平計量物質的質量大小。然而，我們關於熱、燃料、功與
能的計量問題，遲至19世紀中葉，隨著熱功當量的明確和能量守恆定律的建立才逐漸清楚
。能量一詞就是它們的總稱，而能量的計量則通過「卡、焦耳」等新單位的出現而得到解
決。
然而，關於文字、數字、圖畫、聲音的知識已有幾千年歷史了。但是它們的總稱是什
麼，它們如何統一地計量，直到19世紀末還沒有被正確地提出來，更談不上如何去解決了
。20世紀初期，隨著電報、電話、照片、電視、無線電、雷達等的發展，如何計量信號中
信息量的問題被隱約地提上日程。
1928年哈特利(R.V. H. Harley)考慮到從D個彼此不同的符號中取出N個符號並且組成
一個「詞」的問題。如果各個符號出現的概率相同，而且是完全隨機選取的，就可以得到
DN 個不同的詞。從這些詞裡取了特定的一個就對應一個信息量I。哈特利建議用N log D
這個量表示信息量，即I=N log D 。這裡的log表示以10為底的對數。後來，1949年控制
論的創始人維納也研究了度量信息的問題，還把它引向熱力學第二定律。
但是就信息傳輸給出基本數學模型的核心人物還是香農。1948年香農長達數十頁的論
文「通信的數學理論」成了信息論正式誕生的里程碑。在他的通信數學模型中，清楚地提
出信息的度量問題，他把哈特利的公式擴大到概率pi不同的情況，得到了著名的計算信息
熵H的公式：
H=Σ-pi log pi
如果計算中的對數log是以2為底的，那麼計算出來的信息熵就以比特(bit)為單位。
今天在電腦和通信中廣泛使用的字節(Byte)、KB、MB、 GB等詞都是從比特演化而來。「
比特」的出現標誌著人類知道了如何計量信息量。香農的信息論為明確什麼是信息量概念
作出決定性的貢獻。
事實上，香農最初的動機是把電話中的噪音除掉，他給出通信速率的上限，這個結論
首先用在電話上，後來用到光纖，現在又用在無線通信上。我們今天能夠清晰地打越洋電
話或衛星電話，都與通信信道質量的改善密切相關。
科學意義
於是在20世紀中葉，人類終於對三個非常重要的概念：質量、能量、信息量都有了定
量的計量辦法。我們應該牢記，為闡明質量概念做出偉大貢獻的是發現物體力學定律的牛
頓(Sir Isaac Newton，1642-1727)，為闡明能量概念作出偉大貢獻的是熱力學第一定律
的發現者們：邁耳(Julius Robert von Mayer，1814-1878)、焦耳(James Prescott
Joule，1818-1899)、赫爾姆霍茲(Hermann von Helmholtz，1821-1894)、開爾文(Lord
Kelvin，1824-1907)，而為闡明信息概念作出偉大貢獻的就是香農。
20世紀中期隨著原子彈的出現，物理學成為最榮耀的科學學科。在隨後的50年裡，晶
體管、人造衛星、集成電路、電腦的飛躍發展無不與物理學知識的應用有關。但是我們也
驚奇地發現這些新技術都是為提高信息的處理能力服務。光榮的物理學家們忙了半個世紀
，終於發現自己僅是給信息科學當僕人。信息量能進入物理學嗎？但「信息不是物質」！
在物理學的版圖中人們不知道把信息論放到哪裡合適。人類知識體現的這種新的混亂局面
需要我們不斷地澄清。
後來，他在人工智能方面也做了許多工作。例如他設計了一個電子老鼠來解決迷宮問
題。他還研究過四色問題。他設計了國際象棋程序，發表在1950年的論文《Programming
a computer for playing chess》中。1956年在洛斯阿拉莫斯的MANIAC計算機上實現了一
個國際象棋的下棋程序。這一年香農還發表論文說明通用圖靈機可以僅用兩個狀態構建。
榮譽獎項
克勞德·香農在公眾中並不特別知名，但他是使我們的世界能進行立即通信的少數科
學家和思想家之一。他是美國科學院院士、美國工程院院士、英國皇家學會會員、美國哲
學學會會員。他獲得過許多榮譽和獎勵。例如1949年Morris獎、 1955年Ballantine獎、
1962年Kelly獎、1966年的國家科學獎章、IEEE的榮譽獎章、1978年Jaquard獎、1983年
Fritz獎、1985年基礎科學京都獎。他接受的榮譽學位不勝枚舉，不再贅述。
今天，我們懷念香農，要熟悉他的兩大貢獻：一是信息理論、信息熵的概念；另一是
符號邏輯和開關理論。我們更應該學習他好奇心強、重視實踐、追求完美、永不滿足的科
學精神，這是他獲得成功的重要經驗。
--
Reference:
http://www.itedu-tsinghua.com/ReadNews.asp?NewsID=309
發表日期：2004年12月14日 出處：《計算機教育》第10期 作者：劉瑞挺
20世紀中葉，信息論、控制論、系統論等標新立異的新理論相繼問世，有力地「晃動
」著傳統的科學框架。克勞德·香農是一位美國數學工程師，作為信息論的創始人，人們
認為他是20世紀最偉大的科學家之一。他在通信技術與工程方面的創造性工作，為計算機
與遠程通信奠定了堅實的理論基礎。人們尊崇香農為信息論及數字通信時代的奠基之父。
確實，他對人類的貢獻超過了一般的諾貝爾獲獎者。回顧20世紀的信息革命風暴，經他闡
明的信息概念、連同「比特」這個單位已經深入人心，成為今天日常生活都離不開的詞彙
。
克勞德·香農(Claude Elwood Shannon，1916-2001)1916年4月30日誕生於美國密西
根州的Petoskey。在Gaylord小鎮長大，當時鎮裡只有三千居民。父親是該鎮的法官，他
們父子的姓名完全相同，都是Claude Elwood Shannon。母親是鎮裡的中學校長，姓名是
Mabel Wolf Shannon。他生長在一個有良好教育的環境，不過父母給他的科學影響好像
還不如祖父的影響大。香農的祖父是一位農場主兼發明家，發明過洗衣機和許多農業機械
，這對香農的影響比較直接。此外，香農的家庭與大發明家愛迪生(Thomas Alva Edison
，1847-1931)還有遠親關係。
香農的大部分時間是在貝爾實驗室和MIT(麻省理工學院)度過的。在「功成名就」後
，香農與瑪麗(Mary Elizabeth Moore)1949年3月27日結婚，他們是在貝爾實驗室相識的
，瑪麗當時是數據分析員。他們共有四個孩子：三個兒子Robert、James、 Andrew Moore
和一個女兒Margarita Catherine。後來身邊還有兩個可愛的孫女。
2001年2月24日，香農在馬薩諸塞州Medford辭世，享年85歲。貝爾實驗室和MIT發表
的訃告都尊崇香農為信息論及數字通信時代的奠基之父。
攻讀學位
1936年香農在密西根大學獲得數學與電氣工程學士學位，然後進入MIT念研究生。
1938年香農在MIT獲得電氣工程碩士學位，碩士論文題目是《A Symbolic Analysis
of Relay and Switching Circuits》(繼電器與開關電路的符號分析)。當時他已經注意
到電話交換電路與布爾代數之間的類似性，即把布爾代數的「真」與「假」和電路系統的
「開」與「關」對應起來，並用1和0表示。於是他用布爾代數分析並優化開關電路，這
就奠定了數字電路的理論基礎。哈佛大學的伽登納(Howard Gardner)教授說，「這可能是
本世紀最重要、最著名的一篇碩士論文。」
1940年香農在MIT獲得數學博士學位，而他的博士論文卻是關於人類遺傳學的，題目
是《An Algebra for Theoretical Genetics》(理論遺傳學的代數學)。這說明香農的科
學興趣十分廣泛，後來他在不同的學科方面發表過許多有影響的文章。
在讀學位的同時，他還用部分時間跟溫尼法·布什(Vannevar Bush)教授進行微分分
析器的研究。這種分析器是早期的機械模擬計算機，用於獲得常微分方程的數值解。1941
年香農發表了《Mathematical theory of the differential analyzer》(微分分析器的
數學理論)，他寫道：「大多數結果通過證明的定理形式給出。最重要的是處理了一些條
件，有些條件可以生成一個或多個變量的函數，有些條件可使常微分方程得到解。還給出
了一些注意事項，給出求函數的近似值(不能產生精確值)、求調整率的近似值以及自動控
制速率的方法。」
特殊癖好
大家從照片上看，可能以為克勞德·香農是一位文質彬彬的書生。事實上，他有許多
愛好，特別令人難以置信的是香農可以熟練地玩一套雜技。不是在舞台上，而是在日常生
活中，例如在貝爾實驗室的走廊裡。
從MIT到香農寬敞的住宅只有幾英里。他的住宅裡放滿了各種樂器，諸如有5台鋼琴、
30多種其他樂器，從短笛到各種銅管樂器應有盡有。童年時代，他熱衷於裝無線電收音機
、練莫爾斯電報碼、搞密碼學等。在Gaylord 上中學時他還當過Western Union 的信使。
在他的玩具室裡，有一個雜耍傑作，由3個醜人一起玩11個環、7個球和5個棍子，通
過鐘錶機構驅動。可見當他還是孩子時就喜愛雜耍，香農的一生都迷戀於平衡與控制穩定
性。他的平衡興趣與能力是十分有名的，一個膾炙人口的故事是他經常騎著獨輪車
(unbicycle)、手裡拋著三個球來到貝爾實驗室的大廳。有時他還踩著高蹺騎摩托，使同
事害怕不已。他發明過有兩個座位的獨輪車，不過恐怕沒有人敢與他共享。他還把獨輪車
造成偏離地心的，騎在上面忽高忽低，像鴨子行走似的。
他設計並建造了下棋機器、迷宮老鼠(左圖)、雜耍器械以及智力閱讀機。下國際象棋
的機器包括用3個指頭能抓起棋子的手臂、蜂鳴器以及簡單的記錄裝置。他還建造了供孩
子們到湖邊玩耍的升降機，長約600英尺，設有座位。這些活動表明了香農的主張，即好
奇心比實用性對他的刺激更大。他的名言是：「我感到奇妙的是事物何以集成一體。」
參加工作
1941年香農以數學研究員的身份進入新澤西州的AT&T貝爾電話公司，並在貝爾實驗室
工作到1972年，從24歲到55歲，整整31年。1956年他當了MIT的訪問教授，1958年成為正
式教授，1978年退休。
人們描述香農的生活，白天他總是關起門來工作，晚上則騎著他的獨輪車來到貝爾實
驗室。他的同事D. Slepian寫到：「我們大家都帶著午飯來上班，飯後在黑板上玩玩數學
遊戲，但克勞德很少過來。他總是關起門來工作。但是，如果你要找他，他會非常耐心地
幫助你。他能立刻抓住問題的本質。他真是一位天才，在我認識的人中，我只對他一人使
用這個詞。」
香農與John Riordan一起工作，1942年發表了一篇關於串並聯網絡的雙終端數的論文
。這篇論文擴展了麥克馬洪(Percy A. MacMahon，1854-1929)1892年在Electrician上發
表的論文理論。1948年則創立了信息論(information theory)。
在漫長的歲月，他思考過許多問題。除在普林斯頓高等研究院工作過一年外，主要都
在MIT和Bell Lab度過。需要說明的是，在二次世界大戰時，香農博士也是一位著名的密
碼破譯者(這使筆者想到比他大4歲的圖靈博士)。他在Bell Lab的破譯團隊主要是追蹤德
國飛機和火箭，尤其是在德國火箭對英國進行閃電戰時起了很大作用。1949年香農發表了
另外一篇重要論文《Communication Theory of Secrecy Systems》(保密系統的通信理論
)，正是基於這種工作實踐，它的意義是使保密通信由藝術變成科學。
信息理論
1948年香農在Bell System Technical Journal上發表了《A Mathematical Theory
of Communication 》。論文由香農和威沃共同署名。前輩威沃(Warren Weaver，
1894-1978)當時是洛克菲勒基金會自然科學部的主任，他為文章寫了序言。後來，香農仍
然從事技術工作，而威沃則研究信息論的哲學問題。順便提一句，該論文剛發表時，使用
的是不定冠詞A，收入論文集時改為定冠詞The。
這篇奠基性的論文是建立在香農對通信的觀察上，即「通信的根本問題是報文的再生
，在某一點與另外選擇的一點上報文應該精確地或者近似地重現」。這篇論文建立了信息
論這一學科，給出了通信系統的線性示意模型，即信息源、發送者、信道、接收者、信息
宿，這是一個新思想。此後，通信就考慮為把電磁波發送到信道中，通過發送1和0的比特
流，人們可以傳輸圖像、文字、聲音等等。今天這已司空見慣，但在當時是相當新鮮的。
他建立的信息理論框架和術語已經成為技術標準。他的理論在通信工程師中立即獲得成功
，並刺激了今天信息時代所需要的技術發展。
香農考慮的信息源，產生由有限符號組成的詞。它們通過信道進行傳輸，每個符號開
銷有限的信道時間。這裡涉及到統計學問題，如果xn是第n個符號，它是由固定隨機過程
源xn產生的，香農給出一個分析信號誤差序列的方法，它是傳輸系統固有的，可以通過設
計相應的控制系統控制它。
在這篇論文中，香農首次引入「比特」(bit)一詞，如果在信號中附加額外的比特，
就能使傳輸錯誤得到糾正。按照物理學的習慣，把電流單位叫做「安培」，如果給「比特
流」一個單位名，那麼叫做「香農」是比較合適的。
通信的數學理論是香農在數學與工程研究上的頂峰。他把通信理論的解釋公式化，對
最有效地傳輸信息的問題進行了研究。香農的文章立即被世界各國的通信工程師和數學家
採用，大家詳細地論述它、擴展它、完善它。這個學科立刻繁榮起來，成為科學史上光輝
燦爛的一頁。後來，香農感到由他扮演重要角色而開始與通信革命走得有些過遠。他寫道
：「信息理論可能像一個升空的氣球，其重要性超過了它的實際成就」，真是大師的氣魄
。
熵的概念
香農理論的重要特徵是熵(entropy)的概念，他證明熵與信息內容的不確定程度有等
價關係。熵曾經是波爾茲曼在熱力學第二定律引入的概念，我們可以把它理解為分子運動
的混亂度。信息熵也有類似意義，例如在中文信息處理時，漢字的靜態平均信息熵比較大
，中文是9.65比特，英文是4.03比特。這表明中文的複雜程度高於英文，反映了中文詞義
豐富、行文簡練，但處理難度也大。信息熵大，意味著不確定性也大。因此我們應該深入
研究，以尋求中文信息處理的深層突破。不能盲目認為漢字是世界上最優美的文字，從而
引申出漢字最容易處理的錯誤結論。
眾所周知，質量、能量和信息量是三個非常重要的量。
人們很早就知道用秤或者天平計量物質的質量大小。然而，我們關於熱、燃料、功與
能的計量問題，遲至19世紀中葉，隨著熱功當量的明確和能量守恆定律的建立才逐漸清楚
。能量一詞就是它們的總稱，而能量的計量則通過「卡、焦耳」等新單位的出現而得到解
決。
然而，關於文字、數字、圖畫、聲音的知識已有幾千年歷史了。但是它們的總稱是什
麼，它們如何統一地計量，直到19世紀末還沒有被正確地提出來，更談不上如何去解決了
。20世紀初期，隨著電報、電話、照片、電視、無線電、雷達等的發展，如何計量信號中
信息量的問題被隱約地提上日程。
1928年哈特利(R.V. H. Harley)考慮到從D個彼此不同的符號中取出N個符號並且組成
一個「詞」的問題。如果各個符號出現的概率相同，而且是完全隨機選取的，就可以得到
DN 個不同的詞。從這些詞裡取了特定的一個就對應一個信息量I。哈特利建議用N log D
這個量表示信息量，即I=N log D 。這裡的log表示以10為底的對數。後來，1949年控制
論的創始人維納也研究了度量信息的問題，還把它引向熱力學第二定律。
但是就信息傳輸給出基本數學模型的核心人物還是香農。1948年香農長達數十頁的論
文「通信的數學理論」成了信息論正式誕生的里程碑。在他的通信數學模型中，清楚地提
出信息的度量問題，他把哈特利的公式擴大到概率pi不同的情況，得到了著名的計算信息
熵H的公式：
H=Σ-pi log pi
如果計算中的對數log是以2為底的，那麼計算出來的信息熵就以比特(bit)為單位。
今天在電腦和通信中廣泛使用的字節(Byte)、KB、MB、 GB等詞都是從比特演化而來。「
比特」的出現標誌著人類知道了如何計量信息量。香農的信息論為明確什麼是信息量概念
作出決定性的貢獻。
事實上，香農最初的動機是把電話中的噪音除掉，他給出通信速率的上限，這個結論
首先用在電話上，後來用到光纖，現在又用在無線通信上。我們今天能夠清晰地打越洋電
話或衛星電話，都與通信信道質量的改善密切相關。
科學意義
於是在20世紀中葉，人類終於對三個非常重要的概念：質量、能量、信息量都有了定
量的計量辦法。我們應該牢記，為闡明質量概念做出偉大貢獻的是發現物體力學定律的牛
頓(Sir Isaac Newton，1642-1727)，為闡明能量概念作出偉大貢獻的是熱力學第一定律
的發現者們：邁耳(Julius Robert von Mayer，1814-1878)、焦耳(James Prescott
Joule，1818-1899)、赫爾姆霍茲(Hermann von Helmholtz，1821-1894)、開爾文(Lord
Kelvin，1824-1907)，而為闡明信息概念作出偉大貢獻的就是香農。
20世紀中期隨著原子彈的出現，物理學成為最榮耀的科學學科。在隨後的50年裡，晶
體管、人造衛星、集成電路、電腦的飛躍發展無不與物理學知識的應用有關。但是我們也
驚奇地發現這些新技術都是為提高信息的處理能力服務。光榮的物理學家們忙了半個世紀
，終於發現自己僅是給信息科學當僕人。信息量能進入物理學嗎？但「信息不是物質」！
在物理學的版圖中人們不知道把信息論放到哪裡合適。人類知識體現的這種新的混亂局面
需要我們不斷地澄清。
後來，他在人工智能方面也做了許多工作。例如他設計了一個電子老鼠來解決迷宮問
題。他還研究過四色問題。他設計了國際象棋程序，發表在1950年的論文《Programming
a computer for playing chess》中。1956年在洛斯阿拉莫斯的MANIAC計算機上實現了一
個國際象棋的下棋程序。這一年香農還發表論文說明通用圖靈機可以僅用兩個狀態構建。
榮譽獎項
克勞德·香農在公眾中並不特別知名，但他是使我們的世界能進行立即通信的少數科
學家和思想家之一。他是美國科學院院士、美國工程院院士、英國皇家學會會員、美國哲
學學會會員。他獲得過許多榮譽和獎勵。例如1949年Morris獎、 1955年Ballantine獎、
1962年Kelly獎、1966年的國家科學獎章、IEEE的榮譽獎章、1978年Jaquard獎、1983年
Fritz獎、1985年基礎科學京都獎。他接受的榮譽學位不勝枚舉，不再贅述。
今天，我們懷念香農，要熟悉他的兩大貢獻：一是信息理論、信息熵的概念；另一是
符號邏輯和開關理論。我們更應該學習他好奇心強、重視實踐、追求完美、永不滿足的科
學精神，這是他獲得成功的重要經驗。
--
Reference:
http://www.itedu-tsinghua.com/ReadNews.asp?NewsID=309
數學之美３ 隱含馬爾可夫模型在語言處理中的應用
數學之美 系列三 -- 隱含馬爾可夫模型在語言處理中的應用
2006年4月17日 上午 08:01:00
發表者：吳軍，Google 研究員
前言：隱含馬爾可夫模型是一個數學模型，到目前為之，它一直被認為是實現快速精確的
語音識別系統的最成功的方法。複雜的語音識別問題通過隱含馬爾可夫模型能非常簡單地
被表述、解決，讓我不由由衷地感歎數學模型之妙。
自然語言是人類交流信息的工具。很多自然語言處理問題都可以等同於通信系統中的解碼
問題 -- 一個人根據接收到的信息，去猜測發話人要表達的意思。這其實就像通信中，我
們根據接收端收到的信號去分析、理解、還原發送端傳送過來的信息。以下該圖就表示了
一個典型的通信系統：
http://googlechinablog.com/uploaded_images/channel-712509.jpg
其中 s1，s2，s3...表示信息源發出的信號。o1, o2, o3 ... 是接受器接收到的信號。
通信中的解碼就是根據接收到的信號 o1, o2, o3 ...還原出發送的信號 s1，s2，s3...
。
其實我們平時在說話時，腦子就是一個信息源。我們的喉嚨（聲帶），空氣，就是如電線
和光纜般的信道。聽眾耳朵的就是接收端，而聽到的聲音就是傳送過來的信號。根據聲學
信號來推測說話者的意思，就是語音識別。這樣說來，如果接收端是一台計算機而不是人
的話，那麼計算機要做的就是語音的自動識別。同樣，在計算機中，如果我們要根據接收
到的英語信息，推測說話者的漢語意思，就是機器翻譯；如果我們要根據帶有拼寫錯誤的
語句推測說話者想表達的正確意思，那就是自動糾錯。
那麼怎麼根據接收到的信息來推測說話者想表達的意思呢？我們可以利用叫做「隱含馬爾
可夫模型」 （Hidden Markov Model）來解決這些問題。以語音識別為例，當我們觀測到
語音信號 o1,o2,o3 時，我們要根據這組信號推測出發送的句子 s1,s2,s3。顯然，我們
應該在所有可能的句子中找最有可能性的一個。用數學語言來描述，就是在已知
o1,o2,o3,...的情況下，求使得條件概率
P (s1,s2,s3,...|o1,o2,o3....) 達到最大值的那個句子 s1,s2,s3,...
當然，上面的概率不容易直接求出，於是我們可以間接地計算它。利用貝葉斯公式並且省
掉一個常數項，可以把上述公式等價變換成
P(o1,o2,o3,...|s1,s2,s3....) * P(s1,s2,s3,...)
其中
P(o1,o2,o3,...|s1,s2,s3....) 表示某句話 s1,s2,s3...被讀成 o1,o2,o3,...的可能性
, 而
P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能夠成為一個合乎情理的句子的可能性，
所以這個公式的意義是用發送信號為 s1,s2,s3...這個數列的可能性乘以 s1,s2,s3...本
身可以一個句子的可能性，得出概率。
（讀者讀到這裡也許會問，你現在是不是把問題變得更複雜了，因為公式越寫越長了。別
著急，我們現在就來簡化這個問題。）我們在這裡做兩個假設：
第一，s1,s2,s3,... 是一個馬爾可夫鏈，也就是說，si 只由 si-1 決定 (詳見系列一)
；
第二， 第 i 時刻的接收信號 oi 只由發送信號 si 決定（又稱為獨立輸出假設, 即
P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。
那麼我們就可以很容易利用算法 Viterbi 找出上面式子的最大值，進而找出要識別的句
子 s1,s2,s3,...。
滿足上述兩個假設的模型就叫隱含馬爾可夫模型。我們之所以用「隱含」這個詞，是因為
狀態 s1,s2,s3,...是無法直接觀測到的。
隱含馬爾可夫模型的應用遠不只在語音識別中。在上面的公式中，如果我們把
s1,s2,s3,...當成中文，把 o1,o2,o3,...當成對應的英文，那麼我們就能利用這個模型
解決機器翻譯問題； 如果我們把 o1,o2,o3,...當成掃瞄文字得到的圖像特徵，就能利用
這個模型解決印刷體和手寫體的識別。
P (o1,o2,o3,...|s1,s2,s3....) 根據應用的不同而又不同的名稱，在語音識別中它被稱
為「聲學模型」 (Acoustic Model)， 在機器翻譯中是「翻譯模型」 (Translation
Model) 而在拼寫校正中是「糾錯模型」 (Correction Model)。 而P (s1,s2,s3,...) 就
是我們在系列一中提到的語言模型。
在利用隱含馬爾可夫模型解決語言處理問題前，先要進行模型的訓練。 常用的訓練方法
由伯姆（Baum）在60年代提出的，並以他的名字命名。隱含馬爾可夫模型在處理語言問題
早期的成功應用是語音識別。七十年代，當時 IBM 的 Fred Jelinek (賈裡尼克) 和卡內
基·梅隆大學的 Jim and Janet Baker (貝剋夫婦，李開復的師兄師姐) 分別獨立地提出
用隱含馬爾可夫模型來識別語音，語音識別的錯誤率相比人工智能和模式匹配等方法降低
了三倍 (從 30% 到 10%)。 八十年代李開復博士堅持採用隱含馬爾可夫模型的框架， 成
功地開發了世界上第一個大詞彙量連續語音識別系統 Sphinx。
我最早接觸到隱含馬爾可夫模型是幾乎二十年前的事。那時在《隨機過程》（清華「著名
」的一門課）裡學到這個模型，但當時實在想不出它有什麼實際用途。幾年後，我在清華
跟隨王作英教授學習、研究語音識別時，他給了我幾十篇文獻。我印象最深的就是賈裡尼
克和李開復的文章，它們的核心思想就是隱含馬爾可夫模型。複雜的語音識別問題居然能
如此簡單地被表述、解決，我由衷地感歎數學模型之妙。
--
Reference:
http://googlechinablog.com/2006/04/blog-post_17.html
2006年4月17日 上午 08:01:00
發表者：吳軍，Google 研究員
前言：隱含馬爾可夫模型是一個數學模型，到目前為之，它一直被認為是實現快速精確的
語音識別系統的最成功的方法。複雜的語音識別問題通過隱含馬爾可夫模型能非常簡單地
被表述、解決，讓我不由由衷地感歎數學模型之妙。
自然語言是人類交流信息的工具。很多自然語言處理問題都可以等同於通信系統中的解碼
問題 -- 一個人根據接收到的信息，去猜測發話人要表達的意思。這其實就像通信中，我
們根據接收端收到的信號去分析、理解、還原發送端傳送過來的信息。以下該圖就表示了
一個典型的通信系統：
http://googlechinablog.com/uploaded_images/channel-712509.jpg
其中 s1，s2，s3...表示信息源發出的信號。o1, o2, o3 ... 是接受器接收到的信號。
通信中的解碼就是根據接收到的信號 o1, o2, o3 ...還原出發送的信號 s1，s2，s3...
。
其實我們平時在說話時，腦子就是一個信息源。我們的喉嚨（聲帶），空氣，就是如電線
和光纜般的信道。聽眾耳朵的就是接收端，而聽到的聲音就是傳送過來的信號。根據聲學
信號來推測說話者的意思，就是語音識別。這樣說來，如果接收端是一台計算機而不是人
的話，那麼計算機要做的就是語音的自動識別。同樣，在計算機中，如果我們要根據接收
到的英語信息，推測說話者的漢語意思，就是機器翻譯；如果我們要根據帶有拼寫錯誤的
語句推測說話者想表達的正確意思，那就是自動糾錯。
那麼怎麼根據接收到的信息來推測說話者想表達的意思呢？我們可以利用叫做「隱含馬爾
可夫模型」 （Hidden Markov Model）來解決這些問題。以語音識別為例，當我們觀測到
語音信號 o1,o2,o3 時，我們要根據這組信號推測出發送的句子 s1,s2,s3。顯然，我們
應該在所有可能的句子中找最有可能性的一個。用數學語言來描述，就是在已知
o1,o2,o3,...的情況下，求使得條件概率
P (s1,s2,s3,...|o1,o2,o3....) 達到最大值的那個句子 s1,s2,s3,...
當然，上面的概率不容易直接求出，於是我們可以間接地計算它。利用貝葉斯公式並且省
掉一個常數項，可以把上述公式等價變換成
P(o1,o2,o3,...|s1,s2,s3....) * P(s1,s2,s3,...)
其中
P(o1,o2,o3,...|s1,s2,s3....) 表示某句話 s1,s2,s3...被讀成 o1,o2,o3,...的可能性
, 而
P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能夠成為一個合乎情理的句子的可能性，
所以這個公式的意義是用發送信號為 s1,s2,s3...這個數列的可能性乘以 s1,s2,s3...本
身可以一個句子的可能性，得出概率。
（讀者讀到這裡也許會問，你現在是不是把問題變得更複雜了，因為公式越寫越長了。別
著急，我們現在就來簡化這個問題。）我們在這裡做兩個假設：
第一，s1,s2,s3,... 是一個馬爾可夫鏈，也就是說，si 只由 si-1 決定 (詳見系列一)
；
第二， 第 i 時刻的接收信號 oi 只由發送信號 si 決定（又稱為獨立輸出假設, 即
P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。
那麼我們就可以很容易利用算法 Viterbi 找出上面式子的最大值，進而找出要識別的句
子 s1,s2,s3,...。
滿足上述兩個假設的模型就叫隱含馬爾可夫模型。我們之所以用「隱含」這個詞，是因為
狀態 s1,s2,s3,...是無法直接觀測到的。
隱含馬爾可夫模型的應用遠不只在語音識別中。在上面的公式中，如果我們把
s1,s2,s3,...當成中文，把 o1,o2,o3,...當成對應的英文，那麼我們就能利用這個模型
解決機器翻譯問題； 如果我們把 o1,o2,o3,...當成掃瞄文字得到的圖像特徵，就能利用
這個模型解決印刷體和手寫體的識別。
P (o1,o2,o3,...|s1,s2,s3....) 根據應用的不同而又不同的名稱，在語音識別中它被稱
為「聲學模型」 (Acoustic Model)， 在機器翻譯中是「翻譯模型」 (Translation
Model) 而在拼寫校正中是「糾錯模型」 (Correction Model)。 而P (s1,s2,s3,...) 就
是我們在系列一中提到的語言模型。
在利用隱含馬爾可夫模型解決語言處理問題前，先要進行模型的訓練。 常用的訓練方法
由伯姆（Baum）在60年代提出的，並以他的名字命名。隱含馬爾可夫模型在處理語言問題
早期的成功應用是語音識別。七十年代，當時 IBM 的 Fred Jelinek (賈裡尼克) 和卡內
基·梅隆大學的 Jim and Janet Baker (貝剋夫婦，李開復的師兄師姐) 分別獨立地提出
用隱含馬爾可夫模型來識別語音，語音識別的錯誤率相比人工智能和模式匹配等方法降低
了三倍 (從 30% 到 10%)。 八十年代李開復博士堅持採用隱含馬爾可夫模型的框架， 成
功地開發了世界上第一個大詞彙量連續語音識別系統 Sphinx。
我最早接觸到隱含馬爾可夫模型是幾乎二十年前的事。那時在《隨機過程》（清華「著名
」的一門課）裡學到這個模型，但當時實在想不出它有什麼實際用途。幾年後，我在清華
跟隨王作英教授學習、研究語音識別時，他給了我幾十篇文獻。我印象最深的就是賈裡尼
克和李開復的文章，它們的核心思想就是隱含馬爾可夫模型。複雜的語音識別問題居然能
如此簡單地被表述、解決，我由衷地感歎數學模型之妙。
--
Reference:
http://googlechinablog.com/2006/04/blog-post_17.html
數學之美２ 談中文分詞
數學之美 系列二 -- 談談中文分詞
2006年4月10日 上午 08:10:00
發表者: 吳軍， Google 研究員
談談中文分詞
----- 統計語言模型在中文處理中的一個應用
上回我們談到利用統計語言模型進行語言處理，由於模型是建立在詞的基礎上的，對於中
日韓等語言，首先需要進行分詞。例如把句子 「中國航天官員應邀到美國與太空總署官
員開會。」
分成一串詞：
中國 / 航天 / 官員 / 應邀 / 到 / 美國 / 與 / 太空 / 總署 / 官員 / 開會。
最容易想到的，也是最簡單的分詞辦法就是查字典。這種方法最早是由北京航天航空大學
的梁南元教授提出的。
用 「查字典」 法，其實就是我們把一個句子從左向右掃瞄一遍，遇到字典裡有的詞就標
識出來，遇到復合詞（比如 「上海大學」）就找最長的詞匹配，遇到不認識的字串就分
割成單字詞，於是簡單的分詞就完成了。這種簡單的分詞方法完全能處理上面例子中的句
子。八十年代，哈工大的王曉龍博士把它理論化，發展成最少詞數的分詞理論，即一句話
應該分成數量最少的詞串。這種方法一個明顯的不足是當遇到有二義性（有雙重理解意思
）的分割時就無能為力了。比如，對短語 「發展中國家」 正確的分割是「發展-中-國家
」，而從左向右查字典的辦法會將它分割成「發展-中國-家」，顯然是錯了。另外，並非
所有的最長匹配都一定是正確的。比如 「上海大學城書店」的正確分詞應該是 「上海-
大學城-書店，」 而不是 「上海大學-城-書店」。
九十年代以前，海內外不少學者試圖用一些文法規則來解決分詞的二義性問題，都不是很
成功。90年前後，清華大學的郭進博士用統計語言模型成功解決分詞二義性問題，將漢語
分詞的錯誤率降低了一個數量級。
利用統計語言模型分詞的方法，可以用幾個數學公式簡單概括如下：
我們假定一個句子S可以有幾種分詞方法，為了簡單起見我們假定有以下三種：
A1, A2, A3, ..., Ak,
B1, B2, B3, ..., Bm
C1, C2, C3, ..., Cn
其中，A1, A2, B1, B2, C1, C2 等等都是漢語的詞。那麼最好的一種分詞方法應該保證
分完詞後這個句子出現的概率最大。也就是說如果 A1,A2,..., Ak 是最好的分法，那麼
（P 表示概率）：
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 並且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)
因此，只要我們利用上回提到的統計語言模型計算出每種分詞後句子出現的概率，並找出
其中概率最大的，我們就能夠找到最好的分詞方法。
當然，這裡面有一個實現的技巧。如果我們窮舉所有可能的分詞方法並計算出每種可能性
下句子的概率，那麼計算量是相當大的。因此，我們可以把它看成是一個動態規劃（
Dynamic Programming) 的問題，並利用 「維特比」（Viterbi） 算法快速地找到最佳分
詞。
在清華大學的郭進博士以後，海內外不少學者利用統計的方法，進一步完善中文分詞。其
中值得一提的是清華大學孫茂松教授和香港科技大學吳德凱教授的工作。
需要指出的是，語言學家對詞語的定義不完全相同。比如說 「北京大學」，有人認為是
一個詞，而有人認為該分成兩個詞。一個折中的解決辦法是在分詞的同時，找到復合詞的
嵌套結構。在上面的例子中，如果一句話包含 「北京大學」四個字，那麼先把它當成一
個四字詞，然後再進一步找出細分詞 「北京」 和 「大學」。這種方法是最早是郭進在
「Computational Linguistics」 （《計算機語言學》）雜誌上發表的，以後不少系統採
用這種方法。
一般來講，根據不同應用，漢語分詞的顆粒度大小應該不同。比如，在機器翻譯中，顆粒
度應該大一些，「北京大學」就不能被分成兩個詞。而在語音識別中，「北京大學」一般
是被分成兩個詞。因此，不同的應用，應該有不同的分詞系統。Google 的葛顯平博士和
朱安博士，專門為搜索設計和實現了自己的分詞系統。
也許你想不到，中文分詞的方法也被應用到英語處理，主要是手寫體識別中。因為在識別
手寫體時，單詞之間的空格就不很清楚了。中文分詞方法可以幫助判別英語單詞的邊界。
其實，語言處理的許多數學方法通用的和具體的語言無關。在 Google 內，我們在設計語
言處理的算法時，都會考慮它是否能很容易地適用於各種自然語言。這樣，我們才能有效
地支持上百種語言的搜索。
對中文分詞有興趣的讀者，可以閱讀以下文獻：
1. 梁南元
書面漢語自動分詞系統
http://www.touchwrite.com/demo/LiangNanyuan-JCIP-1987.pdf
2. 郭進
統計語言模型和漢語音字轉換的一些新結果
http://www.touchwrite.com/demo/GuoJin-JCIP-1993.pdf
3. 郭進
Critical Tokenization and its Properties
http://acl.ldc.upenn.edu/J/J97/J97-4004.pdf
4. 孫茂松
Chinese word segmentation without using lexicon and hand-crafted training data
http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=980775
--
Refernce:
http://googlechinablog.com/2006/04/blog-post_10.html
2006年4月10日 上午 08:10:00
發表者: 吳軍， Google 研究員
談談中文分詞
----- 統計語言模型在中文處理中的一個應用
上回我們談到利用統計語言模型進行語言處理，由於模型是建立在詞的基礎上的，對於中
日韓等語言，首先需要進行分詞。例如把句子 「中國航天官員應邀到美國與太空總署官
員開會。」
分成一串詞：
中國 / 航天 / 官員 / 應邀 / 到 / 美國 / 與 / 太空 / 總署 / 官員 / 開會。
最容易想到的，也是最簡單的分詞辦法就是查字典。這種方法最早是由北京航天航空大學
的梁南元教授提出的。
用 「查字典」 法，其實就是我們把一個句子從左向右掃瞄一遍，遇到字典裡有的詞就標
識出來，遇到復合詞（比如 「上海大學」）就找最長的詞匹配，遇到不認識的字串就分
割成單字詞，於是簡單的分詞就完成了。這種簡單的分詞方法完全能處理上面例子中的句
子。八十年代，哈工大的王曉龍博士把它理論化，發展成最少詞數的分詞理論，即一句話
應該分成數量最少的詞串。這種方法一個明顯的不足是當遇到有二義性（有雙重理解意思
）的分割時就無能為力了。比如，對短語 「發展中國家」 正確的分割是「發展-中-國家
」，而從左向右查字典的辦法會將它分割成「發展-中國-家」，顯然是錯了。另外，並非
所有的最長匹配都一定是正確的。比如 「上海大學城書店」的正確分詞應該是 「上海-
大學城-書店，」 而不是 「上海大學-城-書店」。
九十年代以前，海內外不少學者試圖用一些文法規則來解決分詞的二義性問題，都不是很
成功。90年前後，清華大學的郭進博士用統計語言模型成功解決分詞二義性問題，將漢語
分詞的錯誤率降低了一個數量級。
利用統計語言模型分詞的方法，可以用幾個數學公式簡單概括如下：
我們假定一個句子S可以有幾種分詞方法，為了簡單起見我們假定有以下三種：
A1, A2, A3, ..., Ak,
B1, B2, B3, ..., Bm
C1, C2, C3, ..., Cn
其中，A1, A2, B1, B2, C1, C2 等等都是漢語的詞。那麼最好的一種分詞方法應該保證
分完詞後這個句子出現的概率最大。也就是說如果 A1,A2,..., Ak 是最好的分法，那麼
（P 表示概率）：
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 並且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)
因此，只要我們利用上回提到的統計語言模型計算出每種分詞後句子出現的概率，並找出
其中概率最大的，我們就能夠找到最好的分詞方法。
當然，這裡面有一個實現的技巧。如果我們窮舉所有可能的分詞方法並計算出每種可能性
下句子的概率，那麼計算量是相當大的。因此，我們可以把它看成是一個動態規劃（
Dynamic Programming) 的問題，並利用 「維特比」（Viterbi） 算法快速地找到最佳分
詞。
在清華大學的郭進博士以後，海內外不少學者利用統計的方法，進一步完善中文分詞。其
中值得一提的是清華大學孫茂松教授和香港科技大學吳德凱教授的工作。
需要指出的是，語言學家對詞語的定義不完全相同。比如說 「北京大學」，有人認為是
一個詞，而有人認為該分成兩個詞。一個折中的解決辦法是在分詞的同時，找到復合詞的
嵌套結構。在上面的例子中，如果一句話包含 「北京大學」四個字，那麼先把它當成一
個四字詞，然後再進一步找出細分詞 「北京」 和 「大學」。這種方法是最早是郭進在
「Computational Linguistics」 （《計算機語言學》）雜誌上發表的，以後不少系統採
用這種方法。
一般來講，根據不同應用，漢語分詞的顆粒度大小應該不同。比如，在機器翻譯中，顆粒
度應該大一些，「北京大學」就不能被分成兩個詞。而在語音識別中，「北京大學」一般
是被分成兩個詞。因此，不同的應用，應該有不同的分詞系統。Google 的葛顯平博士和
朱安博士，專門為搜索設計和實現了自己的分詞系統。
也許你想不到，中文分詞的方法也被應用到英語處理，主要是手寫體識別中。因為在識別
手寫體時，單詞之間的空格就不很清楚了。中文分詞方法可以幫助判別英語單詞的邊界。
其實，語言處理的許多數學方法通用的和具體的語言無關。在 Google 內，我們在設計語
言處理的算法時，都會考慮它是否能很容易地適用於各種自然語言。這樣，我們才能有效
地支持上百種語言的搜索。
對中文分詞有興趣的讀者，可以閱讀以下文獻：
1. 梁南元
書面漢語自動分詞系統
http://www.touchwrite.com/demo/LiangNanyuan-JCIP-1987.pdf
2. 郭進
統計語言模型和漢語音字轉換的一些新結果
http://www.touchwrite.com/demo/GuoJin-JCIP-1993.pdf
3. 郭進
Critical Tokenization and its Properties
http://acl.ldc.upenn.edu/J/J97/J97-4004.pdf
4. 孫茂松
Chinese word segmentation without using lexicon and hand-crafted training data
http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=980775
--
Refernce:
http://googlechinablog.com/2006/04/blog-post_10.html
信息熵（Entropy）到底是用來衡量什麼的？
信息熵（Entropy）到底是用來衡量什麼的？——與Philip ZHANG商榷
思明
Philip ZHANG先生在反駁彭小明的時候，提出一個觀點，他說：「 就語言文
字來說，整體效率不是用民族主義來衡量的，而是用信息熵（Entropy）來衡量
的。」
張先生介紹說：
計算文字效率的基本公式是：
H＝－log2（P）
H 為信息熵的值（或叫信息量），單位是比特（bit）。
在這基點上，他根據資料引證：
英文的平均信息熵是 4.03 比特，
法文的平均信息熵是3.98，
西班牙文的是 4.01，
德文的是 4.10，
俄文的是 4.8，
而中文的平均信息熵是 9.65比特
於是，「漢字是落後的，無論是簡體還是繁體」就成了他輕鬆得到的結論。
其實，要反駁他的結論是一點也不困難的，甚至可以說是非常輕鬆的——只要
知道什麼是一種文字的「平均信息熵」。
只可惜，張先生把方向正好弄錯了180度。
公式是有的，叫做平均信息熵也確實。但是根本就不是文字效率的基本公式，
而是在通訊中編碼的碼長的效率！提出這公式，申農是用以研究信息編碼的。說得
通俗一點，就是要（在可能有噪音的情況下）把已方（信息源）的信息進行標準化
編碼（比如，0－1化），然後傳送出去，對方接收，解碼，恢復成原來的信息。
研究的重點，是多長的一組碼為合理——如果太短，無法正確還原，如果太
長，就有冗余。
在接下去談以前，先要強調，是碼長的節約或冗余，不是信息本身的節約或冗
余。比方說，如果拿盡用分幣買東西，分幣已經多得很，錢卻不一定夠。這是兩回
事。
以英語為例，信息源集合大體是26個字母加上一個空格，這是基本集合。要傳
送給任何對方（比如用莫爾斯電碼），碼長要幾位「0－1」？滿打滿算，是五位。
要是用「平均信息的觀點」來研究處理，會發現：有些字母出現得經常，另外
一些比較不經常用，所以信息源是有點特徵的，這特徵就是信息含量不「飽滿」。
通俗地說，如果英文字母中只有一部分常用，其他罕用，通過巧妙編碼可以把碼長
縮為4個多一點點。實際上由於目前通訊瓶頸已經不像半世紀以前那樣重要，電腦
裡的正規編碼方案全是冗余方案，並無人真正採用緊縮方案，連考慮的價值也沒
有。
那麼怎樣計算信息量又是怎麼回事呢？
以電腦的0－1編碼方法為例，如果「0」和「1」以均等機會出現，P就是1/2，
對數就是－1，H就是1。因此它的信息含量就是1個比特（bit）。如果出現得不均
勻（比如說基本是「0」出現，偶爾才有「1」出現），那麼「0」的P值接近於1，
其對數自然接近於0；另外的「1」的P值接近於0，對數就接近於負無窮，經過加權
平均，（這種無窮乘以0的極限，自然可以用（數學上的計算）方法求出）信息比1
個比特（bit）更小。
因此，任何一組碼的元素（比如英文字母），在最有效使用的情況下，可以傳
達的信息量最大，等於log2（N）（以源碼的元數為N，例如英文的滿荷值為4.75；
俄文為5.08；按照中文的字數，小字庫為12多，大字庫為14多。等等）。
大家知道，英文字母平均信息熵是 4.03 比特，說明它有一點「浪費」（因為
2的4次方是16，這只相當於均勻使用了16個字母）。如果英文的「平均信息量」少
到1或者2，就相當於只有兩個或者四個字母了。所以張先生對英文的表揚可真的一
點意義沒有。
那麼，假設我們的祖先造的漢字只用了很少的部分，平均信息熵就會很小，比
如，要是只用「是，不」二字而其他文字統統不用，那就只要有一個比特就夠。
張先生以為「平均信息熵」越少越好，是犯了一個「方向的錯誤」。可見，張
先生在信息科學上的知識是多麼脆弱，多麼不精確！用這樣的東西作為「證據」，
要我們信改革有幾千年歷史的漢字很是必要，太不負責！
張先生又引用說：
本世紀四十年代，申農和霍夫曼等科學家提出了信息熵理論和方法，基本定理
是：在一種非擴展的無記憶信息源中，字符編碼的長度不能小於信息源的熵。這個
定理適合所有的語言文字，是計算機和網絡通訊的科學技術基礎和工程設計的基本
依據。
這句話全對。不知道張先生是哪裡引用來的，但是張先生顯然不理解其含義。
這話說明的是什麼？原來，這不過是說，因為英文的平均信息熵是4多一點，因此
作為通訊用的英文字符集的實用長度也至少要有那麼長。德文和俄文的字母比英文
多幾個，它們多含一點信息量是正常的。德國人之不改動字母，絕對不是因為信息
量多還是少的緣故。多更不是壞事。其實，大家知道在電腦裡英文字母、德文、俄
文統統用的是8位（8比特）。8位的滿存儲是256個字符，大家相聚在一起，誰多用
誰少用，不會去斤斤計較。德國人也讀英文，俄國人也用德文，更沒有人用它來比
較「語言的優劣」。
中文，一開始是用了雙字節的（即16比特），滿存儲是6萬多，現在中文用了
約1/3（當然其他文種還要用）。這和中文的效率並無直接的聯繫。如果，用一個
漢字表達的「意思」的量，如果（平均起來）和一個英文字母一樣多，那漢字就真
太落後了！
真是這樣？我們的漢字真會這麼落後？比如「我」是兩個字節，「I」是一
個字節。這就是中文不如英文的「唯一例子」了。但是「人、是、起、而、日、
月、用、無、……」這幾百成千個單字（嚴格說所有漢字）英文裡都只要一個字母
嗎？不是。英文的字母只有26個，充其量只能有這26個比中文好——可惜英文的單
字母詞只有一個「I」，一個「a」（意義太簡單，還無獨立使用權）其他的（例如
of，on，to，we，me，go，……）能和漢字打平就好。請注意，在用26個字母構成
的676種二字母組合中，有意義的少之又少（比如aa，ab，ac，ad，ae，……就幾
乎全無意義）。所以，如果有人用漢字對比英文（在同樣意義的詞彙）的byte數，
十有八九漢字要「節約」得多！
自然英文通過製造縮寫的辦法解決了不少問題——UN，USA，WTO，所以說漢字
絕對優越也要謹慎。
最最可笑的是，如果要按照「用拼音」的建議把中文翻譯成拼音（即使那聲調
的符號省去、詞彙連寫等方法全用上），那byte數要大大增加了，雖然那「平均信
息熵」也許還降低了（總不超過5）。打個比方，改用拼音的張先生可以告訴別
人，我的平均信息量已經降低到4多一點（就是說『我現在終於只要用一分的硬幣
買東西了，雖然我每年的開支因此增加了三倍，我才不在乎！』）。因為拼音裡除
了a、e以外，是不許單獨字母成字的，就是a、e，還留空格。所以如果說要用拼音
作文字，在浪費字節上是天下第一的「文字」——看不易懂還暫且不說！在這個意
義上說，「從一九八九年開始，《人民日報》等報刊就用同樣的手法抨擊中文改
革，連續發表文章鼓吹『漢字優越』，說中文改革是盲目西化和導致中國文化傳統
消亡，等等。」真是做得對極了，好極了！
張先生又說：
中文的平均信息熵是 9.65比特，在計算機信息作業的時候，漢字的每個字符
需》要兩個字節的空間，因而中文的信息處理和傳遞的整體效率比英文等拼音文字
的效率要低得多。
這是完全違背基本常識的。套用他的汽車比喻，這好像是說：「獨輪車無疑比
12輪大卡車節省10倍，走的路只有1/10」；又好比說「用一元錢的鈔票買東西比用
五角錢的貴一倍」；等等……
儘管我們已經說明漢字實際上比英文和其他拼音文字只簡不冗（從佔用字節數
的角度看），語言學上的問題仍然相當複雜，誰簡誰繁似乎也還難以成為一種語言
優劣的絕對定論。比如世界語、數學語言、電腦的彙編，顯然都極簡單而且規範，
可是要代替自然的生活語言明明是不行的。這個問題我們暫且不討論。
張先生的文章還存在許多其它問題，比如他說：
不管誰在使用和在哪裡使用，也不管使用者的民族感情如何，這些文字的信息
熵還是它們的信息熵。
他根本就不知道，除了整個「民族」的平均信息熵以外，人人的語言都有其獨
特的信息熵。比如「不高興」先生，碰到事情一般都是不高興；總說「喳」的太
監，他們的語言中的平均信息熵都很小。同樣的字符集而熵小，這絕對不是什麼先
進，是貧乏。
附帶說一句，張先生犯的這個錯誤，國內某一派的「著名語言學家」在十多年
前已經犯過，也被人尖刻批評過。他們既無法理解（大概對於數學絕緣）也不吱
聲，以至於十年過去後，他們的文改信徒還不斷重複這錯誤。可悲又可歎，若把語
言文字工作交給這等「既不內行又不熱心」的人！
[中國研究/zgyj1999/xiamian.htm]
--
Reference:
http://boole.cs.iastate.edu/book/5-%BC%AF(%CE%C4%D1%A7)/2-%CD%F8%C2%E7%D4%D3%D6%BE/%D6%D0%B9%FA%D1%D0%BE%BF/%D6%D0%B9%FA%D1%D0%BE%BF/www.topsin.net/zgyj/zgyj1999/zgyj9910/g991007e.htm
思明
Philip ZHANG先生在反駁彭小明的時候，提出一個觀點，他說：「 就語言文
字來說，整體效率不是用民族主義來衡量的，而是用信息熵（Entropy）來衡量
的。」
張先生介紹說：
計算文字效率的基本公式是：
H＝－log2（P）
H 為信息熵的值（或叫信息量），單位是比特（bit）。
在這基點上，他根據資料引證：
英文的平均信息熵是 4.03 比特，
法文的平均信息熵是3.98，
西班牙文的是 4.01，
德文的是 4.10，
俄文的是 4.8，
而中文的平均信息熵是 9.65比特
於是，「漢字是落後的，無論是簡體還是繁體」就成了他輕鬆得到的結論。
其實，要反駁他的結論是一點也不困難的，甚至可以說是非常輕鬆的——只要
知道什麼是一種文字的「平均信息熵」。
只可惜，張先生把方向正好弄錯了180度。
公式是有的，叫做平均信息熵也確實。但是根本就不是文字效率的基本公式，
而是在通訊中編碼的碼長的效率！提出這公式，申農是用以研究信息編碼的。說得
通俗一點，就是要（在可能有噪音的情況下）把已方（信息源）的信息進行標準化
編碼（比如，0－1化），然後傳送出去，對方接收，解碼，恢復成原來的信息。
研究的重點，是多長的一組碼為合理——如果太短，無法正確還原，如果太
長，就有冗余。
在接下去談以前，先要強調，是碼長的節約或冗余，不是信息本身的節約或冗
余。比方說，如果拿盡用分幣買東西，分幣已經多得很，錢卻不一定夠。這是兩回
事。
以英語為例，信息源集合大體是26個字母加上一個空格，這是基本集合。要傳
送給任何對方（比如用莫爾斯電碼），碼長要幾位「0－1」？滿打滿算，是五位。
要是用「平均信息的觀點」來研究處理，會發現：有些字母出現得經常，另外
一些比較不經常用，所以信息源是有點特徵的，這特徵就是信息含量不「飽滿」。
通俗地說，如果英文字母中只有一部分常用，其他罕用，通過巧妙編碼可以把碼長
縮為4個多一點點。實際上由於目前通訊瓶頸已經不像半世紀以前那樣重要，電腦
裡的正規編碼方案全是冗余方案，並無人真正採用緊縮方案，連考慮的價值也沒
有。
那麼怎樣計算信息量又是怎麼回事呢？
以電腦的0－1編碼方法為例，如果「0」和「1」以均等機會出現，P就是1/2，
對數就是－1，H就是1。因此它的信息含量就是1個比特（bit）。如果出現得不均
勻（比如說基本是「0」出現，偶爾才有「1」出現），那麼「0」的P值接近於1，
其對數自然接近於0；另外的「1」的P值接近於0，對數就接近於負無窮，經過加權
平均，（這種無窮乘以0的極限，自然可以用（數學上的計算）方法求出）信息比1
個比特（bit）更小。
因此，任何一組碼的元素（比如英文字母），在最有效使用的情況下，可以傳
達的信息量最大，等於log2（N）（以源碼的元數為N，例如英文的滿荷值為4.75；
俄文為5.08；按照中文的字數，小字庫為12多，大字庫為14多。等等）。
大家知道，英文字母平均信息熵是 4.03 比特，說明它有一點「浪費」（因為
2的4次方是16，這只相當於均勻使用了16個字母）。如果英文的「平均信息量」少
到1或者2，就相當於只有兩個或者四個字母了。所以張先生對英文的表揚可真的一
點意義沒有。
那麼，假設我們的祖先造的漢字只用了很少的部分，平均信息熵就會很小，比
如，要是只用「是，不」二字而其他文字統統不用，那就只要有一個比特就夠。
張先生以為「平均信息熵」越少越好，是犯了一個「方向的錯誤」。可見，張
先生在信息科學上的知識是多麼脆弱，多麼不精確！用這樣的東西作為「證據」，
要我們信改革有幾千年歷史的漢字很是必要，太不負責！
張先生又引用說：
本世紀四十年代，申農和霍夫曼等科學家提出了信息熵理論和方法，基本定理
是：在一種非擴展的無記憶信息源中，字符編碼的長度不能小於信息源的熵。這個
定理適合所有的語言文字，是計算機和網絡通訊的科學技術基礎和工程設計的基本
依據。
這句話全對。不知道張先生是哪裡引用來的，但是張先生顯然不理解其含義。
這話說明的是什麼？原來，這不過是說，因為英文的平均信息熵是4多一點，因此
作為通訊用的英文字符集的實用長度也至少要有那麼長。德文和俄文的字母比英文
多幾個，它們多含一點信息量是正常的。德國人之不改動字母，絕對不是因為信息
量多還是少的緣故。多更不是壞事。其實，大家知道在電腦裡英文字母、德文、俄
文統統用的是8位（8比特）。8位的滿存儲是256個字符，大家相聚在一起，誰多用
誰少用，不會去斤斤計較。德國人也讀英文，俄國人也用德文，更沒有人用它來比
較「語言的優劣」。
中文，一開始是用了雙字節的（即16比特），滿存儲是6萬多，現在中文用了
約1/3（當然其他文種還要用）。這和中文的效率並無直接的聯繫。如果，用一個
漢字表達的「意思」的量，如果（平均起來）和一個英文字母一樣多，那漢字就真
太落後了！
真是這樣？我們的漢字真會這麼落後？比如「我」是兩個字節，「I」是一
個字節。這就是中文不如英文的「唯一例子」了。但是「人、是、起、而、日、
月、用、無、……」這幾百成千個單字（嚴格說所有漢字）英文裡都只要一個字母
嗎？不是。英文的字母只有26個，充其量只能有這26個比中文好——可惜英文的單
字母詞只有一個「I」，一個「a」（意義太簡單，還無獨立使用權）其他的（例如
of，on，to，we，me，go，……）能和漢字打平就好。請注意，在用26個字母構成
的676種二字母組合中，有意義的少之又少（比如aa，ab，ac，ad，ae，……就幾
乎全無意義）。所以，如果有人用漢字對比英文（在同樣意義的詞彙）的byte數，
十有八九漢字要「節約」得多！
自然英文通過製造縮寫的辦法解決了不少問題——UN，USA，WTO，所以說漢字
絕對優越也要謹慎。
最最可笑的是，如果要按照「用拼音」的建議把中文翻譯成拼音（即使那聲調
的符號省去、詞彙連寫等方法全用上），那byte數要大大增加了，雖然那「平均信
息熵」也許還降低了（總不超過5）。打個比方，改用拼音的張先生可以告訴別
人，我的平均信息量已經降低到4多一點（就是說『我現在終於只要用一分的硬幣
買東西了，雖然我每年的開支因此增加了三倍，我才不在乎！』）。因為拼音裡除
了a、e以外，是不許單獨字母成字的，就是a、e，還留空格。所以如果說要用拼音
作文字，在浪費字節上是天下第一的「文字」——看不易懂還暫且不說！在這個意
義上說，「從一九八九年開始，《人民日報》等報刊就用同樣的手法抨擊中文改
革，連續發表文章鼓吹『漢字優越』，說中文改革是盲目西化和導致中國文化傳統
消亡，等等。」真是做得對極了，好極了！
張先生又說：
中文的平均信息熵是 9.65比特，在計算機信息作業的時候，漢字的每個字符
需》要兩個字節的空間，因而中文的信息處理和傳遞的整體效率比英文等拼音文字
的效率要低得多。
這是完全違背基本常識的。套用他的汽車比喻，這好像是說：「獨輪車無疑比
12輪大卡車節省10倍，走的路只有1/10」；又好比說「用一元錢的鈔票買東西比用
五角錢的貴一倍」；等等……
儘管我們已經說明漢字實際上比英文和其他拼音文字只簡不冗（從佔用字節數
的角度看），語言學上的問題仍然相當複雜，誰簡誰繁似乎也還難以成為一種語言
優劣的絕對定論。比如世界語、數學語言、電腦的彙編，顯然都極簡單而且規範，
可是要代替自然的生活語言明明是不行的。這個問題我們暫且不討論。
張先生的文章還存在許多其它問題，比如他說：
不管誰在使用和在哪裡使用，也不管使用者的民族感情如何，這些文字的信息
熵還是它們的信息熵。
他根本就不知道，除了整個「民族」的平均信息熵以外，人人的語言都有其獨
特的信息熵。比如「不高興」先生，碰到事情一般都是不高興；總說「喳」的太
監，他們的語言中的平均信息熵都很小。同樣的字符集而熵小，這絕對不是什麼先
進，是貧乏。
附帶說一句，張先生犯的這個錯誤，國內某一派的「著名語言學家」在十多年
前已經犯過，也被人尖刻批評過。他們既無法理解（大概對於數學絕緣）也不吱
聲，以至於十年過去後，他們的文改信徒還不斷重複這錯誤。可悲又可歎，若把語
言文字工作交給這等「既不內行又不熱心」的人！
[中國研究/zgyj1999/xiamian.htm]
--
Reference:
http://boole.cs.iastate.edu/book/5-%BC%AF(%CE%C4%D1%A7)/2-%CD%F8%C2%E7%D4%D3%D6%BE/%D6%D0%B9%FA%D1%D0%BE%BF/%D6%D0%B9%FA%D1%D0%BE%BF/www.topsin.net/zgyj/zgyj1999/zgyj9910/g991007e.htm
NUMB3RS
看過 CSI 吧！NUMB3RS 是類似的影集，主角 Don Eppes 是 FBI agent,
他弟弟 Charlie Eppes 則是個天才數學家，Charlie 透過數學理論與
模型去剖析犯罪事件背後的真相及犯罪 pattern ，影集當中提到很多數
學理論，雖然有些講的很豪洨，但又好像言之有物。
另外，除了看影集之外，還可以上網看 Texas Instruments 主導的
""We All Use Math Every Day"" 數學教育計畫，透過影集的內容，把其
中一些簡單的數學拿出來討論，當然不是都很簡單，不過至少你不會看到
證明黎曼猜想的歷史難題 orz
還真是寓教於樂啊 XD~~
The official ""We All Use Math Every Day"" web site
http://www.cbs.com/primetime/numb3rs/ti/
台灣的 AXN 有撥，可是好像快撥完了
http://www.axn-taiwan.com/shows/1002,22,41,29200.html
動物也騎的到，找的到我也有:)
--
Reference:
http://www.cbs.com/primetime/numb3rs/index.shtml
他弟弟 Charlie Eppes 則是個天才數學家，Charlie 透過數學理論與
模型去剖析犯罪事件背後的真相及犯罪 pattern ，影集當中提到很多數
學理論，雖然有些講的很豪洨，但又好像言之有物。
另外，除了看影集之外，還可以上網看 Texas Instruments 主導的
""We All Use Math Every Day"" 數學教育計畫，透過影集的內容，把其
中一些簡單的數學拿出來討論，當然不是都很簡單，不過至少你不會看到
證明黎曼猜想的歷史難題 orz
還真是寓教於樂啊 XD~~
The official ""We All Use Math Every Day"" web site
http://www.cbs.com/primetime/numb3rs/ti/
台灣的 AXN 有撥，可是好像快撥完了
http://www.axn-taiwan.com/shows/1002,22,41,29200.html
動物也騎的到，找的到我也有:)
--
Reference:
http://www.cbs.com/primetime/numb3rs/index.shtml
2006年4月29日 星期六
Ext2 Installable File System For Windows
* 支援 Ext2, Ext3 讀 & ""寫""
* 支援 Large File Feature! ( 安裝時需要勾選 )
If you want to check or modify whether the large file feature of ext2fs.sys
is enabled, it is configured at the registry key
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Ext2fs\Parameters
by the registry value
TriggerLargeFileFeature
If that (DWORD-) value exists and is not equal to 0x0000 the large file
feature is enabled. (Changes will take effect on next reboot.)
* ""不"" 支援 access rights
* ""不"" 支援 UTF-8 或與使用中 Windows 不同的 code pages, 會使用 Windows
預設的 code pages
* ""不"" 支援磁碟重組
* ""不"" 支援 Windows 在 Ext2 分區上開機
* ""不"" 支援 LVM
--
Reference:
http://www.fs-driver.org/index.html
* 支援 Large File Feature! ( 安裝時需要勾選 )
If you want to check or modify whether the large file feature of ext2fs.sys
is enabled, it is configured at the registry key
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Ext2fs\Parameters
by the registry value
TriggerLargeFileFeature
If that (DWORD-) value exists and is not equal to 0x0000 the large file
feature is enabled. (Changes will take effect on next reboot.)
* ""不"" 支援 access rights
* ""不"" 支援 UTF-8 或與使用中 Windows 不同的 code pages, 會使用 Windows
預設的 code pages
* ""不"" 支援磁碟重組
* ""不"" 支援 Windows 在 Ext2 分區上開機
* ""不"" 支援 LVM
--
Reference:
http://www.fs-driver.org/index.html
2006年4月23日 星期日
Ext2fs-Undeletion
◇ [chat] 搶救過去!!!! (ext2 undelete)
作者: thhsieh (居士) 看板: Linux
標題: [chat] 搶救過去!!!! (ext2 undelete)
時間: Tue Feb 2 14:53:04 1999
以下內容可能很多人早就知道了，但我想可能還是對某些人有用，所以就
post 上來大家參考 (嗯! 最近算物理問題算得煩透了，就當我無聊灌灌
水吧 :-)))
===========================================================================
發信人: thhsieh (居士), 信區: SM
標 題: [Sys] 搶救過去!!!! (ext2 undelete)
發信站: 冷月流蘇BBS驛站 (Mon Feb 1 17:21:11 1999) , 轉信
本系的 BBS 系統真是多災多難 (嗯 .... 其實是因為我的疏忽，才會這麼多災
多難 ....) ，繼這幾日系統時間不正確，造成許多人的 ID 被誤砍後，又一次
因系統設定上的問題，將 BBS 的重要備份檔給殺了。這件事是學弟發現後告訴
我的，當我上站來一見到他的 mail, 當真是欲哭無淚，差點沒去撞牆。那個備
分檔有多重要呢? 這麼說吧! 所有等待我們恢復舊信件的使用者資料全在裏頭。
那時已是週六晚 11:00 左右，我一邊想著要編一套說辭向大家解釋無法替大家
恢復舊信件與設定了，一邊還在想是否能夠挽回局面。大家知道， UNIX like
的系統是很難像 M$ 的系統一樣，做到 undelete 的，所有網管前輩都曾再三
警告我們，要小心! 小心! 砍檔之前三思而後行，砍了之後再後悔也沒用。雖
然我已漸漸做到砍檔三思而後行，但之次誤砍事件是系統在背景中定時執行的，
等到我找出原因時已是檔案被砍後一個多小時。
我憑著一點點的印象，想起在網路上，有人討論過在 Linux ext2 filesystem
中 undelete 的可能性，但我所見到的多半是負面的答案，但好像真的有人做過
這件事，於是我第一個所做的，就是馬上將該檔案原來所在的 partition mount
成 read-only, 禁止任何的寫入動作，不是怕再有檔案被誤砍 (因為已沒什麼可
砍的了) ，而是怕有新檔案寫進來，新資料可能會覆蓋到舊資料原本存在的磁區
(block) 。我們現在唯一個指望，就是企圖將檔案原來存在的磁區一個個找回來，
並且「希望」這些磁區上的舊資料都還在，然後將這些磁區串成一個檔案。
終於被我找到了!! 原來這方面的技術文件就存在我自己的系統中 :-))
/usr/doc/HOWTO/mini/Ext2fs-Undeletion.gz
於是我就按照這份文件的指示一步步來，總算將一個長達 8MB 的壓縮檔救回了
99%, 還有一個長達 1.1 MB 的壓縮檔完整無缺地救了回來。感謝上帝、 Linux
的設計者、寫那篇文件的作者、曾經討論過此技術的人、以及 Linux 如此優秀
的 ext2 filesystem, 讓我有機會搶救過去。現在，我將我的搶救步驟做一個整
理讓大家參考，希望有派得上用場的時候 (喔! 不，最好是希望大家永遠不要有
機會用到以下的步數 :-)))
************************************************************************
在此嚴正聲明!! 寫這篇文章的目的，是給那些處於萬不得已情況下的人們，有
一個挽回的機會，並不意味著從此我們就可以大意，砍檔不需要三思。前面提
到，我有一個檔案無法 100% 救回，事實上，長達 8MB 的檔案能救回 99% 已是
幸運中的幸運，一般的情況下若能救回 70% - 80% 已經要愉笑了。所以，不要
指望 undelete 能救回一切。預防勝於治療! 請大家平時就養成好習慣，砍檔前
請三思!!!
************************************************************************
我們能救回的機會有多大? 在 kernel-2.0.X 系列中 (本站所用的 kernel 是
2.0.33) ，取決以下兩點:
1. 檔案原來所在的磁區是否沒有被覆寫?
2. 檔案是否完全連續?
第一點我們可以與時間競賽，就是當一發現檔案誤砍時，要以最快的速度 umount
該 filesystem, 或將該 filesystem remount 成唯讀。就這次的情況而言，檔案
誤砍是在事發一個小時後才發現的，但由於該 filesystem 寫入的機會很少 (我
幾乎可確定一天才只有一次，做 backup)，所以第一點算是過關了。
第二點真的是要聽天由命了，就本站所使用的 kernel, 必須要在假設「長檔案」所
佔的 block 完全連續的情況下，才有可能完全救回來! 一個 block 是 1024 bytes,
長達 8 MB 的檔案就有超過 8000 個 block。在經常讀寫的 filesystem 中，可以
想見長檔案很難完全連續，但在我們的系統中，這一點似乎又多了幾分指望。同時，
Linux ext2 如此精良的 filesystem, 能做到前 7950 多個 block 都連續，這一點
也功不可沒。
好了，以下我就講一下我的步驟。
1. mount filesystem readonly:
該檔案的位置原來是在 /var/hda/backup/home/bbs 下，我們系統的 filesystem
組態是:
root@bbs:/home/ftp/rescue# df
Filesystem 1024-blocks Used Available Capacity Mounted on
/dev/sda1 396500 312769 63250 83% /
/dev/sda3 777410 537633 199615 73% /home
/dev/hda1 199047 36927 151840 20% /var/hda
/dev/hda2 1029023 490998 485710 50% /home/ftp
因此 /var/hda 這個 filesystem 要馬上 mount 成 readonly (以下請用 root 身
份):
mount -o remount,ro /var/hda
當然也可以直接 umount 它，但有時候可能有某些 process 正在此 filesystem
下運作，您可能無法直接 umount 它。因此我選擇 mount readonly。但您也可以
用:
fuser -v -m /usr
看一下目前是那些 process 在用這個 filesystem, 然後一一砍掉，再 umount。
2. 執行
echo lsdel | debugfs /dev/hda1 | less
看一下該 filesystem 最近被砍的 inode (檔案) 有那些 (為什麼是 /dev/hda1?
請見上頭的 df 列表)? 在這裏要說一下，在 UNIX like 的系統中，所有的檔案都
有一個 inode 指向它， inode 中記錄了檔案的重要資訊，如大小、時間、屬性等
等。就我們的系統而言，其列示如下:
debugfs: 92 deleted inodes found.
Inode Owner Mode Size Blocks Time deleted
.................................................................
29771 0 100644 1255337 14/ 14 Sat Jan 30 22:37:10 1999
29772 0 100644 5161017 14/ 14 Sat Jan 30 22:37:10 1999
29773 0 100644 8220922 14/ 14 Sat Jan 30 22:37:10 1999
29774 0 100644 5431 6/ 6 Sat Jan 30 22:37:10 1999
請注意! inode 裏頭不會記錄檔案的檔名，檔名是記錄在該檔案所在的目錄的
data block 中，故在此我們見不到。因此，我們必須要在檔案大小、被砍時間
等資訊中判斷出要救回的檔案是那一個。在此，我們要救回 29773 這個 inode。
3. 執行
echo "stat <29773>"" | debugfs /dev/hda1
列出該 inode 的所有資訊，如下:
debugfs: stat <29773>
Inode: 29773 Type: regular Mode: 0644 Flags: 0x0 Version: 1
User: 0 Group: 0 Size: 8220922
File ACL: 0 Directory ACL: 0
Links: 0 Blockcount: 16124
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x36b31916 -- Sat Jan 30 22:37:10 1999
atime: 0x36aebee4 -- Wed Jan 27 15:23:16 1999
mtime: 0x36adec25 -- Wed Jan 27 00:24:05 1999
dtime: 0x36b31916 -- Sat Jan 30 22:37:10 1999
BLOCKS:
123134 123136 123137 123138 123140 131404 131405 131406 131407 131408 131409
131
410 131411 131668
TOTAL: 14
現在的重點是，必須將該 inode 所指的檔案，所指的 block 全部找回來。在這裏，
列出的資訊顯示只有 14 個 block? 不對啊! 應該要有 8000 多個 block 才對啊!
在這裏要談一下 UNIX like filesystem 的「奧密」了。上頭所列的前 12 個 block
是真正指到檔案資料的 block, 稱之為 direct block 。第 13 個稱為第一階
indirect block, 第 14 個稱為第二階 indirect block 。什麼意思? 該檔的資料
所在的 block 位置如下:
123134
123136
123137
123138
......
131409
131410
131411 =========> 131412
131413
131414 (第一階，共 256 個)
......
131667
131668 =========> 131669 ==========> 131670
131671
131672 (共 256 個)
......
131925
131926 ==========> 131927
131928
131929 (共 256 個)
......
132182
132183 ==========> 132184
132185 (共 256 個)
......
各位明白嗎? 第 13 個 (131411) 與第 14 個 block 其實不是 data, 而是 index,
它指出接下來的 block 的位置。由於一個 block 的大小是 1024 bytes, 一個 int
在 32 位元系統中是 4 bytes, 故一個 block 可以記錄 256 筆資料。以 131411
block 為例，它所記錄的資料即為 (在檔案未砍前):
131412 131413 131414 .... 131667 (共 256 筆)
而這 256 個 block 就真正記錄了檔案資料，所以我們稱為第一階。同理，第二階
就有兩個層 index, 以 131668 來說，它可能記錄了:
131669 131926 132182 .... (最多有 256 筆)
而 131669 的 block 記錄為:
131670 131671 131672 .... 131925 (共 256 筆)
而這 256 個 block 才是真正儲存檔案資料的。而我們要的，就是這些真正儲存檔
案資料的 block 。
理論上，我們只要將這些 index block 的內容全部讀出來，然後照這些 index 把
所有的 block 全部讀到手，就能 100% 救回檔案 (假設這些 block 全部沒有被新
檔案覆寫的話)。工程很大，但是可行。不幸的是，在 kernel-2.0.33, 其設計是，
如果該檔案被砍了，則這些 index block 全部會規零，因此我所讀到的是
0 0 0 0 0 ..... (共 256 筆)
哇! 沒辦法知道這些 data block 真正所在的位置。所以，在此我們做了一個很大
的假設: 整個檔案所在的 block 是連續的! 也就是我上頭的例子。這也就是為什
麼說，只有連續 block (是指後頭的 indirect block) 的檔案才能完整救回，而
這一點就要聽天由命了。
4. 好了，現在我們只好假設所有的檔案處於連續的 block 上，現在請用
http://archie.ncu.edu.tw
去找這個工具: fsgrab-1.2.tar.gz, 並將它安裝起來。因為步驟很簡單，故在此
我就不多談。我們要用它將所需的 block 全部抓出來。它的用法如下:
fsgrab -c count -s skip device
其中 count 是只要 (連續) 讀幾個， skip 是指要從第幾個開始讀，例如我要從
131670 開始連續讀 256 個，就這樣下指令:
fsgrab -c 256 -s 131670 /dev/hda1 > recover
現在我們就開始救檔案吧! 以上頭的資料，我們必須用以下的指令來救:
(注意到頭開的 12 個 block 並沒有完全連續!!!)
fsgrab -c 1 -s 123134 /dev/hda1 > recover
fsgrab -c 3 -s 123136 /dev/hda1 >> recover
fsgrab -c 1 -s 123140 /dev/hda1 >> recover
fsgrab -c 7 -s 131404 /dev/hda1 >> recover
這是開頭的 12 個 block, 對於第一階 indirect, 就資料來看好像是連續的 :-))
fsgrab -c 256 -s 131412 /dev/hda1 >> recover
注意要跳過 131411, 因為它是 index block。對於第二階 indirect, 我們 *假設*
它們都是連續的:
fsgrab -c 256 -s 131670 /dev/hda1 >> recover
fsgrab -c 256 -s 131927 /dev/hda1 >> recover
fsgrab -c 256 -s 132184 /dev/hda1 >> recover
............................................
要一直做，直到 recover 的大小超過我們所要救回的檔案大小 (8220922) 為止。
要注意在這裏我們已很小心地跳過那些 index block (如 131668, 131669, 131926,
132183, ....) 了。
5. 最後一步，就是把檔案「剪」出來，並看看我們救回多少了。在這裏我們可以用
split 這個工具，假設我們重覆上述步驟，弄出來的 recover 檔大小為 8294400,
而我們要的大小是 8220922, 那就這樣下指令:
split -b 8220922 recover rec
則會做出兩個檔，一個是 recaa, 大小是 8220922, 另一個是 recab 則是剩下的大
小，後者是垃圾，扔了即可。現在我們可以檢查這個檔案是不是「完整」的那個被
誤砍的檔案了。由於我們的那個檔案是 .tar.gz 的格式，於是我們這個方法來檢查:
mv recaa recaa.tar.gz
zcat recaa.tar.gz > recaa.tar
如果沒有錯誤訊息，那表示成功了! 完全救回來了。但不幸的是，我們沒有成功，
將弄出的 recaa.tar 改名再 gzip 之後，與原來的 recaa.tar.gz 比一下大小，發
現少了 1%, 表示說該檔原來所在的 block 中最後有 1% 是不連續的 (或者被新寫
入的檔案覆寫了)，但這已是不幸中的大幸了。
=============================================================================
對於在 undelete 時 *必需* 假設所有 block 連續的問題，那份 HOWTO 文件說 Linus
與其他 kernel 設計者正著手研究，看能否克服這個困難，也就是在檔案砍掉時，不要
將 index block 規零。我剛剛試一下 kenrel-2.2.0 的環境，發現已做到了!! 以下是
一個已砍的檔案的 inode data (由 debugfs 所讀出):
debugfs: Inode: 36154 Type: regular Mode: 0600 Flags: 0x0 Version:
1
User: 0 Group: 0 Size: 2165945
File ACL: 0 Directory ACL: 0
Links: 0 Blockcount: 4252
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x36b54c3b -- Mon Feb 1 14:39:55 1999
atime: 0x36b54c30 -- Mon Feb 1 14:39:44 1999
mtime: 0x36b54c30 -- Mon Feb 1 14:39:44 1999
dtime: 0x36b54c3b -- Mon Feb 1 14:39:55 1999
BLOCKS:
147740 147741 147742 147743 147744 147745 147746 147747 147748 147769 147770
157
642 157643 157644 157645 157646 157647 157648 157649 157650 157651 157652
157653
157654 157655 157656 157657 157658 157659 157660 157661 157662 157663 157664
15
7665 157666 157667 157668 157669 157670 157671 157672 157673 157674 157675
15767
6 157677 157678 157679 157680 157681 157682 157683 157684 157685 157686
157687 1
............................................................................
9745 159746 159747 159748 159749 159750 159751 159752 159753 159754 159755
15975
6
TOTAL: 2126
真是太完美了!! 這意味著在 kernel-2.2.X 的環境下，我們不必假設所有的 block 都
連續，而且可以百分之百找回所有砍掉的 block! 因此上述的第二個風險就不存在了。
以上資料，謹供參考。
參考文件: Ext2fs-Undeletion Mini HOWTO
──── 居 士 ────
Email: thhsieh@twcpro.phys.ntu.edu.tw
HomePage: http://twcpro.phys.ntu.edu.tw/~thhsieh
※ Origin: 臺大電機 Maxwell 站 ◆ From: twcpro.phys.ntu.edu.tw
--
Reference:
http://bbs.ee.ntu.edu.tw/boards/Linux/19/1/84.html
http://www.linuxuser.com.tw/power/list2.php?id=2215
作者: thhsieh (居士) 看板: Linux
標題: [chat] 搶救過去!!!! (ext2 undelete)
時間: Tue Feb 2 14:53:04 1999
以下內容可能很多人早就知道了，但我想可能還是對某些人有用，所以就
post 上來大家參考 (嗯! 最近算物理問題算得煩透了，就當我無聊灌灌
水吧 :-)))
===========================================================================
發信人: thhsieh (居士), 信區: SM
標 題: [Sys] 搶救過去!!!! (ext2 undelete)
發信站: 冷月流蘇BBS驛站 (Mon Feb 1 17:21:11 1999) , 轉信
本系的 BBS 系統真是多災多難 (嗯 .... 其實是因為我的疏忽，才會這麼多災
多難 ....) ，繼這幾日系統時間不正確，造成許多人的 ID 被誤砍後，又一次
因系統設定上的問題，將 BBS 的重要備份檔給殺了。這件事是學弟發現後告訴
我的，當我上站來一見到他的 mail, 當真是欲哭無淚，差點沒去撞牆。那個備
分檔有多重要呢? 這麼說吧! 所有等待我們恢復舊信件的使用者資料全在裏頭。
那時已是週六晚 11:00 左右，我一邊想著要編一套說辭向大家解釋無法替大家
恢復舊信件與設定了，一邊還在想是否能夠挽回局面。大家知道， UNIX like
的系統是很難像 M$ 的系統一樣，做到 undelete 的，所有網管前輩都曾再三
警告我們，要小心! 小心! 砍檔之前三思而後行，砍了之後再後悔也沒用。雖
然我已漸漸做到砍檔三思而後行，但之次誤砍事件是系統在背景中定時執行的，
等到我找出原因時已是檔案被砍後一個多小時。
我憑著一點點的印象，想起在網路上，有人討論過在 Linux ext2 filesystem
中 undelete 的可能性，但我所見到的多半是負面的答案，但好像真的有人做過
這件事，於是我第一個所做的，就是馬上將該檔案原來所在的 partition mount
成 read-only, 禁止任何的寫入動作，不是怕再有檔案被誤砍 (因為已沒什麼可
砍的了) ，而是怕有新檔案寫進來，新資料可能會覆蓋到舊資料原本存在的磁區
(block) 。我們現在唯一個指望，就是企圖將檔案原來存在的磁區一個個找回來，
並且「希望」這些磁區上的舊資料都還在，然後將這些磁區串成一個檔案。
終於被我找到了!! 原來這方面的技術文件就存在我自己的系統中 :-))
/usr/doc/HOWTO/mini/Ext2fs-Undeletion.gz
於是我就按照這份文件的指示一步步來，總算將一個長達 8MB 的壓縮檔救回了
99%, 還有一個長達 1.1 MB 的壓縮檔完整無缺地救了回來。感謝上帝、 Linux
的設計者、寫那篇文件的作者、曾經討論過此技術的人、以及 Linux 如此優秀
的 ext2 filesystem, 讓我有機會搶救過去。現在，我將我的搶救步驟做一個整
理讓大家參考，希望有派得上用場的時候 (喔! 不，最好是希望大家永遠不要有
機會用到以下的步數 :-)))
************************************************************************
在此嚴正聲明!! 寫這篇文章的目的，是給那些處於萬不得已情況下的人們，有
一個挽回的機會，並不意味著從此我們就可以大意，砍檔不需要三思。前面提
到，我有一個檔案無法 100% 救回，事實上，長達 8MB 的檔案能救回 99% 已是
幸運中的幸運，一般的情況下若能救回 70% - 80% 已經要愉笑了。所以，不要
指望 undelete 能救回一切。預防勝於治療! 請大家平時就養成好習慣，砍檔前
請三思!!!
************************************************************************
我們能救回的機會有多大? 在 kernel-2.0.X 系列中 (本站所用的 kernel 是
2.0.33) ，取決以下兩點:
1. 檔案原來所在的磁區是否沒有被覆寫?
2. 檔案是否完全連續?
第一點我們可以與時間競賽，就是當一發現檔案誤砍時，要以最快的速度 umount
該 filesystem, 或將該 filesystem remount 成唯讀。就這次的情況而言，檔案
誤砍是在事發一個小時後才發現的，但由於該 filesystem 寫入的機會很少 (我
幾乎可確定一天才只有一次，做 backup)，所以第一點算是過關了。
第二點真的是要聽天由命了，就本站所使用的 kernel, 必須要在假設「長檔案」所
佔的 block 完全連續的情況下，才有可能完全救回來! 一個 block 是 1024 bytes,
長達 8 MB 的檔案就有超過 8000 個 block。在經常讀寫的 filesystem 中，可以
想見長檔案很難完全連續，但在我們的系統中，這一點似乎又多了幾分指望。同時，
Linux ext2 如此精良的 filesystem, 能做到前 7950 多個 block 都連續，這一點
也功不可沒。
好了，以下我就講一下我的步驟。
1. mount filesystem readonly:
該檔案的位置原來是在 /var/hda/backup/home/bbs 下，我們系統的 filesystem
組態是:
root@bbs:/home/ftp/rescue# df
Filesystem 1024-blocks Used Available Capacity Mounted on
/dev/sda1 396500 312769 63250 83% /
/dev/sda3 777410 537633 199615 73% /home
/dev/hda1 199047 36927 151840 20% /var/hda
/dev/hda2 1029023 490998 485710 50% /home/ftp
因此 /var/hda 這個 filesystem 要馬上 mount 成 readonly (以下請用 root 身
份):
mount -o remount,ro /var/hda
當然也可以直接 umount 它，但有時候可能有某些 process 正在此 filesystem
下運作，您可能無法直接 umount 它。因此我選擇 mount readonly。但您也可以
用:
fuser -v -m /usr
看一下目前是那些 process 在用這個 filesystem, 然後一一砍掉，再 umount。
2. 執行
echo lsdel | debugfs /dev/hda1 | less
看一下該 filesystem 最近被砍的 inode (檔案) 有那些 (為什麼是 /dev/hda1?
請見上頭的 df 列表)? 在這裏要說一下，在 UNIX like 的系統中，所有的檔案都
有一個 inode 指向它， inode 中記錄了檔案的重要資訊，如大小、時間、屬性等
等。就我們的系統而言，其列示如下:
debugfs: 92 deleted inodes found.
Inode Owner Mode Size Blocks Time deleted
.................................................................
29771 0 100644 1255337 14/ 14 Sat Jan 30 22:37:10 1999
29772 0 100644 5161017 14/ 14 Sat Jan 30 22:37:10 1999
29773 0 100644 8220922 14/ 14 Sat Jan 30 22:37:10 1999
29774 0 100644 5431 6/ 6 Sat Jan 30 22:37:10 1999
請注意! inode 裏頭不會記錄檔案的檔名，檔名是記錄在該檔案所在的目錄的
data block 中，故在此我們見不到。因此，我們必須要在檔案大小、被砍時間
等資訊中判斷出要救回的檔案是那一個。在此，我們要救回 29773 這個 inode。
3. 執行
echo "stat <29773>"" | debugfs /dev/hda1
列出該 inode 的所有資訊，如下:
debugfs: stat <29773>
Inode: 29773 Type: regular Mode: 0644 Flags: 0x0 Version: 1
User: 0 Group: 0 Size: 8220922
File ACL: 0 Directory ACL: 0
Links: 0 Blockcount: 16124
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x36b31916 -- Sat Jan 30 22:37:10 1999
atime: 0x36aebee4 -- Wed Jan 27 15:23:16 1999
mtime: 0x36adec25 -- Wed Jan 27 00:24:05 1999
dtime: 0x36b31916 -- Sat Jan 30 22:37:10 1999
BLOCKS:
123134 123136 123137 123138 123140 131404 131405 131406 131407 131408 131409
131
410 131411 131668
TOTAL: 14
現在的重點是，必須將該 inode 所指的檔案，所指的 block 全部找回來。在這裏，
列出的資訊顯示只有 14 個 block? 不對啊! 應該要有 8000 多個 block 才對啊!
在這裏要談一下 UNIX like filesystem 的「奧密」了。上頭所列的前 12 個 block
是真正指到檔案資料的 block, 稱之為 direct block 。第 13 個稱為第一階
indirect block, 第 14 個稱為第二階 indirect block 。什麼意思? 該檔的資料
所在的 block 位置如下:
123134
123136
123137
123138
......
131409
131410
131411 =========> 131412
131413
131414 (第一階，共 256 個)
......
131667
131668 =========> 131669 ==========> 131670
131671
131672 (共 256 個)
......
131925
131926 ==========> 131927
131928
131929 (共 256 個)
......
132182
132183 ==========> 132184
132185 (共 256 個)
......
各位明白嗎? 第 13 個 (131411) 與第 14 個 block 其實不是 data, 而是 index,
它指出接下來的 block 的位置。由於一個 block 的大小是 1024 bytes, 一個 int
在 32 位元系統中是 4 bytes, 故一個 block 可以記錄 256 筆資料。以 131411
block 為例，它所記錄的資料即為 (在檔案未砍前):
131412 131413 131414 .... 131667 (共 256 筆)
而這 256 個 block 就真正記錄了檔案資料，所以我們稱為第一階。同理，第二階
就有兩個層 index, 以 131668 來說，它可能記錄了:
131669 131926 132182 .... (最多有 256 筆)
而 131669 的 block 記錄為:
131670 131671 131672 .... 131925 (共 256 筆)
而這 256 個 block 才是真正儲存檔案資料的。而我們要的，就是這些真正儲存檔
案資料的 block 。
理論上，我們只要將這些 index block 的內容全部讀出來，然後照這些 index 把
所有的 block 全部讀到手，就能 100% 救回檔案 (假設這些 block 全部沒有被新
檔案覆寫的話)。工程很大，但是可行。不幸的是，在 kernel-2.0.33, 其設計是，
如果該檔案被砍了，則這些 index block 全部會規零，因此我所讀到的是
0 0 0 0 0 ..... (共 256 筆)
哇! 沒辦法知道這些 data block 真正所在的位置。所以，在此我們做了一個很大
的假設: 整個檔案所在的 block 是連續的! 也就是我上頭的例子。這也就是為什
麼說，只有連續 block (是指後頭的 indirect block) 的檔案才能完整救回，而
這一點就要聽天由命了。
4. 好了，現在我們只好假設所有的檔案處於連續的 block 上，現在請用
http://archie.ncu.edu.tw
去找這個工具: fsgrab-1.2.tar.gz, 並將它安裝起來。因為步驟很簡單，故在此
我就不多談。我們要用它將所需的 block 全部抓出來。它的用法如下:
fsgrab -c count -s skip device
其中 count 是只要 (連續) 讀幾個， skip 是指要從第幾個開始讀，例如我要從
131670 開始連續讀 256 個，就這樣下指令:
fsgrab -c 256 -s 131670 /dev/hda1 > recover
現在我們就開始救檔案吧! 以上頭的資料，我們必須用以下的指令來救:
(注意到頭開的 12 個 block 並沒有完全連續!!!)
fsgrab -c 1 -s 123134 /dev/hda1 > recover
fsgrab -c 3 -s 123136 /dev/hda1 >> recover
fsgrab -c 1 -s 123140 /dev/hda1 >> recover
fsgrab -c 7 -s 131404 /dev/hda1 >> recover
這是開頭的 12 個 block, 對於第一階 indirect, 就資料來看好像是連續的 :-))
fsgrab -c 256 -s 131412 /dev/hda1 >> recover
注意要跳過 131411, 因為它是 index block。對於第二階 indirect, 我們 *假設*
它們都是連續的:
fsgrab -c 256 -s 131670 /dev/hda1 >> recover
fsgrab -c 256 -s 131927 /dev/hda1 >> recover
fsgrab -c 256 -s 132184 /dev/hda1 >> recover
............................................
要一直做，直到 recover 的大小超過我們所要救回的檔案大小 (8220922) 為止。
要注意在這裏我們已很小心地跳過那些 index block (如 131668, 131669, 131926,
132183, ....) 了。
5. 最後一步，就是把檔案「剪」出來，並看看我們救回多少了。在這裏我們可以用
split 這個工具，假設我們重覆上述步驟，弄出來的 recover 檔大小為 8294400,
而我們要的大小是 8220922, 那就這樣下指令:
split -b 8220922 recover rec
則會做出兩個檔，一個是 recaa, 大小是 8220922, 另一個是 recab 則是剩下的大
小，後者是垃圾，扔了即可。現在我們可以檢查這個檔案是不是「完整」的那個被
誤砍的檔案了。由於我們的那個檔案是 .tar.gz 的格式，於是我們這個方法來檢查:
mv recaa recaa.tar.gz
zcat recaa.tar.gz > recaa.tar
如果沒有錯誤訊息，那表示成功了! 完全救回來了。但不幸的是，我們沒有成功，
將弄出的 recaa.tar 改名再 gzip 之後，與原來的 recaa.tar.gz 比一下大小，發
現少了 1%, 表示說該檔原來所在的 block 中最後有 1% 是不連續的 (或者被新寫
入的檔案覆寫了)，但這已是不幸中的大幸了。
=============================================================================
對於在 undelete 時 *必需* 假設所有 block 連續的問題，那份 HOWTO 文件說 Linus
與其他 kernel 設計者正著手研究，看能否克服這個困難，也就是在檔案砍掉時，不要
將 index block 規零。我剛剛試一下 kenrel-2.2.0 的環境，發現已做到了!! 以下是
一個已砍的檔案的 inode data (由 debugfs 所讀出):
debugfs: Inode: 36154 Type: regular Mode: 0600 Flags: 0x0 Version:
1
User: 0 Group: 0 Size: 2165945
File ACL: 0 Directory ACL: 0
Links: 0 Blockcount: 4252
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x36b54c3b -- Mon Feb 1 14:39:55 1999
atime: 0x36b54c30 -- Mon Feb 1 14:39:44 1999
mtime: 0x36b54c30 -- Mon Feb 1 14:39:44 1999
dtime: 0x36b54c3b -- Mon Feb 1 14:39:55 1999
BLOCKS:
147740 147741 147742 147743 147744 147745 147746 147747 147748 147769 147770
157
642 157643 157644 157645 157646 157647 157648 157649 157650 157651 157652
157653
157654 157655 157656 157657 157658 157659 157660 157661 157662 157663 157664
15
7665 157666 157667 157668 157669 157670 157671 157672 157673 157674 157675
15767
6 157677 157678 157679 157680 157681 157682 157683 157684 157685 157686
157687 1
............................................................................
9745 159746 159747 159748 159749 159750 159751 159752 159753 159754 159755
15975
6
TOTAL: 2126
真是太完美了!! 這意味著在 kernel-2.2.X 的環境下，我們不必假設所有的 block 都
連續，而且可以百分之百找回所有砍掉的 block! 因此上述的第二個風險就不存在了。
以上資料，謹供參考。
參考文件: Ext2fs-Undeletion Mini HOWTO
──── 居 士 ────
Email: thhsieh@twcpro.phys.ntu.edu.tw
HomePage: http://twcpro.phys.ntu.edu.tw/~thhsieh
※ Origin: 臺大電機 Maxwell 站 ◆ From: twcpro.phys.ntu.edu.tw
--
Reference:
http://bbs.ee.ntu.edu.tw/boards/Linux/19/1/84.html
http://www.linuxuser.com.tw/power/list2.php?id=2215
2006年4月13日 星期四
2006年4月10日 星期一
訂閱：
文章 (Atom)