자바에서 patricia trie를 구현하십시오.

Question

자바에서 C++ patricia trie를 다시 작성하려고합니다. 는 C++ 코드는 내가 조금 붙어있어 here

full source code

에서입니다. 우리는 키 256 비트의 배열을 만들

#define ZEROTAB_SIZE 256 
head->key = (char*)calloc(ZEROTAB_SIZE, 1); 

, 그래서 우리는 최대 32 자 길이의 문자열을 가질 수 있고 모든 문자는 8 비트로 표현된다

그래서 여기 내 이해입니다. 자바에서 문자 배열을 사용하여이를 구현할 수 있습니까?

template <class T> 
int PatriciaTrie<T>::bit_get(PatriciaTrieKey bit_stream, int n) { 
    if (n < 0) return 2; // "pseudo-bit" with a value of 2. 
    int k = (n & 0x7); 
    return ((*(bit_stream + (n >> 3))) >> k) & 0x1; 
} 

k는 N의 마지막 7 개 비트를 얻을, 우리는 우리가 이동 (정확히 N/8 8 제로보다 낮은 것을 제거하는 것이다 오른쪽으로 이동하기 때문에) 문자열의 N/8 문자로 이동 bit_stream [n >> 3]의 값을 k로 곱한 다음 마지막 비트를 얻습니다. 내가 자바에서 배열을 사용한다면 이것을 다시 쓸 수 있겠습니까?

return (bit_stream[n>>3] >> k) & 0x1; 

? 그것은 혼란을 얻을 경우 루프는 충분히 명확 보이는 루프와 동일한 비 제로 얼마나 많은 비트를 확인하면서

template <class T> 
int PatriciaTrie<T>::bit_first_different(PatriciaTrieKey k1, PatriciaTrieKey k2) { 
    if (!k1 || !k2) 
     return 0; // First bit is different! 
    int n = 0; 
    int d = 0; 
    while ((k1[n] == k2[n]) && 
      (k1[n] != 0) && 
      (k2[n] != 0)) 
     n++; 
    while (bit_get(&k1[n], d) == bit_get(&k2[n], d)) 
     d++; 
    return ((n << 3) + d); 
} 

지금이 두 번째까지 첫 번째 부분이지만, 내가 어떻게 두 번째 루프 확실하지 않다 우리가 두 키의 주소를 가져 와서 만약 그들이 동등한 지 첫 번째 비트를 검사하고 만약 우리가 불균등 한 비트를 찾을 때까지 다시 검사한다면?

주로 키의 주소가 여기에 어떻게 사용되는지 잘 모르겠지만 bit_get 클래스에서도 비트 시프트에 대해 혼란 스러울 수 있습니다.

나는 거기에 C++에서 trie를 비교하고 자바에 대한 자바 클래스를 만들고 싶습니다. 구현을 가능한 한 비슷하게 유지하고 싶습니다.

Answer 1

이 데이터 구조에는 익숙하지 않지만이 코드를 이해하는데 약간의 문제가 있습니다.

먼저 calloc은 비트가 아닌 256 바이트를 할당합니다. new byte[256] Java에서 비교할 수 있습니다.

둘째, n & 0x7은 7 비트가 아니라 n의 3 비트를 가져옵니다. 이것을 쓰는 더 명확한 방법은 n>>3과 n & 7 대신에 n/8과 n%8이 될 것이지만, 컴파일러가 어리 석다면 bitwise 연산이 약간 더 빠를 수도 있습니다.

(bit_stream[n>>3]>>k) & 1가 동일해야합니다.

이제 bit_first_different의 첫 번째 루프는 비트가 아닌 바이트를 루프합니다. 0을 확인하면 키 끝에서 벗어나는 것을 방지 할 수 있습니다. 루프가 종료되면 n은 첫 번째 다른 바이트를 나타냅니다. 두 번째 루프는 어떤 비트가 다른지를 찾습니다.

두 키가 다르지 않은 경우 두 번째 루프가 키 끝에서 벗어나서 세그먼트 오류가 발생할 수 있습니다. bit_get 함수가 캐릭터에 대한 포인터를 기대하고 있기 때문에

이제 &가 k1[n]의 주소를 가지고있다 .. 이는 비트 스트림의 n th 요소에 전달한다. 루프 다음에 d은 k[n]의 첫 번째 다른 비트의 오프셋입니다.

마지막으로 코드는 d (이 바이트의 어떤 비트?) 비트를 제공하기 위해 n (바이트는?)을 결합합니다. 다시 한 번 명확하게 말하면 8*n+d을 옹호 하겠지만 맛은 문제입니다.

Answer 2

Java에서 char 배열로 구현할 수 있습니까?

내 자바 약간 녹슨하지만 난 char이 >> 당신이 그것을 기대하지 않을 것을 의미 자바에 서명 생각합니다. 부호있는 숫자를 이동해도 부호 비트가 이동하지 않으므로 실제로 원하는 것은 >>> 연산자이거나 부호가없는 byte 유형을 사용하기 때문입니다. 나는 이것이 모든 종류의 잘못이라는 느낌을 가지고 있으므로 두 번 확인하십시오.

return (bit_stream [n >> 3] >> k) & 0x1; C 또는 C++에서

는 *(array + k)는 array[k] 그래서 번역이 정확 보인다 작성하는 또 다른 방법입니다. 해석에 관해서는, bit_stream[n>>3]은 본질적으로 원하는 비트가 위치한 바이트를 가져옵니다. >> k 원하는 비트를 최하위 비트 위치로 이동합니다. 마지막으로 우리는 관심없는 모든 비트를 & 0x1으로 마스크 처리하여 제거합니다. 비트가 설정되었는지 여부에 따라 0 또는 1 값이 남습니다.

마지막 함수는 2 비트 문자열을 비교하고 2 문자열이 먼저 다른 비트 위치를 반환합니다.첫 번째 루프는 본질적으로 비트 비교에 의한 것이 아니라 전체 바이트를 검사하는 두 번째 루프의 최적화 된 버전입니다.

즉, 처음에는 모든 바이트를 반복하고 서로 다른 첫 번째 2 개를 찾습니다. 그런 다음 두 개의 다른 바이트를 취해 서로 다른 첫 번째 2 비트를 찾을 때까지 반복합니다. bit_get 함수는 바이트의 어딘 부분에 차이가 있다는 것을 알고 있기 때문에이 시나리오에서는 n보다 큰 7을받지 않습니다. 최종 비트 위치는 다음과 같이 두 루프의 결과로 구성됩니다. (number_of_equal_bytes * 8) + number_of_equal_bits).