Эффективный поиск по общим словам

Ответ 1

идея 0
zip

def pir(s, token):
    return s[[bool(p & token) for p in s]]

pir(s, {'foo', 'zoo'})

идея 1
merge

token = pd.DataFrame(dict(v=['foo', 'zoo']))
d1 = df.stack().reset_index('id', name='v')
s.ix[d1.merge(token).id.unique()]

идея 2
mul + any

d1 = pd.get_dummies(df.stack()).groupby(level=0).sum()
token = pd.Series(1, ['foo', 'zoo'])
s[d1.mul(token).any(1)]

идея 3
isin

d1 = df.stack()
s[d1.isin({'zoo', 'foo'}).unstack().any(1)]

идея 4
query

token = ('foo', 'zoo')
d1 = df.stack().to_frame('s')
s.ix[d1.query( in @token').index.get_level_values(0).unique()]

Ответ 2

Я сделал аналогичные вещи со следующими инструментами

Hbase - Key can have Multiple columns (Very Fast)
ElasticSearch - Nice easy to scale. You just need to import your data as JSON

Apache Lucene - будет очень хорошо для 8 миллионов записей

Ответ 3

Вы можете сделать это с обратным индексом; приведенный ниже код в pypy строит индекс за 57 секунд, выполняет ли запрос или 20 слов 0,00018 секунд и использует 3,2 ГБ памяти. Python 2.7 строит индекс за 158 секунд и делает запрос в 0,0013 секунды, используя около 3,41 ГБ памяти.

Самый быстрый способ сделать это - с растровыми обратными индексами, сжатыми для экономии места.

"""
8m records with between 1 and 20 words each, selected at random from 100k words
Build dictionary of sets, keyed by word number, set contains nos of all records
with that word
query merges the sets for all query words
"""
import random
import time   records = 8000000
words = 100000
wordlists = {}
print "build wordlists"
starttime = time.time()
wordlimit = words - 1
total_words = 0
for recno in range(records):
    for x in range(random.randint(1,20)):
        wordno = random.randint(0,wordlimit)
        try:
           wordlists[wordno].add(recno)
        except:
           wordlists[wordno] = set([recno])
        total_words += 1
print "build time", time.time() - starttime, "total_words", total_words
querylist = set()
query = set()
for x in range(20):
    while 1:
        wordno = (random.randint(0,words))
        if  wordno in wordlists: # only query words that were used
            if  not wordno in query:
                query.add(wordno)
                break
print "query", query
starttime = time.time()
for wordno in query:
    querylist.union(wordlists[wordno])
print "query time", time.time() - starttime
print "count = ", len(querylist)
for recno in querylist:
    print "record", recno, "matches"

Ответ 4

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

data =[['foo', 'bar', 'joe'],
       ['foo'],
       ['bar', 'joe'],
       ['zoo']]

wordlists = {}
print "build wordlists"
for x, d in enumerate(data):
    for word in d:
        try:
           wordlists[word].add(x)
        except:
           wordlists[word] = set([x])
print "query"
query = [ "foo", "zoo" ]
results = set()
for q in query:
    wordlist = wordlists.get(q)
    if  wordlist:
        results = results.union(wordlist)
l = list(results)
l.sort()
for x in l:
    print data[x]

Стоимость во времени и памяти строит списки слов (инвертированные индексы); запрос почти свободен. У вас 12 основных машин, поэтому, по-видимому, у него много памяти. Для повторяемости создайте списки слов, рассоедините каждый список слов и напишите в sqlite или любую базу данных key/value со словом в качестве ключа, а маринованный набор - как двоичный blob. то все, что вам нужно, это:

initialise_database()
query = [ "foo", "zoo" ]
results = set()                             
for q in query:                             
    wordlist = get_wordlist_from_database(q) # get binary blob and unpickle
    if  wordlist:                        
        results = results.union(wordlist)
l = list(results)
l.sort()   
for x in l:      
    print data[x]

альтернативно, используя массивы, которые более эффективны с точки зрения памяти и, вероятно, быстрее для создания индекса. pypy больше, чем в 10 раз быстрее, чем 2.7

import array

data =[['foo', 'bar', 'joe'],
       ['foo'],
       ['bar', 'joe'],
       ['zoo']]

wordlists = {}
print "build wordlists"
for x, d in enumerate(data):
    for word in d:
        try:
           wordlists[word].append(x)
        except:
           wordlists[word] = array.array("i",[x])
print "query"
query = [ "foo", "zoo" ]
results = set()
for q in query:
    wordlist = wordlists.get(q)
    if  wordlist:
        for i in wordlist:
            results.add(i)
l = list(results)
l.sort()
for x in l:
    print data[x]

Ответ 5

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

Наивный подход (в исходном сообщении) позволит до 64 отдельных токенов.

Улучшенный код ниже использует битовую маску, например, фильтр цветения (модульная арифметика при установке бит вокруг 64). Если имеется более 64 уникальных токенов, будут появляться ложные срабатывания, которые будут автоматически проверяться кодом (с использованием исходного кода).

Теперь наихудшая производительность ухудшится, если количество уникальных токенов (намного) больше 64, или если вам особенно не повезло. Хеширование может уменьшить это.

Что касается производительности, используя приведенные ниже контрольные данные, я получаю:

Оригинальный код: 4.67 секунд

Битмакс-код: 0,30 секунд

Однако, когда количество уникальных токенов увеличивается, битмакс-код остается эффективным, в то время как исходный код значительно замедляется. Имея около 70 уникальных токенов, я получаю что-то вроде:

Оригинальный код: ~ 15 секунд

Битмакс-код: 0,80 секунд

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

class WordLookerUpper(object):
    def __init__(self, token_lists):
        tic = time.time()
        self.df = pd.DataFrame(token_lists,
                    index=pd.Index(
                        data=['id%d' % i for i in range(len(token_lists))],
                        name='index'))
        print('took %d seconds to build dataframe' % (time.time() - tic))
        tic = time.time()
        dii = {}
        iid = 0
        self.bits = np.zeros(len(token_lists), np.int64)
        for i in range(len(token_lists)):
            for t in token_lists[i]:
                if t not in dii:
                    dii[t] = iid
                    iid += 1
                # set the bit; note that b = dii[t] % 64
                # this 'wrap around' behavior lets us use this
                # bitmask as a probabilistic filter
                b = dii[t]
                self.bits[i] |= (1 << b)
        self.string_to_iid = dii
        print('took %d seconds to build bitmask' % (time.time() - tic))

    def filter_by_tokens(self, tokens, df=None):
        if df is None:
            df = self.df
        tic = time.time()
        # search within each column and then concatenate and dedup results    
        results = [df.loc[lambda df: df[i].isin(tokens)] for i in range(df.shape[1])]
        results = pd.concat(results).reset_index().drop_duplicates().set_index('index')
        print('took %0.2f seconds to find %d matches using original code' % (
                time.time()-tic, len(results)))
        return results

    def filter_by_tokens_with_bitmask(self, search_tokens):
        tic = time.time()
        bitmask = np.zeros(len(self.bits), np.int64)
        verify = np.zeros(len(self.bits), np.int64)
        verification_needed = False
        for t in search_tokens:
            bitmask |= (self.bits & (1<<self.string_to_iid[t]))
            if self.string_to_iid[t] > 64:
                verification_needed = True
                verify |= (self.bits & (1<<self.string_to_iid[t]))
        if verification_needed:
            results = self.df[(bitmask > 0 & ~verify.astype(bool))]
            results = pd.concat([results,
                                 self.filter_by_tokens(search_tokens,
                                    self.df[(bitmask > 0 & verify.astype(bool))])])
        else:
            results = self.df[bitmask > 0]
        print('took %0.2f seconds to find %d matches using bitmask code' % (
                time.time()-tic, len(results)))
        return results

Сделайте несколько тестовых данных

unique_token_lists = [
    ['foo', 'bar', 'joe'], 
    ['foo'], 
    ['bar', 'joe'], 
    ['zoo'],
    ['ziz','zaz','zuz'],
    ['joe'],
    ['joey','joe'],
    ['joey','joe','joe','shabadoo']
]
token_lists = []
for n in range(1000000):
    token_lists.extend(unique_token_lists)

Запустите исходный код и битмакс-код

>>> wlook = WordLookerUpper(token_lists)
took 5 seconds to build dataframe
took 10 seconds to build bitmask

>>> wlook.filter_by_tokens(['foo','zoo']).tail(n=1)
took 4.67 seconds to find 3000000 matches using original code
id7999995   zoo None    None    None

>>> wlook.filter_by_tokens_with_bitmask(['foo','zoo']).tail(n=1)
took 0.30 seconds to find 3000000 matches using bitmask code
id7999995   zoo None    None    None