#text #codec #dictionary #compressor #forms #balkanoid

app serbzip

一种准无损巴尔干元语言压缩器

9个重大版本

0.10.0 2022年8月15日
0.8.0 2022年8月15日

#275 in 压缩

MIT 协议

120KB
2K SLoC

logo  

一种准无损巴尔干元语言压缩器。

Crates.io docs.rs Build Status codecov

背景

长期以来,人们普遍认为塞尔维亚语是俄语的紧凑变体,元音的使用不如俄语自由。自从1991年放弃里维埃拉以来,旅游收入的损失导致了元音使用的进一步简化。塞尔维亚人越来越需要经济实惠的沟通方式,因为元音并不便宜!

serb.zip是一个轻量级框架,用于将文本从一种词法形式转换为另一种形式。它目前附带一个编解码器——巴尔干语,它是塞尔维亚-克罗地亚语和俄语之间的通用转换器,几乎完全同构——它将一个语言领域映射到另一个语言领域,没有意义损失,有些损失空白和大小写。巴尔干语与英语和东斯拉夫语文本一起工作。

入门

安装

使用cargo安装serb.zip

cargo install serbzip

除非提供自定义字典文件,否则serb.zip需要编译的字典文件在~/.serbzip/dict.blk。第一次使用时,将自动下载并安装支持英语和俄语的基本字典。

压缩文件

当处理输入/输出时,serb.zip可以提供要读取和写入的文件,或者可以交互式运行。我们先尝试交互式压缩输入流。

serbzip -c

这会启动serb.zip,运行balkanoid编解码器,在交互模式下。

██████╗  █████╗ ██╗     ██╗  ██╗ █████╗ ███╗   ██╗ ██████╗ ██╗██████╗
██╔══██╗██╔══██╗██║     ██║ ██╔╝██╔══██╗████╗  ██║██╔═══██╗██║██╔══██╗
██████╔╝███████║██║     █████╔╝ ███████║██╔██╗ ██║██║   ██║██║██║  ██║
██╔══██╗██╔══██║██║     ██╔═██╗ ██╔══██║██║╚██╗██║██║   ██║██║██║  ██║
██████╔╝██║  ██║███████╗██║  ██╗██║  ██║██║ ╚████║╚██████╔╝██║██████╔╝
╚═════╝ ╚═╝  ╚═╝╚══════╝╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═══╝ ╚═════╝ ╚═╝╚═════╝

Enter text; CTRL+D when done.

让我们输入Mearns的《安提戈涅》的第一节。逐行输入以下文本,完成后按CTRL+D。

Yesterday, upon the stair,
I met a man who wasn't there!
He wasn't there again today,
Oh how I wish he'd go away!

serb.zip回显压缩版本

Ystrdy,          pn th       str,
I  mt a mn wh wasn't      thr!
   H wasn't      thr         gn   tdy,
      H  hw I  wsh    h'd  g  wy!

不过,你通常想要压缩文件并将输出写入另一个文件

serbzip -c -i antigonish.txt -o antigonish.sz

这将从当前目录中的antigonish.txt读取并写入到antigonish.sz。按照惯例,我们在serb.zip文件上使用.sz扩展名,但你可以使用任何你喜欢的扩展名。

展开/解压缩文件

扩展操作是压缩的逻辑逆,使用了许多相同的参数。唯一的不同点:使用 -x 标志而不是 -c

serbzip -x -i antigonish.sz -o antigonish.txt

高级用法

自定义字典

serb.zip 可以与自定义字典文件一起运行。字典可以通过 -d 标志指定——可以是换行符分隔的单词列表(.txt)或二进制图像(.blk)。

单词列表是最简单的方法,但解析列表、生成指纹和排序映射向量需要花费时间。尽管如此,它对于测试仍然很有用。

首选的方法是从单词列表编译二进制图像,并在此之后使用二进制图像。

custom.txt 编译成 custom.blk

serbzip -p -d custom.txt -m custom.blk

在压缩和扩展期间使用 custom.blk

serbzip -d custom.blk ...

注意:字典的一致性对于算法的可逆性至关重要。换句话说,如果您使用一个字典来压缩流,然后使用另一个字典来扩展它,某些单词可能不会匹配。默认字典包含约 50K 个英语单词和约 50K 个俄语单词,应该对大多数人来说足够了。

切换编解码器

serb.zip 包含几个编解码器,其中 balkanoid 是默认编解码器。其他编解码器仍在开发中。使用 --codec 标志指定备用编解码器。

获取帮助

如果您正在使用此应用程序,您可能需要寻求专业帮助。

如果您遇到困难,请运行 serbzip --help

serb.zip 作为库使用

要将 serb.zip 嵌入您的应用程序,请遵循以下 说明

serb.zip 的工作原理

每个编解码器的工作方式都不同。它们共享一些共同的概念,但底层算法可能完全不同。

Balkanoid

Balkanoid 是著名的编解码器,是所有这些的起点。它通过组合 字典映射一元编码 之间的压缩和扩展形式映射,而不丢失意义。

Balkanoid 的字典是从一个 指纹 到满足该指纹的所有字典单词的排序向量的映射。指纹通过移除所有元音并将剩余字符转换为小写来获取。例如,"Apple" 的指纹是 "ppl"

字典本质上是一个 HashMap<String, Vec<String>>。向量通过比较单词的长度(最短首先)然后按字典顺序排序。

对于示例单词列表

at
came
cent
come
count
in
inn
it
no
on

生成的字典是

"cm" -> ["came", "come"]
"cnt" -> ["cent", "count"]
"n" -> ["in", "no", "on"]
"t" -> ["at", "it"]
"nn" -> ["inn"]

字典加载完成后,算法通过逐行遍历输入文件。每一行随后通过空白字符进行分词,忽略连续的空白字符序列(此处用字符表示,以提高可读性)。例如,下面这行"To␣be...␣␣␣␣␣or␣␣␣␣␣not␣to␣be!"被捕获为六个单词:["To", "be...", "or", "not", "to", "be!"]。空行或只包含空白字符的行会被分词为[]

每个生成的单词都要受到三个规则集的影响——标点符号、压缩和大小写——按照这个顺序应用。

标点符号规则用于有效地处理带标点的单词,如"banana!"。通常,"banana"会是一个简单的字典查找,但感叹号却是一个麻烦。标点符号将每个单词分成一个前缀和一个后缀。前缀包含从单词开始处的连续字母字符。后缀包含所有其他字符。

  1. 如果单词的第一个字符是反斜杠('\'),则将反斜杠移动到前缀的开头。对于第二个和后续字符,将字符串开头的最长连续字母字符移动到前缀中,而将剩余的字符串分配给后缀。
  2. 如果第一个字符不是反斜杠,则将单词分割,使前缀包含从单词开始处的最长连续字母字符。后缀包含所有其他字符。

例如,对于"bananas!!!",根据规则2,标点符号组为("bananas", "!!!")。对于一个没有标点的单词,前缀包含整个单词(再次根据规则2),而后缀是一个空字符串;例如,"pear"分割为("pear", "")。对于像"\foo?"这样的单词,根据规则1,标点符号组为("\foo", "?")——第一个反斜杠被允许在前缀中。对于一个单独的反斜杠"\",结果是("\", ""),按照规则1。对于一系列的反斜杠"\\\",结果是("\", "\\")

当一个单词由非字母字符分隔的多个片段组成时,只有第一个片段被分配到前缀;例如,"[email protected]"变为("dog", "@pound.com")。这是一个相对较长的后缀的罕见例子;通常,后缀包括尾部的标点符号,这在英语和东斯拉夫语中很常见。尽管人们可能会认为多片段单词可以表示为N元组并相应地编码,但这会使某些单词的算法不可逆。

**压缩规则**用于去元音化单词,是算法的核心。它首先取标点符号组的前缀元素的小写表示,并删除所有元音(在英语变体中不包括'y')。压缩规则不适用于元组的后缀元素——后缀按原样编码。在实践中,后缀比前缀短得多。该规则包括四个部分

  1. 如果单词前缀以反斜杠开始('\'),则将其视为转义序列。在前面添加另一个反斜杠,并返回单词前缀。例如,"\sum"编码为"\\sum"。此规则主要用于编码包含排版命令的论文,如TeX和Markdown。
  2. 将单词前缀转换为小写并生成其指纹。解析小写前缀在从指纹映射的字符串向量中的位置(基于0)。如果单词前缀在字典中,则通过填充空格字符字符串来编码它——字符串的长度等于前缀在向量中的位置——然后输出指纹。例如,假设单词前缀 "no" 在其指纹的字典映射中位于第二个位置: "n" -> ["in", "no", "on"]。它将被编码为 "␣n"——一个空格后跟其指纹。单词 "on" 需要两个空格——"␣␣n"
  3. 否则,如果单词前缀不在字典中并且包含一个或多个元音,则按原样编码。例如,单词前缀 "tea" 不在我们示例字典中,但包含元音,编码为 "tea"
  4. 否则,如果单词前缀仅由辅音组成并且其指纹不在字典中,则按原样编码。例如,单词前缀 "psst" 未映射,因此编码时不变——"psst"。这种情况在东斯拉夫语中比在英语中更为常见;在后者中,仅由辅音组成的单词要么是缩写、首字母缩略词或声音的表示。
  5. 否则,在单词前缀前加一个反斜杠('\')。例如,单词前缀 "cnt" 由所有辅音组成,在现有指纹 "cnt" -> ["cent", "count"] 中没有可解析的位置,编码为 "\cnt"。如果没有这个规则,没有前导空格的 "cnt" 可能会颠倒成 "cent"... 或其他完全不同且不太合适的内容。

大写规则将大写提示编码到输出中,以便可以恢复单词前缀的大写形式。这些规则不是完全可逆的,但绝大多数情况下表现良好。

  1. 如果输入中在第二个字母之后有任意大写字母,则整个输入大写。
  2. 否则,如果输入以大写字母开头,则仅将第一个字母大写,并将输入的其余部分附加到后面。
  3. 否则,如果输入没有大写字母,则不变地将其输出。

每个前缀的编码输出随后与后缀结合,形成完整的、编码后的单词。

一旦每个单词的编码输出被推导出来,通过连接所有输出(使用单个空格字符连接连续的配对)得到结果行。我们早期示例的输出 — ["␣n", "tea", "psst", "\cnt"] 组合成了字符串 "␣n␣tea␣psst␣\cnt"

像压缩一样,扩展首先通过标记每一行开始。只是在扩展的情况下,连续的空白序列不会被丢弃 — 需要它们的计数来解码 压缩规则 1 的输出。这是算法的 一元编码 部分。可以将其视为 运行长度编码 的逆过程。

对于每个标记化的单词,我们首先应用标点符号规则,然后是反向压缩,然后是大写化。

这里的标点符号与之前相同。单词被分割成标点符号元组。前缀被解码,后缀则保持原样。

反向压缩 规则如下

  1. 如果单词前缀以反斜杠开头,则将其删除,并返回剩余的子字符串。例如,编码的单词前缀 "\trouble" 被解码为 "trouble"。单个反斜杠 "\" 解码为空字符串。该规则反转了压缩规则集中规则 1 和规则 5 的输出。
  2. 否则,检查单词前缀的小写版本中的元音。如果至少找到一个元音,则返回小写字符串。例如,单词前缀 "german" 被传递。
  3. 否则,如果小写字符的单词前缀只包含辅音,则将其视为指纹。通过查找位置由前导空格的数量指定的单词在字典中解决。如果指纹在字典中,则始终可以找到原始单词。 (例外是使用了两个不同的字典,这被视为错误。)例如,给定映射 "n" -> ["in", "no", "on"],编码的单词前缀 "␣␣n" 解码为 "on"
  4. 否则,如果指纹不在字典中,则按原样返回单词。例如,如果字典中没有其指纹的映射,则 "kgb" 将被传递。

在反压缩后,将按照压缩路径应用首字母大写规则。首字母大写通常是可逆的——它适用于以大写字母开头或只包含大写字母的单词,例如缩写词。然而,它并不能总是逆转混合大小写的单词以及缩减为单个辅音字母的单词。考虑以下示例。

"Apple"编码为"Ppl,假设字典中包含"ppl" -> ["apple", ...]。它可以正确解码回"Apple"

"KGB"编码为"KGB",因为没有对指纹"kgb"的字典映射,并且可以正确解码。

"LaTeX"编码为"LTX",假设它在字典中存在。它解码为"LATEX",错误地大写了某些字母。这是混合大小写问题的例子。然而,如果单词不在字典中,它将按原样编码,并且首字母大写将被正确恢复。

在实践中,由于缩写词通常不在字典中,因此混合大小写的问题很少发生;这样的单词很少会受到压缩——它们被直接编码。

"Ra"(古埃及的太阳神)编码为"Ra",给定字典映射"r" -> ["ra", ...]。首字母大写被正确逆转。然而,如果输入是缩写词"RA",它也将被编码为"Ra"——在这种情况下首字母大写不可逆。再次,如果"ra"不在字典中,单词将按原样编码,首字母大写将是可逆的。

压缩效率

serb.zip从语言学的角度来看很有趣,但它实际上压缩了吗?

下表显示了使用Balkanoid编解码器压缩一系列文学作品的结果。这些作品的大小从几百千字节到几兆字节不等。对于每个文本,显示了serb.zip输出的大小,以及相对于原始大小的百分比减少。(负值表示相对于原始大小增加了。)

原始文本及其“serb-zipped”变体随后在--best设置下分别进行了gzipbzip2二进制压缩。观察二进制压缩后结果是否改变很有教育意义。记录了大小和压缩比例。

完整的测试集被分为两部分:英语文本和俄语文本。英语测试集要大得多——21部作品对比5部。

英语文本

文件名 大小 单词数 gzip大小 bzip2大小 sz大小 sz压缩率% sz.gz大小 sz+gz压缩率% sz.bz2大小 sz+bz2压缩率%
no_man_is_an_island.txt 396 81 289 283 366 7.57 258 10.72 261 7.77
antigonish.txt 478 97 282 293 552 -15.48 263 6.73 269 8.19
a_dream_within_a_dream.txt 652 141 414 404 648 .61 381 7.97 374 7.42
the_raven.txt 6587 1068 2753 2610 6250 5.11 2513 8.71 2440 6.51
metamorphosis.txt 142017 25094 51125 41494 135843 4.34 47295 7.49 40236 3.03
alice_in_wonderland.txt 174313 29594 61021 49027 167360 3.98 57207 6.25 48216 1.65
the_prince.txt 307808 52982 112051 86353 284168 7.68 103035 8.04 84642 1.98
calculus_made_easy.txt 404533 56128 128753 103437 376411 6.95 122490 4.86 102025 1.36
frankenstein.txt 448821 78122 168673 126241 408328 9.02 154384 8.47 123996 1.77
sherlock_holmes.txt 612668 98533 212198 153006 532337 13.11 192828 9.12 151134 1.22
pride_and_prejudice.txt 798774 124753 267241 182367 671468 15.93 241914 9.47 182294 .04
effective_kafka.txt 832006 121588 260631 186466 740534 10.99 244580 6.15 185031 .76
dracula.txt 881217 164382 335208 245421 855606 2.90 315240 5.95 244016 .57
new_testament.txt 1020010 182644 344546 248323 978194 4.09 326802 5.14 247227 .44
jane_eyre.txt 1084733 188452 428029 317669 1028088 5.22 397902 7.03 311810 1.84
crime_and_punishment_eng.txt 1201520 206553 439388 319534 1161086 3.36 412300 6.16 315694 1.20
moby_dick.txt 1276235 215864 511491 389164 1208689 5.29 476706 6.80 383487 1.45
mormon.txt 1588965 293164 453627 313667 1528402 3.81 425963 6.09 313170 .15
anna_karenina_eng.txt 2068079 352857 743362 535118 1958820 5.28 694156 6.61 529153 1.11
count_of_monte_cristo.txt 2786940 464031 1012102 724410 2600665 6.68 939973 7.12 714182 1.41
war_and_peace_eng.txt 3359372 566334 1221693 888312 3120825 7.10 1134553 7.13 880502 .87

在英语测试集中,单独使用serb.zip压缩在大多数情况下都显著减小了大小。最大的减小出现在《傲慢与偏见》中,达到15.93%,其次是《福尔摩斯回忆录》的13.11%。在大多数情况下,大小的减小是单个位数。在《梦中的梦》中几乎没有变化,压缩率仅为0.61%。

然而,在一种情况下——《安提戈涅》——输出大小增加了15.48%。

应用gzipbzip2真的很有趣。在所有情况下,与没有使用serb.zip的等效二进制压缩相比,输出大小都有所减小。对于gzip,改进范围从《微积分简单易学》的4.86%到《无人是孤岛》的10.72%。对于bzip2,最小改进出现在《傲慢与偏见》上,为0.04%;最大改进出现在《安提戈涅》上,为8.19%。这很有趣,因为《安提戈涅》单独使用serb.zip的结果很差。然而,尽管文件大小增加,信息熵以不成比例的更大速度下降。这有助于二进制压缩器实现更好的总体结果。

俄语文本

文件名 大小 单词数 gzip大小 bzip2大小 sz大小 sz压缩率% sz.gz大小 sz+gz压缩率% sz.bz2大小 sz+bz2压缩率%
u_lukomorya.txt 1599 169 754 609 1528 4.44 744 1.32 620 -1.80
lyublyu_tebya.txt 2290 205 1032 830 2189 4.41 1022 .96 832 -.24
odnazhdy.txt 2359 237 1031 885 2333 1.10 1047 -1.55 905 -2.25
anna_karenina_rus.txt 3072666 288389 802824 520413 3319009 -8.01 841072 -4.76 528303 -1.51
war_and_peace_rus.txt 5368089 494556 1436738 935792 5618619 -4.66 1490941 -3.77 955191 -2.07

对于俄语测试集,结果大相径庭。serb.zip运行的大小差异在4.44%和-8.01%之间。使用二进制后压缩结果没有改善。值得注意的是,《安娜·卡列尼娜》和《战争与和平》在各方面都表现最差。它们也是测试集中最大的作品。

似乎Balkanoid在压缩俄语文本方面不太有效。以下提出了一个理论来解释原因。

在现代英语中,名词没有其他形式,只有单数和复数。在俄语中,名词有变化——这个过程称为“变格”(declension),它给单词不同的结尾,在单数和复数中各有六个情况:属格(nominative),与格(genitive),宾格(dative),主格(accusative),工具格(instrumental),和前置格(prepositional)。此外,俄语有性别:阳性、阴性和中性。

在编码英语单词时,如果单词的单数和复数形式都在字典中,则该单词在所有情况下都可以有效地压缩。在俄语中,单词有众多变体,给定单词在输入文本中恰好以字典中的形式出现的可能性大大降低。在没有语法意识的情况下,仅靠字典压缩似乎不足以实现一致和可衡量的压缩增益——与英语文本观察到的增益相当。

常见问题解答

serb.zip是否可行?

serb.zip(即Balkanoid编解码器)在包括《战争与和平》和《有效的卡夫卡》等文学杰作在内的众多文本上进行了测试,发现它可以在所有情况下正确压缩和展开每个单词。总共评估了超过400万字的27篇文本。其中一些甚至包含了排版命令。serb.zip可行。

它的局限性是什么?

警告和局限性在如何使用serb.zip部分中解释。总的来说

  • 单词之间的连续空格,以及前导和尾随空格将无法恢复。
  • 一些混合大小写的单词的字母大小写将无法正确恢复。
  • 一些包含一个辅音的缩写将无法正确恢复。
  • 该算法要求压缩和展开时使用相同的字典。它无法检测运行之间字典是否已更改。在许多情况下,这将产生可读的展开,尽管输出可能不对应于原始内容。

在其他所有方面,Balkanoid是一个完全可恢复的编解码器。换句话说,压缩输出可以在展开后准确恢复以匹配原始输入。上述局限性在很大程度上是不相关的——它们不影响理解。

serb.zip和Balkanoid之间有什么区别?

serb.zip是一个用于开发、测试和执行将一种词汇形式映射到另一种形式的编解码器的框架。Balkanoid是编解码器的一个实现。在运行serbzip命令而未指定编解码器时,默认将使用Balkanoid。

我喜欢这个项目。我如何贡献?

如果你对这种嘲讽感兴趣,请加入。

能有更多可逆的、可读的转换会很好。猪拉丁语可能是一个好例子。当前的算法很简单,但不是可逆的。也许稍加修改,就可以制作一个完全可逆的无损猪拉丁语编解码器。

serb.zip高度模块化;你可以插入自己的serbzip::codecs::Codec实现,然后开始。

依赖关系

~6–18MB
~274K SLoC