/usr/share/doc/libghc-stringsearch-doc/html/Data-ByteString-Search-KarpRabin.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.ByteString.Search.KarpRabin</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-ByteString-Search-KarpRabin.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-ByteString-Search-KarpRabin.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">stringsearch-0.3.6.4: Fast searching, splitting and replacing of ByteStrings</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>non-portable (BangPatterns)</td></tr><tr><th>Stability</th><td>Provisional</td></tr><tr><th>Maintainer</th><td>Daniel Fischer &lt;daniel.is.fischer@googlemail.com&gt;</td></tr><tr><th>Safe Haskell</th><td>None</td></tr></table><p class="caption">Data.ByteString.Search.KarpRabin</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Overview
</a><ul><li><a href="#g:2">Caution
</a></li></ul></li><li><a href="#g:3">Function
</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Simultaneous search for multiple patterns in a strict <code><a href="/usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.0.2/Data-ByteString.html#t:ByteString">ByteString</a></code>
 using the Karp-Rabin algorithm.
</p><p>A description of the algorithm for a single pattern can be found at
 <a href="http://www-igm.univ-mlv.fr/~lecroq/string/node5.html#SECTION0050">http://www-igm.univ-mlv.fr/~lecroq/string/node5.html#SECTION0050</a>.
</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><a href="#v:indicesOfAny">indicesOfAny</a> :: [<a href="/usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.0.2/Data-ByteString.html#t:ByteString">ByteString</a>] -&gt; <a href="/usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.0.2/Data-ByteString.html#t:ByteString">ByteString</a> -&gt; [(<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, [<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>])]</li></ul></div><div id="interface"><h1 id="g:1">Overview
</h1><div class="doc"><p>The Karp-Rabin algorithm works by calculating a hash of the pattern and
 comparing that hash with the hash of a slice of the target string with
 the same length as the pattern. If the hashes are equal, the slice of the
 target is compared to the pattern byte for byte (since the hash
 function generally isn't injective).
</p><p>For a single pattern, this tends to be more efficient than the na&#239;ve
 algorithm, but it cannot compete with algorithms like
 Knuth-Morris-Pratt or Boyer-Moore.
</p><p>However, the algorithm can be generalised to search for multiple patterns
 simultaneously. If the shortest pattern has length <code>k</code>, hash the prefix of
 length <code>k</code> of all patterns and compare the hash of the target's slices of
 length <code>k</code> to them. If there's a match, check whether the slice is part
 of an occurrence of the corresponding pattern.
</p><p>With a hash-function that
</p><ul><li> allows to compute the hash of one slice in constant time from the hash
     of the previous slice, the new and the dropped character, and
</li><li> produces few spurious matches,
</li></ul><p>searching for occurrences of any of <code>n</code> patterns has a best-case complexity
 of <em>O</em>(<code>targetLength</code> * <code>lookup n</code>). The worst-case complexity is
 <em>O</em>(<code>targetLength</code> * <code>lookup n</code> * <code>sum patternLengths</code>), the average is
 not much worse than the best case.
</p><p>The functions in this module store the hashes of the patterns in an
 <code><a href="/usr/share/doc/ghc-doc/html/libraries/containers-0.5.0.0/Data-IntMap-Strict.html#t:IntMap">IntMap</a></code>, so the lookup is <em>O</em>(<code>log n</code>). Re-hashing is done in constant
 time and spurious matches of the hashes <em>should be</em> sufficiently rare.
 The maximal length of the prefixes to be hashed is 32.
</p></div><h2 id="g:2">Caution
</h2><div class="doc"><p>Unfortunately, the constant factors are high, so these functions are slow.
 Unless the number of patterns to search for is high (larger than 50 at
 least), repeated search for single patterns using Boyer-Moore or DFA and
 manual merging of the indices is faster. <em>Much</em> faster for less than 40
 or so patterns.
</p><p>In summary, this module is more of an interesting curiosity than anything
 else.
</p></div><h1 id="g:3">Function
</h1><div class="top"><p class="src"><a name="v:indicesOfAny" class="def">indicesOfAny</a><a href="src/Data-ByteString-Search-KarpRabin.html#indicesOfAny" class="link">Source</a></p><div class="subs arguments"><p class="caption">Arguments</p><table><tr><td class="src">:: [<a href="/usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.0.2/Data-ByteString.html#t:ByteString">ByteString</a>]</td><td class="doc"><p>List of non-empty patterns
</p></td></tr><tr><td class="src">-&gt; <a href="/usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.0.2/Data-ByteString.html#t:ByteString">ByteString</a></td><td class="doc"><p>String to search
</p></td></tr><tr><td class="src">-&gt; [(<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, [<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>])]</td><td class="doc"><p>List of matches
</p></td></tr></table></div><div class="doc"><p><code><code><a href="Data-ByteString-Search-KarpRabin.html#v:indicesOfAny">indicesOfAny</a></code></code> finds all occurrences of any of several non-empty patterns
   in a strict target string. If no non-empty patterns are given,
   the result is an empty list. Otherwise the result list contains
   the pairs of all indices where any of the (non-empty) patterns start
   and the list of all patterns starting at that index, the patterns being
   represented by their (zero-based) position in the pattern list.
   Empty patterns are filtered out before processing begins.
</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
libghc-stringsearch-doc 0.3.6.4-3 / usr / share / doc / libghc-stringsearch-doc / html / Data-ByteString-Search-KarpRabin.html
