많은 단어 (약 15000)가 포함 된 셀 배열 사전이 있습니다.많은 단어의 Levenshtein 거리의 속도 최적화
모든 단어 쌍에 대해 strdist (Levenshtein 거리를 계산하기 위해) 함수를 계산하고 싶습니다. 나는 두 가지 방법으로 시도했지만 둘 다 정말 느립니다. 보다 효율적인 솔루션은 무엇이 될 수 있습니까? 붙박이 MATLAB
1)
matrix = sparse(m,m);
for i = 1:m-1;
matrix(i,:) = cellfun(@(u) strdist(dict_keys{i},u), dict_keys);
end
2)
matrix = sparse(m,m);
for i = 1:m-1;
for j = i+1:m
matrix(i,j) = strdist(dict_keys{i},dict_keys{j});
end
end
기능 'strdist'되지 : 여기
내 코드 (dict_keys은 길이 m의 내 셀 어레이이다) 기능이므로 File Exchange에서 가져온 것 같습니다. 두 가지 접근 방식이 시간적으로 동일하다는 이유 때문에cellfun은 내부적으로 루프로 확장됩니다.
strdist이 대칭이면 즉, strdist (a, b) == strdist (b, a) 인 경우 계산의 절반을 절약 할 수 있습니다. 이것은 사실 인 것으로 보이므로 두 번째 루프 (수행중인)에서 j<i의 모든 사례 만 계산하십시오.
그렇지 않으면 mex 기능으로 C에서 strdist를 구현할 수 있으며 속도가 약간 향상 될 수 있습니다. Levenshtein 거리의 C 구현은 예를 들어 rosettacode.org에서 찾을 수 있습니다.
알고리즘이 두 문자열의 거리를 계산하는 방법을 자세히 살펴보고 벡터화하고 이차원에서 런타임을 줄이는 것이 가능한지 살펴보십시오. 그러나 이것은 아마도 쉬운 일은 아닙니다.
마지막으로 strdist 호출이 서로 완전히 독립적이기 때문에 Parallel Computing Toolbox 및 멀티 코어 CPU를 사용하면 코드를 쉽게 병렬화 할 수 있습니다.
Levenshtain Automata와 같은 몇 가지 훨씬 빠른 방법이 있습니다.
기능 인라인 소스 코드를 이동 및 외부를 사용할 수 있습니다 모든 r (함수에 대한 첫 번째 입력)을 반복해도 되겠습니까? – Divakar