Changeset 25759 in project for release


Ignore:
Timestamp:
01/05/12 04:48:59 (10 years ago)
Author:
Ivan Raikov
Message:

renamed trie to suffix-tree

Location:
release/4/suffix-tree
Files:
3 deleted
1 edited
3 copied
1 moved

Legend:

Unmodified
Added
Removed
  • release/4/suffix-tree/trunk/suffix-tree.scm

    r25758 r25759  
    11;;
    22;;
    3 ;; An implementation of tries, a data type for representing sets of
    4 ;; lists efficiently, provided there is an ordering relation on the
    5 ;; elements of lists.
     3;; An implementation of suffix tree, a data structure for representing
     4;; sets of lists efficiently, provided there is an ordering relation
     5;; on the elements of lists.
    66;;
    77;; Copyright 2011 Ivan Raikov and the Okinawa Institute of Science and
     
    99;;
    1010;;
    11 ;; A trie is a tree with arcs labeled by elements from the element
    12 ;; type of the lists and with branches ordered on the basis of their
    13 ;; arc labels; moreover, only one branch per distinct label value is
    14 ;; allowed per node.  Ends of lists are designated by an "EOL" marker;
    15 ;; a value may be associated with the EOL symbol.
    16 ;;
    17 ;;
    18 
    19 (module trie
     11;; A suffix tree is a tree with arcs labeled by elements from the
     12;; element type of the lists and with branches ordered on the basis of
     13;; their arc labels; moreover, only one branch per distinct label
     14;; value is allowed per node.  Ends of lists are designated by an
     15;; "EOL" marker; a value may be associated with the EOL symbol.
     16;;
     17;;
     18
     19(module suffix-tree
    2020       
    21         ( make-trie trie-equal? )
     21        ( make-suffix-tree suffix-tree-equal? )
    2222
    2323        (import scheme chicken)
     
    3535       (branches (list-of branch?))))
    3636
    37 (define trie?  (list-of branch?))
    38 
    39 
    40 (define (trie-equal? t1 t2)
     37(define suffix-tree?  (list-of branch?))
     38
     39
     40(define (suffix-tree-equal? t1 t2)
    4141  (let ((t1 (t1 'repr)) (t2 (t2 'repr)))
    4242    (let ((aeq (car t1)) (tr1 (caddr t1))
     
    5454
    5555
    56 (define (make-trie leq key->list . rest)
     56(define (make-suffix-tree leq key->list . rest)
    5757 
    5858  (let-optionals rest ((tr '()))
    5959
    60   (assert (trie? tr))
     60  (assert (suffix-tree? tr))
    6161
    6262  (define empty '())
     
    120120       ))
    121121
    122   ;; Removes lst from tr.  Any branches having a null subtrie
     122  ;; Removes lst from tr.  Any branches having a null subsuffix-tree
    123123  ;; associated with them are deleted.
    124124
     
    143143
    144144  ;; Merges tr1 and tr2.  If there is a list that appears in both
    145   ;; tries, an exception is raised.
     145  ;; suffix-trees, an exception is raised.
    146146
    147147  (define (merge tr1 tr2)
     
    152152
    153153           (((($ branch 'EOL b1) . _) (($ branch 'EOL _) . _))
    154             (error "already in trie" tr1 tr2))
     154            (error "already in suffix-tree" tr1 tr2))
    155155
    156156           (((($ branch 'EOL b1) . tr11) tr2)
     
    170170
    171171
    172   ;; Splits tr into three tries on the basis of a.  The first trie
     172  ;; Splits tr into three suffix-trees on the basis of a.  The first suffix-tree
    173173  ;; consists of branches headed by actions less than a (plus any EOL
    174174  ;; symbol), the second contains the branch (if any) associated with a,
     
    199199         
    200200      ((insert)
    201        (lambda (k bval) (make-trie leq key->list (insert (key->list k) bval tr))))
     201       (lambda (k bval) (make-suffix-tree leq key->list (insert (key->list k) bval tr))))
    202202
    203203      ((lookup)
     
    207207       (lambda (k)
    208208         (let ((v (lookup (key->list k) tr identity)))
    209            (if (trie? v)
    210                (make-trie leq key->list v)
     209           (if (suffix-tree? v)
     210               (make-suffix-tree leq key->list v)
    211211               v))))
    212212
    213213      ((remove)
    214        (lambda (k) (make-trie leq key->list (remove (key->list k) tr))))
     214       (lambda (k) (make-suffix-tree leq key->list (remove (key->list k) tr))))
    215215
    216216      ((merge) 
    217        (lambda (x) (make-trie leq key->list (merge tr x))))
     217       (lambda (x) (make-suffix-tree leq key->list (merge tr x))))
    218218
    219219      ((partition)
  • release/4/suffix-tree/trunk/tests/run.scm

    r25594 r25759  
    1 (use trie)
     1(use suffix-tree)
    22
    3 (define t (make-trie char=? string->list ))
     3(define t (make-suffix-tree char=? string->list ))
    44
    55(define t1 ((t 'insert) "key1" 'test1))
     
    1313(assert (equal? 'test1 ((t3 'lookup)  "1")))
    1414(assert (equal? 'test2 ((t3 'lookup)  "2")))
    15 
    16 
    17 
Note: See TracChangeset for help on using the changeset viewer.