Paste: suffix-array
Author: | prunedtree |
Mode: | factor |
Date: | Wed, 1 Oct 2008 16:50:58 |
Plain Text |
USING: kernel arrays math accessors sequences math.vectors math.order sorting
binary-search sets assocs fry ;
IN: suffix-array
: suffixes dup length [ tail-slice ] with map ;
: new-sa [ suffixes ] map concat [ <=> ] sort ;
: prefix<=> [ swap <=> ] [ head? ] 2bi [ drop +eq+ ] [ ] if ;
: find-index '[ _ prefix<=> ] search drop ;
: from-to
'[ _ head? not ] [ find-last-from drop 1+ ] [ find-from drop ] 3bi ;
: query-sa
[ swap [ find-index ] 2keep from-to ] keep <slice> [ seq>> ] map prune ;
: new-word-sa [ name>> ] map new-sa ;
: name-word-map
dup [ name>> V{ } clone ] H{ } map>assoc [ '[ dup name>> _ at push ] each ] keep ;
: name>words swap at ;
: query-word-sa query-sa [ name>words ] with map concat ;
New Annotation