Batch strfind: поиск множества строк в пределах множества других строк

Question

Вопрос: У меня есть два больших массива ячеек строк A и B. Я хочу узнать самый быстрый способ определить, какие элементы в A содержат в B. В частности, можно ли это сделать без цикла?

Минимальный Пример: (мой фактический A и B содержат 7000000 и 22000 строк, соответственно)

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 возвращает первый индекс где строка в B находится в A, например:

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

Что я пробовал:This сообщение похоже, за исключением того, что они ищут строки исключая другие строки, так что 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)]); 

Bigger Пример: Я тестировал метод 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