MATLAB: совпадение слов между массивами строк - PullRequest
Новая
       46

MATLAB: совпадение слов между массивами строк

3 голосов
/ 08 ноября 2011

Я пытаюсь решить следующую проблему, и мне нужно сделать это как можно более эффективно (т.е. стараться избегать циклов как можно больше).

У меня есть два массива ячеек, а именно: 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]

Первая строка указывает, сколько словв 1-ой строке символов A появляются в четырех строках символов B. И во второй строке то же самое для 2-ой строки символов A.

Реализация двойного цикла проста, но очень трудоемка, особенно потому, чтодлины массива ячеек B (более 3 миллионов ячеек).

Есть идеи?Большое спасибо.

Ксавье

Ответы [ 3 ]

2 голосов
/ 08 ноября 2011

Решение не сложное.

разбить предложения на: 

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, который должен распараллелить это. Если это действительно много слов, возможно, поместите их в базу данных. Это сделает индексацию за вас.

2 голосов
/ 08 ноября 2011

Позвольте мне начать это с публикации «простого» решения (по крайней мере, у других есть базовая линия для сравнения): 

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

Лучшим алгоритмом может быть создание какого-то индекса или хэш-таблицы ...

1 голос
/ 08 ноября 2011

Вы можете использовать Карта , которая предлагает вам эффективную структуру на основе словаря:

Для каждого слова сохраните вектор, показывающий вхождения в каждой строке: 

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

Результат: 

match =

     2     1     0     0
     1     0     1     0

таким образом, у вас есть сложность #wordsA + #wordsB + #singleWordsA вместо # wordsA * # wordsB

EDIT : или, если вам не нравится 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 итерация против # wordsA * # wordsB решения с вложенными циклами.

...