Подходящая структура данных для быстрого поиска на множествах. Импут: теги, вывод: предложение

Question

У меня следующая проблема.

Я получаю 1-10 тегов, связанных с изображением, каждый из которых имеет вероятность существования на изображении.

входы: пляж, женщина, собака, дерево ...

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

например:

пляж -> "развлечения на пляже " / "отдых на пляже " ....

пляж, женщина -> " женщина на пляже "

пляж, женщина, собака -> ничего не найдено!

взять самое близкое существующее, но рассмотреть вероятность скажем так: женщина 0,95, пляж 0,85, собака 0,7 поэтому, если существует, возьмите женщину + пляж (0,95, 0,85), то женщину + собаку и последний пляж + собаку, порядок выше, чем лучше, но мы не суммируем.

Я думал об использовании python sets , но я не совсем уверен, как.

Другой вариант будет defaultdict:

db ['beach'] ['woman'] ['dog'], но я хочу получить тот же результат и из: дб [ 'женщина'] [ 'beeach'] [ 'собака']

Я бы хотел получить хорошее решение. Спасибо.

РЕДАКТИРОВАТЬ: Рабочий раствор

from collections import OrderedDict
list_of_keys = []
sentences = OrderedDict()
sentences[('dogs',)] = ['I like dogs','dogs are man best friends!']
sentences[('dogs', 'beach')] = ['the dog is at the beach']
sentences[('woman', 'cafe')] = ['The woman sat at the cafe.']
sentences[('woman', 'beach')] = ['The woman was at the beach']
sentences[('dress',)] = ['hi nice dress', 'what a nice dress !']


def keys_to_list_of_sets(dict_):
    list_of_keys = []
    for key in dict_:
        list_of_keys.append(set(key))

    return list_of_keys

def match_best_sentence(image_tags):
    for i, tags in enumerate(list_of_keys):
        if (tags & image_tags) == tags:
            print(list(sentences.keys())[i])

list_of_keys = keys_to_list_of_sets(sentences)
tags = set(['beach', 'dogs', 'woman'])
match_best_sentence(tags)

Результаты:

('dogs',)
('dogs', 'beach')
('woman', 'beach')

Это решение работает со всеми ключами упорядоченного словаря, o (n), я хотел бы видеть улучшение производительности.

Answer 1

То, что кажется самым простым способом сделать это без использования БД, это сохранить наборы для каждого слова и взять пересечения.

Более подробно:

Если предложение содержит слово «женщина», то вы помещаете его в набор «женщина». Точно так же для собаки и пляжа и т.д. для каждого предложения. Это означает, что сложность вашего пространства равна O (предложения * average_tags), поскольку каждое предложение повторяется в структуре данных.

Возможно, у вас есть:

>>> dogs = set(["I like dogs", "the dog is at the beach"])
>>> woman = set(["The woman sat at the cafe.", "The woman was at the beach"])
>>> beach = set(["the dog is at the beach", "The woman was at the beach", "I do not like the beach"])
>>> dogs.intersection(beach)
{'the dog is at the beach'}

Который вы можете встроить в объект, который находится над defaultdict, чтобы вы могли взять список тегов, и вы можете пересекать только эти списки и возвращать результаты.

Грубая идея реализации:

from collections import defaultdict
class myObj(object): #python2
    def __init__(self):
        self.sets = defaultdict(lambda: set()) 

    def add_sentence(self, sentence, tags):
         #how you process tags is up to you, they could also be parsed from
         #the input string. 
         for t in tags:
             self.sets[tag].add(sentence)

    def get_match(self, tags):
         result = self.sets(tags[0]) #this is a hack 
         for t in tags[1:]:
             result = result.intersection(self.sets[t])

         return result #this function can stand to be improved but the idea is there

Может быть, из-за этого станет более понятным, как стандартные слова и наборы будут в конечном итоге выглядеть в объекте.

>>> a = defaultdict(lambda: set())
>>> a['woman']
set([])
>>> a['woman'].add(1)
>>> str(a)
"defaultdict(<function <lambda> at 0x7fcb3bbf4b90>, {'woman': set([1])})"
>>> a['beach'].update([1,2,3,4])
>>> a['woman'].intersection(a['beach'])
set([1])
>>> str(a)
"defaultdict(<function <lambda> at 0x7fcb3bbf4b90>, {'woman': set([1]), 'beach': set([1, 2, 3, 4])})"

Answer 2

Это в основном зависит от размера базы данных и количества комбинаций между ключевыми словами. Кроме того, это зависит также от того, какую операцию вы выполняете чаще всего.
Если он небольшой и вам нужна быстрая find операция, можно использовать словарь с frozensets в качестве ключей, который содержит теги и со значениями всех связанных предложений.

Например,

d=defaultdict(list)
# preprocessing
d[frozenset(["bob","car","red"])].append("Bob owns a red car")

# searching
d[frozenset(["bob","car","red"])]  #['Bob owns a red car']
d[frozenset(["red","car","bob"])]  #['Bob owns a red car']

Для сочетаний слов типа "боб", "автомобиль" у вас есть разные возможности в зависимости от количества ключевых слов и того, что важнее. Например

• Вы можете иметь дополнительные записи для каждой комбинации
• Вы можете перебирать ключи и проверять те, которые содержат car и bob