Part I - 文本预处理（分词与词干还原）
O. Anqiao
这几天我开了一个新项目，用 Haskell 语言编写的自然语言处理库（AHNLP，Angiao's Haskell Natural Language Processing）也顺便写博客，给各位分享一下这涉及到的简单知识 总要写点计算机的东西，防止你们忘了我会编程 哼（傲娇
NLP 概论
自然语言处理（Natural Language Processing，NLP）是涉及人工智能和语言学的领域，通过算法来使计算机处理和分析人类自然语言。
一个较早的自然语言处理技术的应用就是机器翻译，在早期的机器翻译系统中，基于规则的方法较为常见，这些方法依赖于大量的语言学规则和双语词典来进行翻译。而现代的自然语言处理技术又被应用深度学习技术，通过构建复杂的神经网络模型来提高语言理解和生成的准确性。统计机器翻译（Statistical Machine Translation, SMT）和神经机器翻译（Neural Machine Translation, NMT）开始兴起，Google 翻译就是一个广泛使用的机器翻译服务，最初使用的是统计方法，但近年来出现了 Google Neural Machine Translation 来提高翻译质量。
去年10月也就是我九年级的时候，我在一篇有关机器学习的 Blog 中使用 Haskell 语言编写了一个简单的，基于词频分析的文本分类示例，非要说的话也是和 NLP 有那么一点关系的。总的来说，就是 NLP 和自然语言，也就是我们作为人类日常使用的、变化多的语言的方面的东西挂钩，大概能对这个领域有一个概念。
我们要做什么？
本文的内容来自于我最近在做的 Haskell 语言的NLP库（针对英语）。现阶段我打算利用空余时间中的空余时间在这个库中实现一些常用的涉及到 NLP 技术的功能，例如在文本预处理阶段，我们会涉及到分词、词性标注、词干提取、词形还原等内容，而句法分析则会涉及到句子解析和依存分析，语义分析什么的...这些都是后话。我用了半小时左右写了与本文内容有关的代码，而我希望借它们能提供一些相关的算法解释和实现思路。
尽管本文会涉及到的“分词”与“词干提取”非常简单，而我选择了Haskell，其编程风格和结构与主流的一些OOP语言还是有很大差别的。感觉这一篇内容真的好水，没什么难度，当乐子看看就好
分词器（Tokenizer）
我们设计一个分词器，将文本分割成较小的基本单位，在英语这可能是字符、单词、短语或者句子。
说一个先例，2023年冬天，我初二的时候做了一个小demo（一个键值数据库）。当时考虑到做一个命令解析器，在命令行中输入对应的命令并解析成适用的数据结构，以对数据库做对应的操作。命令是很明确的，而部分嵌套的表达式不适用“空白格换行”的做法，因此我当时实现的 “Lexer” 做的是将输入的内容以空白格为界分开（不同的参数），并逐个对其字符进行分割，逐个字符读取直到组成一个关键字并返回对应的对象。如果是用括号、逗号等特殊符号的表达式，则以此为界分割对象等，而括号是以先进先出为原则识别的（所以支持了嵌套的数据结构）。
程序指定的命令优先，但是作为自然的沟通方式的英语不是，它有几十万个单词，逐个对照识别是不现实的。所以作为文本预处理的第一步，我们只需要将单词简单粗暴地以常见的单位来分割即可，即单词/句子/指定分隔符。
单词分割
简单粗暴的分词，Haskell 的标准库已经有了，所以我们直接用即可
# ./src/Tokenization.hs
import Data.List (words)
import Data.Char (isSpace)
tokenize :: String -> [String]
tokenize text = words text
符号分割
我们在下述 “按分隔符分割” 的函数中定义了一个函数 splitOnDelimiters，它接受一个字符列表作为分隔符，和被分割的字符串。调用内部递归函数 go 来处理实际的分割任务，并返回处理结果。
span 部分的逻辑很简单：
token是从xs开始直到第一个分隔符之前的子字符串，rest是从第一个分隔符开始的剩余字符串。
从字符串 rest 开始，删除所有在分隔符列表 delimiters 中的字符，得到新的字符串 rest'。最后将 token 添加到结果列表中，并递归地调用 go 函数处理剩下的字符串 rest'，继续分割字符串。
另外，主函数调用后使用了 filter 过滤掉空字符串，确保返回的结果列表中没有空的子字符串。
# ./src/Tokenization.hs
import Data.List (words, dropWhile)
...
tokenizeWithDelimiters :: [Char] -> String -> [String]
tokenizeWithDelimiters delimiters text = filter (not . null) (splitOnDelimiters delimiters text)
where
splitOnDelimiters :: [Char] -> String -> [String]
splitOnDelimiters delimiters str = go str
where
go [] = []
go xs =
let (token, rest) = span (`notElem` delimiters) xs
rest' = dropWhile (`elem` delimiters) rest
in token : go rest'
句子分割
有了“按分隔符分割”的函数，以英语中的句子为单位分割就很简单了，只要将英语中分割句子的 .?! 作为分隔符调用上面的函数即可。
# ./src/Tokenization.hs
import Data.List (words, dropWhile, dropWhileEnd)
...
tokenizeSentences :: String -> [String]
tokenizeSentences text = map trim (tokenizeWithDelimiters ".!?" text)
where
trim = dropWhile (== ' ') . dropWhileEnd (== ' ')
测试
分词器的部分很简单，就这样。我在这里给一些测试代码，读者可以自行测试。
spec :: Spec
spec = do
describe "Tokenization" $ do
it "tokenizes text into words" $ do
tokenize "Hello world!" `shouldBe` ["Hello", "world!"]
it "tokenizes text into sentences" $ do
tokenizeSentences "Hello world! How are you? I am fine." `shouldBe`
["Hello world", "How are you", "I am fine"]
it "tokenizes text with custom delimiters including spaces, commas, and exclamation marks" $ do
tokenizeWithDelimiters [' ', ',', '!'] "Hello,world! How,are you!" `shouldBe`
["Hello", "world", "How", "are", "you"]
词干还原（Stemming）
在英语中由于词性和时态，一个单词可能会有多种形式，而所谓的“词干”就是单词的核心部分，是去除所有词缀（如前缀、后缀）之后的基本形式。
在自然语言处理中，我们经常通过词干还原来将变体词汇归纳为同一个词干，可以减少文本中的变异性。这里要注意与词形还原（Lemmatization）的区别：在词干还原中我们主要就是为了“简”，所以有时会提取成没有实际意义单词，例如 apple/apples -> appl；而相比之下词性还原更重视准确性和语义完整性，产生的结果要求是实际存在的词汇，适用需要较高语义精度的场景。
本文我示例实现的是一个经典的词干还原算法 Porter Stemmer （后面简称波特词干算法）。我们将词干还原过程分为多个阶段，每个阶段应用一组特定的规则。它可以说最初是为了搜索引擎而生的，当时是作为一个大型 Information Retrieval 项目的一部分被提出的。
注：本文的示例编写于我了解 Porter 本人对算法进行改进并发布的 Snowball 之前，在实测中我发现了最初版本的波特词干算法中的一些问题，在固定的算法步骤中，我自行作了一些改进（可能与更新版本的 Snowball 改进内容不同，仅自己的总结），我会说明我做了改进的地方，有一些可能只是我天真的自作主张，请读者多加辨别。
本章涉及的源代码，未特别强调的默认在源文件
./src/PorterStemmer.hs内。
CVC（Consonant-Vowel-Consonant）
我们知道英语中有元音 a,e,i,o,u，若 y 出现在其他辅音之后，它被认为是辅音，否则是元音。而除此之外的字母是辅音字母。
所谓的 CVC 是指 "辅音-元音-辅音" 的结构模式。后面我们会通过这种结构来确定是否应用特定的词干还原规则，所以在那之前，我们应该先实现判断单词的部分是否是CVC结构，由于涉及到对元音、辅音、双元音的判断，所以我们分开不同的函数写。
辅音
该函数会判断字符串指定位置的字符是否为辅音，内容还是很浅显的...其中也包含了对 y 是否为辅音的判断。
# ./src/PorterStemmer.hs
isConsonant :: String -> Int -> Bool
isConsonant word i
| i < 0 || i >= length word = error "Index out of bounds"
| c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' = False
| c == 'y' = i == 0 || not (isConsonant word (i - 1))
| otherwise = True
where
c = word !! i
元音
依赖上面判断辅音的函数，若传入的是正常的单词，则不是辅音的字符即为元音。
hasVowel :: String -> Int -> Bool
hasVowel word j = any (\i -> not (isConsonant word i)) [0..j]
单词的测度
在波特词干算法中，我们会定义一个 “Measure” 以表示单词或单词的一部分中，元音-辅音序列的数量。
以辅音/元音将组成单词的字母区分，任何单词或者单词的一部分都可以以 形式表示，其中下标 表示括号内重复出现的次数，方括号表示任意出现的内容。我们要这么做是因为，波特词干算法会有多个阶段的规则，每个阶段中的规则应用到单词需要有条件约束，防止最后单词被过度 “还原” 或者错误还原成一个没有意义的词干。
函数如下，返回的是从字符开始直到给定位置的测度。我们从单词的开头开始，初始化测度计数、位置指针为 0，额外定义两个函数处理辅音和元音字符并进行计数，思路应该是非常显然的。当遍历到单词的结尾或指定位置时，返回测度计数作为最终结果。
measure :: String -> Int -> Int
measure word j = countSequences 0 0
where
len = length word
countSequences n i
| i > j = n
| not (isConsonant word i) = countVowels n (i + 1)
| otherwise = countSequences n (i + 1)
countVowels n i
| i > j = n
| isConsonant word i = countSequences (n + 1) (i + 1)
| otherwise = countVowels n (i + 1)
还原流程
在波特词干算法中，单词实际被化为目标的词干要经过固定顺序的步骤（其中就会涉及，我们先前所实现的对单词结构的分析）
在还原步骤之前，我们先编写一些基本的函数。还原的过程肯定涉及到对单词后缀的检查，所以我们写一个函数判断单词是否以给定字符串结尾。
endsWith :: String -> String -> (Bool, Int)
endsWith word suffix
| suffixLen > wordLen = (False, 0)
| take suffixLen (drop offset word) == suffix = (True, offset - 1)
| otherwise = (False, 0)
where
wordLen = length word
suffixLen = length suffix
offset = wordLen - suffixLen
然后是对词尾应用变换的函数。其中的 setTo 是标准地将单词的后缀替换为新的后缀（传入要替换的末尾的索引位置），而后面的 apply 和 applyIf 是测度为正地应用、或者测度大于指定数值的应用。
setTo :: String -> String -> Int -> String
setTo word newSuffix j = take (j + 1) word ++ newSuffix
apply :: String -> String -> Int -> String
apply word newSuffix j =
if measure word j > 0 then setTo word newSuffix j else word
applyIf :: String -> String -> Int -> Int -> String
applyIf word newSuffix j m =
if measure word j > m then setTo word newSuffix j else word
Step 1
在算法的第一步，我们会处理最常见的词尾变化和变形的情况。
第一步是对结尾含有 s 的单词进行处理 ，注意，除了变形的复数词尾要去掉之外，只有在单词以 s 结尾且倒数第二个字符不是 s 的情况下，才会去掉最后一个 s。
step1a :: String -> String
step1a word
| (True, j) <- word `endsWith` "sses" = setTo word "ss" j
| (True, j) <- word `endsWith` "ies" = setTo word "i" j
| length word > 1 && last word == 's' && last (init word) /= 's' = init word
| otherwise = word
然后是对过去式和现在进行时的处理，若 ed/ing 前一个是元音，则需要进一步处理.
step1b :: String -> String
step1b word
| (found, j) <- endsWith word "eed", found = apply word "ee" j
| (found, j) <- endsWith word "ed", found && hasVowel (take (j + 1) word) j = step1b2 (take (j + 1) word)
| (found, j) <- endsWith word "ing", found && hasVowel (take (j + 1) word) j = step1b2 (take (j + 1) word)
| otherwise = word
“进一步处理” 是因为如果直接去除 ed/ing，对于例如 hopping -> hopp，我们期望的是 hop，所以要多加一个对于去除了词尾的单词的双辅音的判断。
hasVowelBeforeY :: String -> Int -> Bool
hasVowelBeforeY word index
| index < 0 = False
| otherwise = any (\i -> not (isConsonant word i)) [0..index]
以及类似于 troubling -> troubl -> trouble 一类的单词，我们也需要特殊处理，所以这些去除 ed/ing 后的单词我们还要进一步检查并处理它们的词尾。
最后是在单词测度为 1 且以 CVC 结构结尾时，通常需要在结尾添加回那个e，例如 caving -> cav -> cave，所以多加一个判断。
注意，这里我擅自让符合 handleDoubleConsonan 处理的单词也要经过 applyCVC 的判断，因为我在体验网上大部分 Porter/Snowball 的示例时都发现，hope 会被原样输出而 'hopping -> hop'，我去看原论文发现这貌似是符合预期的，但是我认为这比较不合理，所以擅自做了更改。
step1b2 :: String -> String
step1b2 word
| (found, j) <- endsWith word "at", found = setTo word "ate" j
| (found, j) <- endsWith word "bl", found = setTo word "ble" j
| (found, j) <- endsWith word "iz", found = setTo word "ize" j
| otherwise = applyCVC (handleDoubleConsonant word)
where
handleDoubleConsonant w
| hasDoubleConsonant w (length w - 1) =
if last w `elem` "lsz"
then w
else init w
| otherwise = w
applyCVC w
| measure w (length w - 1) == 1 && isCVC w (length w - 1) = w ++ "e"
| otherwise = w
英语中，很多形容词和副词以 y 结尾，其比较级和最高级通常会变为 i 例如 happy -> happier/happiest），所以我们对于以 y 结尾并且它前面有元音的单词，将 y 替换为 i。
step1c :: String -> String
step1c word
| (True, j) <- endsWith word "y", hasVowelBeforeY word (j - 1) = setTo word "i" j
| otherwise = word
hasVowelBeforeY :: String -> Int -> Bool
hasVowelBeforeY word index
| index < 0 = False
| otherwise = any (\i -> not (isConsonant word i)) [0..index]
Step 2-4
步骤 2-4 会比较简单，不涉及一些逻辑上的判断（只是直接对满足特定测度的词尾应用特定的规则），所以放在一起展示即可，其意义也很明显。
步骤二是对特定的派生后缀（如 "-ational", "-enci"）进行简化，统一具有相同词干但不同派生形式的单词。
step2 :: String -> String
step2 word
| (found, j) <- endsWith word "ational", found = apply word "ate" j
| (found, j) <- endsWith word "tional", found = apply word "tion" j
| (found, j) <- endsWith word "enci", found = apply word "ence" j
| (found, j) <- endsWith word "anci", found = apply word "ance" j
| (found, j) <- endsWith word "izer", found = apply word "ize" j
| (found, j) <- endsWith word "abli", found = apply word "able" j
| (found, j) <- endsWith word "alli", found = apply word "al" j
| (found, j) <- endsWith word "entli", found = apply word "ent" j
| (found, j) <- endsWith word "eli", found = apply word "e" j
| (found, j) <- endsWith word "ousli", found = apply word "ous" j
| (found, j) <- endsWith word "ization", found = apply word "ize" j
| (found, j) <- endsWith word "ation", found = apply word "ate" j
| (found, j) <- endsWith word "ator", found = apply word "ate" j
| (found, j) <- endsWith word "alism", found = apply word "al" j
| (found, j) <- endsWith word "iveness", found = apply word "ive" j
| (found, j) <- endsWith word "fulness", found = apply word "ful" j
| (found, j) <- endsWith word "ousness", found = apply word "ous" j
| (found, j) <- endsWith word "aliti", found = apply word "al" j
| (found, j) <- endsWith word "iviti", found = apply word "ive" j
| (found, j) <- endsWith word "biliti", found = apply word "ble" j
| otherwise = word
步骤三我们处理词缀变化较小的词汇。
step3 :: String -> String
step3 word
| (found, j) <- endsWith word "icate", found = apply word "ic" j
| (found, j) <- endsWith word "ative", found = apply word "" j
| (found, j) <- endsWith word "alize", found = apply word "al" j
| (found, j) <- endsWith word "iciti", found = apply word "ic" j
| (found, j) <- endsWith word "ical", found = apply word "ic" j
| (found, j) <- endsWith word "ful", found = apply word "" j
| (found, j) <- endsWith word "ness", found = apply word "" j
| (found, j) <- endsWith word "sion", found = apply word "s" j
| otherwise = word
步骤四字测度大于1时，删除基本的后缀。
step4 :: String -> String
step4 word
| (found, j) <- endsWith word "al", found = applyIf word "" j 1
| (found, j) <- endsWith word "ance", found = applyIf word "" j 1
| (found, j) <- endsWith word "ence", found = applyIf word "" j 1
| (found, j) <- endsWith word "er", found = applyIf word "" j 1
| (found, j) <- endsWith word "ic", found = applyIf word "" j 1
| (found, j) <- endsWith word "able", found = applyIf word "" j 1
| (found, j) <- endsWith word "ible", found = applyIf word "" j 1
| (found, j) <- endsWith word "ant", found = applyIf word "" j 1
| (found, j) <- endsWith word "ement", found = applyIf word "" j 1
| (found, j) <- endsWith word "ment", found = applyIf word "" j 1
| (found, j) <- endsWith word "ent", found = applyIf word "" j 1
| (found, j) <- endsWith word "ou", found = applyIf word "" j 1
| (found, j) <- endsWith word "ism", found = applyIf word "" j 1
| (found, j) <- endsWith word "ate", found = applyIf word "" j 1
| (found, j) <- endsWith word "iti", found = applyIf word "" j 1
| (found, j) <- endsWith word "ous", found = applyIf word "" j 1
| (found, j) <- endsWith word "ive", found = applyIf word "" j 1
| (found, j) <- endsWith word "ize", found = applyIf word "" j 1
| (found, j) <- endsWith word "hood", found = applyIf word "" j 1
| otherwise = word
Step 5
这是算法简化过程的最后一步。我们会删除单词结尾的无意义的 "e"，并且测度条件确保这种删除不会改变单词的词义。再简化以双辅音 "l" 结尾的单词，统一词根形式。
step5 :: String -> String
step5 word
| (found, j) <- endsWith word "e", found =
let stemmed = apply word "" j
m = measure stemmed (length stemmed - 1)
in if m > 1
then stemmed
else if m == 1 && not (isCVC stemmed (length stemmed - 1))
then stemmed
else word
| hasDoubleConsonant word (length word - 1) && last word == 'l' = init word
| otherwise = word
最后的处理
最后我们要做的就是把这坨东西给整合起来，但是在这里我自作了一个不知是否合适的主张，有部分特殊单词例如我最先注意到的 bus->bu，我不希望它这么变，所以额外做了一个“例外单词列表”，如果属于例外的则会直接返回不经过上述处理。
我会在结尾附上开源链接，里面有“例外单词列表”的源代码，读者可以自行查阅或选择略过这部分。如果日后我想继续完善这个东西，我会对不规则变形做一个对照表（暂时没有这个打算）。
import Word.ExceptionalWords(isExceptionalWord)
...
stem :: String -> String
stem word
| isExceptionalWord word = word
| otherwise = step5 (step4 (step3 (step2 (step1c (step1b (step1a word))))))
思考与改进？
写完正文的次日，我看完了 Porter 后续发布的有关 Snowball 的论文 很抱歉出于近期的时间问题，我不打算去实现它，所以我会就此尽量精确地提炼其中关于改进词干算法的观点，分享一点自己的想法。。
Snowball 是一种专门用于定义和实现词干提取算法的编程语言。它提供一种统一的描述语言，确保了词干提取算法的精确实现，避免了由于不同实现之间的误差而导致的问题。作者本人的说法是，发明 Snowball 的主要目的之一是填补现有词干算法在非英语语言中的空白，虽然在许多自然语言上已经进行了大量的词干提取研究，但大多数研究缺乏明确的算法描述，使得它们难以被广泛使用。
传统的词干提取算法精准度更容易导致引入新的同形异义词、或者去掉的后缀不足、去掉了词干的一部分，作者直接了当地称之为，过度/不足/错误词干提取。在非英语的语言这种问题会更多，非英语的西方语言中，我个人比较熟悉法语/德语，举个例子 réalité(抵抗)/réaliser(意识到) -> réal 就是一个错误的词干提取。虽然借助词典可以一定程度上减少这种问题，但是工作量巨大，而且时效性也会是问题。
最早的 Porter 词干化器完全不处理不规则形式，就例如news（我当时意识到了这个问题，而将它加入了例外单词表），但是作者在 Snowball 的论文中提及了一个有效的词干化算法应留有处理不规则形式的“空隙”，而不是将特殊形式硬编码到软件中的观点。还有对于停用词的问题 即搜索引擎为提高效率忽略的词，作者认为停用词词干化并不实用，例如英语的 be、法语有40多个变形的 être、德语那多到可以煮着吃的冠词。作者认为忽略它们或者叫建立一个映射是比较可行的（注意这篇论文是2001年的）
说那么多，Snowball 最重要的地方就在于——灵活，用户可以自行通过添加停用词表来调整词干提取的行为，确保停用词在检索过程中被有效处理。对于奇奇怪怪的不规则变换，它允许通过规则和异常词表来改进处理效果，减少词干提取中的错误。用户无需直接看到词干形式，系统可以在后台自动处理词干提取，并展示用户最频繁的代表词或处理过的查询结果（再强调这玩意是 2001 年的东西，尽管我们现代看来是显然的，但是在当时是相当先进的）。
随便的总结
我对这个 AHNLP 的初衷是实现一系列有关自然语言处理的算法，内容较为底层而非单一功能的，实目前对它的方向也没用特别明确，这篇文章只是偶然踏出的第一步。一方面是我水平和学习能力非常有限、另一方面是我的时间分配能力有待提高最近实在有点忙。还有就是我太久没写代码了，你可能不信，我写这些代码卡壳最多的地方是语法错误lmao。
我接下来可能想做一些九不搭八的东西，例如朴素贝叶斯分类器做过一些demo、SVM、卷积神经网络、循环神经网络什么的进行文本分类和分析，这些才是我熟悉的（骄傲）因为对于这个即兴的 “项目”，我还是出于一个比较没有计划的状态，当然非常欢迎对此有想法的读者提出见解。
引用资料 & 相关链接
Carleton University. Porter stemmer M.F. Porter, Snowball: A language for stemming algorithms Martin Porter's Home Page，里面有一个非常炫酷的旋转胡椒博士饮料瓶
我的 Github 链接们：
Github主页：https://github.com/MAKIROR 本文项目链接：https://github.com/MAKIROR/AHNLP 我的机器学习示例库：https://github.com/MAKIROR/RHML 初二时做的那坨东西：https://github.com/MAKIROR/ROR-KvDB
Ouyang Anqiao 02:16 03/08/2024
gzanqiao@hotmail.com
业余的 机器学习/计算机科学/数学 爱好者。
