Распознавание именованных объектов на основе списка для поисковой системы: как масштабировать?

Question

Я работаю в поисковой системе для документов, хранящихся в Solr.

В пользовательском запросе я хочу обнаружить именованные объекты (лица, организации, города ...) .

Пример запроса:

Барак Обама, жена, возраст

В этом запросе я хочу обнаружить, что «Барак Обама» - это человек .

Поскольку запросы не являются реальными фразами, для classi c NER (Spacy, Stanford NER ...) трудно работать должным образом. Итак, я принял этот подход :

• сохранить в словаре все найденные в документах сущности (отсортированные по убыванию длины)

• l oop словарь, чтобы увидеть, содержит ли пользовательский запрос сущности

  def find_entities(query,entities_dict):
  
      entities=[]
      new_query=query.lower()
  
      for entity in entities_dict:
          if find_substring(entity,new_query):
              entities.append({entity:entities_dict[entity]})
              new_query = re.sub(r'\b{}\b'.format(entity), '', new_query)
      return(new_query,entities)
  

На данный момент в моем индексе Solr около 200k сущностей : создание словаря занимает несколько минут; после загрузки этот подход работает хорошо, быстро и не так много памяти.

В ближайшем будущем у меня будет 50-100 миллионов объектов .

I думаю, что будет невозможно сохранить эти объекты в памяти.

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

Answer 1

Одно очевидное грубое решение состоит в том, чтобы просто распределить ваш поисковый индекс: вы создаете, например, 100 узлов со словарем по 1 миллиону сущностей в каждом, вы запускаете их параллельно и объединяете результаты.

Другое решение (которое может дополнять разбиение индекса) состоит в том, чтобы сохранить ваши сущности не в простом списке, а вместо этого в дереве префиксов (он же tr ie). ) или на графике Aho-Corasick . Эти структуры данных значительно ускоряют поиск по подстроке, потому что они пытаются сопоставить все сущностей с вашим запросом за один проход, используя тот факт, что многие сущности имеют идентичные подстроки в них ,

На самом деле, я использовал pyahocorasick для поиска нескольких миллионов объектов (фильмов, песен, актеров и т. Д.) В коротких запросах, и это, похоже, очень хорошо масштабировалось. , Формально временная сложность Aho-Corasick не зависит от общего числа объектов, а только от количества соответствующих объектов в конкретном запросе. Поэтому, если поиск замедляется (что маловероятно), имеет смысл посмотреть, какие объекты генерируют множество ложных положительных совпадений, и удалить их из индекса. В моем случае, после удаления очень распространенных сущностей, таких как «Это» (это имя mov ie!), Средство сравнения ускорилось еще больше.

Вот пример. Сначала мы получаем объекты для поиска (15 тыс. Городов):

pip install pyahocorasick
wget https://simplemaps.com/static/data/world-cities/basic/simplemaps_worldcities_basicv1.6.zip
unzip simplemaps_worldcities_basicv1.6.zip

Затем мы создаем автомат, который может сопоставлять сущности (города):

import pandas as pd
import re
import ahocorasick
cities = pd.read_csv('worldcities.csv')

def preprocess(text):
    """
    Add underscores instead of non-alphanumeric characters 
    and on the word boundaries in order to tell words from word substrings.
    """
    return '_{}_'.format(re.sub('[^a-z0-9]', '_', text.lower()))

index = ahocorasick.Automaton()
for city in cities.city:
    index.add_word(preprocess(city), city)
index.make_automaton()
# this object can be pickled to disk and then loaded back

И теперь на самом деле применим это Индекс для поиска объектов в тексте:

def find_cities(text, searcher):
    result = dict()
    for end_index, city_name in searcher.iter(preprocess(text)):
        end = end_index - 1
        start = end - len(city_name)
        result[(start, end)] = city_name
    return result

print(find_cities( 'Tver’ is somewhere between Moscow and Saint Petersburg', index))
# {(0, 5): 'Tver’', (27, 33): 'Moscow', (38, 54): 'Saint Petersburg', (44, 54): 'Petersburg'} 
# the search takes about 0.1 ms

Наивный поиск дает те же результаты, но занимает около 10 мс:

for city in cities.city:
    idx = text.find(city)
    if idx >=0:
        print(idx, city)

Вот блокнот с моим код.