MATLAB: mots correspondant entre les tableaux de cellules de chaînes

Question

J'essaie de résoudre le problème suivant, et je dois le faire aussi efficacement que possible (c'est-à-dire en essayant d'éviter les boucles autant que possible). J'ai deux matrices de cellules, à savoir A et B. Chaque cellule de A et B contient une chaîne de caractères. La longueur de ces chaînes de caractères est variable. Disons que:

A={‘life is wonderful’, ‘matlab makes your dreams come true’}; 

B={‘life would be meaningless without wonderful matlab’, ‘what a wonderful world’, ‘the shoemaker makes shoes’, ‘rock and roll baby’}; 

De plus, le nombre d'éléments de réseau de cellules B est d'environ trois ordres de grandeur plus grande que celle du réseau de cellules A.

Mon but est de trouver combien de mots de chaque chaîne char dans a apparaissent également dans toutes les chaînes de caractères de B.

Pour l'exemple précédent, un résultat convenable pourrait être quelque chose comme:

match = [2 1 0 0 
1 0 1 0] 

la première ligne indique h ow beaucoup de mots dans la première chaîne char de A apparaissent dans les quatre chaînes de caractères de B. Et la deuxième rangée, la même chose pour la deuxième chaîne de caractères de A.

La mise en œuvre de la double boucle est simple, mais très longue surtout en raison de la longueur du réseau de cellules B (plus de 3 millions de cellules).

Des idées? Merci beaucoup.

Xavier

Answer 1

Laissez-moi cela a commencé en postant la solution "simple" (au moins d'autres ont une base de comparaison contre):

A = {'life is wonderful', 'matlab makes your dreams come true'}; 
B = {'life would be meaningless without wonderful matlab', 'what a wonderful world', 'the shoemaker makes shoes', 'rock and roll baby'}; 

count = zeros(numel(A),numel(B)); 

%# for each string 
for i=1:numel(A) 
    %# split into words 
    str = textscan(A{i}, '%s', 'Delimiter',' '); str = str{1}; 

    %# for each word 
    for j=1:numel(str) 
     %# count occurences 
     count(i,:) = count(i,:) + cellfun(@numel, strfind(B,str{j})); 
    end 
end 

Le résultat:

>> count 
count = 
    2  1  0  0 
    1  0  1  0 

Un meilleur algorithme pourrait être de construire une sorte d'index ou de table de hachage ...

Answer 2

Le s La solution n'est pas complexe.

diviser les phrases à part avec:

a_words = regexp(A,'(\w+)','match') 
b_words = regexp(B,'(\w+)','match') 

puis comparer dans une boucle:

match = nan(numel(a_words),numel(b_words)); 
for i = 1:numel(a_words) 
    for j = 1:numel(b_words) 
     match(i,j) = sum(ismember(a_words{i},b_words{j})); 
    end 
end 

mais pour le rendre plus rapide - je ne suis pas vraiment sûr. Vous pouvez définitivement mettre la boucle interne dans un parfor qui devrait paralléliser cela. Si c'est vraiment beaucoup de mots, mettez-les dans une base de données. Cela fera l'indexation pour vous.

Answer 3

Vous pouvez exploiter Map, qui vous offre une structure à base de dictionnaire efficace:

Pour chaque ENREGISTRE vecteur représentant les occurrences dans chaque chaîne:

A = {'life is wonderful', 'matlab makes your dreams come true'}; 
B = {'life would be meaningless without wonderful matlab', 'what a wonderful world', 'the shoemaker makes shoes', 'rock and roll baby'}; 

mapA = containers.Map(); 
sizeA = size(A,2); 
for i = 1:size(A,2)   % for each string 
    a = regexpi(A(i),'\w+','match'); 
    for w = a{:}    % for each word extracted 
     str = cell2mat(w); 
     if(mapA.isKey(str))  % if word already indexed 
      occ = mapA(str); 
     else     % new key 
      occ = zeros(1,sizeA); 
     end 
     occ(i) = occ(i)+1; 
     mapA(str) = occ; 
    end 
end 

% same for B 
mapB = containers.Map(); 
sizeB = size(B,2); 
for i = 1:size(B,2) 
    a = regexpi(B(i),'\w+','match'); 
    for w = a{:} 
     str = cell2mat(w); 
     if(mapB.isKey(str)) 
      occ = mapB(str); 
     else 
      occ = zeros(1,sizeB); 
     end 
     occ(i) = occ(i)+1; 
     mapB(str) = occ; 
    end 
end 

puis, pour chaque mot unique qui se trouve dans A, calculer les correspondances avec B

match = zeros(size(A,2),size(B,2)); 
for w = mapA.keys 
    str = cell2mat(w); 
    if (mapB.isKey(str)) 
     match = match + diag(mapA(str))*ones(size(match))*diag(mapB(str)); 
    end 
end 

Résultat:

match = 

    2  1  0  0 
    1  0  1  0 

cette façon, vous avez une complexité #wordsA + #wordsB + #singleWordsA au lieu de # * # wordsA wordsB

EDIT: ou, si vous ne l'aimez pas Map, vous pouvez enregistrer le mot -occurrence-vecteurs dans un vecteur ordonné par ordre alphabétique. Ensuite, vous pouvez rechercher des correspondances de vérifier simultanément les deux vecteurs:

(supposons que nous utilisons un struct où l'attribut w est la chaîne de mots et occ est le vecteur d'occurrence)

i = 1; j = 1; 
while(i<=size(wordsA,2) && i<=size(wordsB,2)) 
if(strcmp(wordsA(i).w, wordsB(j).w)) 
    % update match 
else 
    if(before(wordsA(i).w, wordsA(i).w)) % before: fancy function returning 1 if the first argument comes (alphabetically) before the second one (no builtin function comes to my mind) 
     i = i+1; 
    else 
     j = j+1; 
    end 
end 

si vous cherchez ' matlab 'et vous savez dans la 10e position est stocké' vie 'est inutile de vérifier les positions avant, puisque le vecteur est classé par ordre alphabétique. Donc nous avons # motsA + # motsB itération vs # motsA * # motsB de la solution de boucles imbriquées.