Tôi nên sử dụng cấu trúc dữ liệu nào cho mã hóa địa lý?

Question

Tôi đang cố gắng tạo một tập lệnh Python sẽ lấy địa chỉ làm đầu vào và sẽ nhổ ra vĩ độ và kinh độ của nó, hoặc vĩ độ và kinh độ trong trường hợp có nhiều kết quả khớp, giống như Nominatim.

Vì vậy, đầu vào và đầu ra có thể là: -

1. Trong: New York, Hoa Kỳ => Out: New York (lat: x1 lon: y1)
2. Trong : New York => Out: New York (lat: x1 lon: y1)
3. Trong: đường Pearl, New York, USA => Out: Pearl Street (lat: x2 lon: y2)
4. Trong: đường Pearl, USA => Out: Pearl Street (lat: x2 lon: y2), Pearl Street (lat: x3 lon: y3)
5. Trong: Pearl Street => Out: Pearl Street (lat: x2 lon: y2), Pearl Street (lat: x3 lon: y3)
6. Trong: 103 Alkazam, New York, USA => Out: New York (lat: x1 lon: y1)

Trong 6 ở trên, New York đã được trả lại vì không tìm thấy địa chỉ nào với địa chỉ 103 Alkazam, New York, USA, nhưng ít nhất có thể tìm thấy New York, USA.

Ban đầu tôi nghĩ đến việc xây dựng một cây đại diện cho mối quan hệ phân cấp nơi anh chị em được sắp xếp theo thứ tự bảng chữ cái. Nó có thể là như sau: -

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

Nhưng vấn đề là người dùng có thể cung cấp địa chỉ không đầy đủ như trong 2, 4 và 5.

Vì vậy, tôi tiếp theo nghĩ của việc sử dụng một cây tìm kiếm và lưu trữ các đầy đủ địa chỉ trong mỗi nút. Nhưng điều này cũng khá tệ vì: -

• Điều này sẽ lưu trữ dữ liệu dư thừa cao trong mỗi nút. Vì đây sẽ là một dữ liệu thực sự lớn nên vấn đề bảo tồn không gian.
• Nó sẽ không thể tận dụng thực tế là người dùng đã thu hẹp không gian tìm kiếm.

Tôi có một yêu cầu bổ sung . Tôi cần phát hiện lỗi chính tả. Tôi đoán rằng sẽ phải được xử lý như một vấn đề riêng biệt và có thể coi mỗi nút là các chuỗi chung chung.

Cập nhật 1

Một xây dựng ít. Dữ liệu đầu vào sẽ là một danh sách, trong đó mục trên chỉ mục dưới là phụ huynh của mục trong chỉ mục cao hơn; và tất nhiên họ có thể hoặc không thể là cha mẹ hoặc con cái ngay lập tức. Vì vậy, đối với truy vấn 1, đầu vào sẽ là ["USA", "NEW YORK"]. Vì vậy, nó là hoàn toàn tốt đẹp mà USA, New York trả về không có kết quả.

Người dùng có thể định vị tòa nhà nếu anh ta có địa chỉ và dữ liệu của chúng tôi rất chi tiết.

Cập nhật 2 (lậu Case)

Nếu người dùng truy vấn Pearl Street, USA, vì vậy algo của chúng tôi sẽ có thể xác định vị trí địa chỉ vì nó biết Pearl Street có New York như phụ huynh và USA là mẹ của nó.

Cập nhật 3 (Thặng dư Trường hợp)

Giả sử các truy vấn người dùng cho 101 C, Alley A, Pearl Street, New York. Ngoài ra giả sử dữ liệu của chúng tôi biết là 101 C nhưng không biết về Alley A. Theo số 101 C là con ngay lập tức của Pearl Street. Ngay cả trong trường hợp này, nó sẽ có thể xác định vị trí địa chỉ.

Answer 1

Nhờ tất cả những câu trả lời của họ, câu trả lời của họ là hữu ích, nhưng không giải quyết tất cả mọi thứ tôi cần. Cuối cùng tôi đã tìm thấy một cách tiếp cận mà đã chăm sóc của tất cả các trường hợp của tôi. Cách tiếp cận là phiên bản sửa đổi của những gì tôi đề xuất trong câu hỏi.

Cách tiếp cận cơ bản

Ở đây tôi sẽ đề cập đến một cái gì đó gọi là 'nút', nó là một đối tượng lớp trong đó sẽ chứa các thông tin địa lý như kinh độ một nơi đơn vị của độ, kinh độ, có lẽ kích thước quá, và địa chỉ đầy đủ của nó.

Nếu địa chỉ của thực thể là '101 C, Pearl Street, New York, Hoa Kỳ', thì điều này có nghĩa là cấu trúc dữ liệu của chúng tôi sẽ có ít nhất bốn nút cho - '101 C', 'Pearl Street', 'Mới York 'và' USA '. Mỗi nút sẽ có một phần name và một phần address. Đối với '101 C', name sẽ là '101 C' và địa chỉ sẽ là 'Pearl Street, New York, Hoa Kỳ'.

Ý tưởng cơ bản là có cây tìm kiếm của các nút này, trong đó nút name sẽ được sử dụng làm khóa cho tìm kiếm. Chúng tôi có thể nhận được nhiều kết quả phù hợp, vì vậy sau đó chúng tôi cần xếp hạng kết quả về mức độ phù hợp của nút số address của nút với kết quả được hỏi.

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

Giả sử chúng tôi có dữ liệu địa lý như trên.Vì vậy, tìm kiếm '101 C, NEW YORK' sẽ không chỉ trả lại các nút '101 C' trong 'NEW YORK' mà còn là nút trong 'INDIA'. Điều này là do bản ngã sẽ chỉ sử dụng name, tức là '101 C' ở đây, để tìm kiếm các nút. Sau đó chúng tôi có thể đánh giá chất lượng của kết quả bằng cách đo sự khác biệt của nút address của nút từ địa chỉ được truy vấn. Chúng tôi không sử dụng kết hợp chính xác vì người dùng được phép cung cấp địa chỉ không đầy đủ, như trong trường hợp này.

Phân loại kết quả tìm kiếm

Để cấp chất lượng của các kết quả chúng ta có thể sử dụng Longest Common Subsequence. Các trường hợp 'Omission' và 'Thặng dư' được chăm sóc tốt trong bản ngã này.

Tốt nhất là nếu tôi để đoạn mã thực hiện cuộc trò chuyện. Dưới đây là một triển khai Python phù hợp với mục đích này.

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) 

Tối ưu hóa cách tiếp cận

tôi giải cứu về cách tiếp cận trên (cơ bản) vì nó buộc dư thừa, và nó không thể cắt tận dụng thực tế là nếu người dùng đã cung cấp 'Mỹ' trong truy vấn của mình thì chúng ta cần không nhìn vào các nút trong 'INDIA'.

Cách tiếp cận tối ưu hóa này giải quyết cả hai vấn đề trên ở mức độ khá lớn. Giải pháp không phải là có một cây tìm kiếm lớn. Chúng tôi có thể phân vùng không gian tìm kiếm thành 'USA' và 'INDIA'. Sau đó chúng tôi có thể phân tích lại những không gian tìm kiếm đó một cách khôn ngoan. Đây là những gì tôi gọi là 'cắt'.

Trong biểu đồ bên dưới - SearchSlice đại diện cho 'lát cắt' và SearchPool đại diện cho cây tìm kiếm.

      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 

vài điểm mấu chốt để nhận thấy ở trên ...

• Mỗi miếng chỉ là một mức độ đơn sâu. Điều này không thực sự rõ ràng ở trên.
• Tên mức độ cắt lát không xuất hiện trong địa chỉ con của nó. Ví dụ: SearchSlice(USA) duy trì một phần trạng thái trong 'Hoa Kỳ'. Vì vậy, các nút trong 'NEW YORK' không bao gồm tên 'NEW YORK' hoặc 'USA' trong số address của chúng. Cũng vậy với các khu vực khác. Quan hệ phân cấp ngầm định nghĩa địa chỉ đầy đủ.
• '101 C' address bao gồm số gốc của nó là name vì chúng không bị cắt.

Scaling khả năng

Trường hợp có một xô (hồ bơi), có một khả năng mở rộng quy mô tiềm ẩn. Chúng tôi (nói) chia dữ liệu địa lý cho 'Hoa Kỳ' thành hai nhóm. Cả hai đều có thể trên các hệ thống khác nhau. Vì vậy, nó là hoàn toàn tốt nếu hồ bơi 'NEW YORK' là trên hệ thống A nhưng hồ bơi 'CALIFORNIA' là trên hệ thống B, vì họ không chia sẻ bất kỳ dữ liệu, ngoại trừ cho cha mẹ của khóa học.

Đây là thông báo trước. Chúng tôi cần phải lặp lại các bậc cha mẹ mà sẽ luôn luôn là một lát. Vì các slice có nghĩa là bị giới hạn về số nên cấu trúc phân cấp sẽ không quá sâu, do đó không nên quá thừa để sao chép chúng.

Mã làm việc

Vui lòng tham khảo GitHub của tôi để biết working demo Python code.

Answer 2

cách sử dụng bản đồ lưu trữ khóa-giá trị và tìm kiếm toàn văn.

• chìa khóa cho chuỗi vị trí
• giá trị cho location_level và lat & dữ liệu lon.
• tìm kiếm theo:
  • split chuỗi người dùng nhập vào các từ địa điểm duy nhất (không chỉ bằng dấu phẩy)
  • tìm kiếm mỗi từ trong bản đồ
  • trở lat & lon cấp vị trí nhỏ nhất

python.dict, memcached, mongodb .... sẽ đáp ứng nhu cầu của bạn.

• nếu u có quá nhiều từ vị trí, chia location_level như một bản đồ mới, hai tìm kiếm sẽ tăng tốc độ
• quên mức vị trí, traet như tìm kiếm toàn văn
• dữ liệu khổng lồ? chìa khóa băm để chuỗi ngắn hoặc số

một số questiongs để xem xét:

• làm thế nào để lưu trữ dữ liệu trong cơ sở dữ liệu
• làm thế nào để init cây tìm kiếm của bạn từ dữ liệu, nếu có
• cách mở rộng/chỉnh sửa cây tìm kiếm trong thời gian chạy
• khả năng chịu lỗi cho đầu vào/lưu trữ
• không gian lưu trữ> tốc độ? hoặc tốc độ> lưu trữ?

như vậy, hơn có thể sử dụng trường hợp thử nghiệm cho người dùng nhập vào

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 

cho tình hình:

• nhanh tốc độ với khổng lồ dữ liệu;
• chịu đầy đủ lỗi;
• dễ điều chỉnh với dung lượng và thời gian chạy

giải pháp tốt nhất: (còn phức tạp-est)

• phẳng giá trị khóa lưu trữ bản đồ
• tìm kiếm toàn văn
  • hoặc khóa băm với tìm kiếm B-tree

chương trình/trang web của bạn có thể chạy nhanh như google.

Answer 3

Nếu bạn cố gắng tạo cấu trúc dữ liệu cho vấn đề này, tôi nghĩ bạn sẽ có dự phòng dữ liệu. Thay vào đó bạn có thể sử dụng cây/biểu đồ & cố gắng triển khai thuật toán tìm kiếm tìm kiếm các từ từ đầu vào của người dùng dựa trên các giá trị nút. Kết hợp mờ có thể giúp bạn tạo nhiều kết quả nhất có thể và bạn có thể đề xuất/hiển thị cho người dùng một số kết quả hàng đầu trong số họ theo mức độ tin cậy về mức độ giống nhau của họ.

này cũng có thể chăm sóc viết sai, vv