工程日志
Mapsake 如何构建其离线旅行地理信息库。
将照片坐标转换为国家、地区、城市和机场需要的不止是查找最近的地点。 Mapsake 如何结合开放式地点数据、边界几何、确定性规则和本地索引。
坐标尚未成为一个地点。
旅行照片可以包含令人印象深刻的精度纬度和经度。这两个数字仍然无法说明相机是在日本、京都府、京都还是在回家的关西国际机场。
负责回答这些问题的组件是一个地理 Gazetteer：一个命名地理位置的结构化目录。Mapsake 将其地理 Gazetteer 捆绑在应用程序中，以及用于绘制和测试国家和一级区域的边界线。搜索、手动标记、照片导入、地点故事、护照统计、成就，甚至是一些朋友视图都依赖于此。
将所有坐标发送到网络地理编码器会更简单。但这会使大量照片的导入速度变慢，使其更依赖于网络，更难重现，并且隐私性更差。离线路线的创建需要更多的前期工程，但它为 Mapsake 提供了稳定的地理词汇表，该词汇表在飞机上、在家以及在源数据集更改后的数年之后都能以相同的方式工作。
这是关于该层如何构建的故事，点和线在哪里不一致，以及为什么“最近的城市”仅仅是正确答案的开始。
四个公开数据集，四个不同的任务
Mapsake 需要的所有信息都无法来自单个来源，因此构建流程将四种类型的开放数据结合在一起。
- GeoNames。 提供国家、一级行政区、人口稠密地区、稳定标识符、其他名称、坐标和人口。
- OurAirports 提供机场、IATA和ICAO代码、名称、市、以及坐标。
- Natural Earth 提供国家和 admin-1 级行政区的边界几何数据，以及实用的地图标签点。
- Mapsake 拥有的一个小型层记录了产品决策，例如支持的国家/地区计数模式、别名和无法从通用来源安全推断的更正。
每个数据源擅长不同的方面。 GeoNames 知道城市属于哪个区域和国家/地区，但城市坐标只是一个点，而不是边界。 Natural Earth 知道多边形在哪里绘制，但其特征标识符并不总是与 GeoNames 的标识符完全匹配。 OurAirports 知道 KLAX 和 LAX 指的是同一个机场，但这并不是机场周围的所有地点的层次结构。
构建脚本会下载并缓存上游文件，对其进行归一化处理，验证关系，并生成两个已提交的工件：一个只读的 SQLite 数据库和一个简化的 GeoJSON 几何体。应用程序会分发这些结果。应用程序不会在首次启动时下载世界数据库，也不会依赖于旅行期间源网站的在线状态。
提交生成的工件也有助于使发布可重现。 发行的版本具有已知的地理世界模型。 更新源代码是一种可以测试和审查的有意代码更改，而不是一种不可见的服务器端更改，该更改会在一夜之间更改某人的地图。
一个故意简单的 SQLite 数据库。
第一个地理信息库包含 252 个国家/地区、3,861 个地区、33,744 个城市和 4,564 个机场，总大小约为 14 MB。 它使用了操作系统中已经提供的 SQLite 库以及一个小的本地包装器，而不是添加更大的数据库框架。
该模式有意保持简单。大陆包含国家/地区。国家/地区包含区域。区域包含城市。机场包含国家/地区代码和坐标。稳定的源标识符成为 Mapsake 标记中存储的标识符：ISO alpha-2 用于国家/地区，GeoNames 管理代码用于区域，GeoNames ID 用于城市，以及 IATA 代码用于机场。
Mapsake 还将人类可读的名称和谱系规范化到每个保存的标记中。这种冗余是有用的。个人旅行记录应该保持可读，即使稍后 Gazetteer 重命名了某个位置、删除了记录或在导出时不可用。标识符用于匹配；快照使用户的数据保持自包含。
SQLite非常适合这项工作，因为它只生成一次数据库，并多次进行查询。它支持索引、构建过程中的事务以及无需服务进程的全文本搜索。该应用程序以只读方式打开捆绑文件，因此不存在引用数据的迁移风险，并且不会因为中断的写入而损坏数据。
搜索不仅仅是包含 (text)。
手动标记从一个搜索字段开始，该字段涵盖大洲、国家/地区、地区、城市和机场。搜索“san”应首先找到有意义的城市，而不是不常见的记录；“LAX”应找到机场；并且即使没有重音符号的名称也应有效。
此构建会创建一个 FTS5 表，其中包含显示名称、选定的替代名称、代码、谱系、坐标、类型和重要性值。Unicode 标记器会删除匹配的重音符号。在查询时，Mapsake 会忽略大小写和重音符号，删除可能成为全文本语法的字符，为每个标记添加前缀匹配，并对完全匹配的名称进行排序，使其优先于前缀和通用匹配。
重要性会打破剩余的平局。 大陆和国家不应低于名称相似的村庄。 城市人口为主要地点赋予合理的权重。 大型机场在文本匹配基本相同的情况下排名高于小型机场。
替代名称是故意限制的。 GeoNames 可以为热门地点提供非常长的多语言列表。 将每个拼写复制到设备索引会增加噪音和大小。 构建器保留一组有限的、去重的有用变体，并单独保留原始显示名称，与折叠的搜索表单分开。
搜索结果返回与分层浏览中使用的 GazetteerPlace 模型相同的模型。 用户可以直接搜索，也可以浏览大陆、国家、地区和城市，而无需创建两个可能不一致的地理系统。
线条回答的问题与点回答的问题不同
第一个照片解析器选择最近的城市并继承该城市的国家/地区和区域。 在密集区域，这通常看起来很完美。 靠近边界时，它可能会以难以察觉的方式出错。
想象一下，一张照片是在蒙大拿州境内拍摄的，但数据库中最近的有人居住的地方在北达科他州。最近城市计算是正确的，但结果不是照片拍摄的行政区域。同样的问题出现在国际边界、孤岛地区以及海岸线稀疏、附近没有人口稠密地区的地方。
边界几何回答的是包含关系，而不是接近关系。Mapsake 解码 Natural Earth 国家/地区和 admin-1 多边形，检查哪个环包含坐标，并使用该结果来保护国家/地区和区域的分配。然后，它可以搜索受限于多边形国家/地区或区域的最近的城市。
这会产生一种有用的劳动分工:
- 多边形包含定义行政区域。
- 地理信息库的层次结构提供稳定的 ID 和名称。
- 约束的最近城市搜索提供有用的位置信息，而不会超出已建立的界限。
- 一个附近的机场检查仅添加在预先设置的紧密距离内的机场。
线路数据和地点目录本身都不足够。 它们结合使用可以将坐标转换为可靠的路线。
admin-1 审计发现了系统性不匹配。
国家多边形和地区多边形来自 Natural Earth 的不同图层，并且区域图层的标识符并不总是与 GeoNames 匹配。有些错误很明显，而其他错误会产生看似合理但实际上不正确的填充。
早期的一个转换表将魁北克错误地分配到了新不伦瑞克省的地理信息。其他功能缺少代码，使用了来自相邻系统的代码，或者以与 Gazetteer 不同的方式表示行政单位。仅凭视觉方式查看世界地图，无法可靠地找到所有这些错误。
新的替换状态构建将城市视为预言。 对于每个候选多边形，它会询问哪个地理区域的城市实际上位于其中。 现有的 Natural Earth 代码经过验证，而不是盲目信任。 无法通过验证的特征可以被空间重新分配、拆分或排除。 生成的输出然后使用 SQLite 中已经存在的精确区域 ID。
这是一个跨数据集测试的实用形式。声称是某个区域的多边形应该包含该区域中城市的说服性样本。当两个来源不同时，构建会提供证据，而不是静默地选择首先加载的值。
在一次审计中，发现了一些特殊情况，例如将人口稠密的附属区域包含在母国地理范围内。Mapsake 修复了这些情况中的一小部分，以便照片可以解析为 Gazetteer 和国家/地区计数设置理解的同一国家/地区。
在不传输原始世界数据大小的情况下，显示更清晰的线条。
最初のAtlas使用了Natural Earth的1:110百万个国家边界数据层。它非常紧凑和快速，但当Mapsake添加了更详细的地图、地点故事和区域信息时，海岸线变得明显粗糙。
地图后来移动到 1:10 百万层。该来源包含更多细节，因此对其进行捆绑和渲染而不进行更改会增加存储空间、解码时间、叠加层构建和重新着色工作。构建管道使用 Douglas-Peucker 算法，以大约 0.004 度的容差简化每个环，然后将坐标舍入到稳定的精度。
结果的国家/地区文件约为 6.5 MB。 它在 Mapsake 呈现的缩放级别下保留了有用的海岸线细节，同时删除了会落在实际上相同的像素上的顶点。 Admin-1 几何体经过类似的验证和简化过程。
简化必须满足正确性约束：较小的多边形仍然必须对真实照片坐标做出相同的决策。后续的基准测试会故意将点放置在边界附近，并比较优化后的命中测试与冻结的参考。更快的线条只有在它们仍然能够回答相同的包含问题时才有用。
从 34,000 扩展到 234,000 的城市。
第一次数据库使用了 GeoNames 中的人口超过 15,000 的城市。 这使得软件包保持紧凑，但它使得乡村旅行、小岛、徒步小镇以及许多家庭位置的标签距离过远。
Mapsake 后来采用了 GeoNames 数据。 城市500, 覆盖了大约 500 人的人口稠密地区以及行政中心。城市表增加了约七倍，达到约 234,000 条记录，而捆绑数据库从约 14 MB 增加到约 69 MB。
这次交易是在 App Clip 被移除之后进行的。Clip 的下载上限是限制数据库的最主要原因。一旦主应用程序成为唯一的消费者，更广泛的覆盖范围比维持人为的小城市限制更有价值。
全文本索引对次要位置的替代名称仍然是选择性的，并且区域浏览仍然限制了它一次渲染的内容。数据可以广泛，而无需每个屏幕都显示整个表。
覆盖范围在网络地理编码器最不可靠的地方最重要。一个位于偏远地区的偏远小镇不应被标记为距离数小时的城市，仅仅是因为紧凑的数据集没有包含它。
查找最近的城市成为一个共享性能问题
原始的最近城市查询会扩大一个经纬度范围，要求 SQLite 计算每个候选对象的加权距离，创建一个临时排序，并返回最接近的行。这很容易理解，并且足够准确，但 82,000 照片库会将每个查询的少量成本转化为导入、回忆、地图生成和 Constellations 中的重复工作，从而需要几秒钟。
第一个改进添加了一个狭窄的 0.4 度的探测范围，以在更广泛的回退之前进行搜索。 密集区域通常会从一个较小的候选者集中找到城市。 记忆化以及持久的地理单元缓存也阻止了附近的照片重复执行相同的工作。
最重要的改进是将 234,000 城市的数字坐标加载到内存索引中，并按纬度排序。二分搜索找到当前纬度范围内的切片，一个受限的循环检查经度和加权距离，并且仅从 SQLite 中检索获胜的行。一个小的记录缓存使重复获胜变得廉价。
行为没有改变。优化后的函数仍然在第一个非空搜索窗口中选择最近的城市，包括确定性的平局处理。旧 SQL 路径的基准版本会检查数百个位于边界上的坐标，以进行精确的 ID 匹配。
在模拟器上，中等规模的最近城市批处理时间从 2.11 秒缩短到 5.2 毫秒。在物理 iPhone 上的运行时间从 3.06 秒缩短到 6.35 毫秒。这些改进影响了多个功能，因为词汇表是共享的基础设施，而不是导入屏幕的私有实现细节。
发现重叠多边形，这是一个错误。
性能等效性检查发现了一个在优化之前就存在的错误。某些 admin-1 多边形是故意重叠的，尤其是在首都区域位于周围区域内的区域。例如，柏林和勃兰登堡、首尔和京畿道以及基辅市及其州。
旧的命中测试会接受 Swift 字典中首先出现的匹配多边形。由于进程之间的字典迭代顺序会发生变化，因此相同的坐标在重新启动应用程序后可能会获得不同的区域。
Mapsake 现在按多边形面积对重叠的候选对象进行排序，并允许面积最小、最具体的对象获胜。参考实现遵循相同的规则。使用 82,000 张照片的固定测试用例必须在冷启动和热启动路径中产生零差异，才能接受几何优化。
此错误是一个很好的提醒，即“在多边形内”并不总是“是”或“否”的问题。地理数据包含群岛、嵌套首都、反子午线交叉、多边形、孔、有争议的边界和源约定。确定性策略与点在多边形内的算法同样重要。
离线模式是隐私功能和产品功能。
Mapsake 的照片导入功能可以在不将坐标发送到第三方地理编码服务的情况下处理大型照片库。这可以保护敏感的旅行和家庭位置，消除每个请求的定价，避免速率限制，并使进度可预测。
它还使编辑更加一致。手动搜索、照片导入、Passport 卡、成就、朋友快照、邮票匹配和地点故事使用相同的稳定地点 ID，因此它们使用相同的语言。从飞行日志导入的机场可以与附近照片检测到的相同机场进行去重。通过搜索找到的城市可以与 Then & Now 中使用的城市匹配。
该包不被视为完美或永久的。源属性信息在应用程序中可见。构建脚本会保存在代码旁边。已知的更正信息会明确显示。基准测试数据会保护在困难坐标下的行为。更新地理世界是一个发布事件，会产生可审查的后果。
如果要重新构建，我保留哪些内容？
最可靠的选择不是单独的算法。它们是责任之间的界限：
- 使用点来表示名称、稳定的标识、搜索和层次结构。
- 使用线条和多边形进行包含。
- 生成只读的产品文件，而不是在手机上解析四个上游格式。
- 存储可读的快照，其中包含用户数据，同时保留源 ID 以进行匹配。
- 在使其变快之前，使常见的离线路径具有确定性。
- 保持一个较慢的参考实现，直到证明优化后的输出是等效的。
地理信息库最初是一个早期的搜索功能。它已成为 Mapsake 的关键系统之一，因为几乎每个高级功能最终都需要回答同一个简单的问题：这是什么地方？
为了获得正确的答案，您需要了解地理并非单一数据库或巧妙的查询。 它是名称、点、线、产品规则以及用户期望识别的旅行记录之间的仔细协议。