8

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

因此，可能的输入和输出可能是：-

  1. 输入：美国纽约=> 输出：纽约（纬度：x1 经度：y1）
  2. 输入：纽约=> 输出：纽约（纬度：x1 经度：y1）
  3. 输入：美国纽约珍珠街=> 输出：珍珠街（纬度：x2 经度：y2）
  4. 输入：美国珍珠街=> 输出：珍珠街（纬度：x2 经度：y2），珍珠街（纬度：x3 经度：y3）
  5. 进：珍珠街=> 出：珍珠街（纬度：x2 经度：y2），珍珠街（纬度：x3 经度：y3）
  6. 输入： 103 Alkazam，纽约，美国=> 输出：纽约（纬度：x1 经度：y1）

在上面的 6 中，由于没有找到带有 address 的地方，所以返回了 New York 103 Alkazam, New York, USA，但它至少可以找到New York, USA。

最初我想建立一个树来表示兄弟姐妹按字母顺序排序的层次关系。可能是这样的：-

                                     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。即使在这种情况下，它也应该能够找到地址。

4

3 回答 3

2

感谢所有人的回答，他们的回答很有帮助，但并没有解决我需要的所有问题。我终于找到了一种处理我所有情况的方法。该方法是我在问题中建议的修改版本。

基本方法

在这里我将提到一个叫做“节点”的东西，它是一个类对象，它将包含地理信息，比如一个地方实体的纬度、经度，也可能是维度，以及它的完整地址。

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

基本思想是拥有这些节点的搜索树，其中节点name将用作搜索的键。我们可能会得到多个匹配，所以稍后我们需要根据节点address与查询的匹配的好坏对结果进行排名。

                                    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, NEW YORK”不仅会返回“NEW YORK”中的“101 C”节点，还会返回“INDIA”中的节点。这是因为算法只会使用name'101 C' 来搜索节点。稍后我们可以通过测量节点address与查询地址的差异来对结果的质量进行评分。我们没有使用完全匹配，因为允许用户提供不完整的地址，就像在这种情况下一样。

评分搜索结果

要对结果的质量进行分级，我们可以使用Longest Common Subsequence。这个算法很好地处理了“遗漏”和“剩余”的情况。

最好让代码来说话。下面是为此目的量身定制的 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)在“美国”中维护一个州的切片。因此，“NEW YORK”下的节点在其address. 其他地区也一样。层次关系隐含地定义了完整地址。
  • '101 C'也address包括其父级name，因为它们没有被切片。

扩展可能性

哪里有桶（池），哪里就有隐含缩放的可能性。我们（比如说）将“美国”的地理数据分为两组。两者都可以在不同的系统上。因此，如果“NEW YORk”池在系统 A 上，而“CALIFORNIA”池在系统 B 上，则完全没问题，因为它们不共享任何数据，当然除了父母。

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

工作守则

请参阅我的 GitHub 以获取有效的演示 Python 代码。

于 2012-04-15T15:19:33.667 回答
1

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

  • 位置字符串的键
  • location_level 和 lat&lon 数据的值。
  • 搜索：
    • 将用户输入字符串拆分为单个位置的单词（不仅是逗号）
    • 搜索地图中的每个单词
    • 返回最小位置级别的纬度和经度

python.dict,memcached,mongodb .... 将满足您的需求。

  • 如果你的位置词太多，将location_level拆分为新地图，两次搜索会加快
  • 忘记位置级别，将其作为全文搜索
  • 海量数据？短字符串或数字的哈希键

需要考虑的一些问题：

  • 如何将数据存储在数据库中
  • 如何从数据中初始化搜索树（如果有）
  • 如何在运行时扩展/编辑搜索树
  • 输入/存储容错
  • 存储空间>速度？还是速度>存储？

所以，用户输入的更有用的测试用例

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-tree 搜索的哈希键

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

于 2012-04-12T13:15:33.683 回答
0

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

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

于 2012-04-12T14:18:52.113 回答