选举2029：邮政编码处理技术
在上一篇关于记录和集合的实用文章之后，这篇博文可能不会给读者提供解决自己项目问题的思路，也没有向微软提出任何功能请求。但这确实是一个让我感到非常有趣的领域。
英国邮政编码简介
我意识到这篇博文的大多数读者可能不在英国。大多数国家都有某种形式的邮政编码，但细节因国家而异。例如，英国邮政编码的粒度与美国邮政编码大不相同。英国邮政编码非常精细——通常只对应街道的一部分——因此知道门牌号和邮政编码通常足以精确定位地址。
对我的选举网站重要的是，每个邮政编码都位于单一选区——这正是我想使用它们的目的。我的选区页面允许你开始输入选区名称或邮政编码，并在你输入时过滤结果。我怀疑相当一部分英国人口知道自己的邮政编码但不知道所在选区的名称（特别是在2023年边界变更之后），因此能够指定其中任意一项都很有帮助。
维基百科有更多关于英国邮政编码的信息，我在这里简要总结一下。注意，我只关心现代邮政编码——维基百科有关于历史演变的细节，但我的网站不需要关心遗留邮政编码。
邮政编码由外部代码（outcode）和内部代码（incode）组成。外部代码是一个区域后跟一个地区，内部代码是一个扇区后跟一个单元。以我的邮政编码RG30 4TT为例：
- 外部代码: RG30
- 区域: RG
- 地区: 30
- 内部代码: 4TT
- 扇区: 4
- 单元: TT
内部代码非常统一：总是一个数字后跟两个字母。（这两个字母来自20个字符的字母表。）外部代码则更有"趣"，因为它们属于以下七种格式之一，其中'9’代表"任意数字"，‘A’代表"字母"（尽管字母表有所不同）：
- A9A
- A99
- AA9
- AA99
- 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"作为匹配的外部代码。由此，我们需要说：
- 哪些选区由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范围内），试图"聪明"并没有特别好。当我尝试将尽可能多的信息打包到每个字节中时，代码变得越来越复杂…而当我对每个映射应用与领域无关的压缩时，结果很好。
我认为在编写代码以尝试利用已知数据特征与依赖现有的与领域无关的算法之间找到平衡并不罕见。这只是我遇到的最清晰的例子之一。