Как мне нечётко сопоставлять элементы в столбце массива в python?

Question

У меня есть массив имен команд из NCAA, а также статистика, связанная с ними. Названия школ часто сокращаются или опускаются полностью, но обычно во всех вариациях названия есть общий элемент (например, Alabama Crimson Tide против Crimson Tide). Все эти имена содержатся в массиве в произвольном порядке. Я хотел бы иметь возможность взять все варианты названия команды путем нечеткого сопоставления их и переименовать все варианты в одно имя. Я работаю в Python 2.7, и у меня есть массив данных со всеми данными. Буду признателен за любую помощь, так как я никогда раньше не использовал нечеткое сопоставление.

Я рассмотрел нечеткое сопоставление через цикл for, который (несмотря на то, что он невероятно медленный) сравнивает каждый элемент в столбце массива с любым другим элементом, но я не совсем уверен, как его построить.

В настоящее время мой массив выглядит так:

{Имена, информация1, информация2, информация 3}

Длина массива составляет несколько тысяч строк, поэтому я стараюсь сделать программу максимально эффективной.

Answer 1

Расстояние редактирования Левенштейна является наиболее распространенным способом нечеткого сопоставления строк. Он доступен в пакете python-Levenshtein. Другое популярное расстояние - расстояние Яро Винклера, также доступное в том же пакете.

Предполагая простой массив numpy массив:

import numpy as np
import Levenshtein as lv

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

Мы определяем помощников, чтобы дать нам индексы расстояний Левенштейна и Яро, между строкой, которую мы имеем, и всеми строками в массиве.

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))

Теперь обратите внимание, что расстояние Левенштейна является целочисленным значением, подсчитанным в количестве символов, в то время как расстояние Яро является значением с плавающей запятой, которое обычно изменяется от 0 до 1. Давайте проверим это, используя 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'))]

И мы получаем:

['stum']
['string' 'stum' 'Such' 'Say' 'nay' 'ming']
['Such' 'Say' 'nay' 'powder' 'hiden' 'ming']
['string' 'stum' 'Such' 'Say' 'nay' 'powder' 'hiden' 'parrot' 'ming']