1

I have an array of team names from NCAA, along with statistics associated with them. The school names are often shortened or left out entirely, but there is usually a common element in all variations of the name (like Alabama Crimson Tide vs Crimson Tide). These names are all contained in an array in no particular order. I would like to be able to take all variations of a team name by fuzzy matching them and rename all variants to one name. I'm working in python 2.7 and I have a numpy array with all of the data. Any help would be appreciated, as I have never used fuzzy matching before.

I have considered fuzzy matching through a for-loop, which would (despite being unbelievably slow) compare each element in the column of the array to every other element, but I'm not really sure how to build it.

Currently, my array looks like this:

{Names , info1, info2, info 3}

The array is a few thousand rows long, so I'm trying to make the program as efficient as possible.

a7xcarter
  • 56
  • 1
  • 7
  • Few thousands rows shall be pretty quick in a for loop running over an array that is in memory. – grochmal Aug 16 '16 at 16:54
  • On my last attempt at doing this, it never finished. I do agree that it shouldn't take forever, so I must be doing something wrong. I'm just unsure how to tackle the loop. – a7xcarter Aug 16 '16 at 21:02

1 Answers1

1

The Levenshtein edit distance is the most common way to perform fuzzy matching of strings. It is available in the python-Levenshtein package. Another popular distance is Jaro Winkler's distance, also available in the same package.

Assuming a simple array numpy array:

import numpy as np
import Levenshtein as lv

ar = np.array([
      'string'
    , 'stum'
    , 'Such'
    , 'Say'
    , 'nay'
    , 'powder'
    , 'hiden'
    , 'parrot'
    , 'ming'
    ])

We define helpers to give us indexes of Levenshtein and Jaro distances, between a string we have and all strings in the array.

def levenshtein(dist, string):
    return map(lambda x: x<dist, map(lambda x: lv.distance(string, x), ar))

def jaro(dist, string):
    return map(lambda x: x<dist, map(lambda x: lv.jaro_winkler(string, x), ar))

Now, note that Levenshtein distance is an integer value counted in number of characters, whilst Jaro's distance is a floating point value that normally varies between 0 and 1. Let's test this using np.where:

print ar[np.where(levenshtein(3, 'str'))]
print ar[np.where(levenshtein(5, 'str'))]
print ar[np.where(jaro(0.00000001, 'str'))]
print ar[np.where(jaro(0.9, 'str'))]

And we get:

['stum']
['string' 'stum' 'Such' 'Say' 'nay' 'ming']
['Such' 'Say' 'nay' 'powder' 'hiden' 'ming']
['string' 'stum' 'Such' 'Say' 'nay' 'powder' 'hiden' 'parrot' 'ming']
grochmal
  • 2,901
  • 2
  • 22
  • 28
  • Awesome, thank you! I've been trying to install the python-Levenshtein package for a while, I didn't realize I needed a c++ compiler in order to install it, but this does help with my problem – a7xcarter Aug 18 '16 at 19:09
  • @a7xcarter - Well, you wanted speed so a C based implementation is the quickest. But, maybe, I should mention that there is [jellyfish](https://pypi.python.org/pypi/jellyfish) which is written completely in python and also exports `.levenshtein_distance` and `.jaro_distance` – grochmal Aug 18 '16 at 20:43