큰 문자열의 빠른 근사 문자열 차이

Question

두 개의 문자열 사이의 차이를 변경 모니터 시스템의 일부로 계량하려고합니다.

내가 겪고있는 문제는 문자열이 대입니다. 나는 종종 100K + 문자로 문자열을 처리 할 수 ​​있습니다.

저는 현재 Levenshtein 거리를 사용하고 있지만 큰 문자열의 경우 levenshtein 거리를 계산하는 것은 매우 비효율적입니다. 심지어 최상의 구현은 O(min(mn)) 만 관리합니다.

두 문자열의 길이가 거의 같기 때문에 거리 계산 프로세스에 많은 시간이 걸릴 수 있습니다.

고정밀도는 필요하지 않습니다. 1000 (예 : 0.1 %)에서 1의 변경 해상도는 제 신청에 충분합니다.

더 효율적인 문자열 거리 계산을 위해 어떤 옵션이 있습니까?

Answer 1

일부 오류를 허용 할 수있는 경우 문자열을 작은 청크로 분할하고 쌍 거리 L 거리를 계산할 수 있습니다.

다음 단계 (최악의 시나리오는 당신에게 2 * <number of insert/deletes> * <number of chunks> 대신 <number of insert/deletes>의 거리를 줄 것이다) 방법은 분명히 교체, 삽입에 대한 정확한 결과를 얻을 것입니다 및 삭제 청크의 수에 따라 정확도의 벌금을 부과 할

1. 는 먼저 작은 청크 크기를 시도 크고 더 큰 덩어리로 이동하고 각 사이에 드롭을 준수 프로세스 적응을 할 수 있었다, 나는 변화의 예상 특성에 따라 그 일을 두 가지 방법을 참조 되풀이. 그것은 측정 된 거리의 얼마나 많은 부분이 오차인지 추정하는데 도움이 될 것입니다.
2. 두 개의 청크의 차이점을 찾으면 차이점을 확인하고 (정확히 얼마나 많은 문자가 추가/삭제 된 것인지) 확인하고 그에 따라 왼쪽 또는 오른쪽으로 다음 청크를 이동하십시오.