通过常用词进行高效查找

Question

我有一个分为单词的名称(字符串)列表.有800万个名字,每个名字最多包含20个单词(代币).唯一令牌的数量是220万.我需要一种有效的方法来查找包含查询中至少一个单词的所有名称(最多可包含20个单词,但通常只包含几个单词).

我目前的方法使用Python Pandas,看起来像这样(后面提到original):

>>> df = pd.DataFrame([['foo', 'bar', 'joe'], 
                       ['foo'], 
                       ['bar', 'joe'], 
                       ['zoo']], 
                      index=['id1', 'id2', 'id3', 'id4'])
>>> df.index.rename('id', inplace=True)  # btw, is there a way to include this into prev line?
>>> print df

       0     1     2
id                  
id1  foo   bar   joe
id2  foo  None  None
id3  bar   joe  None
id4  zoo  None  None

def filter_by_tokens(df, tokens):
    # 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])]
    return pd.concat(results).reset_index().drop_duplicates().set_index(df.index.name)

>>> print filter_by_tokens(df, ['foo', 'zoo'])

       0     1     2
id                  
id1  foo   bar   joe
id2  foo  None  None
id4  zoo  None  None    

目前这种查找(在完整数据集上)在我的(相当强大的)机器上需要5.75秒.我想至少加速它,比如10次.

通过将所有列压缩为一个并对其执行查找(后面称为original, squeezed),我能够达到5.29s :

>>> df = pd.Series([{'foo', 'bar', 'joe'}, 
                    {'foo'}, 
                    {'bar', 'joe'}, 
                    {'zoo'}], 
                    index=['id1', 'id2', 'id3', 'id4'])
>>> df.index.rename('id', inplace=True)
>>> print df

id
id1    {foo, bar, joe}
id2              {foo}
id3         {bar, joe}
id4              {zoo}
dtype: object

def filter_by_tokens(df, tokens):
    return df[df.map(lambda x: bool(x & set(tokens)))]

>>> print filter_by_tokens(df, ['foo', 'zoo'])

id
id1    {foo, bar, joe}
id2              {foo}
id4              {zoo}
dtype: object

但那仍然不够快.

另一个似乎易于实现的解决方案是使用Python多处理(由于GIL并且没有I/O,因此线程在这里应该没有帮助,对吧？).但问题是需要将大数据帧复制到每个进程,这会占用所有内存.另一个问题是我需要filter_by_tokens在循环中多次调用,因此它会在每次调用时复制数据帧,这是低效的.

请注意,单词可能会在名称中出现多次(例如,最常用的单词在名称中出现600k次),因此反向索引会很大.

什么是有效写这个的好方法？Python解决方案首选,但我也对其他语言和技术(例如数据库)开放.

---

UPD: 我已经测量了我的两个解决方案的执行时间以及@piRSquared在他的回答中提出的5个解决方案.结果如下(tl; dr最好是2x改进):

+--------------------+----------------+
|       method       | best of 3, sec |
+--------------------+----------------+
| original           | 5.75           |
| original, squeezed | 5.29           |
| zip                | 2.54           |
| merge              | 8.87           |
| mul+any            | MemoryError    |
| isin               | IndexingError  |
| query              | 3.7            |
+--------------------+----------------+

mul+any在d1 = pd.get_dummies(df.stack()).groupby(level=0).sum()(在128Gb RAM机器上)给出MemoryError .

isin使IndexingError: Unalignable boolean Series key provided上s[d1.isin({'zoo', 'foo'}).unstack().any(1)],显然是因为形状df.stack().isin(set(tokens)).unstack()比原来的数据框(8.39M VS 8.41M行),不知道为什么,以及如何解决的形状略显不足.

请注意,我使用的机器有12个内核(虽然我上面提到了并行化的一些问题).所有解决方案都使用单核.

结论(截至目前):(zip2.54s)与original squeezed解决方案(5.29s)相比提高了2.1 倍.这很好,但如果可能的话,我的目标是至少提高10倍.所以我现在离开(仍然很棒)@piRSquared的答案是不可接受的,欢迎提出更多建议.

Answer 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()]

想法
mul2+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('s in @token').index.get_level_values(0).unique()]