Changeset 1549 for docs/Working/parlensort.tex
 Timestamp:
 Oct 22, 2011, 2:04:00 PM (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

docs/Working/parlensort.tex
r1302 r1549 9 9 \maketitle 10 10 11 \section{ The Idea}11 \section{LengthGroup Bitstreams} 12 12 13 13 Given streams $S$ and $E$ that mark the starts and ends of Names. … … 18 18 ends of Names of length 1, $E_1$, and the stream 19 19 of ends of Names of greater than length 1, $E_{>1}$, as follows. 20 Here $n(S)$ is the bitstream ``next'' operation, shifting the 21 stream forward one position. 20 22 21 23 \begin{eqnarray*} … … 57 59 \end{eqnarray*} 58 60 61 62 \section{Parallel Hashing} 63 64 Given length groups identified as in the previous section, 65 it is possible to perform parallel hash value calculation for 66 names in each group as follows. 67 68 The first step is to create hash streams. 69 Let $B_0, B_1, \ldots, B_7$ be the {\em basis} bitstreams 70 determined by character stream transposition. That is, 71 the $k$th basis bitstream $B_k$ consists of the $k$th bit 72 of each character in the source data stream. 73 Then we may compute hash streams by some bitwise logical combination 74 of basis bit streams. 75 For example, the following two hash streams may be useful. 76 77 \begin{eqnarray*} 78 h_a & = & B_2 \oplus B_4 \oplus B_6 \\ 79 h_b & = & B_3 \oplus B_5 \oplus B_7 \\ 80 \end{eqnarray*} 81 82 83 84 85 59 86 \section{Followup} 60 87 … … 84 111 lengths? This avoids allocation of lengthbased position arrays, the memory 85 112 operations of insertion of positions into those arrays, boundschecking on those 86 arrays and maintaining an auxiliary array of lengths of theeach array.113 arrays and maintaining an auxiliary array of lengths of each array. 87 114 88 115 A further benefit may be from the programming side: the length sorting can
Note: See TracChangeset
for help on using the changeset viewer.