basis/suffix-arrays/suffix-arrays-docs.factor

   1 ! Copyright (C) 2008 Marc Fauconneau.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays help.markup help.syntax io.streams.string
   4 sequences strings math suffix-arrays.private ;
   5 IN: suffix-arrays
   6
   7 HELP: >suffix-array
   8 { $values
   9      { "seq" sequence }
  10      { "array" array } }
  11 { $description "Creates a suffix array from the input sequence.  Suffix arrays are arrays of slices." } ;
  12
  13 HELP: SA{
  14 { $description "Creates a new literal suffix array at parse-time." } ;
  15
  16 HELP: suffixes
  17 { $values
  18      { "string" string }
  19      { "suffixes-seq" "a sequence of slices" } }
  20 { $description "Returns a sequence of tail slices of the input string." } ;
  21
  22 HELP: from-to
  23 { $values
  24      { "index" integer } { "begin" sequence } { "suffix-array" "a suffix-array" }
  25      { "from/f" "an integer or f" } { "to/f" "an integer or f" } }
  26 { $description "Finds the bounds of the suffix array that match the input sequence. A return value of " { $link f } " means that the endpoint is included." }
  27 { $notes "Slices are [m,n) and we want (m,n) so we increment." } ;
  28
  29 HELP: query
  30 { $values
  31      { "begin" sequence } { "suffix-array" "a suffix-array" }
  32      { "matches" array } }
  33 { $description "Returns a sequence of sequences from the suffix-array that contain the input sequence. An empty array is returned when there are no matches." } ;
  34
  35 ARTICLE: "suffix-arrays" "Suffix arrays"
  36 "The " { $vocab-link "suffix-arrays" } " vocabulary implements the suffix array data structure for efficient lookup of subsequences. This suffix array implementation is a sorted array of suffixes. Querying it for matches uses binary search for efficiency." $nl
  37
  38 "Creating new suffix arrays:"
  39 { $subsections >suffix-array }
  40 "Literal suffix arrays:"
  41 { $subsections POSTPONE: SA{ }
  42 "Querying suffix arrays:"
  43 { $subsections query } ;
  44
  45 ABOUT: "suffix-arrays"