bitDP 이야기

비트 연산 기술 Advent Calendar 2016 12일째 보도다.
여러분이 가장 좋아하는 비트DP 이야기입니다.편집 거리(Edit Distance:ED)를 bitDP로 약간 계산하면

거리 편집

먼저 정의부터 시작한다.
편집 거리(ED; 레벤스타인 거리: Levennshtein Distance라고도 함)는 두 문자열 사이에 정의된 문자열을 다른 문자열로 변환할 때의 최소 {바꾸기, 삽입, 삭제} 횟수를 나타냅니다.
예를 들어 abcdefg와 abxdeg의 편집 거리는 2이고 부채의 교체는 1회c→x, 삽입은 0회, 삭제는 1회f이다.

일반적 으로 해답 하다

아시다시피 2차원적인 DP로 풀 수 있습니다.여기에는 점화 공식만 표시됩니다.

비트DP로 푸세요.

이미 알고 있는 비트 병렬 알고리즘Myers 알고리즘.일본어 해설 글을 많이 썼고 궁금한 사람도 많았어요.

비트 병렬 알고리즘을 사용한 편집 거리

C++: 편집 거리를 계산하는 알고리즘

거리를 빠르게 편집하는 계산 방법

DP 변수는 1셀에 1비트 열을 지정하고 64비트 레지스터를 사용하여 64셀의 점차적인 공식을 병렬로 계산합니다(대단).물론 위에서 보여준 점화 공식에서 1개의 칸 1비트로 표시할 수 없기 때문에 이 알고리즘에서 우리는 필요한 비트 폭을 압축할 때 인접한 칸 값의 차이로 칸 값을 대체한다.편집 거리의 점화 공식에서 이 차이는 {-1, 0, 1} 세 가지(논문에서 증명됨)로 나뉘기 때문에 p와 m 두 변수 {(p, m)}=(0, 1), (0, 0), (1, 0)}를 준비하여 1개 단원 1bit x 레지스터 4개(종횡으로 교차하는 p, m)를 실현하였다.
1단원 1비트이기 때문에 그 SIMD보다 병행도가 높고, 덧셈 명령을 이용한 카드가 의존관계 검사를 해결하는 곳이 좋다.

LLCS도 풀 수 있을 것 같아요.

최장 공통 부분 열 길이(Length of Longgest Common Substing: LLCS)도 비슷한 2차원 DP로 문제를 풀 수 있습니다.이것도 인접한 DP 변수의 차가 {0, 1} 중 하나이기 때문에 편집 거리와 마찬가지로bitDP를 되돌릴 수 있습니다.현재 가장 아름다운 알고리즘은 왜냐하면인 것 같다.구상은 ED의 알고리즘과 같지만 하나의 변수(수평차분)를 반전시켜 연산 횟수를 줄인다.

아무튼 일단 이룰게요.

이 알고리즘의 강점은 모든 데이터를 레지스터에 저장한 상태에서 64개의 칸을 업데이트할 수 있다는 점이다.이 특징을 손상시키지 않기 위해서 나는 자세하게 기술할 것이다.
그러나 임의의 길이의 입력을 받아들이는 것은 매우 번거롭기 때문에 입력은 최대 64자만 입력할 수 있다.uint64_t editdist(char const *a, uint64_t alen, char const *b, uint64_t blen);라면 아마 실용적으로 사용할 수 있을 거예요.예를 들어 문장의 일부분을 잘라서 ED를 계산하는 경우zero-copy를 통해 실현할 수 있다.

코드

풀버전 여기 있어요.

uint64_t editdist(
    char const *a,
    uint64_t alen,
    char const *b,
    uint64_t blen)
{
    v32i8_t a1 = _loadu_v32i8(a), a2 = _loadu_v32i8(a + 32);
    uint64_t ph = 0xffffffffffffffff, mh = 0;
    for(char const *p = b; p < b + blen; p++) {
        v32i8_t b = _set_v32i8(*p);
        uint64_t eq = (_m(_eq_v32i8(b, a2))<<32) | _m(_eq_v32i8(b, a1));
        uint64_t xh = eq | mh, xv = (((eq & ph) + ph) ^ ph) | eq;
        uint64_t pv = mh | ~(xv | ph), mv = ph & xv;
        pv<<=1; mv<<=1; pv |= 0x01ULL;
        ph = mv | ~(xh | pv); mh = pv & xh;
    }
    uint64_t mask = (0x01ULL<<alen) - 1;
    return(blen + popcnt(ph & mask) - popcnt(mh & mask));
}

uint64_t llcs(
    char const *a,
    uint64_t alen,
    char const *b,
    uint64_t blen)
{
    v32i8_t a1 = _loadu_v32i8(a), a2 = _loadu_v32i8(a + 32);
    uint64_t h = 0xffffffffffffffff;
    for(char const *p = b; p < b + blen; p++) {
        v32i8_t b = _set_v32i8(*p);
        uint64_t eq = (_m(_eq_v32i8(b, a2))<<32) | _m(_eq_v32i8(b, a1));
        uint64_t v = h & eq; h = (h + v) | (h - v);
    }
    uint64_t mask = (0x01ULL<<alen) - 1;
    return(alen - popcnt(h & mask));
}

컴파일 결과

clang-3.9 -O3 -msse4.1 on mac.ED 설치의 내부 주기만 표시됩니다.의도대로 스토리지의 회피/재부팅이 손실되었습니다.

LBB0_2:                                 ## =>This Inner Loop Header: Depth=1
    movzbl  (%rdx), %ebx
    movd    %ebx, %xmm5
    pshufb  %xmm4, %xmm5
    movdqa  %xmm5, %xmm6
    pcmpeqb %xmm2, %xmm6
    pmovmskb    %xmm6, %ebx
    movdqa  %xmm5, %xmm6
    pcmpeqb %xmm3, %xmm6
    pmovmskb    %xmm6, %ecx
    shll    $16, %ecx
    orl %ebx, %ecx
    shlq    $32, %rcx
    movdqa  %xmm5, %xmm6
    pcmpeqb %xmm0, %xmm6
    pmovmskb    %xmm6, %edi
    pcmpeqb %xmm1, %xmm5
    pmovmskb    %xmm5, %ebx
    shll    $16, %ebx
    orl %edi, %ebx
    orq %rcx, %rbx
    movq    %rbx, %rcx
    andq    %rax, %rcx
    addq    %rax, %rcx
    xorq    %rax, %rcx
    orq %rbx, %rcx
    orq %r13, %rbx
    movq    %rcx, %rdi
    orq %rax, %rdi
    notq    %rdi
    orq %r13, %rdi
    andq    %rax, %rcx
    addq    %rcx, %rcx
    leaq    1(%rdi,%rdi), %rdi
    movq    %rdi, %rax
    orq %rbx, %rax
    notq    %rax
    orq %rcx, %rax
    andq    %rdi, %rbx
    incq    %rdx
    cmpq    %r12, %rdx
    movq    %rbx, %r13
    jb  LBB0_2

끝말

기준 획득

진열의 불러오기, 페이지 경계를 넘으면 SEGV가 있을 가능성...

UTF-8을 어떻게 먹을 수 있을까...

따라서 이러한 문제가 해결되면 언제든지 업데이트됩니다.
내일(오늘)은 소@_primenumber 씨의 공동 비트 스캔 리버스라고 한다.

참고 문헌

Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming., Journal of the ACM (JACM). 1999

Heikki Hyyrö, Bit-Parallel LCS-length Computation Revisited., Proc. 15th Australasian Workshop on Combinatorial Algorithms (AWOCA 2004). 2004.