App*_*rew 8 python geocoding large-data-volumes large-data openstreetmap
我正在尝试创建一个Python脚本,该脚本将地址作为输入,并且会在多次匹配的情况下吐出其纬度和经度,或纬度和经度,就像Nominatim一样.
因此,可能的输入和输出可能是: -
在上面的6中,纽约被归还,因为找不到地址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.即使在这种情况下,它也应该能够找到地址.
感谢所有人的回答，他们的回答很有帮助，但没有解决我需要的一切。我终于找到了一种可以解决我所有案例的方法。该方法是我在问题中建议的修改版本。
在这里，我将提到“节点”，它是一个类对象，其中包含地理信息，例如地点实体的纬度、经度，也许还有维度及其完整地址。
如果实体的地址是“101 C，Pearl Street，New York，USA”，那么这意味着我们的数据结构将至少有四个节点：“101 C”、“Pearl Street”、“New York”和“美国'。每个节点都有一个name和 一个address部分。对于“101 C”，name将为“101 C”，地址将为“美国纽约珍珠街”。
基本思想是建立一个由这些节点组成的搜索树，其中节点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稍后我们可以通过测量节点与查询地址的差异来对结果的质量进行评分。我们没有使用完全匹配，因为用户可以提供不完整的地址，如本例所示。
为了对结果的质量进行评分，我们可以使用最长公共子序列。在这个算法中，“遗漏”和“过剩”的情况得到了很好的处理。
最好让代码来说话。下面是为此目的量身定制的 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. 其他地区也是如此。层次结构关系隐含地定义了完整地址。address包括其父级，name因为它们没有被切片。哪里有桶（池），哪里就有隐含的扩展可能性。我们（比如说）将“美国”的地理数据分为两组。两者可以位于不同的系统上。因此，如果“NEW YORk”池位于系统 A 上而“CALIFORNIA”池位于系统 B 上，则完全没问题，因为它们不共享任何数据，当然，父母除外。
这是警告。我们需要复制父母，它永远是一个切片。由于切片的数量是有限的，所以层次结构不会太深，所以复制它们不应该太冗余。
请参阅我的 GitHub，获取可运行的演示 Python 代码。
| 归档时间： |
|
| 查看次数： |
1099 次 |
| 最近记录： |