Thuật toán Khóa đối sánh địa chỉ

Question

Tôi có một danh sách các địa chỉ trong hai bảng riêng biệt hơi bị tắt mà tôi cần để có thể khớp. Ví dụ, cùng một địa chỉ có thể được nhập theo nhiều cách:

• 110 Kiểm tra St
• 110 thử nghiệm St.
• 110 Kiểm tra đường

Mặc dù đơn giản, bạn có thể tưởng tượng tình hình ở scenerios phức tạp hơn. Tôi đang cố gắng phát triển một thuật toán đơn giản để có thể khớp các địa chỉ trên như một khóa.

Ví dụ: chìa khóa có thể là "11TEST" - đầu tiên là hai trong số 110, đầu tiên là hai Kiểm tra và hai biến thể đầu tiên trên đường phố. Khóa khớp đầy đủ cũng sẽ bao gồm 5 mã zip đầu tiên cũng như trong ví dụ trên, khóa đầy đủ có thể trông giống như "11TEST44680".

Tôi đang tìm ý tưởng cho thuật toán hoặc tài nguyên hiệu quả mà tôi có thể xem xét để xem xét khi phát triển điều này. Bất kỳ ý tưởng nào cũng có thể là mã giả hoặc bằng ngôn ngữ bạn chọn.

Chúng tôi chỉ quan tâm đến địa chỉ ở Hoa Kỳ. Trong thực tế, chúng tôi chỉ xem xét địa chỉ từ 250 mã zip từ Ohio và Michigan. Chúng tôi cũng không có quyền truy cập vào bất kỳ phần mềm bưu chính mặc dù sẽ được mở cho ý tưởng cho các giải pháp hiệu quả chi phí (nó về bản chất sẽ được sử dụng một lần). Xin lưu ý rằng đây là một dữ liệu ban đầu từ nguồn chính phủ để gợi ý về cách người dùng có thể làm sạch nó hữu ích khi tôi xây dựng ứng dụng nhưng tôi rất muốn có được sự khởi đầu tốt nhất mà tôi có thể tốt nhất có thể.

Answer 1

Tôi đang làm việc trên một thuật toán tương tự như chúng ta nói, nên xử lý các địa chỉ ở Canada, Mỹ, Mexico và Vương quốc Anh vào thời điểm tôi hoàn thành. Vấn đề tôi gặp phải là chúng nằm trong cơ sở dữ liệu của chúng tôi ở định dạng văn bản 3 trường [bất cứ ai nghĩ rằng rằng là một ý tưởng hay nên được IMHO chụp], vì vậy cố gắng xử lý các tuyến đường nông thôn, giao hàng chung, thu âm lượng lớn, nhiều quốc gia, tỉnh so với tiểu bang so với quận, mã bưu điện so với mã zip, lỗi chính tả không phải là nhiệm vụ nhỏ hoặc đơn giản.

Lỗi chính tả không phải là một điều nhỏ - nhất là khi bạn đến các quốc gia sử dụng tên tiếng Pháp - phù hợp với Saint, Sainte, St, Ste, Saint, Saint, Sts, Stes, Grand, Grande, Grands, Grandes có hoặc không có khoảng thời gian hoặc dấu gạch nối vào phần lớn hơn của tên không gây ra sự cố hiệu suất - đặc biệt khi St có thể có nghĩa là số hoặc phố và có thể hoặc không được nhập đúng ngữ cảnh (ví dụ như nữ tính và nam tính). Điều gì sẽ xảy ra nếu địa chỉ được nhập chính xác nhưng có địa chỉ hoặc mã bưu chính không chính xác?

Một nơi để bắt đầu tìm kiếm của bạn là Levenstein Distance Algorithm mà tôi thấy hữu ích khi loại bỏ một phần lớn các lỗi chính tả. Sau đó, chủ yếu là trường hợp tìm kiếm từ khóa và so sánh với cơ sở dữ liệu bưu chính.

Tôi thực sự quan tâm đến việc cộng tác với bất kỳ ai hiện đang phát triển các công cụ để thực hiện việc này, có lẽ chúng tôi có thể hỗ trợ lẫn nhau cho một giải pháp chung. Tôi đã là một phần của con đường ở đó và đã vượt qua tất cả các vấn đề tôi đã đề cập cho đến nay, có người khác làm việc trên cùng một vấn đề sẽ thực sự hữu ích để trả lại ý tưởng.

Cheers - [ben tại afsinc dot ca]

Answer 2

Tại Vương quốc Anh, chúng tôi sẽ sử dụng:

• Nhà Tên hoặc Số (nơi tên bao gồm số Flat cho khối căn hộ)
• Mã bưu

Bạn chắc chắn nên sử dụng mã bưu điện, nhưng ở Mỹ tôi tin rằng mã Zip của bạn bao gồm các khu vực rất rộng so với mã bưu điện ở Vương quốc Anh. Do đó, bạn sẽ cần phải sử dụng đường phố và thành phố.

dụ của bạn sẽ không phân biệt giữa 11 Đường Test, 110-119 đường thử nghiệm vv

Nếu công ty của bạn có quyền truy cập vào một hệ thống tra cứu địa chỉ, tôi sẽ chạy tất cả các dữ liệu thông qua đó để lấy dữ liệu trở lại ở định dạng nhất quán, có thể với các phím địa chỉ có thể được sử dụng để khớp.

Answer 3

Nếu bạn không chọn để sử dụng một hệ thống hiện có, một ý tưởng là phải làm như sau:

• số Extract từ dòng địa chỉ
• thay thế các từ đường phố phổ biến với khoảng trống
• tạo trận đấu chuỗi

ví dụ: "555 Canal Street":

• số Extract cung cấp cho "555" + "Canal Street"
• Thay thế từ đường phố cho "555" + "Kênh"
• Tạo chuỗi trận đấu cho "555Canal"

"Kênh st 555" sẽ cung cấp cho cùng một chuỗi trùng khớp.

Bằng chữ phố, nghĩa là từ và chữ viết tắt của "đường phố" trong ngôn ngữ của bạn, ví dụ: "st", "st.", "Blv", "ave", "avenue", v.v. chuỗi.

Bằng cách trích xuất các số và tách chúng ra khỏi chuỗi, nó không quan trọng nếu chúng là đầu tiên hoặc cuối cùng.

Answer 4

Nếu tôi muốn giải quyết vấn đề này, tôi sẽ chuyển đổi từng chuỗi địa chỉ thành một cây bằng cách sử dụng thứ tự hoạt động được xác định trước.

Ví dụ: 110 Test Street Apt 3. Bất cứ nơi nào California 90210 =>

1. Lấy loại địa chỉ. Ví dụ: Địa chỉ đường phố có các định dạng khác nhau mà địa chỉ tuyến đường nông thôn và địa chỉ này khác nhau theo quốc gia.
2. Cho rằng đây là địa chỉ đường phố, nhận được chuỗi đại diện cho loại đường phố và chuyển đổi thành một enum (eBoulevard, eRoad, v.v.)
3. Vì đây là địa chỉ đường phố, hãy kéo ra đường tên (lưu trữ trong chữ thường)
4. Cho rằng đây là địa chỉ đường phố, hãy lấy số đường phố

5. Vì đây là địa chỉ đường phố (có thể trước số đường phố có dấu gạch ngang) , có thể là sau "Apt.", v.v ...)

   eStreet //1.an enum of possible address types eg. eStreet, eRuralRoute,... 
        | 
       eStreet  //2.an enum of street types eg. eStreet, eBlvd, eWay,... 
   / | \ 
   

   Tên số Apt | | | kiểm tra 110 3

Ví dụ: RR # 3 Anywhere California 90210 =>

1. Lấy loại địa chỉ: đường nông thôn

2. Cho rằng đây là một địa chỉ đường nông thôn, có được số tuyến đường

   eRuralRoute 
        | 
        3 
   

Bạn sẽ cần phải làm một cái gì đó tương tự cho thông tin quốc gia và zip.

Sau đó so sánh các cây kết quả.

Điều này làm cho việc so sánh rất đơn giản, tuy nhiên, mã để tạo cây là rất phức tạp. Bạn sẽ muốn thử nghiệm crap của nó trên hàng ngàn và hàng ngàn địa chỉ. Vấn đề của bạn đơn giản hơn nếu đó chỉ là các địa chỉ ở Hoa Kỳ mà bạn quan tâm; Địa chỉ của Anh như đã đề cập là khá khác nhau và địa chỉ Canada có thể có tiếng Pháp trong đó (ví dụ: Place D'Arms, Rue Laurent, v.v ...)

Answer 5

sử dụng một bản sắc cho chính chủ chốt, điều này sẽ luôn là duy nhất và sẽ làm cho nó dễ dàng hơn để hợp nhất các bản sao sau đó.

buộc nhập dữ liệu phù hợp với giao diện người dùng. Làm cho chúng nhập mỗi thành phần trong hộp văn bản riêng của nó. Số nhà được nhập vào hộp riêng, tên phố trong hộp riêng, thành phố trong hộp riêng, tiểu bang từ danh sách lựa chọn, v.v. Điều này sẽ giúp tìm kiếm các trận đấu dễ dàng hơn

có hai quá trình "tiết kiệm"

• sau lần lưu ban đầu, thực hiện tìm kiếm để tra cứu các kết quả phù hợp, trình bày chúng với danh sách các kết quả phù hợp cũng như danh sách kết quả mới.
• sau khi họ chọn cái mới lưu nó, nếu họ chọn một ai sử dụng hiện có mà ID

sạch dữ liệu. Hãy thử để loại bỏ "đường phố", "st", "ổ đĩa", vv và lưu trữ nó như một char StreetType (1) sử dụng một FK để một bảng có chứa các chữ viết tắt thích hợp, vì vậy bạn có thể xây dựng đường phố.

nhìn vào Soundex và KHÁC BIỆT

Tôi đã làm việc tại các công ty lớn mà duy trì danh sách mailinig, và họ đã không cố gắng để làm điều đó tự động, họ đã sử dụng người để lọc ra các mới từ dups vì nó là khó khăn như vậy làm. Lập kế hoạch cho một tính năng hợp nhất để bạn có thể hợp nhất thủ công các bản sao khi chúng xảy ra và gợn các giá trị thông qua các PK.

Bạn có thể xem trong bản đồ google api và xem liệu bạn có thể chuyển vào địa chỉ của bạn và nhận lại trận đấu hay không. Tôi không quen thuộc với nó, đây chỉ là suy đoán.

Answer 6

Nếu bạn muốn tonot phát triển một và thay vì sử dụng một sản phẩm off-the-shelf có sử dụng nhiều công nghệ đề cập ở đây, xem: http://www.melissadata.com/dqt/matchup-api.htm

Disclaimer: Tôi đã có một vai trò trong việc phát triển và công việc của mình cho công ty.

Answer 7

Nếu hiệu quả về chi phí để công ty của bạn viết công cụ chuẩn hóa địa chỉ của riêng mình thì tôi khuyên bạn nên bắt đầu với USPS address standard. Ngoài ra, có một số nhà cung cấp cung cấp các công cụ phía máy chủ và dịch vụ web để chuẩn hóa, sửa chữa và xác minh địa chỉ.

Công ty của tôi sử dụng AccuMail Gold vì mục đích này vì nó không chỉ tiêu chuẩn hóa & sửa địa chỉ. Khi chúng tôi xem xét chi phí tiền lương của một tuần thậm chí để phát triển một công cụ trong nhà, sự lựa chọn để mua một sản phẩm có sẵn là hiển nhiên.

Answer 8

Thủ tục Chuẩn hóa/hợp nhất/thanh trừng bạn cần phải làm theo được mô tả tại http://semaphorecorp.com/mpdd/mpdd.html