Какова будет лучшая реализация функции __hash__, если функция __eq__ определяет равенство, используя расстояние редактирования?

Question

У меня есть странное требование, когда мне нужно найти общих "Клиентов" из двух разных и очень больших списков. Каждая запись в обоих списках является объектом Customer, который содержит имя и фамилию клиента и его адрес (с разбивкой по адресным строкам, таким как address_line1, address_line2 и т. Д.). Проблема в том, что существует вероятность того, что данные в любом списке могут быть неполными, например, для одной из записей в первом списке имя клиента может отсутствовать, тогда как во втором списке, для того же клиента, его имя адрес (строка 2 и строка 3) может отсутствовать. Что мне нужно сделать, так это найти клиентов, присутствующих в обоих списках. Следует отметить, что списки могут быть большими. Еще один момент, о котором следует помнить, это то, что имена и адреса могут быть семантически одинаковыми, но могут не возвращать результат при точном сопоставлении строк. Например, в первом списке адрес клиента в первом списке может иметь вид B-502 ABC Street тогда как адрес того же клиента во втором списке может быть в форме B 502 ABC Street, Причина, по которой я использую расстояние редактирования, заключается в том, чтобы учитывать ошибки ввода пользователя в списке и обрабатывать некоторые другие незначительные различия в данных, присутствующих в обоих списках.

Я реализовал функцию eq в классе Customer следующим образом.

import re
import editdistance # Using this: https://pypi.python.org/pypi/editdistance

class Customer:
    def __init__(self, fname, lname, address1, address2, address3, city):
        # Removing special characters from all arguments and converting them to lower case
        self.fname = re.sub("[^a-zA-Z0-9]", "", fname.lower())
        self.lname = re.sub("[^a-zA-Z0-9]", "", lname.lower())
        self.address1 = re.sub("[^a-zA-Z0-9]", "", address1.lower())
        self.address2 = re.sub("[^a-zA-Z0-9]", "", address2.lower())
        self.address3 = re.sub("[^a-zA-Z0-9]", "", address3.lower())
        self.city = re.sub("[^a-zA-Z0-9]", "", city.lower())

    def __eq__(self, other):
        if self.lname == "" or self.lname != other.lname:
            return False

        t = 0

        if self.fname != "" and other.fname != "" and self.fname[0] == other.fname[0]:
            t += 1

        if editdistance.eval(self.fname, other.fname) <= 2:
            t += 3

        if editdistance.eval(self.address1, other.address1) <= 3:
            t += 1

        if editdistance.eval(self.address2, other.address2) <= 3:
            t += 1

        if editdistance.eval(self.address3, other.address3) <= 3:
            t += 1

        if editdistance.eval(self.city, other.city) <= 2:
            t += 1

        if t >= 4:
            return True

        return False

    def __hash__():
        # TODO:  Have a robust implementation of a hash function here. If two objects are "equal", their hashes should be the same

Чтобы клиенты присутствовали в обоих списках, я бы сделал следующее:

set(first_list).intersection(set(second_list))

Но чтобы это работало, объект Customer должен быть хешируемым.

Может ли кто-нибудь помочь мне с хорошим механизмом хеширования?

Answer 1

Ваш единственный вариант - нормализовать данные. Если вам нужно сравнить равенство, и у вас могут быть разные форматы, решение - нормализация. Преобразуйте все, чтобы оно было в одном и том же формате в обоих списках.

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

Первый ключевой вопрос: какой процент ошибок вы можете себе позволить? Потому что с пользовательским вводом и большими данными у вас всегда будет их.

Следующим шагом будет измерение процента ошибки, которую вы получите с этим алгоритмом расстояния (или любым другим алгоритмом). Тщательно выбирайте выборочные данные, чтобы процент не зависел от полных данных.

Если этот процент вам подходит, используйте этот алгоритм, если нет, найдите другие алгоритмы и измерьте их.