选举2029：邮政编码
在上一篇关于记录和集合的实践性文章之后，这篇文章不太可能给任何人关于如何在自己项目中解决问题的启发，也没有向微软提出任何功能请求。不过，我发现这个领域真的很有趣。
英国邮政编码简介
我意识到这篇博客文章的大多数读者可能不在英国。大多数国家都有某种形式的邮政编码，但具体细节因国家而异。例如，英国邮政编码与美国邮政编码在覆盖范围上非常不同。英国邮政编码非常精细——通常只是一条街道的一部分——所以知道门牌号和邮政编码通常足以定位到一个精确的地址。
对我的选举网站来说重要的是，每个邮政编码都位于单一的选区——而这正是我想使用它们的目的。我的选区页面允许您开始输入选区名称或邮政编码，并在您输入时过滤结果。我怀疑相当一部分英国人口知道自己的邮政编码，但不知道自己的选区名称（尤其是在2023年选区边界变更之后），因此能够指定两者中的任何一个都很有帮助。
维基百科上有更多关于英国邮政编码的信息，但我在这里简要总结一下。请注意，我只关心现代邮政编码——维基百科有关于事物如何演变的历史细节，但我的网站不需要关心遗留的邮政编码。
邮政编码由一个外部编码（或外向编码）后跟一个内部编码（或内向编码）组成。外部编码是一个区域后跟一个地区，内部编码是一个扇区后跟一个单元。例如，我的邮政编码是RG30 4TT，分解为：
- 外部编码：RG30
- 区域：RG
- 地区：30
- 内部编码：4TT
- 扇区：4
- 单元：TT
内部编码非常规整：它总是由一个数字后跟两个字母组成。（这两个字母在一个20个字符的字母表内。）外部编码则更“有趣”，因为它们属于以下七种格式之一，其中“9”代表“任何数字”，“A”代表“一个字母”（尽管字母表有所不同）：
- AA9
- AA99
- A9
- A99
- A9A
- AA9A
注意，前两种外部编码格式仅在于它们是有一个还是两个数字——并且记住内部编码总是以数字开头。当解析预期表示完整邮政编码的文本时，这没有问题（因为你可以通过假设最后三个字符是内部编码来判断外部编码的长度）——但当我需要解析一个不完整的邮政编码时，它可能是模糊的。例如，“RG31 4FG”和“RG3 1AA”都是有效的邮政编码，并且由于我不想强迫用户输入空格，“RG31”应该显示两个邮政编码对应的选区（分别是“Reading West and Mid Berkshire”和“Reading Central”）。
需求
在我的选举网站中使用邮政编码的需求非常简单：
- 从外部来源（我找到的是国家统计局）摄取数据。
- 以紧凑的格式存储我们所需的一切，理想情况下存储在单个 Firestore 文档中（即 1MB）。
- 将数据保存在内存中，仍然使用相当紧凑的格式。
- 提供一个 API，输入为“邮政编码前缀”，返回“所有以该前缀开头的邮政编码所覆盖的选区集合”，并且速度足够快，让人感觉“即时”。
有趣的是，维基百科提到“一个包含所有170万个邮政编码的表格”，但我目前摄取的文件有 2,712,507 个条目。我过滤掉了一些，但最终仍然有 2,687,933 个不同的邮政编码。我不知道维基百科的数字是笔误，还是确实存在差异。
剧透警告：网络延迟很容易主导向 API 发出请求的延迟。在慕尼黑使用机场 WiFi（对于免费 WiFi 来说相当不错）时，我看到的往返时间约为 60 毫秒，而页面在我输入时感觉几乎是即时更新的。但在 ASP.NET Core 内部的时间不到一毫秒（这还包括按选区名称进行过滤）。
存储和内存格式
从逻辑上讲，输入数据只是一系列“邮政编码，选区代码”条目。选区代码长度为 9 个字符。这意味着对于 2,712,507 个条目，一个非常朴素的表示（假设邮政编码平均为 7 个字符，选区代码为 9 个字符，每个条目占用 16 个字符）将刚好超过 42MB，这还没有考虑将数据拆分为条目所需的开销。我们肯定能做得更好。
这里有大量的冗余——我们肯定能做得更好。首先，我朴素的计算假设每个字符使用一个字节，即使我们需要的每个字符都在 A-Z、0-9 的范围内（即一个 36 个字符的字母表）——并且这些值中的几个字符被限定只能是数字。
按外部编码分组
但是，在我们开始编写复杂代码以更少的字节表示条目字符串值之前，实际数据中存在更多冗余。邮政编码并不是随机分配给所有选区的。同一扇区（例如“RG30 4”）内的大多数邮政编码都将位于同一选区。即使我们按外部编码（例如“RG30”）分组，每组中代表的选区数量也相对较少。
在撰写本文时，有 3077 个外部编码：
- 851 个完全位于 1 个选区内
- 975 个位于 2 个选区内
- 774 个位于 3 个选区内
- 348 个位于 4 个选区内
- 98 个位于 5 个选区内
- 21 个位于 6 个选区内
- 8 个位于 7 个选区内
- 2 个位于 8 个选区内
我们还需要区分无效和有效的邮政编码——因此我们可以将“根本没有选区”视为上述每行中的一个额外选区。
在每个外部编码中，有 4000 个可能的内部编码，它们总是相同的（0AA, 0AB .. 9ZY, 9ZZ）。因此，对于每个外部编码，我们只需要一个包含 4000 个值的数组。
一个简单的表示，每个值使用一个字节，那么每个映射就是 4000 字节，有 3077 个这样的映射（每个外部编码一个）——那就是 12,308,000 字节。
压缩映射
我们是否可以通过利用我们并不真的需要每个值一个完整字节这一事实来做得更好？对于那 851 个位于单一选区的外部编码，每个值将是 0 或 1。对于那 975 个位于两个选区的外部编码，每个值将是 0、1 或 2——依此类推。即使不跨字节分割数据，我们也可以将这些映射存储为：
- 851 个映射，每个值 1 位（每个映射 500 字节）
- （975 + 774）个映射，每个值 2 位（每个映射 1000 字节）
- 剩余（348 + 98 + 21 + 8 + 2）个映射，每个值 4 位（每个映射 2000 字节）
总共是 (851*500) + ((975 + 774) * 1000) + ((348 + 98 + 21 + 8 + 2) * 2000) = 3,128,500 字节。这听起来很棒——节省了映射所需空间的四分之三！但它仍然远远超过 Firestore 文档的最大大小。而且，当然，对于每个外部编码，我们还需要外部编码文本，以及映射中代表的选区列表。这应该不会太多，但对于已经超支的大小预算来说并没有帮助。
在这一点上，我尝试了多种选项，包括按扇区而不是外部编码进行分组（因为实际上很少有外部编码拥有全部十个可能的扇区，并且在一个扇区内，选区数量可能更少，因此我们将有更多扇区可以用每个值 1 位或 2 位来表示）。我尝试了手工制作的行程编码和各种选项。我确实成功地将数据压缩了很多——但代码变得越来越复杂。从根本上说，我所做的是执行压缩，并试图应用一些关于数据的知识来达到一个不错的压缩水平。
大约在这个时候，我决定不再试图让代码变得更聪明，而是尝试让代码更简单，并依赖现有代码的聪明。简单的 4000 字节映射包含大量冗余。我没有手动挤出这些冗余，而是尝试了通用压缩——使用 DeflateStream 和 InflateStream。结果超出了我的预期：压缩后的映射总大小仅为 500,602 字节。这为每个外部编码的额外信息留下了充足的空间，同时仍然远低于 1MB 的文档限制。
我需要指出的是，当我谈到存储选项时，我提到了使用 Google Cloud Storage 代替 Firestore 的可能性——那样的话就根本不需要这种压缩了。虽然删除压缩代码会很好，但它是一个非常独立的功能块——最终实际上只有大约 15 行代码。
处理请求
那么，存储需求得到满足后，我们完成了吗？事实证明，差不多。我将所有内容以未压缩的形式保存在内存中，每个按外部编码的映射为每个内部编码存储一个字节——如前所述，导致内存占用略高于 12MB。这没问题。每个按外部编码的映射都存储为一个 OutcodeMapping。
将前缀转换为一组可能选区的过程比较繁琐，仅仅是因为格式的模糊性。对于单个字符，我不返回任何内容——要求用户在开始处理之前输入邮政编码的两个字符是合理的。
很容易存储一个“前两个字符”到“可能的 OutcodeMapping 条目列表”的字典。该列表总是相当短，并且可以非常迅速地筛选为“仅与提供的前缀实际匹配的条目”。对于每个匹配的 OutcodeMapping，然后我们需要找到由提供的剩余前缀的内部编码部分可能代表的选区。
例如，如果用户键入了“RG30”，那么我们将迅速筛选到“RG3”和“RG30”作为匹配的外部编码。由此，我们需要说明：
- RG3 中以“0”开头的内部编码代表哪些选区？
- RG30 的内部编码代表哪些选区？（对于该外部编码，我们已经消耗了提供的整个前缀。）
通过将其拆分为外部编码和内部编码，事情变得简单得多，因为内部编码格式非常简单。例如，如果用户键入了“RG30 4”，那么上面的问题就变成了：
- RG3 中以“04”开头的内部编码代表哪些选区？
- 不可能有，因为内部编码的第二个字符永远不会是数字。
- RG30 中以“4”开头的内部编码代表哪些选区？
在一个外部编码映射中，我们总是要处理零个、一个、两个或三个字符：
- 零个字符：该外部编码的完整选区集合
- 一个字符：该“扇区”的选区集合（我们可以很容易地缓存；每个外部编码只有十个扇区）
- 两个字符：最繁琐的一个——在映射中查找该“半单元”的所有 20 种可能性。
- 三个字符：一个邮政编码，所以只需在映射中查找；结果要么是空（如果邮政编码无效），要么是一个单一条目的结果。
我怀疑我的实现还有更多效率可以挖掘——但它已经足够快，我根本不在乎。在某个时候，我可能会做一个负载测试，看看在保持低延迟的同时，我可以处理多少请求……但我非常惊讶这会成为问题。（嘿，如果有必要，Cloud Run 会启动更多实例。）
结论
我喜欢这个话题有两个原因。首先，它是如此独立。你不需要了解网站的其他部分、选举民调、政党等，就能理解这个小领域。你需要了解邮政编码和选区，仅此而已。除此之外，这使它成为一个愉快的写作主题。其次，结果似乎非常令人印象深刻，而付出的努力相对较少。在大约半兆字节的数据中，我们存储了超过 270 万个邮政编码的信息，并且最终的查找成本极低。
在文章中采取的方法之间，也存在一个有趣的并非完全矛盾的地方。
首先，尽管数据在某种程度上是将一个 6/7 字符的输入（邮政编码）映射到一个 9 字符的输出（选区代码），但它远非随机。只有 650 个选区，并且选区显然在邮政编码方面非常“聚集”（因此，两个仅在第五个或之后字符不同的邮政编码很可能属于同一个选区）。我所采取的方法利用我们对数据的了解作为第一道工序——因此这方面是非常特定领域的。仅仅压缩“邮政编码 选区代码”行文件只能让我们压缩到刚刚超过 7MB。
相比之下，当我们已经进展到“对于每个外部编码，我们有一个包含 4000 个条目的映射，每个条目映射到一个介于 0 和 8 之间（含）的数字”（并且意识到对于许多外部编码，数字要么在 0-1 之间，要么在 0-2 之间）时，试图“聪明”并没有很好地奏效。随着我试图将尽可能多的信息打包到每个字节中，代码变得越来越复杂……而当我将领域无关的压缩应用于每个映射时，结果非常好。
我认为，在编写代码以利用已知数据特征与依赖现有的领域无关算法之间找到平衡，这种情况并不少见。这只是我所遇到的最清晰的例子之一。