Levenshtein 거리 알고리즘 최적화

Question

Levenshtein 거리를 사용하여 사용자가 입력 한 것과 가장 가까운 결과를 결정하는 저장 프로 시저가 있습니다. 속도에 실제로 영향을 미치는 유일한 함수는 가장 가까운 거리의 레코드를 선택하기 전에 모든 레코드의 Levenshtein 거리를 계산하는 함수입니다 (필자는 Levenshtein 함수를 호출하는 대신 0을 넣어 검증했습니다). 테이블에는 150 만 개의 레코드가 있으므로 약간의 조정조차 몇 초 정도면 쓸 수 있습니다. 지금은 전체가 10 분 이상 실행됩니다. 사용 방법은 다음과 같습니다.

ALTER function dbo.Levenshtein 
( 
    @Source nvarchar(200), 
    @Target nvarchar(200) 
) 
RETURNS int 
AS 
BEGIN 
DECLARE @Source_len int, @Target_len int, @i int, @j int, @Source_char nchar, @Dist int, @Dist_temp int, @Distv0 varbinary(8000), @Distv1 varbinary(8000) 

SELECT @Source_len = LEN(@Source), @Target_len = LEN(@Target), @Distv1 = 0x0000, @j = 1, @i = 1, @Dist = 0 

WHILE @j <= @Target_len 
BEGIN 
    SELECT @Distv1 = @Distv1 + CAST(@j AS binary(2)), @j = @j + 1 
END 

WHILE @i <= @Source_len 
BEGIN 
    SELECT @Source_char = SUBSTRING(@Source, @i, 1), @Dist = @i, @Distv0 = CAST(@i AS binary(2)), @j = 1 

WHILE @j <= @Target_len 
BEGIN 
    SET @Dist = @Dist + 1 
    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j-1, 2) AS int) + 
        CASE WHEN @Source_char = SUBSTRING(@Target, @j, 1) THEN 0 ELSE 1 END 

    IF @Dist > @Dist_temp 
    BEGIN 
     SET @Dist = @Dist_temp 
    END 

    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j+1, 2) AS int)+1 

    IF @Dist > @Dist_temp SET @Dist = @Dist_temp 
    BEGIN 
     SELECT @Distv0 = @Distv0 + CAST(@Dist AS binary(2)), @j = @j + 1 
    END 
END 

SELECT @Distv1 = @Distv0, @i = @i + 1 
END 

RETURN @Dist 
END 

여기서부터해야 할 부분은 무엇입니까?

Answer 1

내가 과거에이 방법은 "데이터베이스"(실제로 맞춤법 교정기 용 단어 사전)를 trie로 저장하는 것입니다.

그런 다음 분기 및 바인딩 루틴을 사용하여 가장 가까운 항목을 찾습니다. 작은 거리의 경우 소요 시간은 거리면에서 지수 함수입니다. 큰 거리의 경우, 지금 보는 것처럼 사전 크기가 선형입니다.

분기 및 경계는 기본적으로 트라이의 깊이 우선 트리 워크이지만 오류 예산이 있습니다. 각 노드에서 현재 levenshtein 거리를 추적하고 예산을 초과하는 경우 트리의 해당 분기를 잘라냅니다.

먼저 예산을 0으로 걷습니다. 그러면 정확한 일치 항목 만 찾습니다. 일치하는 항목을 찾지 못하면 하나의 예산으로 처리합니다. 그러면 1의 거리에서 일치하는 항목을 찾을 수 있습니다. 아무 것도 찾지 못하면 2의 예산으로 작업을 수행합니다. 이것은 비효율적 인 것처럼 들리지만, 각 걷기에는 이전 걷기보다 훨씬 더 많은 시간이 걸리기 때문에 마지막 걸음이 시간을 지배합니다.

추가 : 코드의 개요 (내 C를 사면) :

// dumb version of trie node, indexed by letter. You can improve. 
typedef struct tnodeTag { 
    tnodeTag* p[128]; 
} tnode; 

tnode* top; // the top of the trie 

void walk(tnode* p, char* s, int budget){ 
    int i; 
    if (*s == 0){ 
    if (p == NULL){ 
     // print the current trie path 
    } 
    } 
    else if (budget >= 0){ 
    // try deleting this letter 
    walk(p, s+1, budget-1); 
    // try swapping two adjacent letters 
    if (s[1]){ 
     swap(s[0], s[1]); 
     walk(p, s, budget-1); 
     swap(s[0], s[1]); 
    } 
    if (p){ 
     for (i = 0; i < 128; i++){ 
     // try exact match 
     if (i == *s) walk(p->p[i], s+1, budget); 
     // try replacing this character 
     if (i != *s) walk(p->p[i], s+1, budget-1); 
     // try inserting this letter 
     walk(p->p[i], s, budget-1); 
     } 
    } 
    } 
} 

는 기본적으로, 당신이 그것을 건너 뛰는 동일한 노드에서 검색하여 편지를 삭제 시뮬레이션합니다. 당신은 전진하지 않고 트라이를 내림으로써 편지를 삽입하는 것을 시뮬레이션합니다. 글자를 일치시키는 것처럼 행동함으로써 글자를 대체하는 것처럼 시뮬레이트합니다. 당신이 그것의 걸림돌을 얻을 때, 당신은 O와 0을 대체하는 것과 같은 다른 가능한 불일치를 추가 할 수 있습니다. L 또는 I - 그런 바보 같은 것들.

트라이에있는 현재 단어를 나타내는 문자 배열 인수를 추가하려고합니다.