python - 将字符串从一个 numpy 数组匹配到另一个

Question

您好，我正在使用 python 3，我已经面对这个问题有一段时间了，但我似乎无法解决这个问题。

我有 2 个包含 strings 的 numpy 数组

array_one = np.array(['alice', 'in', 'a', 'wonder', 'land', 'alice in', 'in a', 'a wonder', 'wonder land', 'alice in a', 'in a wonder', 'a wonder land', 'alice in a wonder', 'in a wonder land', 'alice in a wonder land'])

如果您注意到，array_one 实际上是一个数组，其中包含句子的 1-gram、2-gram、3-gram、4-gram、5-gram 爱丽丝梦游仙境。

I purposefully have taken wonderland as two words wonder and land.

现在我有另一个包含一些位置和名称的 numpy 数组。

array_two = np.array(['new york', 'las vegas', 'wonderland', 'florida'])

现在我要做的是获取 array_two 中存在的 array_one 中的所有元素。

如果我使用两个数组的 np.intersect1d 取出交集，我不会得到任何匹配项，因为 wonderland 是 array_one< 中的两个单独的词 而在 array_two 中它是一个单词。

有什么办法吗？我尝试了堆栈 ( this ) 的解决方案，但它们似乎不适用于 python 3

array_one would at max have 60-100 items while array_two would at max have roughly 1 million items but an average of 250,000 - 500,000 items.

---

编辑

我使用了一种非常天真的方法，因为直到现在我还找不到解决方案，我从两个 arrays 中替换了 white space 然后使用结果boolean array ([True, False, True]) to `filter on the original array.下面是代码:

import numpy.core.defchararray as np_f
import numpy as np


array_two_wr = np_f.replace(array_two, ' ', '')
array_one_wr = np_f.replace(array_one, ' ', '')
intersections = array_two[np.in1d(array_two_wr, array_one_wr)]

But I am not sure this is the way to go considering the number of elements in array_two

Answer 1

Minhashing 绝对可以用在这里。下面是 minhashing 背后的非常普遍的想法:对于列表中的每个对象，对该对象进行多次哈希处理，并更新一个对象，该对象跟踪为每个列表成员计算的哈希值。然后检查生成的哈希值集，并针对每个哈希值找到计算该哈希值的所有对象(我们刚刚存储了这些数据)。如果仔细选择散列函数，计算相同散列的对象将非常相似。

有关 minhashing 的更详细说明，请参阅 Mining Massive Datasets 的第 3 章.

这是一个使用您的数据和数据草图 (pip install datasketch) 的示例 Python 3 实现，它计算哈希值:

import numpy as np
from datasketch import MinHash, MinHashLSH
from nltk import ngrams

def build_minhash(s):
  '''Given a string `s` build and return a minhash for that string'''
  new_minhash = MinHash(num_perm=256)
  # hash each 3-character gram in `s`
  for chargram in ngrams(s, 3):
    new_minhash.update(''.join(chargram).encode('utf8'))
  return new_minhash

array_one = np.array(['alice', 'in', 'a', 'wonder', 'land', 'alice in', 'in a', 'a wonder', 'wonder land', 'alice in a', 'in a wonder', 'a wonder land', 'alice in a wonder', 'in a wonder land', 'alice in a wonder land'])
array_two = np.array(['new york', 'las vegas', 'wonderland', 'florida'])

# create a structure that lets us query for similar minhashes
lsh = MinHashLSH(threshold=0.3, num_perm=256)

# loop over the index and value of each member in array two
for idx, i in enumerate(array_two):
  # add the minhash to the lsh index
  lsh.insert(idx, build_minhash(i))

# find the items in array_one with 1+ matches in arr_two
for i in array_one:
  result = lsh.query(build_minhash(i))
  if result:
    matches = ', '.join([array_two[j] for j in result])
    print(' *', i, '--', matches)

结果(array_one 成员在左边，array_two 匹配在右边):

 * wonder -- wonderland
 * a wonder -- wonderland
 * wonder land -- wonderland
 * a wonder land -- wonderland
 * in a wonder land -- wonderland
 * alice in a wonder land -- wonderland

此处调整精度/召回率的最简单方法是将 threshold 参数更改为 MinHashLSH。您也可以尝试修改散列技术本身。在这里，我在为每个 ngram 构建 minhash 时使用了 3 个字符的哈希值，耶鲁大学的数字人文实验室发现这种技术在捕获文本相似性方面非常强大:https://github.com/YaleDHLab/intertext