Question

Text

Text 是由文字堆砌而成、可以阅读的东西。

我们将 Text 打散为基本单位，以便理解 Text：

从书写的观点：英文的基本单位叫做 letter ，即是 ABC...这 26 种英文字母。中文的基本单位叫做 字 ，即是字典裡面那些字。

从语言的观点：英文的基本单位叫做 word ，由一个以上的 letter 组成，例如 apple、boy、cat。中文的基本单位叫做 词 ，由一个以上的字组成，例如苹果、男孩、猫。

从电脑的观点：基本单位叫做 character ，繁中译作“字元”，简中译作“字符”。电脑可以处理的字元，主要是依据 ASCII 与 Unicode 的规定。英文字元有 ABCDabcd1234,.!?等。中文字元包括了字典裡面那些字，以及ㄅㄆㄇㄈ。，、：等注音符号与标点符号；绝大部分的中文字都有收录，只漏了一些冷僻的字。

在电脑萤幕上显示字元，只要打开 文字编辑器 ，选择 输入法 ，用手指敲敲键盘即可。还可以进一步，将电脑萤幕上的字元，储存到 纯文字档案 裡；将 纯文字档案 裡的字元，显示在电脑萤幕上。

想要写程式在电脑萤幕上显示字元，只要运用 scanf、printf、cin、cout，就会以 Command-line Interface 显示字元。还可以进一步，写程式将字元储存到档案；写程式从档案读取字元。

想要处理字元，相关的学问有 字串学 与 编码理论 。相关的本站文件有 String 与 Code 。

Font

Font 就是文字的造型。译作“字体”或“字型”。

电脑显示字元，必须透过字型。只要有文字的地方，通常都能更换字型，例如文字编辑器、浏览器、作业系统、命令提示字元。可供选择的字型，主要是看你的电脑安装了哪些字型。

制作字型属于 Graphics 的领域，以后再来介绍。

Text Editor（Under Construction!）

Text Viewer

“文字阅读器”是阅读纯文字档案的工具，例如 Unix 系统的 more 与 less 指令。

Text Editor

“文字编辑器”不仅能阅读纯文字档案，也能编辑纯文字档案。例如 Notepad 就是一个众所皆知的文字编辑器。资深的电脑玩家应该还听过 Vim 与 UltraEdit 这些经典的文字编辑器。台湾人制造的文字编辑器，像是 汉书 与 Notepad++ ，大家应该也有所耳闻。

程式设计师开发程式码的工具，例如 Microsoft Visual Studio 、 Code::Blocks 、 Eclipse 等等的 IDE ，其基础也是文字编辑器！

很多程式语言已经内建了文字编辑器，例如 C#的 TextBox、Java 的 JTextArea，我们可以直接拿来用。不过如果你想要添加特殊的功能、想要开发特殊的文字编辑器，还是必须先亲手实作一遍，瞭解原理，才有办法涂涂改改。另一方面，对于程式设计的初学者来说，亲手撰写文字编辑器也会是一个很好的练习机会。

本篇文章将引导大家实作一个阳春的文字编辑器。首先实作古早味的 Textual User Interface, TUI 的文字编辑器，再来实作现代化的 Graphical User Interface, GUI 的文字编辑器。

Textual User Interface

如果你是使用 Windows 作业系统的 cmd.exe ，在 MSDN 网站上面可以找到详细的 说明文件 。

如果你是使用 Mac OS 作业系统的 Terminal.app ，或者是使用 Linux 作业系统的 console ，那麽就要用 ANSI escape code 这套公定标准来控制色彩和游标──这跟 BBS 所用的是一样的。（也就是说，Windows 完全没有依循公定标准。）

你也可以使用现成工具： ncurses 。

File I/O

“读取硬碟”比“读取记忆体”花费更多时间。一般的做法是，预先将档案从硬碟複制到记忆体，每当捲动文字编辑器的画面，就直接读取记忆体，而不必读取硬碟。

文字档案不大时，可以一口气 把整个档案填入记忆体 。

文字档案很大时，可以动态载入资料：随著画面捲动，才把对应的档案填入记忆体。

纯文字档案顶多几 MB，而家用电脑的记忆体都是数 GB、行动电话的记忆体也有 1GB，记忆体十分充足，所以大可不必动态载入资料、搞的自己要死不活。

Data Structure

文字通常以“行”为单位呈现，遭遇断行字元，随即换行显示。文字切成一行一行分开储存，是个不错的策略。

注意到 Windows、Mac OS、Linux 的断行字元都不一样，必须 小心处理 、 小心处理 。

一行文字使用一个 array（插入与删除很慢）或者一个 list（就定位很慢）是最简单的方式。由于一行顶多几百个字元，再加上现在电脑性能相当优越，所以这种方式其实简洁明快。

更高级的方式是使用 unrolled linked list ，它是用 list 串起一堆 array；或者使用 rope ，它是一棵二元树。当一行有成千上万个字元，这种方式的优势就会显露出来，打字不会卡卡的。

一行文字的资料结构已经解决了，接著要串连每一行。同样地，上述四种资料结构都可以拿来用。

Rich Text Editor（Under Construction!）

Rich Text 与 Markup Language

Rich Text 是指附加了字型、大小、颜色、位置、图片、超连结等等资讯的 Text。实务上的做法是：定义特殊的格式，以便附加资讯。著名的 Rich Text 格式像是 HTML 、 TEX 、 RTF 。

以 HTML 为例，它藉由“标籤”来附加资讯。首先使用纯文字编辑器读取.html 档案，编辑 Rich Text，然后使用浏览器读取.html 档案，就变成美美的网页了。

为了附加资讯，于是发明了 保留字 的概念：某些文字必须当作“此为附加资讯”的提示，不能当作纯文字。

为了让保留字也可以成为纯文字，于是又发明了 跳脱字元 的概念：以罕见的文字组合，代替保留字。

以 HTML 为例，标籤不能当作纯文字，例如<p>。如果想要显示跟标籤一模一样的纯文字，就必须利用 跳脱字元& ：写下&lt;就变成<，写下&gt;就变成>，写下&lt;p&gt;就变成<p>了。

聪明的读者肯定马上又想到：如果想要显示&lt;的纯文字呢？答案是跳脱字元本身也要设计跳脱字元：写下&amp;就变成&，写下&amp;lt;就变成&lt;。下图是本段落的 HTML 原始码：

Rich Text Editor

可以实际动手操作的范例： http://ckeditor.com/demo 。

用纯文字编辑器来设计 Rich Text，眼睛看著纯文字、脑袋想著真实画面，非常迂迴不直觉，是 真正的男子汉才会做的事情 。于是有人提倡 WYSIWYG（所见即所得） 的概念：编辑器直接显示真实画面，使用者直接编辑真实画面；编辑器根据使用者的操作过程，暗地裡生成 Rich Text。

知名的富文字编辑器软体，例如编辑 RTF 的 Microsoft Word 、编辑 HTML 的 Adobe DreamWeaver 。现在网路发达，也有很多人开发 网页版的富文字编辑器 ，例如 CKEditor 、 TinyMCE 。

很多 IDE 也有富文字编辑器，以便直觉地设计 GUI 程式，就是俗称的“拉介面”。例如 C++Builder 、 Qt Creator 、 Microsoft Visual Studio 。

很多程式语言已经内建了富文字编辑器，例如 Qt 的 QTextEdit、C#的 RichTextBox，我们可以直接拿来用。

文字是人类最擅长的媒体，所以富文字编辑器举目皆是。即时通讯软体 Skype 、 LINE ，社群网站 Facebook ，部落格网站 Blogger ，微博网站 Twitter 、 新浪微博 ，都可以见到富文字编辑器的身影。

如何制作 Rich Text Editor？

我从未设计过富文字编辑器，所以无法介绍。各位可以 参与开源专案 、从做中学；或者也可以 进入相关行业 、入门学艺。

想要发明 Rich Text 的格式，请参考各种 markup language ，从既有的格式汲取经验。

想要解析 Rich Text，请参考 parsing 。相关的学校课程是 编译器 。相关的本站文章是 Formal Language 。

想要绘制真实画面，请参考各种 排版引擎 。

当然啦，对于凡事讲求速成的人来说，直接用现成的富文字编辑器就好了，大可不必学习这麽多东西。

UVa 12417

Text Parser（Under Construction!）

Text Parser

“文字剖析器”。读取文字，根据格式，建立阶层架构。

相关理论是 制式语言 。

亦得更进一步，转换架构，建立新文字。

经典应用如 documentation generator ：把程式码视为纯文字档案。设计一个剖析器，从程式码当中抽取注解内容、函数名称，然后再设计一个剖析器，自动生成网页说明文件。

经典应用如 template engine ：根据使用者输入的片段文字，生成程式码。

Programming Language（Under Construction!）

Opcode

运算码、机器码。参照 CPU 的规格书、让 CPU 执行特定工作的 二元码 。

从 CPU 底部的针脚们输入指令，让 CPU 执行特定工作，大致的过程是：一、查询 CPU 规格书，查询特定指令，查询该指令所用的针脚是哪些，以及其电压高低。二、根据规格书，调整 CPU 每根针脚的电压高低。三、找到启动指令的针脚，调高电压（有如按下启动开关、按下执行按钮）。电流一齐流动，CPU 执行工作。

数学上，我们可以将针脚们的电压，想成是 0 和 1 组成的字串，也就是二元码。针脚依序编号，电压高代表 1，电压低代表 0。

顺带一提，启动开关就是 clock。持续地执行各种指令、规律地按下启动开关，就像时钟秒针一样滴答滴答，所以取名为 clock。CPU 的工作速度，可以从 clock 的速度看出来。

读者可以修习电子学、数位逻辑、计算机组织与结构等课程，瞭解 CPU 的细节。这裡就不多提了。

Assembly Language

组合语言。让 CPU 工作的文字指令。

因为机器码难读难懂，所以人类发明了组合语言──使用有意义的文字来描述工作指令。之后再特地打造 parser，称作组译器，将组合语言变成机器码。

儘管组合语言依然难读难懂，但是总比机器码好多了。

CPU 厂商，除了提供 CPU 的规格书，还会提供一套组合语言暨组译器，方便工程师编写程式。除此之外，为了避免让工程师每换一颗新 CPU、就跟著换一套组合语言，CPU 厂商们也一起约定了组合语言的大致格式，主要有两套，请参考 RISC 和 CISC 。

读者可以修习组合语言、微处理器、嵌入式系统等课程，瞭解组合语言的细节。这裡就不多提了。

Programming Language

程式语言。让 CPU 工作的文字指令，文字拥有特殊结构。

一般说到指令，很容易联想到“立正、敬礼、稍息”。电脑世界裡面，让 CPU 做事情的指令，差不多就是这麽单纯。

不过这样的指令实在太简单，只能做简单的工作。遇到複杂的工作，就必须堆叠大量指令，让事情变得複杂、难以理解。经典范例是流亡台湾的匪军刺枪术：“气刀体一致。防右刺！刺！刺！防左刺！刺！刺！防下刺！刺！刺！上击！衝击！衝击！砍劈！横击！衝击！衝击！砍劈！迴旋！迴旋！”

因为组合语言难读难懂，所以人类又发明了程式语言──建立了段落、层级、单元等等概念，让人类不必浪费力气鑽细节，让人类能宏观大局。之后再特地打造 parser，称做编译器，将程式语言变成组合语言、再变成机器码。

儘管程式语言依然难读难懂，但是总比组合语言好多了。

程式语言的理论仍在发展当中。本人学识粗浅，无法介绍。请读者自行上网搜寻 课程 、 书籍 。

Assembler

组译器。组合语言变成机器码。

Compiler

编译器。程式语言先变成组合语言，再变成机器码。

深奥幽玄。如果你确信被什麽东西附身，那麽再来深入研究吧。

https://mitpress.mit.edu/sicp/
http://www.cppgm.org/
http://www.yinwang.org/blog-cn/2013/03/28/chez-scheme

另外必须提一下 LLVM，这是最近几年的新观念，大家都在跟进。编译器的流程中间多了一层：程式语言先变成 LLVM，再变成组合语言，再变成机器码。

LLVM 降低了事情的複杂度，让大家可以分开处理程式语言的特殊细节、基础结构。程式语言变成 LLVM 时，解决掉各种不同程式语言的特殊细节。LLVM 变成组合语言时，大家就可以直接根据语言结构，实施最佳化。

ICPC 2727

Interpreter

解译器、直译器。可以想成是 online 版本的编译器，一边读取指令，一边执行指令。

必须建立多馀的组合语言，以处理正在计算的变数。

Input Method（Under Construction!）

Input Method

输入法 。用来输入文字的软体。

键盘最初是美国人发明的，上面只有印制英文字母，也只能输入英文字母。其他国家为了输入自己的语言文字，只好在键盘上面 额外印制符号 ，然后自己设计输入法。台湾的键盘额外印上注音符号，配合 注音输入法 ，就能输入中文字了。除了作业系统内建的输入法以外，著名的繁体中文输入法还有 自然输入法 和 酷音输入法 。

现在科技发达，输入文字不见得要透过键盘，而是透过触控萤幕、麦克风，所以输入法的发展重点也随著改变。早期的输入法，著重拆字组字；近代的输入法，著重选字填词。事过境迁、沧海桑田，过去那些拆字组字的输入法，例如 仓颉输入法 和 呒虾米输入法 ，现在看来彷彿是消耗民众精力的玩具。

输入法除了输入文字以外，还有另一个重要用途是输入特殊符号。自从 Unicode 兴起之后，亟需发展一个能够输入各种特殊符号的输入法。

如何制作 Input Method？

制作输入法，有个极大的难题：必须瞭解作业系统。当代的输入法，由作业系统直接管辖。想要绘制选字视窗、想要将选好的文字传送到目前开启的软体，都要依赖作业系统提供的 API 。

我是个外行人，没办法介绍什麽。大家可以请教这些专家：针对 Windows 作业系统，可以请教 PCMan ；针对 Linux 作业系统，可以请教 酷音输入法的贡献者 ；针对浏览器，可以参考目前 W3C 正在制定当中的 Input Method Editor API 。

如果只是想练习、不想搞那麽複杂，其实也可以略过作业系统 API，只是打出来的文字只能出现在自己的程式视窗裡面罢了。

键盘按键与注音符号的对应表

1 -> ㄅ
q -> ㄆ
a -> ㄇ
z -> ㄈ
...

起先有很多种 键盘按键与注音符号的对应方式 ，不过现在只剩下一种了，就是键盘上看到那一种。

程式语言处理的其实是数字，我们建立的其实是“ASCII 编号”与“注音符号编号”的对应表。

使用者敲打键盘、输入 ASCII 编号，就换成注音符号编号。

亦得制作 虚拟键盘 ，让使用者点选滑鼠、输入 ASCII 编号。Windows 作业系统开启注音输入法，按下 ctrl alt ,出现“萤幕小键盘”，那就是虚拟键盘。Android 作业系统开启任何输入法，都会出现虚拟键盘。

注音符号与中文字的对应表

ㄅㄚ  -> 八巴吧...
ㄅㄚˊ -> 拔钹跋...
ㄅㄚˇ -> 把靶钯...
ㄅㄚˋ -> 爸霸坝...
ㄅㄚ˙ -> 吧爸巴...
ㄅㄛ  -> 波拨剥...
ㄅㄛˊ -> 伯柏泊...
...

注音符号 的声母 21 个、介母 3 个、韵母 13 个、声调 5 种，拼音方式低于 22*4*14*5 = 1540 < 2^11 种。简单的编码方式是声母 5bit、介母 2bit、韵母 4bit、声调 3bit，拼成 13bit，用 2 byte 的 short 变数记录。

程式语言处理的其实是数字，我们建立的其实是“拼音编码”与“Unicode 编号”的对应表。

实务上如何得到这个表，我尚未调查清楚，麻烦读者提供线索！我不清楚政府单位是否有公定公布这个表，我推测也许只能从开源专案获得这个表，例如酷音输入法。

注音符号与常用词语的对应表

ㄅㄚ          -> 八(199 次) 吧(12 次)
ㄅㄚˋ ㄅㄚ˙   -> 爸爸(32 次)
ㄔㄤˊ ㄐㄧㄢˋ -> 常见(120 次)　长剑(57 次)
...

电脑自动选字、读者手动选字，就查表，列出最常用的 词语 。表格的资料结构採用 trie 而不用 array，可减少查表时间。

实务上如何得到这个表，我尚未调查清楚，麻烦读者提供线索！有一种得到这个表的方式，是利用 Natural Language 领域的 Text Segmentation，从网路上收集大量文章，以演算法自动断词，统计词语出现次数。

词语组合（断词与选词）

一句话通常很长很长，不只一个词语。电脑必须自动选择正确的词语组合。

ㄅㄚˋ ㄅㄚ˙ ㄇㄢˇ ㄔㄤˊ ㄐㄧㄢˋ 爸爸满常见(O) 爸爸满长剑(X)
ㄅㄚˋ ㄅㄚ˙ ㄇㄞˇ ㄔㄤˊ ㄐㄧㄢˋ 爸爸买常见(X) 爸爸买长剑(O)
ㄋㄧˇ ㄏㄨㄟˋ ㄧㄤˇ ㄕˋ ㄇㄚ˙   你会痒是吗(O) 你会仰式吗(O)

複杂的方法是 建立剖析树 ， 分析语法语意 。

简单的方法是穷举所有的词语组合方式，找到最好的词语组合：採用 greedy method 令长词优先配对；或者以 dynamic programming 计算出现次数总和（或机率）最大的词语组合。接下来使用者可以不断选字填字，每次都重新计算最佳的词语组合。

进阶的方法是 n-gram ，建立词语衔接词语的对应表，同时记录使用次数（或机率）。中文词语林林总总，这个表非常大，需要超大型资料库。

2-gram   【併入图片】
爸爸 + 满 -> 23 次
爸爸 + 买 -> 30 次
买 + 常见 -> 47 次
买 + 长剑 -> 3 次
满 + 常见 -> 60 次
满 + 长剑 -> 2 次
满 + 长   -> 51 次
...

制作完成之后，可用 白痴造句 、 同音文章 、《一首因爱睏在输入时按错键的情诗》进行测试。

结语

全世界只有台湾在用注音符号，其他国家则用英文拼音。全世界只有台湾在用 KK 音标，其他国家则用 IPA。想要深入鑽研输入法的读者，最好也研究一下其他国家的输入法，以免故步自封。

Natural Language（Under Construction!）

Natural Language

自然语言是人类所说的语言，与 制式语言 相对应。

人类语言庞大複杂、人类文法缺乏规律。工程师放弃教条式的文法，改为观察词彙与词彙之间的关联，判断最佳词彙组合。这群人只碰计算机科学、不碰语言学，于是创造了新称呼“自然语言处理”。

语言学 旨在研究人类的文字文法、发音韵律、说话沟通、写作翻译等等，都属于语言学的范畴。

与自然语言有关的是语意学、语用学。

知名的工具为 NLTK 。 繁体中文的语料库 。

http://courses.washington.edu/ling472/
http://icwww.epfl.ch/~chappeli/tidt/
http://www.utcompling.com/courses

资料结构，索引表。统计词彙出现次数。

Text Tokenization

分词。英文单字，将变化型改回原型。

tokenization  英文句子去除标点符号，打散成单字
lemmatisation 英文单字的变化型，变成原型
stemming      英文单字的变化型，去除字尾
http://tartarus.org/martin/PorterStemmer/

Text Tokenization

分词。中文句子，断开成许多词彙。

将一句话断开成许多词彙 ---> 将 一句 话 断开 成 许多 词彙

读者可以先玩玩看 中研院的断词系统 、 谷歌书籍词彙统计 。

人类在对谈时，大脑一瞬间综合了声调、文法、情境、表情与肢体动作、认知、知识，藉此正确地分词。每个人出生的前十年，大脑不断地发展这个能力，但是我们至今仍然不知道这个能力的详细内容。目前计算机科学家所能掌握的，仅仅是文法而已。

先前于输入法的章节，已经介绍过分词演算法。

一、建立“常见词彙大全”。
　　穷举所有的词语组合方式，找到最好的词语组合。
　甲、 greedy method ，令长词优先配对。
　乙、 dynamic programming ，计算出现次数总和（或机率乘积）最大的词语组合。

　　优点：计算速度飞快而且精准。
　　缺点：无法处理未知词彙。

二、 n-gram ，n 是一个变数。此处以 2-gram 为例：

　　　　　　　　　　　 2-gram
　　　　常见词彙何其多 ------> 常见、见词、词彙、彙何、何其、其多

　　蒐集大量文章，统计所有 2-gram 的出现次数即可。就这麽简单。
　　教科书习惯表示成机率：出现次数再除以总次数。
　　缺点：完全没有参考中文文法，经常得到莫名其妙的词彙。
　　优点：採用机率模型，可以容忍人类乱无章法的句法！

三、剖析树。
　　依照文法，分解句子变成树状图，并且 判断词性 。
　　然而人类讲话乱无章法，穷举各种状况的时间複杂度极高。

四、 有向无环图 DAG 。
　　比树状图还有弹性。

Text Segmentation

分段。一篇文章，自动切割出适当段落。

TextTiling algorithm

Text Prediction

预测。知道接下来要说什麽。

Natural Language Generation

生成 。自动写作，生成文章。

http://en.wikipedia.org/wiki/SCIgen
http://en.wikipedia.org/wiki/Article_spinning
http://images3.wikia.nocookie.net/__cb20120321065110/hunterx/9/92/Neon%27s_Lovely_Ghostwriter.jpg

Automated Content Authorship
http://wordai.com/
http://mag.udn.com/mag/digital/storypage.jsp?f_ART_ID=131873
http://www.insead.edu/facultyresearch/faculty/profiles/pparker/
http://www.insead.edu/facultyresearch/faculty/personal/pparker/

Report Generator
http://narrativescience.com/
http://mag.udn.com/mag/digital/printpage.jsp?f_ART_ID=389334

lyrics generator
http://arxiv.org/abs/1505.04771   DopeLearning
Automatic Rhyme Detection
http://mining4meaning.com/2015/02/13/raplyzer/

Neural Storyteller
http://www.cs.toronto.edu/~mbweb/

Political Speech Generation
http://arxiv.org/abs/1601.03313

Natural Language Understanding

理解 。将文章涵义以数值形式记录下来。

前阵子流行的手法是 主题模型 ：观察每份文章的词彙，根据词彙们的出现次数、比重，判断文章类型。

Latent Semantic Analysis, LDS
vector space model + SVD
(跟 eigenxxxxx 不太一样，没有先求两两共变异数)

Probabilistic Latent Semantic Analysis, PLDS
document->topic->word
http://blog.csdn.net/yangliuy/article/details/8330640

LDA, Latent Dirichlet Allocation
http://cos.name/2013/01/lda-math-gamma-function/
http://cos.name/2013/01/lda-math-beta-dirichlet/

Natural Language Summarization

摘要 。归纳文章重点。理解、生成。

http://xenia.media.mit.edu/~mueller/storyund/storyres.html

Natural Language Correction

校正。给定一句话，进行修正。

Natural Language Communication（Question Answering）

问答。给定一句话，产生适当的回话。

例如 掰噗 、 Akinator 、Eugene Goostman。

Natural Language Translation（Machine Translation）

翻译 。一份文章，翻译成另外一种语言。

目前功能很阳春，科学家正在努力克服。知名软体如 Google Translate 、 Dr.eye 。

http://www.statmt.org/book/
http://mt-class.org/
http://104.131.78.120/

Natural Language Identification

鑑定 。一份文章，判断所属语言。

Natural Language Compression

压缩。减少文字数量，保留原本意义。

ACB Compression（Associative Coder of Buyanovsky）
http://www.stringology.org/DataCompression/acb/index_en.html
http://www.cs.brandeis.edu/~fabricio/files/cosci170.htm

PPM Compression（Prediction by Partial Matching）
http://www.stringology.org/DataCompression/ppmc/index_en.html
http://en.wikipedia.org/wiki/Prediction_by_Partial_Matching

Natural Language Programming

编程 。靠一张嘴写程式。