• R/O
  • SSH
  • HTTPS

tsukurimashou: Commit


Commit MetaInfo

Revision482 (tree)
Time2013-11-09 00:33:07
Authormskala

Log Message

minor documentation tweaks

Change Summary

Incremental Difference

--- trunk/idsgrep/idsgrep.tex (revision 481)
+++ trunk/idsgrep/idsgrep.tex (revision 482)
@@ -1472,7 +1472,7 @@
14721472 or Unicode-style traditional ones, belong to the class of
14731473 \emph{context-free} languages. They describe tree-like structures nested to
14741474 arbitrary depth, similar in nature to programming-language expressions
1475-containing balanced parentheses although balanced parantheses as such are
1475+containing balanced parentheses although balanced parentheses as such are
14761476 not actually part of EIDS syntax. The natural way to parse these involves
14771477 an abstract machine with a stack-like memory that can assume an infinite
14781478 number of different states. Regular expressions can only be used to
@@ -2251,14 +2251,17 @@
22512251 integer called the \emph{threshold}. We call these pairs \emph{lambda
22522252 filters}. Define $\mathit{check}((m,\lambda),v)$ to compute the bitwise AND
22532253 of the mask $m$ and vector $v$, count how many bits are set in the result,
2254-and then return $\mathsf{T}$ if and only if the count is strictly more than
2255-the threshold $\lambda$. The filter for \texttt{<foo>!?} will consist of a
2256-mask that selects the three bits for \texttt{foo}, and a threshold of $2$.
2257-It matches if and only if those three bits are all set, which is definitely
2258-true for haystacks that match the needle and reasonably unlikely to be true
2259-for haystacks that do not match the needle. So far this is just the usual
2260-lookup algorithm for a Bloom filter. But by choosing different masks and
2261-thresholds, we can also do other kinds of filtering.
2254+and then return $\mathsf{T}$ if and only if the count is strictly
2255+more\footnote{This definition may seem to be off by one from
2256+the most intuitive way to do it, but $\lambda$ is defined this way for
2257+consistency with related work in the combinatorial design theory
2258+literature.} than the threshold $\lambda$. The filter for \texttt{<foo>!?}
2259+will consist of a mask that selects the three bits for \texttt{foo}, and a
2260+threshold of $2$. It matches if and only if those three bits are all set,
2261+which is definitely true for haystacks that match the needle and reasonably
2262+unlikely to be true for haystacks that do not match the needle. So far this
2263+is just the usual lookup algorithm for a Bloom filter. But by choosing
2264+different masks and thresholds, we can also do other kinds of filtering.
22622265
22632266 Suppose we have two filters $(m_1,\lambda_1)$ and $(m_2,\lambda_2)$. Let
22642267 $m_3$ be the bitwise OR of $m_1$ and $m_2$, and let $\lambda_3$ be the
--- trunk/tug2013/preprint.tex (revision 481)
+++ trunk/tug2013/preprint.tex (revision 482)
@@ -631,7 +631,7 @@
631631 I have never fully understood \MF's traditional proof system based on
632632 greyscale fonts and ``literate'' programming, and in any case its reliance
633633 on the standard coordinate array \verb|z[]| would not mix well with
634-Tsukurimashou's object stack concept. Tsukruimashou generates proofs in a
634+Tsukurimashou's object stack concept. Tsukurimashou generates proofs in a
635635 completely different way. When unwinding the stack the rendering code
636636 writes a ``proof file,'' essentially a machine-readable log of all the
637637 things it is rendering. The build system collects the proof files and runs
Show on old repository browser