From: ············@googlemail.com
Subject: Suffix tree/array
Date: Sat, 06 Jan 2007 23:16:52 +0000
Message-ID: <1168125411.926597.298300@38g2000cwa.googlegroups.com>

Hi,

Does anyone know of a suffix tree or suffix array implementation in CL?


Thanks,
Tayssir

• Re: Suffix tree/array Pascal Bourguignon
• Re: Suffix tree/array Pascal Bourguignon

From: Pascal Bourguignon
Subject: Re: Suffix tree/array
Date: Sun, 07 Jan 2007 01:56:10 +0000
Message-ID: <871wm7a9c5.fsf@thalassa.informatimago.com>

············@googlemail.com writes:
> Does anyone know of a suffix tree or suffix array implementation in CL?

I didn't know any, but a quick browsing of wikipedia, and some little
suggar burning by a few nerons gives:


(defun suffix-array (string)
  (map 'vector (function car)
       (sort
        (loop 
           :for i :from 0 :below (length string)
           :collect (cons i (make-array (- (length string) i)
                                        :element-type (array-element-type string)
                                        :displaced-to string
                                        :displaced-index-offset i)))
        (function string<=) :key (function cdr))))


C/USER2[919]> (suffix-array "abracadabra")
#(10 7 0 3 5 8 1 4 6 9 2)

       

Of course, you need a few free neurons to work it out...

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The rule for today:
Touch my tail, I shred your hand.
New rule tomorrow.

From: Pascal Bourguignon
Subject: Re: Suffix tree/array
Date: Sun, 07 Jan 2007 02:52:00 +0000
Message-ID: <87ps9r8s6n.fsf@thalassa.informatimago.com>

············@googlemail.com writes:
> Does anyone know of a suffix tree or suffix array implementation in CL?

Also, three years ago, rif published his implementation of McCreight's
O(n) suffix-tree algorithm in cll:
http://groups.google.com/group/comp.lang.lisp/msg/d0828f590a78e958
http://paste.lisp.org/display/34390

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.