How to smartly match two data frames using Python (using pandas or other means)?
<p>I have one pandas dataframe composed of the names of the world's cities as well as countries, to which cities belong,</p>

<pre><code>city.head(3)

    city    country
0   Qal eh-ye Now   Afghanistan
1   Chaghcharan Afghanistan
2   Lashkar Gah Afghanistan
</code></pre>

<p>and another data frame consisting of addresses of the world's universities, which is shown below:</p>

<pre><code>df.head(3)
    university
0   Inst Huizhou, Huihzhou 516001, Guangdong, Peop...
1   Guangxi Acad Sci, Nanning 530004, Guangxi, Peo...
2   Shenzhen VisuCA Key Lab SIAT, Shenzhen, People...
</code></pre>

<p>The locations of cities' names are irregularly distributed across rows. I would like to match the city names with the addresses of world's universities. That is, I would like to know which city each university is located in. Hopefully, the city name matched is shown in the same row as the address of each university.</p>

<p>I've tried the following, and it doesn't work because the locations of cities are irregular across the rows.</p>

<pre><code>df['university'].str.split(',').str[0]
</code></pre>

<p>My suggestion is that after a few pre-processing that reduce address into city level information (we don't need to be exact, but try your best; like removing numbers etc), and then merge the dataframes based on text similarities.</p>

<p>You may consider text similarity measures like levenshtein distance or jaro-winkler which are commonly used to match the words.</p>

<p>Here is example for text similarity:</p>

<pre><code>class DLDistance:
    def __init__(self, s1): 
        self.s1 = s1
        self.d = {}
        self.lenstr1 = len(self.s1)     
        for i in xrange(-1,self.lenstr1+1):
            self.d[(i,-1)] = i+1

    def distance(self, s2):
        lenstr2 = len(s2)
        for j in xrange(-1,lenstr2+1):
            self.d[(-1,j)] = j+1

        for i in xrange(self.lenstr1):
            for j in xrange(lenstr2):
                if self.s1[i] == s2[j]:
                    cost = 0
                else:
                    cost = 1
                self.d[(i,j)] = min(
                               self.d[(i-1,j)] + 1, # deletion
                               self.d[(i,j-1)] + 1, # insertion
                               self.d[(i-1,j-1)] + cost, # substitution
                              )
                if i and j and self.s1[i]==s2[j-1] and self.s1[i-1] == s2[j]:
                    self.d[(i,j)] = min (self.d[(i,j)], self.d[i-2,j-2] + cost) # transposition

        return self.d[self.lenstr1-1,lenstr2-1]

if __name__ == '__main__':
   base = u'abs'
   cmpstrs = [u'abs', u'sdfbasz', u'asdf', u'hfghfg']
   dl = DLDistance(base)

   for s in cmpstrs:
      print "damerau_levenshtein"
      print dl.distance(s)
</code></pre>

<p>Even though, it has high level of computation complexity since it calculate N*M times of distance measure where N rows in the first dataframe, M rows in the second dataframe.(To reduce computatinal complexity, you can truncate the set who needs comparison by only comparing the rows which have the same first character)</p>

<p>levenshtein distance: <a href="https://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">https://en.wikipedia.org/wiki/Levenshtein_distance</a></p>

<p>jaro-winkler: <a href="https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance" rel="nofollow">https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance</a></p>

python pandas dataframe match