我应该使用哪种数据结构进行地理编码？

Question

我正在尝试创建一个Python脚本，它将以地址为输入，并输出其纬度和经度，或在多个匹配项的情况下输出多个纬度和经度，就像Nominatim一样。

因此，可能的输入和输出如下：

1. 输入: 美国纽约 => 输出: 纽约 (纬度:x1 经度:y1)
2. 输入: 纽约 => 输出: 纽约 (纬度:x1 经度:y1)
3. 输入: 美国纽约珍珠街 => 输出: 珍珠街 (纬度:x2 经度:y2)
4. 输入: 美国珍珠街 => 输出: 珍珠街 (纬度:x2 经度:y2), 珍珠街 (纬度:x3 经度:y3)
5. 输入: 珍珠街 => 输出: 珍珠街 (纬度:x2 经度:y2), 珍珠街 (纬度:x3 经度:y3)
6. 输入: 美国纽约Alkazam大街103号 => 输出: 纽约 (纬度:x1 经度:y1)

在第6个例子中，由于找不到地址为美国纽约Alkazam大街103号的地点，因此返回了美国纽约。

起初，我考虑构建一棵树来表示层级关系，其中兄弟节点按字母顺序排序。它可能会像这样：

                                     GLOBAL
                                       |
                   ---------------------------------------------
                   |            | ...
                  USA
             ---------------
             |        | ...
         CALIFORNIA  NEW YORK 
            |         |
     -----------    -------------
     |        |..   |          |....
 PEARL STREET      PEARL STREET

但问题在于用户可能提供不完整的地址，例如2、4和5。

因此，我接下来考虑使用搜索树，并在每个节点中存储完全合格的地址。但这也很糟糕，因为：

- 这将在每个节点中存储高度冗余的数据。由于这将是一个非常大的数据，因此空间保留至关重要。 - 它将无法利用用户缩小搜索空间的事实。

我有一个额外的要求。我需要检测拼写错误。我想这将必须作为一个单独的问题处理，并将每个节点视为通用字符串。

更新1

稍作解释。输入将是一个列表，其中较低索引上的项是较高索引上的项的父项；它们当然可以是或不是直接父项或子项。因此，对于查询1，输入将是["USA"，"NEW YORK"]。因此，USA, New York没有返回结果是完全可以的。

用户应该能够找到建筑物，如果他有地址，而我们的数据是如此详细。

更新2（省略案例）

如果用户查询“Pearl Street, USA”，那么我们的算法应该能够定位到该地址，因为它知道“Pearl Street”有“New York”作为父级，而“USA”是其父级。

更新3（剩余情况）：

假设用户查询“101 C, Alley A, Pearl Street, New York”。还假设我们的数据确实知道“101 C”，但不知道“Alley A”。根据它，“101 C”是“Pearl Street”的直接子项。即使在这种情况下，它也应该能够找到地址。

- AppleGrew

---

我认为标签[missing-data]在这里是合适的。 - moooeeeep

我所说的缺失数据是指在用户的查询中缺少。比如上面的第四个查询，它没有"纽约"这个参数。我们的数据可能非常详细，也可能不够详细。因此，在这种情况下，用户要求获取位于"美国"的"珍珠街"，这应该可以工作，因为我们的数据知道虽然它不直接位于"美国"，但通过"纽约"它是在美国的。 - AppleGrew

@gbulmer 完全同意。但更新2和3是有效的情况。特别是更新2。我将“101 C”视为名称；一个字符串。数字部分没有特殊含义。更新2和3的重点是用户可能会错过/跳过某些级别，而我们的数据也可能会缺少一些级别。因此，从代码的角度来看，第二种情况就像用户输入了一些不存在的级别。 - AppleGrew

@gbulmer 再想一想，你的意思是我应该限制和定义我想要的确切级别。是的，那应该会简化很多事情。你本可以用简单的话来表达。;-) - AppleGrew

@AppleGrew - 我试图在回答问题时取得平衡，既不会给出太多的答案以至于剥夺了解决问题的乐趣，也不会不够有帮助而引起沮丧（每个人都有自己的哲学）。你的 :-）表明我可能做得很好，你获得了“有所领悟”的时刻 :-) - gbulmer

Answer 1

感谢所有人的答案，它们很有帮助，但并没有解决我所需要的一切。最终我找到了一个方法来处理我所有的情况。这个方法是我在问题中提出的方法的修改版本。

基本方法

在这里，我将引用一个叫做“节点”的东西，它是一个类对象，将包含地理信息，如一个地点实体的纬度、经度，可能还有尺寸，以及它的完整地址。

如果实体的地址是“101 C, Pearl Street, New York, USA”，那么这意味着我们的数据结构将至少有四个节点——“101 C”、“Pearl Street”、“New York”和“USA”。每个节点都有一个名称和一个地址部分。对于“101 C”，名称将是“101 C”，地址将是“Pearl Street, New York, USA”。

基本思想是拥有这些节点的搜索树，其中节点名称将用作搜索的关键字。我们可能会得到多个匹配项，因此稍后需要根据节点的地址与查询地址的匹配程度对结果进行排名。

                                    EARTH
                                      |
                ---------------------------------------------
                |                                           |
               USA                                        INDIA
                |                                           |
        ---------------------------                     WEST BENGAL
        |                         |                         |
     NEW YORK                 CALIFORNIA                 KOLKATA
        |                         |                         |
   ---------------            PEARL STREET              BARA BAZAR
   |             |                                          |
PEARL STREET   TIME SQUARE                                 101 C
   |             |
  101 C         101 C

假设我们有如上的地理数据。因此，搜索“101 C，纽约”不仅会返回“纽约”的“101 C”节点，还会返回“印度”的一个节点。这是因为算法仅使用name，即这里的“101 C”，来搜索节点。稍后，我们可以通过测量节点的address与查询地址的差异来评估结果的质量。由于用户允许提供不完整的地址，因此我们没有使用精确匹配。

评估搜索结果

为了评估结果的质量，我们可以使用最长公共子序列。这个算法很好地处理了“省略”和“多余”的情况。

最好让代码说话。下面是一个专门为此目的量身定制的Python实现。

def _lcs_diff_cent(s1, s2):
    """
    Calculates Longest Common Subsequence Count Difference in percentage between two strings or lists.

    LCS reference: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem.
    Returns an integer from 0-100. 0 means that `s1` and `s2` have 0% difference, i.e. they are same.
    """
    m = len(s1)
    n = len(s2)

    if s1 == s2:
        return 0
    if m == 0: # When user given query is empty then that is like '*'' (match all)
        return 0
    if n == 0:
        return 100

    matrix = [[0] * (n + 1)] * (m + 1)
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                matrix[i][j] = matrix[i-1][j-1] + 1
            else:
                matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j])

    return int( ( 1 - float(matrix[m][n]) / m ) * 100 )

优化方法

我放弃了上述（基本）方法，因为它会强制冗余，并且不能利用这样一个事实：如果用户在查询中提供了“美国”，那么我们就不需要查看“印度”的节点。

这种优化方法在很大程度上解决了以上两个问题。解决方案不是拥有一个大的搜索树。我们可以将搜索空间划分为“美国”和“印度”等。稍后，我们可以进一步将这些搜索空间按州进行重新划分。这就是我所说的“切片”。

在下面的图表中，“SearchSlice”表示“切片”，而“SearchPool”表示搜索树。

                            SearchSlice()
                                  |
            ---------------------------------------------
            |                                           |
        SearchSlice(USA)                           SearchSlice(INDIA)
            |                                           |
    ---------------------------                  SearchPool(WEST BENGAL)
    |                         |                   |
 SearchPool(NEW YORK)     SearchPool(CALIFORNIA)  |- KOLKATA
    |                         |                   |- BARA BAZAR, KOLKATA
    |- PEARL STREET           |- PEARL STREET     |- 101 C, BARA BAZAR, KOLKATA
    |- TIME SQUARE
    |- 101 C, PEARL STREET
    |- 101 C, TIME SQUARE

注意以下几点：

• 每个切片仅有单层级别，但在上方不是很明显。
• 切片级别的名称不会出现在其子项的地址中。例如， SearchSlice(USA) 维护了一个“美国”州的切片。因此，“纽约”下的节点不包括“纽约”或“美国”的名称在它们的address中。其他地区也是如此。层次关系隐含地定义了完整的地址。
• '101 C' 的address也包括其父级的name，因为它们没有被切片。

扩展可能性

当有一个存储桶（池）时，存在一个隐含的扩展可能性。我们将“美国”的地理数据分成两组（例如）。两者可以在不同的系统上。因此，“纽约”池可以在A系统上，而“加利福尼亚”池可以在B系统上，因为它们除了父项外不共享任何数据。

这里有一个警告。我们需要复制父级，它们将始终是一个切片。由于切片应该数量有限，以便层次结构不会太深，因此复制它们不应该太冗余。

工作代码：

请参考我的GitHub，了解Python工作演示代码。

- AppleGrew

Answer 2

如何使用键值存储映射和全文搜索呢？

• 地点字符串用作键
• 地点级别和经纬度数据用作值
• 搜索方法：
  • 将用户输入的字符串按照单个位置单词分割（不仅仅是逗号）
  • 在映射中搜索每个单词
  • 返回最小位置级别的经纬度

Python中的字典、Memcached、MongoDB等工具都可以满足您的需求。

• 如果您有太多的位置单词，可以将位置级别拆分为一个新的映射，进行两次搜索以加快速度
• 忘记地点级别，当做全文搜索即可
• 大数据？将键哈希为短字符串或数字

一些需要考虑的问题：

• 如何在数据库中存储数据
• 如果有的话，如何从数据初始化您的搜索树
• 如何在运行时扩展/编辑搜索树
• 对于输入/存储的容错能力
• 存储空间>速度？还是速度>存储空间？

因此，需要更多的可用测试案例来测试用户输入。

101 C, Time Square, New York, US
101 C, Pearl street, New York, US

101 C, Time Square, SomeCity, Mars
101 C
101 C, US
101 C, New York, US

101 C, New York, Time Square, US

North Door, 101 C, Time Square, New York, US
South Door, 101 C, Time Square, New York, US

针对情况：

• 处理大量数据的高速度；
• 完全容错；
• 易于调整存储和运行时。

最佳解决方案（也是最复杂的）：

• 平面键值映射存储；
• 全文搜索
  • 或哈希键与B树搜索

您的程序/网站可能能够像谷歌一样快速运行。

- fanlix

---

您的意思是键将是完整的位置字符串吗？请注意，根据数据，“完整位置”实际上可能并不是完整地址。（请参见“更新3”）。 - AppleGrew

@AppleGrew 我把事情搞得太复杂了。你已经有可运行的解决方案了。 - fanlix

Answer 3

如果你尝试为这个问题创建数据结构，我认为你会有数据冗余。相反，你可以使用树/图，并尝试实现一个搜索算法，该算法根据用户输入的单词搜索节点值。模糊匹配可以帮助你生成最可能的结果，并且你可以根据它们相似度配额的置信水平向用户建议/展示其中前几个。

这也可以处理拼写错误等问题。

- 0xc0de