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个字符。这意味着一个非常朴素的2712507个条目的表示，每个条目占用16个字符（假设邮政编码平均为7个字符，选区代码9个字符），将略低于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”作为匹配的外码。由此，我们需要说明：

哪些选区是由以“0”开头的RG3的内码表示的？
哪些选区是由RG30的内码表示的？（对于该外码，我们已经消耗了所提供的整个前缀。）

通过将其拆分为外码，然后内码，它使生活变得简单得多，因为内码格式非常简单。例如，如果用户键入了“RG30 4”，那么上面的问题就变成了：

哪些选区是由以“04”开头的RG3的内码表示的？
- 不可能有这些，因为内码的第二个字符永远不会是数字。
哪些选区是由以“4”开头的RG30的内码表示的？

在外码映射中，我们总是处理零个、一个、两个或三个字符：

零个字符：该外码的完整选区集合
一个字符：该“扇区”的选区集合（我们可以很容易地缓存；每个外码只有十个扇区）
两个字符：最棘手的一个——在映射中查找该“半单元”的所有20种可能性。
三个字符：一个单独的邮政编码，所以只需在映射中查找；结果要么是什么都没有（如果邮政编码无效），要么是单条目结果

我怀疑这里可以从我的实现中挤出更多的效率——但它已经足够快，我真的不在乎。在某个时候，我可能会做一个负载测试，看看在保持低延迟的同时可以处理多少请求……但我非常惊讶这会造成问题。（而且，嘿，如果需要的话，Cloud Run会启动更多的实例。）

结论

我喜欢这个话题的两点。首先，它是如此独立。你不需要了解网站的其他部分、选举民意调查、政党等就能理解这个小领域。你需要了解邮政编码和选区，但仅此而已。除此之外，这使它成为一个愉快的写作话题。其次，结果似乎非常令人印象深刻，而付出的努力相对较少。在大约半兆字节的数据中，我们存储了超过270万个邮政编码的信息，而且最终的查找成本极低。

这篇文章中采取的方法有一个有趣的非完全矛盾之处。

首先，即使数据在某种程度上是将一个6/7字符的输入（邮政编码）映射到一个9字符的输出（选区代码），它也远非随机。只有650个选区，而且选区显然在邮政编码方面非常“聚集”（因此两个仅在第五个或更晚字符上不同的邮政编码很可能属于同一个选区）。我采用的方法使用我们对数据的了解作为第一步——所以这方面是非常领域特定的。仅仅压缩一个“邮政编码选区代码”行的文件只能将其压缩到略高于7MB。

相反，当我们到了“对于每个外码，我们有一个4000个条目的映射，每个条目对应一个0到8之间的数字”（并且意识到对于许多外码，数字要么在0-1范围内，要么在0-2范围内）这一步时，试图“聪明”并没有特别好。当我试图将尽可能多的信息打包到每个字节中时，代码变得越来越复杂……而当我将领域无关的压缩应用于每个映射时，结果却很好。

我认为，在编写代码以尝试利用已知数据特性与依赖现有领域无关算法之间找到平衡点，这种情况并不罕见。这只是我遇到的最清晰的例子之一。