选举2029：邮政编码

在上一篇关于记录和集合的实用文章之后，这篇文章不太可能给任何人提供如何在自己的项目中解决问题的思路，也没有向微软提出任何功能请求。不过，我发现这个领域真的很有趣。

英国邮政编码简介

我意识到这篇博客的大多数读者可能不在英国。大多数国家都有某种形式的邮政编码，但细节因国家而异。例如，英国邮政编码的规模与美国邮政编码有很大不同。英国邮政编码非常精细——通常只是单条街道的一部分——因此知道房屋/公寓号码和邮政编码通常足以找到精确的地址。

对我的选举网站重要的是，每个邮政编码都在一个单一的选区中——而这正是我想使用它们的目的。我的选区页面允许您开始输入选区名称或邮政编码，并在您输入时过滤结果。我怀疑英国人口的很大一部分知道他们的邮政编码，但不知道他们的选区名称（特别是在2023年边界变更之后），因此能够指定其中任何一个都很有帮助。

维基百科有更多关于英国邮政编码的信息，但我会在这里简要总结。请注意，我只关心现代邮政编码——维基百科有关于事物如何演变的历史细节，但我的网站不需要关心遗留邮政编码。

邮政编码由外部代码（outcode）和内部代码（incode）组成。外部代码是一个区域后跟一个地区，内部代码是一个扇区后跟一个单元。例如，我的邮政编码是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个映射，每个值一个位（每个映射500字节）
• 975 + 774个映射，每个值两个位（每个映射1000字节）
• 剩余（348 + 98 + 21 + 8 + 2）个映射，每个值四个位（每个映射2000字节）

总共是（851*500）+ ((975 + 774) * 1000) + ((348 + 98 + 21 + 8 + 2) * 2000) = 3,128,500字节。这听起来很棒——它节省了映射所需空间的三分之四！但它仍然远远超过Firestore文档的最大大小。当然，对于每个外部代码，我们还需要外部代码文本和映射中代表的选区列表。那应该不多，但对已经超支的大小预算没有帮助。

在这一点上，我尝试了多个选项，包括按扇区而不是外部代码分组（因为很少有外部代码实际上拥有所有十个可能的扇区，并且在一个扇区内可能有更少的选区，因此我们将有更多的扇区可以用每个值一个或两个位表示）。我尝试了手动的游程编码和各种选项。我确实成功地将内容压缩了很多——但代码变得越来越复杂。从根本上说，我所做的是执行压缩，并尝试应用一些关于数据的知识以实现体面的压缩水平。

大约在这一点上，我决定停止尝试让代码更智能，而是尝试让代码更简单，并依赖现有代码的智能。简单的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范围内）时，尝试“聪明”并没有很好地工作。当我尝试将尽可能多的信息打包到每个字节中时，代码变得越来越复杂……而当我将领域无关的压缩应用于每个映射时，结果很好。

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