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 문자열에 나타납니다. 두 번째 행은 A의 두 번째 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, 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 

결과 :

,363,210

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 반복 vs. # wordsA * # wordsB를 가지고 있습니다.