Correlating company entities between different data sources I have two datasets with information about companies and my task is to correlate (match) companies from dataset A to companies in dataset B. Datasets are from different sources.

The columns in both datasets include fields such as company_name, country, state, city, address, zip.  All companies are in the US. 

The problem is that even though we have the company_name on both sides - the names in A aren't equal to the names in B. So for example on A you might have Google and on B you might have Google Inc. Another example is Amazon and Amazon LLC. etc, there are many different variations to that.
These aren't typos, but just different representations of the same entity, one is more common and the other is more formal.
The addresses themselves aren't always the same as well. Probably b/c a company might have more than one address. (at least large companies do)   

What is the best approach to correlate (match) these entities b/w these two data sources?
There are about 500k companies in each dataset. 

A few ideas come to mind: 


Soundex function on the company name (tried it, not great)
Levenshtein distance b/w names of each two potential matches (didn't try it yet, but it is O(n*m))
Levenshtein b/w the concatenated values of company names state, city, etc (also O(n*m))
Geocode the address and build a function that takes into account the Levenshtein distance as well as geographical distance. 
Clean up the "INC", "LLC" and all other extensions and run any of 1-4.


What's your take? Any other suggestions? 

Thanks!
First of all I would clean up INC, LLC, BV etcetera from both the sources. After this there are a few options. Since Levenshtein is a metric you can use metric trees to search your space more efficiently (about O(n*log(m))). This will still be very slow so there are approximations available, for example the cosine similarity on bi-grams of the names. You can do this using matrix multiplication which is both very efficient and easily distributable. Instead of taking the highest similarity you could take the top-n and do further analysis on these, for example the real Levenshtein distance. The fact that you have additional information could be useful, you could add this to your similarity function in some way but this will be guess work. Most of these ideas I got from a PyData meetup that was recorded, a speaker from ING (a big bank) discusses the exact problem you have albeit on a bigger set with less additional information:

https://www.youtube.com/watch?v=4ohTsblxOJs