Вернуть лучшие совпадения для входного запроса, имеющего несколько функций в Python - PullRequest
Новая
       57

Вернуть лучшие совпадения для входного запроса, имеющего несколько функций в Python

0 голосов
/ 18 октября 2018

У меня есть предметы следующим образом: 

[
    { "id":"item1", "age": 1, "color": 'fff', "rate": 3 },
    { "id":"item2", "age": 2, "color": '000', "rate": 4 },
    { "id":"item3", "age": 3, "color": 'eee', "rate": 5 },
    { "id":"item4", "color": 'bbb', "rate": 5 }
]

Теперь я ожидаю, что пользователь будет искать желаемый предмет: {"age": 1, "color": '000', "rate":5} или даже {"age": 3, "color": 'abc'}

Я хотел бы найтилучшее соответствие для этого запроса.Как я могу это сделать?Я не ищу точного ответа.Хотя мне интересно реализовать его как бэкэнд-сервис, поэтому с Python все должно быть в порядке.Я просто не знаю, как решить проблему.Есть ли какой-то алгоритм сопоставления или нечеткий поиск, на который мне нужно обратить внимание?

ОБНОВЛЕНИЕ : данные большие (миллионы элементов), для каждого имеется 50-100 ключейпредметы, но некоторые предметы могут не иметь их все.Также пользовательские запросы могут содержать не все ключи.

Ответы [ 2 ]

0 голосов
/ 18 октября 2018

Я предполагаю, что вы хотите, чтобы элемент data соответствовал наилучшему, а не наилучшему соответствию для каждого ключа по всем значениям.

Это может помочь вам начать: 

>>> data = [
...     { "id":"item1", "age": 1, "color": 'fff', "rate": 3 },
...     { "id":"item2", "age": 2, "color": '000', "rate": 4 },
...     { "id":"item3", "age": 3, "color": 'eee', "rate": 5 }
... ]
>>> user_input = {"age": 1, "color": 'fff', "rate":5}
>>>
>>> criterion = lambda d: len(user_input.items() & d.items())
>>> max(data, key=criterion)
{'id': 'item1', 'age': 1, 'color': 'fff', 'rate': 3}

Вызов max возвращает единственный элемент data с двумя совпадениями здесь.

Если вам нужно более сложное нечеткое сопоставление, чем просто подсчет прямых попаданий, например, 'ffe' ближе к 'fff' чем 'abc', то вам нужно

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

Для строк рассмотрим расстояние Левенштейна и abs(x - y) для числовых типов.

0 голосов
/ 18 октября 2018

Насколько велик ваш набор данных?

Для небольшого набора данных вы можете сделать это за O (n * m) время (n элементов в списке, m ключей в dict), просто взяв элемент, который имеет наибольшее количество совпадений после сравнения значений в тех же ключах, отслеживание количества совпадений. 

search_item = {"age": 1, "color": '000', "rate": 5}
mx = -float('inf')
for item in lst:
    curr = sum(search_item[k]==item[k] for k in item)
    if curr > mx:
        match = item
        mx = curr
print(match)

Критерий поиска может быть не простым сопоставлением значения ключа.Вы можете определить это!

Для очень большого набора данных вы могли бы вместо этого построить k -d дерево из вашего списка и сократить время поиска до O (log (n)) следует в случае, если вы будете использовать список / дерево для поиска нескольких элементов.

Вам следует преобразовать шестнадцатеричные цвета в числовой тип , чтобы у вас был однородный intпечатать по размерам и сравнивать проще, так как сравнение целых чисел проще, чем нечеткое сопоставление строк.

Например, цвет ffb ближе к fff, чем eee: 

>>> int('fff', 16)
4095
>>> int('ffb', 16)
4091
>>> int('eee', 16)
3822
...