Index: /docs/Working/parlensort.tex
===================================================================
--- /docs/Working/parlensort.tex (revision 1548)
+++ /docs/Working/parlensort.tex (revision 1549)
@@ -9,5 +9,5 @@
\maketitle
-\section{The Idea}
+\section{Length-Group Bitstreams}
Given streams $S$ and $E$ that mark the starts and ends of Names.
@@ -18,4 +18,6 @@
ends of Names of length 1, $E_1$, and the stream
of ends of Names of greater than length 1, $E_{>1}$, as follows.
+Here $n(S)$ is the bitstream ``next'' operation, shifting the
+stream forward one position.
\begin{eqnarray*}
@@ -57,4 +59,29 @@
\end{eqnarray*}
+
+\section{Parallel Hashing}
+
+Given length groups identified as in the previous section,
+it is possible to perform parallel hash value calculation for
+names in each group as follows.
+
+The first step is to create hash streams.
+Let $B_0, B_1, \ldots, B_7$ be the {\em basis} bitstreams
+determined by character stream transposition. That is,
+the $k$th basis bitstream $B_k$ consists of the $k$th bit
+of each character in the source data stream.
+Then we may compute hash streams by some bitwise logical combination
+of basis bit streams.
+For example, the following two hash streams may be useful.
+
+\begin{eqnarray*}
+h_a & = & B_2 \oplus B_4 \oplus B_6 \\
+h_b & = & B_3 \oplus B_5 \oplus B_7 \\
+\end{eqnarray*}
+
+
+
+
+
\section{Follow-up}
@@ -84,5 +111,5 @@
lengths? This avoids allocation of length-based position arrays, the memory
operations of insertion of positions into those arrays, bounds-checking on those
-arrays and maintaining an auxiliary array of lengths of the each array.
+arrays and maintaining an auxiliary array of lengths of each array.
A further benefit may be from the programming side: the length sorting can