MATLAB：字符串單元格數組之間的匹配

Question

我試圖解決以下問題，並且我需要儘可能高效地執行它（即儘可能避免循環）。

我有兩個單元格陣列，分別是A和B.A和B的每個單元格都包含一串字符。這些字符串的長度是可變的。比方說：

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’}; 

此外，單元陣列B的元素的數量約爲幅度比單元陣列A的大三個數量級

我的目標是要找到每一個字符的字符串的多少單詞在A也出現在B.

的每字符串對於前面的示例中，合適的結果可能是這樣的：

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

第一行指示ħ在A的第一個char字符串中出現很多單詞，出現在B的四個char字符串中，而第二行，對於第二個char字符串同樣如此。

雙循環實現非常簡單，但非常耗時由於單元陣列B的長度（超過300萬個單元）。

任何想法？非常感謝你。

澤維爾

Answer 1

讓我得到張貼的 「直白」 的解決方案（至少別人有一個基準來比較）這個開始：

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 

結果：

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

更好的算法可以構建某種索引或散列表...

Answer 2

s解決方案並不複雜。

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

然後比較在一個循環： - 我真的不知道

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 

而且使人們更快

與分開拆分句子。 您可以將內部循環放入應該並行化的parfor中。 如果確實有很多單詞可能會將它們放入數據庫中。這將爲你做索引。

Answer 3

您可以利用Map，它爲您提供高效的基於字典的結構：

對於每一個單詞保存顯示在每個字符串中的出現的向量：

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 

然後，對於發現的每個獨特的單詞A，計算匹配與乙

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 

結果：

match = 

    2  1  0  0 
    1  0  1  0 

這種方式，您有一個#wordsA + #wordsB +的#singleWordsA代替＃wordsA *＃wordsB

編輯的複雜性：或者，如果你不喜歡Map，你可以保存字按字母順序排列的向量中的發生向量。然後，你可以看看比賽同時檢查兩個載體：

（假設我們使用的是結構，其中w屬性是字串和occ是發生向量）

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 

，如果你正在尋找' matlab'，你知道在第10個位置存儲'生命'是無用的檢查位置之前，因爲矢量按字母順序排列。所以我們有嵌套循環解決方案的＃wordsA +＃wordsB iteration與＃wordsA *＃wordsB。