Linkage of large datasets Let me set the scene
I have two data sources, one is 16e6 rows of data, the other is 160k rows of data. Each of these have text string identifiers [e.g. some allegory of 'name', 'address', 'postcode']. 
There are some extra points to note about these datasets:


*

*there is not guaranteed information in each field [they may be empty]

*there has been no validation of entered data, so there may be typos in any of the fields

*they are in plain text format and the only software [on a mediocre spec machine]  available to me is python with no admin/database server creating rights or ability to install much outside of the standard anaconda distribution install


The task
for every entry in the smaller table, match it to [potentially more than one match so much check the entirety of] the larger table and add onto it the corresponding row in the smaller
My question
How would you go about this in a 'clever' way? It is hoped that whatever approach is adopted can be abstracted so that another, different dataset can undergo this same process. This means minimising the amount of human interaction or time.
Things I've already considered


*

*brute force matching on e.g. combinedstring.replace(' ','').upper()
this leads to 'too small' [63%] a proportion of matches because of inconsistentices in spelling, missing data etc. across both [they are from different sources]

*tiered approach matching on 'name' then 'address' then 'postcode'
not a lot better for the same reasons

*consideration of some kind of ML approach
thankfully I have access to scikitlearn if it is useful


Reading in the data is fine, I have no problems working with these datasets thanks to pandas [and the iterator for the larger one]. 
The last point is probably where the best method lies. However, there are a fair few problems in my setup: the choice of metric here, should clustering be considered as an example, is vitally important; there is also the consideration that a matrix of [e.g.] Levenshtein distances takes up a heck of a lot of memory on its own before you have to do anything else with all the data [lets not talk about building one for the 16M rows dataset]. Any kind of clustering approach has to live in less memory than I have available [8GB RAM, or 120GB if its all being done on disk]. 
I have also already tried using fuzzywuzzy but there are quite a few ways in which to actually score it so again the choice of metric is the problem. If there is something like 'Street' in the name then partial token approaches score very highly when I wouldn't want to and some other scorers score quite badly when I would say that it is a match. 
I would love to be able to build an abstract program to be able to do this for whatever datasets are given to me and within my technological limitations. I would hope for something that does not involve a large amount of human time validating all the matches at the very end. On the surface its a very simple problem but I would rather work   
Any and all suggestions welcome, if it is indeed going to be a case of accepting the 63% then what technology [in terms of methods or whatever] would best suit improving this? I'm a proficient programmer in a fair few languages now so if I need to pester our IT people for something specific [they're never going to let me create my own sql server or the like though] then I can at least give a big 'this is annoying and needs a lot of people wasting a lot of time checking' mark in the box. 
I did look around for the best SE place to put this, most of the ML threads came from around these parts so apologies if its in the wrong place - let me know where I should ask in that instance. I also didn't find any other threads that asked the same question and had the amount of data I have either. If they exist let me know.
 A: You've got your work cut out for you. Luckily, there is a large computer science literature that develops explicit models for record linkage that dates back several decades. I would begin with papers by William Winkler at the US Census Bureau. Bill was recently honored by the ASA for his many contributions over the years. Here are links to a few of his papers that deal with various types of models for record linkage:
http://www.amstat.org/sections/srms/Proceedings/papers/2000_003.pdf
http://doku.iab.de/fdz/events/2008/SDC-Workshop_Winkler_Paper.pdf
https://fcsm.sites.usa.gov/files/2014/05/J1_Winkler_2013FCSM.pdf
https://www.cs.cmu.edu/~wcohen/matching/WinklerAsa02.pdf
There are many others working in the field along with Winkler. Here's a recent paper that leverages a Bayesian framework for linkage...
http://www.stat.cmu.edu/proposals/MauricioSadinle.pdf
Hope these help.
A: I'm the lead author on Splink a Python/Spark based package for record linkage at scale, which would probably be a good fit for the kind of problem you describe.
It implements a version of the Fellegi-Sunter model similar to that used by Winkler.
A key feature is that Splink is designed to work at scale (100 million records +), which it achieves by parallelising the record linkage task across the cluster.
You can try the software in your browser here and view of explorable/interactive explanations of the underlying model here
