string - 批量 strfind : finding lots of strings within lots of other strings

Question

问题:我有两个大型字符串元胞数组A 和B。我想知道识别 A 中哪些元素包含 B 中哪些元素的最快方法。特别是不循环能不能做到？

最小示例:(我的实际 A 和 B 分别包含 7,000,000 和 22,000 个字符串)

A = {'one';
     'two';
     'three';
     'four'};
B = {'ee';
     'xx';
     'r'};

该示例所需的输出是

C = [ 0 0 0 ;
      0 0 0 ;
      1 0 1 ;
      0 0 1 ];

其中 C 的行和列分别对应于 A 和 B 的元素。对于我的目的，我只需要一个真/假答案，但如果 C 返回 where B 中的字符串的第一个索引，我将获得加分A，例如:

C = [ 0 0 0 ;
      0 0 0 ;
      4 0 3 ;
      0 0 4 ];

我尝试过的: This post 是类似的，除了他们正在寻找字符串排除 其他字符串，因此 regexp 提供了一个很好的解决方案——我认为这不适用于此处。对我们来说，循环可以完成工作，但速度太慢:

for i=1:length(A);
    for j=1:length(B);
        C(i,j) = max([0,strfind(A{i},B{j})]); disp(C(i,j));
    end
end

或者，基本上是相同的东西，但是使用 cellfun:

AA = repmat(A,[1 length(B)]);
BB = repmat(B,[length(A) 1]);
C  = reshape(cellfun(@(a,b) max([0,strfind(a,b)]),AA(:),BB(:)),[length(A),length(B)]);

更大的例子:我在一些更大的数组(仍然比我需要的要小)上测试了 cellfun 方法:

N=10000; M=200;
A=cellstr(char(randi([97,122],[N,10])));  %// N random length 10 lowercase strings
B=cellstr(char(randi([97,122],[M,4])));   %// M random length 4 lowercase strings

tic;
AA=repmat(A,[1 length(B)]);
BB=repmat(B,[length(A) 1]);
C=reshape(cellfun(@(a,b) max([0,strfind(a,b)]),AA(:),BB(:)),[length(A),length(B)]); 
toc

Elapsed time is 21.91 seconds.

有什么想法吗？ regexp 有帮助吗？ ismember 有帮助吗？我卡在循环了吗？

Answer 1

一般来说，我建议您的预期输出矩阵在内存方面会很大，无论如何您都需要重新考虑您的方法。

如果您有一个较小的数据集，您可以按如下方式进行:

A = {'one';
     'two';
     'three';
     'four'};
B = {'ee';
     'xx';
     'r'};

%// generate indices
n = numel(A);
m = numel(B);
[xi,yi] = ndgrid(1:n,1:m);

%// matching
Ax = A(xi);
By = B(yi);
temp = regexp(Ax,By,'start');

%// localize empty cell elements
%// cellfun+@isempty is quite fast
emptyElements = cellfun(@isempty, temp);

%// generate output
out = zeros(n,m);
out(~emptyElements) = [temp{:}];

---

out =

     0     0     0
     0     0     0
     4     0     3
     0     0     4