重建拼写检查器,第3点:查找-化合物和解决方案

2021-01-15 20:25:27

这是“重建拼写检查器”系列的第三部分,专门介绍世界上最受欢迎的拼写检查器Hunspell的工作原理。

在第一部分中,我描述了Hunspell是什么;以及为什么我决定用Python重写它。它是一种解释性的重写,旨在通过将Hunspell的知识“翻译”为高级语言并附带大量评论来发掘Hunspell背后的知识。

在第二部分中,我介绍了查找(通过字典进行单词正确性检查)算法的基本知识,包括词缀压缩。

这部分是查找算法说明的后继内容,致力于单词复合以及一些不太复杂但仍然重要的问题:单词大小写和单词中断。为了理解这一部分,强烈建议阅读前一部分。至少,您应该记住,带有.dic-file所指定标志的词干具有.aff-file中定义的标志的含义。

许多语言,例如德语,荷兰语或挪威语,都有单词复合功能:两个词干可以连接在一起,产生新单词。要通过复合检查语言单词的拼写,拼写检查器需要将其分解为所有可能的部分,并检查是否存在部分组合,以使所有部分都是复合词中允许使用的正确词。

Hunspell有两种独立的机制可以在aff文件中指定语言的复合逻辑:每词干标志和类似regexp的规则。有时,两种机制都在同一词典中使用。

有一个通用的COMPOUNDFLAG指令来指定标志,将其附加到词干时,意味着“该词干可以在化合物中的任何位置”(例如来自LibreOffice的Norvegian词典的示例):

#在nb_NO.aff:...#指令中定义:任何带有" z"的单词标记允许位于化合物COMPOUNDFLAG z#中nb_NO.dic:... fritt / CEGKVz ...røyk/ AEGKVWz

fritt(“免费”)和røyk(“烟”)都带有z标志,这意味着它们可以在复合词中的任何位置,因此,“røykfritt”(“无烟” =“禁止吸烟”)为有效的人,也“frittrøyk”人1。

还有更精确的COMPOUNDBEGIN / COMPOUNDMIDDLE / COMPOUNDEND指令,设置只能在化合物中某个位置的词干标记。这些指令指定的标志可以自由地混合:一个化合物可以由标有通用COMPOUNDFLAG的部分和标有COMPOUNDEND的另一部分组成。

为了检查复合词的正确性,Hunspell需要截取所有可能长度的词的开头,并检查复合词开头是否允许使用有效词干。如果是这样,该算法将递归地分割下一部分,直到将整个单词拆分为复合部分(或找不到合适的部分)为止。

请注意,根据单词的长度以及化合物中允许有多少个词典单词,循环可能会花费一些时间:可以重复我们在上一部分中描述的过程(基于词缀的正确形式搜索)各种“部分候选人”的数十次。

还有另一种指定复合逻辑的方法。它是由COMPOUNDRULE指令实现的,它具有A * B?C之类的语句(意思是“正确的复合词由任意数量的带有标志A的单词,然后是带有标志B的一个或零个单词,然后是带有标志C的强制性单词组成” ”)。它的最常见用途是在数字中指定后缀。例如,在en_US词典中:

#en_US.affCOMPOUNDRULE 2#我们在下面列出了2条复合规则COMPOUNDRULE n * 1t#规则1:任意数量(*)带有" n"标记的茎,然后是" 1"标记的茎,然后是标记为“ t”的词干COMPOUNDRULE n * mp#规则2:任意数量(*)的标记为" n的词干,然后是" m"的词干,然后以"标记的词干#en_US.dic#...将数字定义为" stems"对于此规则:0 / nm1 / n12 / nm3 / nm4 / nm5 / nm6 / nm7 / nm8 / nm9 / nm#...并且数字后缀也作为词干,并且带有不同的标志!第0 / pt1st / p1th / tc2nd / p2th / tc3rd / p3th / tc4th / pt5th / pt6th / pt7th / pt8th / pt9th / pt

这导致Hunspell可以说“ 1201st”是正确的(规则n * mp匹配:“ 1”和“ 2”带有“ n”个标志,“ 0”带有“ m”,以及“ 1st”带有“ p” ”),“ 1211th”是正确的(另一个有效规则:n * 1t),但“ 1211st”则不正确。

在有COMPOUNDRULE的情况下处理单词正确性检查,需要再次将单词递归地拆分为可能的部分,但是这次应该检查已发现的部分是否与已知规则部分匹配。

使事情变得更复杂为了匹配现实生活的复杂性,两种复合词检查算法都需要考虑:

数字限制:某些词典可能会限制化合物一部分的最小尺寸或最大部分数。

词缀:默认情况下,复合词的开头允许使用任何前缀,结尾则允许使用任何后缀;但是,有些词缀可能带有标语“不应在任何化合物中使用”,而另一些词缀可能标有“允许在化合物中间使用”(例如,非第一个前缀或非-后缀)最后部分)。

aff文件中存在的一些规则拒绝将某些看似正确的复合词视为不正确:例如,如果复合词边界处的字母增加了三倍(fall + lucka);如果化合物的某些部分重复(dubb + bon + bon);如果化合物的非第一部分被大写,或者“在化合物部分的边界处禁止使用这种类似正则表达式的样式”,依此类推。

其中一些设置可能会在复合检查的中间导致一个全新的单词检查循环:例如,CHECKCOMPOUNDREP设置告诉算法:使用在aff文件中指定的REP表(典型的字母拼写错误的序列,例如“ f = > ph”,通常用于建议),以检查化合物的某些部分(应用替换词)是否为有效词。如果是,那么这是不正确的化合物!例如。 “ badabum”分为“ ba”,“ da”,“ bum”部分,但是,如果我们应用替换“ u => oo”,结果“ daboom”是正确的非复合词……那么我们应该认为“ badabum”是拼写错误的,而“ ba daboom”很可能是拼写错误的东西。

词缀检查和(解)复合是算法的主要部分,但还有更多内容!只是一个简短的概述,可以给您一些品味:

单词大小写:“ kitten”可以拼写为“ Kitten”或“ KITTEN”,而“ Paris”不能拼写为“ paris”……但是,该词在aff文件中可能带有定义为KEEPCASE的标志,这意味着仅在字典中的确切情况下;

…德语也有复杂之处:“ SS”可以小写为“ ss”或“ß”(“ sharp s”),都应通过字典进行检查;当单词为大写时,也应将其检查允许使用“ß”:“STRAßE”;

…以及突厥语中“ i”的大小写规则是不同的:“ i =>İ”和“ I =>ı”;

…化合物的结尾部分可能带有一个标语,标明“该化合物应标有首字母大写”:在瑞典语词典中,有一些特殊词,例如“ afrika”,只允许在化合物的末尾使用,并要求整个化合物放在标题中:“ Sydafrika”(南非);

分词:“ foo-bar”应作为整个词进行检查,也应作为两个单独的词“ foo”和“ bar”进行检查……除非aff-file通过禁止分词或更改应采用的模式来重新定义此词被打破。

词典中可能存在一些带有定义为FORBIDDENWORD的标志的单词:它用于禁止逻辑上可能存在的单词(允许的词干带有允许的后缀),但是这种特定的组合在语言上是错误的。

可能在aff-file中定义了一个ICONV(“输入转换”)指令,该指令指出在进行拼写检查之前要转换哪些字符:例如,用简单的'替换几种印刷撇号。简化字典或拆开连字(fi→fi)。但是,此功能不仅可以用于处理花式字体:例如,荷兰语词典使用它来强制使用“ ij”的适当大小写:在荷兰语中,它被视为单个实体,并且两个字母应始终具有相同的大小写。这是通过对连字的ICONCing来实现的:ij→ij和IJ→IJ(但是Ij不会转换,也不会在词典中找到,因为所有词典单词也都包含连字)。

一个在aff-file中定义的IGNORE伪指令,指示在拼写检查之前删除哪些字符(阿拉伯语和闪米特语,其中可能存在元音,但应忽略它们)。

要全面学习,请从Lookup .__ call__方法开始阅读Spylls文档。您不会失望的!

重申一下以上内容:有许多好而有用的字典可用于多种语言的拼写检查,并且可以以Hunspell的格式免费获得,并且可能会尝试在自己的代码中重用它们。但是,从不那么复杂的输入格式转变为完全可靠的拼写检查的过程至少包括:

读取aff文件(由多个指令“类型”组成,并且读取逻辑取决于特定指令)和dic文件(带有标志的单词)—我们将在以后的第二期中讨论这个有趣的任务;

词缀分析:即时(Hunspell和Spylls的做法),或者一次:将带有标志的词干列表“解包”为带有词缀的单词;

复合分析-除非您只想省略对复合语言的支持(显然无法通过预先生成的“所有正确复合词”列表来解决);

其中一些任务与Hunspell的构建方式直接相关,并且可能会以不同的方式完成。但是,大多数情况下,本章试图证明“检查单词是否拼写正确”,尤其是英语以外的语言,至少可以说是一项不那么琐碎的任务。

而且我们甚至还没有开始提出更正建议,我们很乐意在下一部分中进行。如果您不想错过后续活动,请在Twitter上关注我或订阅我的邮件列表!

PS:非常感谢我忠实的编辑@squadette。没有他的宝贵帮助,文本将更加令人费解!

第二种形式在Google中找不到-这种复合形式在语法上是正确的,但没有任何意义。 ↩

我承认,从正确的格式描述开始在逻辑上是正确的,但我想先告诉您最有趣的内容。将会有一篇关于文件格式以及如何阅读它们的文章。对于不耐烦的人,Spylls文档非常全面地介绍了aff和dic文件。 ↩

分享: