在java中執行patricia trie

我正試圖在java中重寫C++ patricia trie。 C++代碼是從here 在java中執行patricia trie

我有點卡住了。

因此，這裏是我的理解：

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

我們創造的關鍵256位的陣列，所以我們可以有32個字符的最大長度的字符串，每個字符表示與8位。我可以用java中的char數組實現這個嗎？

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個字符（不完全N/8，因爲右移將消除任何比8至零下），那麼我們轉向bit_stream [n >> 3]的值由k表示，然後我們得到最後一位。如果我在java中使用數組，我可以將其重寫爲

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); 
}

現在這是它得到混亂，第一部分，直到第二while循環看起來不夠清楚，環路和檢查有多少位是平等的，不爲零，但我不知道是什麼的第二個循環我們把這兩個鍵的地址，並檢查第一個比特，如果他們是平等的，如果他們是我們再次檢查，直到我們發現不等比特？

主要我不確定在這裏如何使用密鑰的地址，但我可能會在bit_get類的位移時感到困惑。

我想做一個比較之間的c + +和我的Java類java和我想保持儘可能相似的實現。

來源

2012-10-28 Arnas

calloc（256，1）爲每個1字節大的256個元素分配內存。字節，而不是位。 –

https://github.com/rkapsi/patricia-trie/blob/master/src/main/java/org/ardverk/collection/PatriciaTrie.java – PiotrNycz

我對這個數據結構並不熟悉，但是您對這段代碼的理解存在一些問題。

首先，calloc分配256個字節，而不是位。在java中可以比較。

二，n & 0x7得到三位n，不是七位。一個更清晰的方式來寫這將是n/8和n%8，而不是n>>3和n & 7，但如果您的編譯器是愚蠢的，按位操作可能會稍快。

您正確的看到(bit_stream[n>>3]>>k) & 1是一樣的。

現在，bit_first_different中的第一個循環遍歷字節，而不是位。檢查0是爲了防止按鍵結束。一旦該循環終止，n引用第一個不同的字節。第二個循環然後尋找哪個位是不同的。

請注意，如果兩個鍵沒有不同，那麼第二個循環可能會在鍵的末尾運行，從而可能導致分段錯誤。現在

，該&走的是k1[n]的地址，因爲bit_get函數需要一個指向字符...這通過在比特流的n個元素。在循環之後，d是k[n]的第一個不同位的偏移量。

最後代碼結合n（哪個字節？）與d（哪個位在那個字節？）給出這個位。爲了清楚起見，我再次提倡8*n+d，但這是一個品味問題。

來源

2012-10-28 18:51:19 mdgeorge

A [patricia tree]（http://en.wikipedia.org/wiki/Patricia_tree）是一個trie變體。 'bit_first_different'函數可能用於查找在插入和查找過程中密鑰從樹上脫落的位置。 –

即使假設這兩個鍵是不同的，我至少會添加一條註釋說明前提條件。 – mdgeorge

我可以用java中的char數組實現這個嗎？

我的Java是有些生疏，但我相信char是Java，這意味着>>不會做你指望它有什麼簽名。這是因爲轉換一個有符號的數字不會改變符號位，所以你真正想要的是>>>運算符，或者只是使用未簽名的byte類型。我有一種感覺，這是各種各樣的錯誤，所以請仔細檢查。

return（bit_stream [n >> 3] >> k）& 0x1;

在C或C++，*(array + k)只是另一種方式來寫array[k]所以你的翻譯看起來是正確的。至於解釋，bit_stream[n>>3]本質上取得所需位所在的字節。 >> k將最低有效位位置的所需位移動。最後，我們通過用& 0x1掩蓋它們來移除我們不感興趣的所有位。這取決於該位是否設置，使我們的值爲0或1。

最終功能的作用是比較2位字符串，並返回2個字符串首先不同的位位置。第一個循環基本上是第二個循環的優化版本，而不是逐位比較，而是檢查整個字節。

換句話說，它首先遍歷每個字節，並找到不同的前兩個字節。然後它將這兩個不同的字節並遍歷它們，直到找到前兩個不同的位。請注意，bit_get函數在這種情況下永遠不會收到大於7的字符，因爲我們知道字節中某處存在差異。然後最終的位位置由兩個循環的結果構建，如下所示：(number_of_equal_bytes * 8) + number_of_equal_bits)。

來源

2012-10-28 18:43:39

在java中執行patricia trie

回答

相關問題